Bài giảng Lập trình C++ - Chương 17: Data Structures

Travel in one direction (null-terminated) Circular, singly-linked As above, but last node points to first Doubly-linked list Each node has a forward and backwards pointer Travel forward or backward Last node null-terminated Circular, double-linked As above, but first and last node joined * 17.5 	Stacks Stack Nodes can be added/removed from top Constrained version of linked list Like a stack of plates Last-in, first-out (LIFO) data structure Bottom of stack has null link Stack operations Push: add node to top Pop: remove node from top Stores value in reference variable * 17.5 	Stacks Stack applications Function calls: know how to return to caller Return address pushed on stack Most recent function call on top If function A calls B which calls C: Used to store automatic variables Popped of stack when no longer needed Used by compilers Example in the exercises in book C B B B A A A A A * 17.5 	Stacks Upcoming program Create stack from list insertAtFront, removeFromFront Software reusability Inheritance Stack inherits from List Composition Stack contains a private List object Performs operations on that object Makes stack implementation simple * stack.h (1 of 2) 1 // Fig. 17.10: stack.h 2 // Template Stack class definition derived from class List. 3 #ifndef STACK_H 4 #define STACK_H 5 6 #include "list.h" // List class definition 7 8 template 9 class Stack : private List { 10 11 public: 12 // push calls List function insertAtFront 13 void push( const STACKTYPE &data ) 14 { 15 insertAtFront( data ); 16 17 } // end function push 18 19 // pop calls List function removeFromFront 20 bool pop( STACKTYPE &data ) 21 { 22 return removeFromFront( data ); 23 24 } // end function pop 25 * stack.h (2 of 2) 26 // isStackEmpty calls List function isEmpty 27 bool isStackEmpty() const 28 { 29 return isEmpty(); 30 31 } // end function isStackEmpty 32 33 // printStack calls List function print 34 void printStack() const 35 { 36 print(); 37 38 } // end function print 39 40 }; // end class Stack 41 42 #endif * fig17_11.cpp(1 of 3) 1 // Fig. 17.11: fig17_11.cpp 2 // Template Stack class test program. 3 #include 4 5 using std::endl; 6 7 #include "stack.h" // Stack class definition 8 9 int main() 10 { 11 Stack intStack; // create Stack of ints 12 13 cout doubleStack; // create Stack of doubles 33 double value = 1.1; 34 35 cout 9 class Stack { 10 11 public: 12 // no constructor; List constructor does initialization 13 14 // push calls stackList object's insertAtFront function 15 void push( const STACKTYPE &data ) 16 { 17 stackList.insertAtFront( data ); 18 19 } // end function push 20 21 // pop calls stackList object's removeFromFront function 22 bool pop( STACKTYPE &data ) 23 { 24 return stackList.removeFromFront( data ); 25 26 } // end function pop 27 * stackcomposition.h(2 of 2) 28 // isStackEmpty calls stackList object's isEmpty function 29 bool isStackEmpty() const 30 { 31 return stackList.isEmpty(); 32 33 } // end function isStackEmpty 34 35 // printStack calls stackList object's print function 36 void printStack() const 37 { 38 stackList.print(); 39 40 } // end function printStack 41 42 private: 43 List stackList; // composed List object 44 45 }; // end class Stack 46 47 #endif * 17.6 	Queues Queue Like waiting in line Nodes added to back (tail), removed from front (head) First-in, first-out (FIFO) data structure Insert/remove called enqueue/dequeue Applications Print spooling Documents wait in queue until printer available Packets on network File requests from server * 17.6 	Queues Upcoming program Queue implementation Reuse List as before insertAtBack (enqueue) removeFromFront (dequeue) * queue.h (1 of 2) 1 // Fig. 17.13: queue.h 2 // Template Queue class definition derived from class List. 3 #ifndef QUEUE_H 4 #define QUEUE_H 5 6 #include "list.h" // List class definition 7 8 template 9 class Queue : private List { 10 11 public: 12 // enqueue calls List function insertAtBack 13 void enqueue( const QUEUETYPE &data ) 14 { 15 insertAtBack( data ); 16 17 } // end function enqueue 18 19 // dequeue calls List function removeFromFront 20 bool dequeue( QUEUETYPE &data ) 21 { 22 return removeFromFront( data ); 23 24 } // end function dequeue 25 * queue.h (2 of 2) 26 // isQueueEmpty calls List function isEmpty 27 bool isQueueEmpty() const 28 { 29 return isEmpty(); 30 31 } // end function isQueueEmpty 32 33 // printQueue calls List function print 34 void printQueue() const 35 { 36 print(); 37 38 } // end function printQueue 39 40 }; // end class Queue 41 42 #endif * fig17_14.cpp(1 of 3) 1 // Fig. 17.14: fig17_14.cpp 2 // Template Queue class test program. 3 #include 4 5 using std::endl; 6 7 #include "queue.h" // Queue class definition 8 9 int main() 10 { 11 Queue intQueue; // create Queue of ints 12 13 cout doubleQueue; // create Queue of doubles 33 double value = 1.1; 34 35 cout node, insert into right subtree If value nor class Tree; 8 9 template 10 class TreeNode { 11 friend class Tree; 12 13 public: 14 15 // constructor 16 TreeNode( const NODETYPE &d ) 17 : leftPtr( 0 ), 18 data( d ), 19 rightPtr( 0 ) 20 { 21 // empty body 22 23 } // end TreeNode constructor 24 * treenode.h (2 of 2) 25 // return copy of node's data 26 NODETYPE getData() const 27 { 28 return data; 29 30 } // end getData function 31 32 private: 33 TreeNode *leftPtr; // pointer to left subtree 34 NODETYPE data; 35 TreeNode *rightPtr; // pointer to right subtree 36 37 }; // end class TreeNode 38 39 #endif * tree.h (1 of 6) 1 // Fig. 17.18: tree.h 2 // Template Tree class definition. 3 #ifndef TREE_H 4 #define TREE_H 5 6 #include 7 8 using std::endl; 9 10 #include 11 #include "treenode.h" 12 13 template 14 class Tree { 15 16 public: 17 Tree(); 18 void insertNode( const NODETYPE & ); 19 void preOrderTraversal() const; 20 void inOrderTraversal() const; 21 void postOrderTraversal() const; 22 23 private: 24 TreeNode *rootPtr; 25 * tree.h (2 of 6) 26 // utility functions 27 void insertNodeHelper( 28 TreeNode **, const NODETYPE & ); 29 void preOrderHelper( TreeNode * ) const; 30 void inOrderHelper( TreeNode * ) const; 31 void postOrderHelper( TreeNode * ) const; 32 33 }; // end class Tree 34 35 // constructor 36 template 37 Tree::Tree() 38 { 39 rootPtr = 0; 40 41 } // end Tree constructor 42 43 // insert node in Tree 44 template 45 void Tree::insertNode( const NODETYPE &value ) 46 { 47 insertNodeHelper( &rootPtr, value ); 48 49 } // end function insertNode 50 * tree.h (3 of 6) 51 // utility function called by insertNode; receives a pointer 52 // to a pointer so that the function can modify pointer's value 53 template 54 void Tree::insertNodeHelper( 55 TreeNode **ptr, const NODETYPE &value ) 56 { 57 // subtree is empty; create new TreeNode containing value 58 if ( *ptr == 0 ) 59 *ptr = new TreeNode( value ); 60 61 else // subtree is not empty 62 63 // data to insert is less than data in current node 64 if ( value data ) 65 insertNodeHelper( &( ( *ptr )->leftPtr ), value ); 66 67 else 68 69 // data to insert is greater than data in current node 70 if ( value > ( *ptr )->data ) 71 insertNodeHelper( &( ( *ptr )->rightPtr ), value ); 72 73 else // duplicate data value ignored 74 cout 80 void Tree::preOrderTraversal() const 81 { 82 preOrderHelper( rootPtr ); 83 84 } // end function preOrderTraversal 85 86 // utility function to perform preorder traversal of Tree 87 template 88 void Tree::preOrderHelper( 89 TreeNode *ptr ) const 90 { 91 if ( ptr != 0 ) { 92 cout data leftPtr ); // go to left subtree 94 preOrderHelper( ptr->rightPtr ); // go to right subtree 95 96 } // end if 97 98 } // end function preOrderHelper 99 * tree.h (5 of 6) 100 // begin inorder traversal of Tree 101 template 102 void Tree::inOrderTraversal() const 103 { 104 inOrderHelper( rootPtr ); 105 106 } // end function inOrderTraversal 107 108 // utility function to perform inorder traversal of Tree 109 template 110 void Tree::inOrderHelper( 111 TreeNode *ptr ) const 112 { 113 if ( ptr != 0 ) { 114 inOrderHelper( ptr->leftPtr ); // go to left subtree 115 cout data rightPtr ); // go to right subtree 117 118 } // end if 119 120 } // end function inOrderHelper 121 * tree.h (6 of 6) 122 // begin postorder traversal of Tree 123 template 124 void Tree::postOrderTraversal() const 125 { 126 postOrderHelper( rootPtr ); 127 128 } // end function postOrderTraversal 129 130 // utility function to perform postorder traversal of Tree 131 template 132 void Tree::postOrderHelper( 133 TreeNode *ptr ) const 134 { 135 if ( ptr != 0 ) { 136 postOrderHelper( ptr->leftPtr ); // go to left subtree 137 postOrderHelper( ptr->rightPtr ); // go to right subtree 138 cout data 4 5 using std::cout; 6 using std::cin; 7 using std::fixed; 8 9 #include 10 using std::setprecision; 11 12 #include "tree.h" // Tree class definition 13 14 int main() 15 { 16 Tree intTree; // create Tree of int values 17 int intValue; 18 19 cout > intValue; 23 intTree.insertNode( intValue ); 24 25 } // end for * fig17_19.cpp(2 of 3) 26 27 cout doubleTree; // create Tree of double values 37 double doubleValue; 38 39 cout > doubleValue; 44 doubleTree.insertNode( doubleValue ); 45 46 } // end for 47 48 cout << "\nPreorder traversal\n"; 49 doubleTree.preOrderTraversal(); 50 * fig17_19.cpp(3 of 3) 51 cout << "\nInorder traversal\n"; 52 doubleTree.inOrderTraversal(); 53 54 cout << "\nPostorder traversal\n"; 55 doubleTree.postOrderTraversal(); 56 57 cout << endl; 58 59 return 0; 60 61 } // end main * fig17_19.cppoutput (1 of 1) Enter 10 integer values: 50 25 75 12 33 67 88 6 13 68   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