Transcript 1 - Vanderbilt University

1
20
Data Structures
 2008 Pearson Education, Inc. All rights reserved.
2
Much that I bound, I could not free; Much that I freed
returned to me.
— Lee Wilson Dodd
‘Will you walk a little faster?’ said a whiting to a snail,
‘There’s a porpoise close behind us, and he’s treading on
my tail.’
— Lewis Carroll
There is always room at the top.
— Daniel Webster
Push on — keep moving.
— Thomas Morton
I’ll turn over a new leaf.
— Miguel de Cervantes
 2008 Pearson Education, Inc. All rights reserved.
3
OBJECTIVES
In this chapter you will learn:
 To form linked data structures using pointers, selfreferential classes and recursion.
 To create and manipulate dynamic data structures
such as linked lists, queues, stacks and binary trees.
 To use binary search trees for high-speed searching
and sorting.
 To understand various important applications of
linked data structures.
 To understand how to create reusable data structures
with class templates, inheritance and composition.
 2008 Pearson Education, Inc. All rights reserved.
4
20.1
20.2
20.3
20.4
20.5
20.6
20.7
20.8
Introduction
Self-Referential Classes
Dynamic Memory Allocation and Data Structures
Linked Lists
Stacks
Queues
Trees
Wrap-Up
 2008 Pearson Education, Inc. All rights reserved.
5
20.1 Introduction
• Dynamic data structures
– Grow and shrink during execution
– Linked lists
• Collections of data items “lined up in a row”
• Insertions and removals are made anywhere
– Stacks
• Insertions and removals are made only at top
• Important in compilers and operating systems
– Queues
• Insertions are made at back, removals are made at front
• Represent waiting lines
 2008 Pearson Education, Inc. All rights reserved.
6
20.1 Introduction (Cont.)
• Dynamic data structures (Cont.)
– Binary trees
• Facilitate
– High-speed searching and sorting
– Elimination of duplicates
• Used in
– Representations of file system directories
– Compilation of expressions into machine language
 2008 Pearson Education, Inc. All rights reserved.
7
20.2 Self-Referential Classes
• Self-referential class
– Contains a pointer member that points to an object of the
same class type
– Example
• Class Node
{
…
Node *nextPtr;
};
– Pointer data member nextPtr is a link
• Can tie a Node to another Node
 2008 Pearson Education, Inc. All rights reserved.
8
Fig. 20.1 | Two self-referential class objects linked together.
 2008 Pearson Education, Inc. All rights reserved.
9
Common Programming Error 20.1
Not setting the link in the last node of a linked
data structure to null (0) is a (possibly fatal) logic
error.
 2008 Pearson Education, Inc. All rights reserved.
20.3 Dynamic Memory Allocation and
Data Structures
10
• Dynamic memory allocation
– Enables a program to obtain more memory at execution
time
• That memory can be released when it is no longer needed
– Limited by amount of physical or virtual memory
• Memory must be shared among many programs
 2008 Pearson Education, Inc. All rights reserved.
20.3 Dynamic Memory Allocation and
Data Structures (Cont.)
11
•new operator
– Dynamically allocates memory for an object
– Takes as argument the type of the object being allocated
– Returns pointer to the newly-allocated object
– Example
• Node *newPtr = new Node( 10 );
– Allocates sizeof( Node ) bytes for new Node object
– Calls Node constructor with argument 10
– Assigns address of new Node object to newPtr
 2008 Pearson Education, Inc. All rights reserved.
20.3 Dynamic Memory Allocation and
Data Structures (Cont.)
12
•delete operator
– Calls the destructor and deallocates memory for an object
– Example
• delete newPtr;
– Calls Node destructor for object pointed to by newPtr
– Deallocates memory of object pointed to by newPtr
– Does not delete pointer variable newPtr
– If called on a null pointer
• Has no effect
 2008 Pearson Education, Inc. All rights reserved.
13
20.4 Linked Lists
• Linked list
– Linear collection of self-referential class objects
• Called nodes
• Connected by pointer links
– Accessed via a pointer to the first node
• Subsequent nodes are accessed via previous node’s link
– By convention, link in last node is set to null pointer 0
– Additional nodes are dynamically allocated as necessary
 2008 Pearson Education, Inc. All rights reserved.
14
20.4 Linked Lists (Cont.)
• Linked list (Cont.)
– Advantages over arrays
• Linked lists are dynamic
– Length can increase or decrease as necessary
• Efficient insertion of new elements into a sorted list
– Existing list elements do not need to be moved
 2008 Pearson Education, Inc. All rights reserved.
15
Performance Tip 20.1
An array can be declared to contain more
elements than the number of items expected,
but this can waste memory. Linked lists can
provide better memory utilization in these
situations. Linked lists allow the program to
adapt at runtime. Note that class template
vector (introduced in Section 7.11)
implements a dynamically resizable arraybased data structure.
 2008 Pearson Education, Inc. All rights reserved.
16
Performance Tip 20.2
Insertion and deletion in a sorted array can be
time consuming—all the elements following
the inserted or deleted element must be shifted
appropriately. A linked list allows efficient
insertion operations anywhere in the list.
 2008 Pearson Education, Inc. All rights reserved.
17
Performance Tip 20.3
The elements of an array are stored contiguously in memory.
This allows immediate access to any array element, because
the address of any element can be calculated directly based
on its position relative to the beginning of the array. Linked
lists do not afford such immediate “direct access” to their
elements. So accessing individual elements in a linked list can
be considerably more expensive than accessing individual
elements in an array. The selection of a data structure is
typically based on the performance of specific operations
used by a program and the order in which the data items are
maintained in the data structure. For example, it is typically
more efficient to insert an item in a sorted linked list than a
sorted array.
 2008 Pearson Education, Inc. All rights reserved.
18
Performance Tip 20.4
Using dynamic memory allocation (instead of
fixed-size arrays) for data structures that grow
and shrink at execution time can save memory.
Keep in mind, however, that pointers occupy
space and that dynamic memory allocation incurs
the overhead of function calls.
 2008 Pearson Education, Inc. All rights reserved.
19
Fig. 20.2 | A graphical representation of a list.
 2008 Pearson Education, Inc. All rights reserved.
1
// Fig. 20.3: Listnode.h
2
3
4
// Template ListNode class definition.
#ifndef LISTNODE_H
#define LISTNODE_H
Outline
// forward declaration of class List required to announce that class
// List exists so it can be used in the friend declaration at line 13
template< typename NODETYPE > class List;
Listnode.h
20
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template< typename NODETYPE>
class ListNode
{
(1 of 2)
Declare class List< NODETYPE >
as a friend
friend class List< NODETYPE >; // make List a friend
public:
ListNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return data in node
private:
NODETYPE data; // data
ListNode< NODETYPE > *nextPtr; // next node in list
}; // end class ListNode
// constructor
template< typename NODETYPE>
Member data stores a value of
type parameter NODETYPE
Member nextPtr stores a pointer to the
next ListNode object in the linked list
25 ListNode< NODETYPE >::ListNode( const NODETYPE &info )
26
: data( info ), nextPtr( 0 )
27 {
28
// empty body
29 } // end ListNode constructor
 2008 Pearson Education,
Inc. All rights reserved.
30
31 // return copy of data in node
32 template< typename NODETYPE >
21
Outline
33 NODETYPE ListNode< NODETYPE >::getData() const
34 {
35
return data;
36 } // end function getData
37
38 #endif
Listnode.h
(2 of 2)
 2008 Pearson Education,
Inc. All rights reserved.
1
// Fig. 20.4: List.h
2
3
// Template List class definition.
#ifndef LIST_H
4
5
6
#define LIST_H
7
8
using std::cout;
9
10
11
12
13
#include "listnode.h" // ListNode class definition
22
Outline
#include <iostream>
List.h
(1 of 7)
template< typename NODETYPE >
class List
{
14 public:
15
List(); // constructor
16
~List(); // destructor
17
18
19
20
void
void
bool
bool
insertAtFront( const NODETYPE & );
insertAtBack( const NODETYPE & );
removeFromFront( NODETYPE & );
removeFromBack( NODETYPE & );
21
bool isEmpty() const;
private data members firsrtPtr (a pointer to
the first ListNode in a List) and lastPtr (a
pointer to the last ListNode in a List)
22
void print() const;
23 private:
24
ListNode< NODETYPE > *firstPtr; // pointer to first node
25
26
27
28
ListNode< NODETYPE > *lastPtr; // pointer to last node
// utility function to allocate new node
ListNode< NODETYPE > *getNewNode( const NODETYPE & );
29 }; // end class List
30
 2008 Pearson Education,
Inc. All rights reserved.
31 // default constructor
32 template< typename NODETYPE >
23
Outline
33 List< NODETYPE >::List()
34
: firstPtr( 0 ), lastPtr( 0 )
35 {
36
// empty body
Initialize both pointers to 0 (null)
37 } // end List constructor
38
List.h
(2 of 7)
39 // destructor
40 template< typename NODETYPE >
41 List< NODETYPE >::~List()
42 {
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
if ( !isEmpty() ) // List is not empty
{
cout << "Destroying nodes ...\n";
ListNode< NODETYPE > *currentPtr = firstPtr;
ListNode< NODETYPE > *tempPtr;
while ( currentPtr != 0 ) // delete remaining nodes
{
tempPtr = currentPtr;
cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
} // end while
} // end if
Ensure that all ListNode objects in
a List object are destroyed when
that List object is destroyed
cout << "All nodes destroyed\n\n";
60 } // end List destructor
 2008 Pearson Education,
Inc. All rights reserved.
61
62 // insert node at front of list
Places a new node at the front of the list
63 template< typename NODETYPE >
64 void List< NODETYPE >::insertAtFront( const NODETYPE &value )
65 {
66
ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node
67
68
if ( isEmpty() ) // List is empty
69
70
71
firstPtr = lastPtr = newPtr; // new list has only one node
else // List is not empty
{
newPtr->nextPtr = firstPtr; // point new node to previous 1st
72
73
74
Outline
Use function getNewNode to
allocate a new ListNode
containing
value and
List.h
assign it to newPtr
(3 of 7)
If the list is empty, then both
firstPtr and lastPtr
node are set to newPtr
firstPtr = newPtr; // aim firstPtr at new node
} // end else
75 } // end function insertAtFront
76
77
78
79
80
24
Thread the new node into the list so that
the new node points to the old first node
andback
firstPtr
points to the new node
Places a new node at the
of the list
// insert node at back of list
template< typename NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
81
82
83
84
ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node
85
else // List is not empty
86
87
88
89
{
if ( isEmpty() ) // List is empty
firstPtr = lastPtr = newPtr; // new list has only one node
lastPtr->nextPtr = newPtr; // update previous last node
lastPtr = newPtr; // new last node
} // end else
90 } // end function insertAtBack
Use function getNewNode to
allocate a new listNode
containing value and
assign it to newPtr
If the list is empty, then both
firstPtr and lastPtr
are set to newPtr
Thread the new node into the list so that
the old last node points to the new node
 2008 Pearson Education,
and lastPtr points to the new node
Inc. All rights reserved.
91
92 // delete node from front of list
93 template< typename NODETYPE >
Removes the front node of the list and copies
Outline
the node value to the reference parameter
94 bool List< NODETYPE >::removeFromFront( NODETYPE &value )
95 {
96
97
98
if ( isEmpty() ) // List is empty
return false; // delete unsuccessful
else
99
{
Return false if an attempt is made to
remove a node from an empty list
List.h
Save a pointer to the first node,
(4 of 7)
which will be removed
100
101
ListNode< NODETYPE > *tempPtr = firstPtr; // hold tempPtr to delete
102
103
if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0; // no nodes remain after removal
104
105
else
firstPtr = firstPtr->nextPtr; // point to previous 2nd node
106
107
108
value = tempPtr->data; // return data being removed
delete tempPtr; // reclaim previous front node
109
return true; // delete successful
110
} // end else
111 } // end function removeFromFront
25
If the list has only one element,
leave the list empty
Set firstPtr to point
to the second node
(the new first node)
Copy the removed node’s
data to reference
parameter value
112
delete the removed node
 2008 Pearson Education,
Inc. All rights reserved.
113 // delete node from back of list
114 template< typename NODETYPE >
115 bool List< NODETYPE >::removeFromBack( NODETYPE &value )
116 {
26
Removes the back node of the list and copies
the node value to theOutline
reference parameter
Return false if an attempt is made to
remove a node from an empty list
117
if ( isEmpty() ) // List is empty
118
119
120
121
return false; // delete unsuccessful
List.h
else
{
Save a pointer to the last node,
(5 of 7)
ListNode< NODETYPE > *tempPtr = lastPtr; // hold tempPtr to delete which will be removed
122
123
124
if ( firstPtr == lastPtr ) // List has one element
firstPtr = lastPtr = 0; // no nodes remain after removal
125
else
126
127
128
{
Assign currentPtr the
address of the first node to
prepare to “walk the list”
ListNode< NODETYPE > *currentPtr = firstPtr;
129
// locate second-to-last element
130
while ( currentPtr->nextPtr != lastPtr )
131
132
133
lastPtr = currentPtr; // remove last node
134
currentPtr->nextPtr = 0; // this is now the last node
currentPtr = currentPtr->nextPtr; // move to next“Walk
node
the list” until currentPtr
points to the node before the last
node, which will be the new last node
135
} // end else
136
137
value = tempPtr->data; // return value from old last node
138
139
delete tempPtr; // reclaim former last node
return true; // delete successful
140
If the list has only one element,
leave the list empty
} // end else
Make the currentPtr
node the new last node
Copy the removed node’s data
to reference parameter value
delete the removed node
 2008 Pearson Education,
Inc. All rights reserved.
141 } // end function removeFromBack
27
Outline
142
143 // is List empty?
144 template< typename NODETYPE >
145 bool List< NODETYPE >::isEmpty() const
146 {
147
return firstPtr == 0;
Determine whether the
List is empty
148 } // end function isEmpty
List.h
(6 of 7)
149
150 // return pointer to newly allocated node
151 template< typename NODETYPE >
152 ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
153
const NODETYPE &value )
154 {
155
return new ListNode< NODETYPE >( value );
Return a dynamically allocated
ListNode object
156 } // end function getNewNode
157
158 // display contents of List
159 template< typename NODETYPE >
160 void List< NODETYPE >::print() const
161 {
162
if ( isEmpty() ) // List is empty
163
{
164
cout << "The list is empty\n\n";
165
return;
166
} // end if
 2008 Pearson Education,
Inc. All rights reserved.
167
168
ListNode< NODETYPE > *currentPtr = firstPtr;
169
170
171
172
173
174
175
28
Outline
cout << "The list is: ";
while ( currentPtr != 0 ) // get element data
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
List.h
Iterate through the list and
output the value in each node (7 of 7)
176
} // end while
177
178
cout << "\n\n";
179 } // end function print
180
181 #endif
 2008 Pearson Education,
Inc. All rights reserved.
1
2
// Fig. 20.5: Fig20_05.cpp
// List class test program.
3
4
5
6
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
7
8 #include <string>
9 using std::string;
10
29
Outline
Fig20_05.cpp
(1 of 6)
11 #include "List.h" // List class definition
12
13 // function to test a List
14 template< typename T >
15 void testList( List< T > &listObject, const string &typeName )
16 {
17
cout << "Testing a List of " << typeName << " values\n";
18
instructions(); // display instructions
19
20
21
22
int choice; // store user choice
T value; // store input value
23
24
25
26
do // perform user-selected actions
{
cout << "? ";
cin >> choice;
27
 2008 Pearson Education,
Inc. All rights reserved.
28
29
30
switch ( choice )
{
case 1: // insert at beginning
31
32
cout << "Enter " << typeName << ": ";
cin >> value;
33
34
35
36
37
listObject.insertAtFront( value );
listObject.print();
break;
case 2: // insert at end
cout << "Enter " << typeName << ": ";
38
39
40
41
42
cin >> value;
listObject.insertAtBack( value );
listObject.print();
break;
case 3: // remove from beginning
43
44
if ( listObject.removeFromFront( value ) )
cout << value << " removed from list\n";
45
46
47
listObject.print();
break;
48
49
50
51
52
53
54
55
56
30
Outline
Fig20_05.cpp
(2 of 6)
case 4: // remove from end
if ( listObject.removeFromBack( value ) )
cout << value << " removed from list\n";
listObject.print();
break;
} // end switch
} while ( choice != 5 ); // end do...while
 2008 Pearson Education,
Inc. All rights reserved.
57
cout << "End list test\n\n";
58 } // end function testList
59
60 // display program instructions to user
31
Outline
61 void instructions()
62 {
63
64
cout << "Enter one of the following:\n"
<< " 1 to insert at beginning of list\n"
65
<< "
2 to insert at end of list\n"
66
67
68
<< "
<< "
<< "
3 to delete from beginning of list\n"
4 to delete from end of list\n"
5 to end list processing\n";
Fig20_05.cpp
(3 of 6)
69 } // end function instructions
70
71 int main()
72 {
73
// test List of int values
74
75
76
77
List< int > integerList;
testList( integerList, "integer" );
78
79
List< double > doubleList;
testList( doubleList, "double" );
// test List of double values
80
return 0;
81 } // end main
 2008 Pearson Education,
Inc. All rights reserved.
32
Testing a List of integer values
Enter one of the following:
1 to insert at beginning of list
2 to insert at end of list
3 to delete from beginning of list
4 to delete from end of list
5 to end list processing
? 1
Enter integer: 1
The list is: 1
Outline
Fig20_05.cpp
(4 of 6)
? 1
Enter integer: 2
The list is: 2 1
? 2
Enter integer: 3
The list is: 2 1 3
? 2
Enter integer: 4
The list is: 2 1 3 4
? 3
2 removed from list
The list is: 1 3 4
(continued at top of next slide... )
 2008 Pearson Education,
Inc. All rights reserved.
(...continued from bottom of previous slide)
? 3
1 removed from list
The list is: 3 4
? 4
4 removed from list
The list is: 3
33
Outline
Fig20_05.cpp
(5 of 6)
? 4
3 removed from list
The list is empty
? 5
End list test
Testing a List of double values
Enter one of the following:
1 to insert at beginning of list
2 to insert at end of list
3 to delete from beginning of list
4 to delete from end of list
5 to end list processing
? 1
Enter double: 1.1
The list is: 1.1
? 1
Enter double: 2.2
The list is: 2.2 1.1
(continued at top of next slide... )
 2008 Pearson Education,
Inc. All rights reserved.
(...continued from bottom of previous slide)
? 2
Enter double: 3.3
The list is: 2.2 1.1 3.3
? 2
Enter double: 4.4
The list is: 2.2 1.1 3.3 4.4
34
Outline
Fig20_05.cpp
(6 of 6)
? 3
2.2 removed from list
The list is: 1.1 3.3 4.4
? 3
1.1 removed from list
The list is: 3.3 4.4
? 4
4.4 removed from list
The list is: 3.3
? 4
3.3 removed from list
The list is empty
? 5
End list test
All nodes destroyed
All nodes destroyed
 2008 Pearson Education,
Inc. All rights reserved.
35
Error-Prevention Tip 20.1
Assign null (0) to the link member of a new node.
Pointers should be initialized before they are used.
 2008 Pearson Education, Inc. All rights reserved.
36
Fig. 20.6 | Operation insertAtFront represented graphically.
 2008 Pearson Education, Inc. All rights reserved.
37
Fig. 20.7 | Operation insertAtBack represented graphically.
 2008 Pearson Education, Inc. All rights reserved.
38
Fig. 20.8 | Operation removeFromFront represented graphically.
 2008 Pearson Education, Inc. All rights reserved.
39
Fig. 20.9 | Operation removeFromBack represented graphically.
 2008 Pearson Education, Inc. All rights reserved.
40
20.4 Linked Lists (Cont.)
• Linked list (Cont.)
– Circular, singly linked list
• Pointer in last node points back to first node
– Doubly linked list
• Each node has a link to next node and a link to previous node
• Two “start pointers”
– One to first node, one to last node
• Allows traversals both forward and backward
– Circular, doubly linked list
• Forward link of last node points back to first node
• Backward link of first node points to last node
 2008 Pearson Education, Inc. All rights reserved.
41
Fig. 20.10 | Circular, singly linked list.
 2008 Pearson Education, Inc. All rights reserved.
42
Fig. 20.11 | Doubly linked list.
 2008 Pearson Education, Inc. All rights reserved.
43
Fig. 20.12 | Circular, doubly linked list.
 2008 Pearson Education, Inc. All rights reserved.
44
20.5 Stacks
• Stack
– Allows nodes to be added and removed only at the top
• Referred to as a last-in, first-out (LIFO) data structure
– Can be implemented as a constrained linked list
• Link of the last node of the stack is set to null to indicate
bottom of the stack
– Manipulated using member functions push and pop
• push inserts new node at the top
• pop removes node from the top and retrieves its value
 2008 Pearson Education, Inc. All rights reserved.
45
20.5 Stacks (Cont.)
• Stack (Cont.)
– Applications of stacks
• Function call stack
– Stores return addresses for function calls
– Stores values of automatic variables in function calls
• Used by compilers
– Evaluating expressions
– Generating machine-language code
 2008 Pearson Education, Inc. All rights reserved.
1
// Fig. 20.13: Stack.h
2
// Template Stack class definition derived from class List.
3
#ifndef STACK_H
4
#define STACK_H
46
Outline
5
6
#include "List.h" // List class definition
7
8
9
10
11
template< typename STACKTYPE >
class Stack : private List< STACKTYPE >
{
public:
12
13
// push calls the List function insertAtFront
void push( const STACKTYPE &data )
14
15
{
16
} // end function push
17
18
19
20
21
// pop calls the List function removeFromFront
bool pop( STACKTYPE &data )
{
return removeFromFront( data );
22
23
Stack.h
Create a Stack class template through
(1 of 2) private
inheritance of the List class template
insertAtFront( data );
Perform push and pop by delegating to baseclass member functions insertAtFront
and removeFromFront, respectively
} // end function pop
 2008 Pearson Education,
Inc. All rights reserved.
24
// isStackEmpty calls the List function isEmpty
25
26
bool isStackEmpty() const
{
27
28
29
30
31
32
47
Outline
return isEmpty();
} // end function isStackEmpty
// printStack calls the List function print
void printStack() const
{
33
print();
34
} // end function print
35 }; // end class Stack
Member functions isStackEmpty and
Stack.h
printStack delegate to base-class
member functions isEmpty
and print,
(2 of 2)
respectively
36
37 #endif
 2008 Pearson Education,
Inc. All rights reserved.
1
// Fig. 20.14: Fig20_14.cpp
2
// Template Stack class test program.
3
#include <iostream>
4
5
using std::cout;
using std::endl;
48
Outline
6
7
8
Fig20_14.cpp
#include "Stack.h" // Stack class definition
(1 of 3)
9 int main()
10 {
11
Stack< int > intStack; // create Stack of ints
12
13
14
cout << "processing an integer Stack" << endl;
15
16
17
18
// push integers onto intStack
for ( int i = 0; I < 3; i++ )
{
intStack.push( i );
19
20
intStack.printStack();
} // end for
21
22
23
24
int popInteger; // store int popped from stack
// pop integers from intStack
25
while ( !intStack.isStackEmpty() )
26
{
27
28
29
30
Push integers 0 through 2 onto intStack
Pop integers 2 through 0 off intStack
intStack.pop( popInteger );
cout << popInteger << " popped from stack" << endl;
intStack.printStack();
} // end while
 2008 Pearson Education,
Inc. All rights reserved.
31
32
33
Stack< double > doubleStack; // create Stack of doubles
double value = 1.1;
49
Outline
34
35
36
37
38
cout << "processing a double Stack" << endl;
39
{
40
41
42
43
44
doubleStack.push( value );
doubleStack.printStack();
value += 1.1;
} // end for
45
46
47
48
49
50
double popDouble; // store double popped from stack
51
52
53
54
55
Fig20_14.cpp
// push floating-point values onto doubleStack
for ( int j = 0; j < 3; j++ )
(2 of 3)
Push values 1.1, 2.2 and 3.3 onto doubleStack
// pop floating-point values from doubleStack
while ( !doubleStack.isStackEmpty() )
{
doubleStack.pop( popDouble );
Pop values 3.3, 2.2 and 1.1 off doubleStack
cout << popDouble << " popped from stack" << endl;
doubleStack.printStack();
} // end while
return 0;
56 } // end main
 2008 Pearson Education,
Inc. All rights reserved.
processing an integer Stack
The list is: 0
50
Outline
The list is: 1 0
The list is: 2 1 0
2 popped from stack
The list is: 1 0
Fig20_14.cpp
1 popped from stack
The list is: 0
(3 of 3)
0 popped from stack
The list is empty
processing a double Stack
The list is: 1.1
The list is: 2.2 1.1
The list is: 3.3 2.2 1.1
3.3 popped from stack
The list is: 2.2 1.1
2.2 popped from stack
The list is: 1.1
1.1 popped from stack
The list is empty
All nodes destroyed
All nodes destroyed
 2008 Pearson Education,
Inc. All rights reserved.
1
// Fig. 20.15: Stackcomposition.h
2
// Template Stack class definition with composed List object.
3
#ifndef STACKCOMPOSITION_H
4
5
6
#define STACKCOMPOSITION_H
7
8
9
10
11
#include "List.h" // List class definition
template< typename STACKTYPE >
class Stack
{
public:
12
13
14
15
// no constructor; List constructor does initialization
16
17
18
19
20
{
21
22
23
24
bool pop( STACKTYPE &data )
{
return stackList.removeFromFront( data );
} // end function pop
51
Outline
Stack
composition.h
(1 of 2)
// push calls stackList object's insertAtFront member function
void push( const STACKTYPE &data )
stackList.insertAtFront( data );
} // end function push
// pop calls stackList object's removeFromFront member function
 2008 Pearson Education,
Inc. All rights reserved.
25
26
27
28
// isStackEmpty calls stackList object's isEmpty member function
bool isStackEmpty() const
{
29
30
31
32
return stackList.isEmpty();
} // end function isStackEmpty
33
34
35
void printStack() const
{
stackList.print();
36
} // end function printStack
// printStack calls stackList object's print member function
52
Outline
Stack
composition.h
(2 of 2)
37 private:
38
List< STACKTYPE > stackList; // composed List object
39 }; // end class Stack
40
41 #endif
This implementation of the Stack class template contains
a List< STACKTYPE > object called stackList
 2008 Pearson Education,
Inc. All rights reserved.
53
20.6 Queues
• Queue
– First item in line is serviced first, others wait in line
• Nodes removed only from head and inserted only at tail
• Referred to as a first-in, first-out (FIFO) data structure
– Insert and remove operations are enqueue and dequeue
– Applications of queues
• Waiting lines for
– Processor usage
– Printing jobs
– Packets at a router
– File system requests
 2008 Pearson Education, Inc. All rights reserved.
1
// Fig. 20.16: Queue.h
2
// Template Queue class definition derived from class List.
3
#ifndef QUEUE_H
4
5
6
7
8
9
10
11
#define QUEUE_H
#include "List.h" // List class definition
template< typename QUEUETYPE >
class Queue : private List< QUEUETYPE >
{
public:
54
Outline
Queue.h
Create a Queue class template through
private
(1 of 2)
inheritance of the List class template
12
13
14
15
// enqueue calls List member function insertAtBack
void enqueue( const QUEUETYPE &data )
{
insertAtBack( data );
16
} // end function enqueue
17
18
19
20
// dequeue calls List member function removeFromFront
bool dequeue( QUEUETYPE &data )
{
21
22
return removeFromFront( data );
} // end function dequeue
Perform enqueue and dequeue by
delegating to base-class member
functions insertAtBack and
removeFromFront,
respectively
 2008 Pearson Education,
Inc. All rights reserved.
23
24
// isQueueEmpty calls List member function isEmpty
25
26
bool isQueueEmpty() const
{
27
55
Outline
return isEmpty();
28
} // end function isQueueEmpty
29
30
31
32
// printQueue calls List member function print
void printQueue() const
{
33
print();
34
} // end function printQueue
35 }; // end class Queue
36
Queue.h
Member functions isQueueEmpty
and
printQueue delegate to base-class
(2 of 2)
member functions isEmpty and print,
respectively
37 #endif
 2008 Pearson Education,
Inc. All rights reserved.
1
2
3
// Fig. 20.17: Fig20_17.cpp
// Template Queue class test program.
#include <iostream>
4
5
6
7
8
9
using std::cout;
using std::endl;
56
Outline
Fig20_17.cpp
#include "Queue.h" // Queue class definition
(1 of 3)
int main()
10 {
11
12
Queue< int > intQueue; // create Queue of integers
13
cout << "processing an integer Queue" << endl;
14
15
16
// enqueue integers onto intQueue
for ( int i = 0; i < 3; i++ )
17
{
18
19
20
21
22
23
24
intQueue.enqueue( i );
intQueue.printQueue();
} // end for
Enqueue integers 0 through 2 to intQueue
int dequeueInteger; // store dequeued integer
// dequeue integers from intQueue
25
while ( !intQueue.isQueueEmpty() )
26
27
28
29
30
{
Dequeue integers 0 through 2 from intQueue
intQueue.dequeue( dequeueInteger );
cout << dequeueInteger << " dequeued" << endl;
intQueue.printQueue();
} // end while
 2008 Pearson Education,
Inc. All rights reserved.
31
32
Queue< double > doubleQueue; // create Queue of doubles
33
double value = 1.1;
57
Outline
34
35
36
cout << "processing a double Queue" << endl;
37
38
// enqueue floating-point values onto doubleQueue
for ( int j = 0; j < 3; j++ )
39
40
{
41
42
43
44
doubleQueue.printQueue();
value += 1.1;
} // end for
45
46
double dequeueDouble; // store dequeued double
47
48
49
50
// dequeue floating-point values from doubleQueue
while ( !doubleQueue.isQueueEmpty() )
Dequeue
{
doubleQueue.dequeue( dequeueDouble );
51
52
doubleQueue.enqueue( value );
Fig20_17.cpp
(2 of 3)
Enqueue values 1.1, 2.2 and 3.3 to doubleQueue
values 1.1, 2.2 and 3.3 from doubleQueue
cout << dequeueDouble << " dequeued" << endl;
doubleQueue.printQueue();
53
} // end while
54
55
return 0;
56 } // end main
 2008 Pearson Education,
Inc. All rights reserved.
processing an integer Queue
The list is: 0
58
Outline
The list is: 0 1
The list is: 0 1 2
0 dequeued
The list is: 1 2
Fig20_17.cpp
(2 of 3)
1 dequeued
The list is: 2
2 dequeued
The list is empty
processing a double Queue
The list is: 1.1
The list is: 1.1 2.2
The list is: 1.1 2.2 3.3
1.1 dequeued
The list is: 2.2 3.3
2.2 dequeued
The list is: 3.3
3.3 dequeued
The list is empty
All nodes destroyed
All nodes destroyed
 2008 Pearson Education,
Inc. All rights reserved.
59
20.7 Trees
• Tree
– Nonlinear, two-dimensional data structure
– Tree nodes contain two or more links
• Binary tree nodes contain exactly two links
 2008 Pearson Education, Inc. All rights reserved.
60
20.7 Trees (Cont.)
• Tree (Cont.)
– Terminology
• Root node
– First node in a tree
• Child node
– Node linked to by another node (its parent)
– In a binary tree, there is a left child and a right child
• Subtree
– Tree defined by treating a child node as the root of its
own tree
• Siblings
– Multiple children of a single parent node
• Leaf node
– Node with no children
 2008 Pearson Education, Inc. All rights reserved.
61
Fig. 20.18 | A graphical representation of a binary tree.
 2008 Pearson Education, Inc. All rights reserved.
62
20.7 Trees (Cont.)
• Tree (Cont.)
– Binary search tree
• Values in any left subtree are less than value in its parent
node
• Values in any right subtree are greater than value in its
parent node
• Can be recursively traversed in three ways
– Inorder
• Left subtree, then current node, then right subtree
– Preorder
• Current node, then left subtree, then right subtree
– Postorder
• Left subtree, then right subtree, then current node
 2008 Pearson Education, Inc. All rights reserved.
63
Fig. 20.19 | A binary search tree.
 2008 Pearson Education, Inc. All rights reserved.
1
// Fig. 20.20: Treenode.h
2
// Template TreeNode class definition.
3
4
#ifndef TREENODE_H
#define TREENODE_H
5
6
// forward declaration of class Tree
7
8
9
64
Outline
Treenode.h
template< typename NODETYPE > class Tree;
(1 of 2)
// TreeNode class-template definition
10 template< typename NODETYPE >
11 class TreeNode
12 {
13
friend class Tree< NODETYPE >;
14 public:
15
16
// constructor
TreeNode( const NODETYPE &d )
: leftPtr( 0 ), // pointer to left subtree
data( d ), // tree node data
17
18
19
20
21
22
Declare Tree< NODETYPE > as
TreeNode< NODETYPE >’s friend
Initialize this node to be a leaf
node with data value d
rightPtr( 0 ) // pointer to right substree
{
// empty body
} // end TreeNode constructor
23
24
// return copy of node's data
25
26
NODETYPE getData() const
{
27
28
return data;
} // end getData function
 2008 Pearson Education,
Inc. All rights reserved.
29 private:
65
30
TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
31
NODETYPE data;
32
TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
Outline
33 }; // end class TreeNode
34
Treenode.h
35 #endif
(2 of 2)
Pointers leftPtr and rightPtr point to the
node’s left and right subtrees, respectively
 2008 Pearson Education,
Inc. All rights reserved.
1
// Fig. 20.21: Tree.h
2
// Template Tree class definition.
3
#ifndef TREE_H
4
#define TREE_H
5
6
#include <iostream>
7
8
using std::cout;
using std::endl;
9
10 #include "Treenode.h"
66
Outline
Tree.h
(1 of 6)
11
12 // Tree class-template definition
13 template< typename NODETYPE > class Tree
14 {
15 public:
16
Tree(); // constructor
17
18
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
19
void inOrderTraversal() const;
20
void postOrderTraversal() const;
21 private:
22
TreeNode< NODETYPE > *rootPtr;
23
24
25
// utility functions
void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
26
27
28
29 };
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
// end class Tree
30
 2008 Pearson Education,
Inc. All rights reserved.
31 // constructor
32 template< typename NODETYPE >
33 Tree< NODETYPE >::Tree()
Initialize rootPtr to zero to indicate
that the tree is initially empty
67
Outline
34 {
35
rootPtr = 0; // indicate tree is initially empty
Tree.h
36 } // end Tree constructor
37
(2 of 6)
38 // insert node in Tree
39 template< typename NODETYPE >
40 void Tree< NODETYPE >::insertNode( const NODETYPE &value )
41 {
42
insertNodeHelper( &rootPtr, value );
43 } // end function insertNode
Call utility function insertNodeHelper
to recursively insert a node into the tree
44
 2008 Pearson Education,
Inc. All rights reserved.
45 // utility function called by insertNode; receives a pointer
46 // to a pointer so that the function can modify pointer's value
47 template< typename NODETYPE >
68
Outline
Parameter ptr is a pointer to
a pointer to a TreeNode
48 void Tree< NODETYPE >::insertNodeHelper(
49
50 {
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
51
52
53
54
// subtree is empty; create new TreeNode containing value
if ( *ptr == 0 )
(3 of 6)
*ptr = new TreeNode< NODETYPE >( value );
A new TreeNode is created,
else // subtree is not empty
initialized and inserted in the tree
55
56
57
Tree.h
{
// data to insert is less than data in current node
if ( value < ( *ptr )->data )
58
59
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
60
61
{
62
63
64
65
// data to insert is greater than data in current
Recursively call insertNodeHelper
with the address of the pointer to the
node appropriate binary search subtree
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else // duplicate data value ignored
cout << value << " dup" << endl;
66
} // end else
67
} // end else
68 } // end function insertNodeHelper
69
If the value to be inserted is identical to
the data value in the root node, do not
insert the duplicate value into the tree
 2008 Pearson Education,
Inc. All rights reserved.
70 // begin preorder traversal of Tree
69
71 template< typename NODETYPE >
72 void Tree< NODETYPE >::preOrderTraversal() const
Outline
73 {
74
preOrderHelper( rootPtr );
75 } // end function preOrderTraversal
76
77 // utility function to perform preorder traversal of Tree
Tree.h
(4 of 6)
78 template< typename NODETYPE >
79 void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const
80 {
81
if ( ptr != 0 )
82
{
83
cout << ptr->data << ' '; // process node
84
preOrderHelper( ptr->leftPtr ); // traverse left subtree
85
preOrderHelper( ptr->rightPtr ); // traverse right subtree
86
} // end if
87 } // end function preOrderHelper
88
Process the
89 // begin inorder traversal of Tree
90
91
92
93
94
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
inOrderHelper( rootPtr );
} // end function inOrderTraversal
value in the node, traverse the
left subtree, traverse the right subtree
95
 2008 Pearson Education,
Inc. All rights reserved.
96 // utility function to perform inorder traversal of Tree
97 template< typename NODETYPE >
98 void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
70
Outline
99 {
100
if ( ptr != 0 )
101
{
Tree.h
102
inOrderHelper( ptr->leftPtr ); // traverse left subtree
103
cout << ptr->data << ' '; // process node
104
inOrderHelper( ptr->rightPtr ); // traverse right subtree
105
(5 of 6)
} // end if
106 } // end function inOrderHelper
107
108 // begin postorder traversal of Tree
Traverse the left subtree, process the value
in the node, traverse the right subtree
109 template< typename NODETYPE >
110 void Tree< NODETYPE >::postOrderTraversal() const
111 {
112
postOrderHelper( rootPtr );
113 } // end function postOrderTraversal
114
 2008 Pearson Education,
Inc. All rights reserved.
115 // utility function to perform postorder traversal of Tree
71
Outline
116 template< typename NODETYPE >
117 void Tree< NODETYPE >::postOrderHelper(
118
TreeNode< NODETYPE > *ptr ) const
119 {
120
if ( ptr != 0 )
121
{
Tree.h
122
postOrderHelper( ptr->leftPtr ); // traverse left subtree
123
postOrderHelper( ptr->rightPtr ); // traverse right subtree
124
cout << ptr->data << ' '; // process node
125
(6 of 6)
} // end if
126 } // end function postOrderHelper
127
128 #endif
Traverse the left subtree, traverse the right
subtree, process the value in the node
 2008 Pearson Education,
Inc. All rights reserved.
1
// Fig. 20.22: Fig20_22.cpp
2
// Tree class test program.
3
4
#include <iostream>
using std::cout;
5
using std::cin;
6
7
8
9
using std::fixed;
72
Outline
Fig20_22.cpp
#include <iomanip>
using std::setprecision;
(1 of 3)
10
11 #include "Tree.h" // Tree class definition
12
13 int main()
14 {
15
16
17
18
19
20
21
22
23
24
Instantiate integer tree intTree
of type Tree< int >
Tree< int > intTree; // create Tree of int values
int intValue;
cout << "Enter 10 integer values:\n";
// insert 10 integers to intTree
for ( int i = 0; i < 10; i++ )
{
cin >> intValue;
intTree.insertNode( intValue );
25
26
27
} // end for
28
29
intTree.preOrderTraversal();
cout << "\nPreorder traversal\n";
Insert int values into the binary tree
Perform traversal of intTree
 2008 Pearson Education,
Inc. All rights reserved.
30
cout << "\nInorder traversal\n";
31
32
intTree.inOrderTraversal();
33
cout << "\nPostorder traversal\n";
34
35
36
37
38
intTree.postOrderTraversal();
39
40
41
cout << fixed << setprecision( 1 )
<< "\n\n\nEnter 10 double values:\n";
42
43
44
45
// insert 10 doubles to doubleTree
for ( int j = 0; j < 10; j++ )
{
cin >> doubleValue;
46
47
48
49
50
73
Outline
Tree< double > doubleTree; // create Tree of double values
double doubleValue;
Fig20_22.cpp
(2 of 3)
Instantiate floating-point tree doubleTree
of type Tree< double >
Insert double values into the binary tree
doubleTree.insertNode( doubleValue );
} // end for
cout << "\nPreorder traversal\n";
doubleTree.preOrderTraversal();
Perform traversal of doubleTree
51
52
53
cout << "\nInorder traversal\n";
doubleTree.inOrderTraversal();
 2008 Pearson Education,
Inc. All rights reserved.
54
74
55
cout << "\nPostorder traversal\n";
56
doubleTree.postOrderTraversal();
Outline
57
58
cout << endl;
59
return 0;
Fig20_22.cpp
60 } // end main
Enter 10 integer values:
50 25 75 12 33 67 88 6 13 68
(3 of 3)
Preorder traversal
50 25 12 6 13 33 75 67 68 88
Inorder traversal
6 12 13 25 33 50 67 68 75 88
Postorder traversal
6 13 12 33 25 68 67 88 75 50
Enter 10 double values:
39.2 16.5 82.7 3.3 65.2 90.8 1.1 4.4 89.5 92.5
Preorder traversal
39.2 16.5 3.3 1.1 4.4 82.7 65.2 90.8 89.5 92.5
Inorder traversal
1.1 3.3 4.4 16.5 39.2 65.2 82.7 89.5 90.8 92.5
Postorder traversal
1.1 4.4 3.3 16.5 65.2 89.5 92.5 90.8 82.7 39.2
 2008 Pearson Education,
Inc. All rights reserved.
75
Fig. 20.23 | A binary search tree.
 2008 Pearson Education, Inc. All rights reserved.
76
20.7 Trees (Cont.)
• Tree (Cont.)
– Applications of binary search trees
• Duplicate elimination
– Inserting duplicate will follow same path as original
– Duplicate can be discarded when compared with orignal
• Searching (in a balanced binary search tree)
– Has O(log n) runtime
• Each comparison of a node to search key eliminates
half the nodes
• Maximum of log2 n comparisons are required
• Sorting (binary tree sort)
– Inorder traversal of a binary search tree results in
processing the values in ascending order
 2008 Pearson Education, Inc. All rights reserved.