1
|
- A COMPONENT BASED APPROACH TO LIST BASED DATA STRUCTURES
|
2
|
- Conceptual (What)
- Implementation (How)
|
3
|
- String of Entries
- Push
- Pop
- Is_Empty
- Length_of
|
4
|
- Initially S = L
- Push( d, S)
- Push( b, S)
- Push( c, S)
- Pop(result, S)
- Push( a, S)
- Length_of(S)
- L
- D
- bd
- cbd
- bd
- abd
- 3
|
5
|
- Array: For small stacks
- Dynamic structure: For
unpredictable stacks with possibly large numbers of entries
|
6
|
- Conceptually a pair of strings
- Advance
- Reset
- Length_of_Remainder
- Insert
- Remove
- Advance_to_End
- Swap_Remainders
- Clear_List
|
7
|
- Initially L = L, L
- Insert( t, L)
- Insert(q, L)
- Insert(b, L)
- Advance(L)
- Advance(L)
- Remove(res, L)
- Insert(a, L)
- L, L
- L, t
- L, qt
- L, bqt
- b, qt
- bq, t
- bq, L
- bq, a
|
8
|
- public:
- List();
- // Create empty List
- void Advance();
- /*Requires |Rem|>0
- Ensures @Rem = x + Rem
- Prec = @Prec + x*/
- T Peek();
- /*Requires List is not empty
- Ensures Peek = Rem.c*/
- int Length_of_Rem();
- /*Requires True
- Ensures Length_of_Rem =
|Rem| */
- void Reset();
- /*Requires True
- Ensures Prec is empty, Rem =
@Prec + @Rem*/
-
|
9
|
- private:
- struct node
- {
- T c;
- node * next;
- };
- node * prec;
- node * prerem;
- node * rem;
|
10
|
- template <class T> List<T>::List()
- //Constructor for empty list
- {
- prec = new(node);
- prec->next = NULL;
- prerem = prec;
- rem = NULL;
- }
- template <class T> void List<T>::Advance()
- //Advance to next Node in list...
- //i.e. move first element of rem to end of prec
- {
- if (rem != NULL) //if rem is not
empty
- {
- prerem = prerem->next; //advance rem pointers
- rem = rem->next;
- }
- }
|
11
|
- Define a stack to be a list_position.
- A client who is looking for reusable components would see the
specifications for a list position and choose it to act as the basis for
creating the type stack.
- To Push an entry, say E, call S.Reset, followed by S.Insert(E), where S
has been declared to be a stack,.
- A Pop is achieved by first doing a Reset and then a Remove.
- To check whether the stack is empty, one can do a Reset and then call
Length_of_Rem.
- What is equally important is that now a client of the stack will not
need to know anything about lists or pointers, because the client will
simply declare a stack and make appropriate calls to Push and Pop,
leaving the implementation details to the writer of the stack component.
- This approach results in complete adherence to the principles of
information hiding and separation of concerns.
|
12
|
- To do an enqueue, call Reset followed by Insert.
- To dequeue, call Advamce_to_End
followed by Insert.
- All of the pointer work was done in the list_position, leaving the queue
writer to reason at the appropriate level of abstraction, rather than
needing to worry about setting up nodes or links.
- A client of the queue component will simply call enqueues and dequeues,
doing all thinking and reasoning at that level without any need to worry
about low level details.
|
13
|
- Consider what is sometimes called an ordered list, and treated as a
different component from a list.
- We see that such a distinction is not necessary at all, since one can
produce an ordered list without ever using a pointer or reference. We can simply use the list_position as
defined, and as new items are inserted, we advance along the list until
we find the position we want to satisfy the ordering requirement and
then call Insert.
|
14
|
- suppose we have the following characters we want to put into a sorted
list: t, a, c, x, e, w.
- Call Insert on t, creating a list of one entry that conceptually looks
like (L, t).
- Next, to insert the a, we use a loop to Advance until we find an entry
the is alphabetically past the a.
In this case, that happens right away. As soon as we see the t, we stop the
advancing loop and do an Insert, resulting in (L, at).
- Next we Reset and then Advance until we find an element past c. This happens at the position, (a,
t). Calling Insert results in (a,
ct). Now Reset and continue with
the x. This causes us to advance
until we reach the end of the list where we do an insert, getting (act,
x). We continue in this way until
all of the elements have been entered.
|
15
|
- cout << "Enter a string of characters terminated with
'0'." <<
- // endl;
- List<char> L; //Declare a list of characters named L
- char c;
- cin >> c;
- L.Insert(c); //Puts first value in L
- cin >> c;
- while (c != '0') //Waits for 0
input to stop
- {
- if (c < L.Peek()) L.Reset(); //if c is too small, reset
- //and start from the beginning
- while (L.Length_of_Rem() && (c > L.Peek()))
- L.Advance(); //advance to
the correct spot
- L.Insert(c); //now that we are
at the correct postition,
- //insert the character
- cin >> c; //and take the next character
- }
- L.Reset(); //Reset the list so we can output from the beginning
- cout << "The sorted data is as follows:" << endl;
- while (L.Length_of_Rem()) //while Rem is not empty
- {
- cout << L.Peek() << ' '; //output each element of the list
- L.Advance();
- }
- cout << endl;
- ////////////////////////////
|
16
|
- //Insert sort for integers//
- ////////////////////////////
- cout << "Enter integers, terminated by 0."
<<endl;
- List<int> B; //declare a list of integers named B
- int d;
- cin >> d;
- B.Insert(d); //Puts first value in B
- cin >> d;
- while (d != 0) //Waits for 0
input to stop
- {
- if (d < B.Peek()) B.Reset();
- while (B.Length_of_Rem() && (d > B.Peek()))
- B.Advance();
- B.Insert(d);
- cin >> d;
- }
- B.Reset();
- cout << "The sorted data is as follows:" << endl;
- while (B.Length_of_Rem())
- {
- cout << B.Peek() << ' ';
- B.Advance();
- }
- cout << endl;
- } //end
|
17
|
- What about reinforcing pointer or reference ideas?
- Give lots of pointer assignments
- Point out to students that the purpose is to reinforce these ideas, but
in real practice, they would not program this way
|
18
|
- Reasoning at the right level of abstraction
- Information Hiding
- Cohesion
- Reuse of certified software
- Great feedback from employers
|