数据结构与算法分析 第9章 答案 Larry Nyhoff 清华大学.pdf

Chapter 9 96 Chapter 9 ADT Implementations Templates and Standard Containers Exercises 9 3 1 template DataType average DataType a DataType b return a b 2 2 template DataType max DataType a DataType b if a b return a else return b 3 template DataType median DataType a DataType b DataType c DataType max a min b if a max return max else if c min return min else return c 4 template DataType arraySum DataType x int length DataType sum x 0 for int index 1 index length index sum x index return sum Chapter 9 97 5 template void arrayMaxMin DataType x int length DataType for int i 1 i length i if x i max max x i 6 template int search DataType x int length DataType target for int index 0 index length index if x index target return index return 1 index of 1 denotes not found 7 ListT h This header file defines the data type List for processing lists Basic operations are Constructor empty Check if list is empty insert Insert an item erase Remove an item display Output the list Output operator include ifndef LISTT define LISTT const int CAPACITY 1024 template class List public Function Members Class constructor List Construct a List object Precondition None Postcondition An empty List object has been constructed mySize is 0 Chapter 9 98 empty operation bool empty const Check if a list is empty Precondition None Postcondition true is returned if the list is empty false if not insert and erase void insert ElementType item int pos Insert a value into the list at a given position Precondition item is the value to be inserted there is room in the array mySize CAPACITY and the position satisfies 0 pos mySize Postcondition item has been inserted into the list at the position determined by pos provided there is room and pos is a legal position void erase int pos Remove a value from the list at a given position Precondition The list is not empty and the position satisfies 0 pos mySize Postcondition element at the position determined by pos has been removed provided pos is a legal position output void display ostream Display a list Precondition The ostream out is open Postcondition The list represented by this List object has been inserted into out private Data Members int mySize current size of list stored in myArray ElementType myArray CAPACITY array to store list elements end of List class template Prototype of output operator template ostream endif Chapter 9 99 Definition of class constructor template inline List List mySize 0 Definition of empty template inline bool List empty const return mySize 0 Definition of display template inline void List display ostream i mySize i out myArray i Definition of output operator template inline ostream return out Definition of insert template void List insert ElementType item int pos if mySize CAPACITY cerr No space for list element terminating execution n exit 1 if pos mySize cerr Illegal location to insert pos pos i myArray i myArray i 1 Now insert item at position pos and increase list size myArray pos item mySize Chapter 9 100 Definition of erase template void List erase int pos if mySize 0 cerr List is empty n return if pos mySize cerr Illegal location to delete pos List unchanged n return Shift array elements left to close the gap for int i pos i mySize i myArray i myArray i 1 Decrease list size mySize 8 QueueT h contains the declaration of class template Queue Basic operations Constructor Constructs an empty queue empty Checks if a queue is empty enqueue Modifies a queue by adding a value at the back front Accesses the front queue value leaves queue unchanged dequeue Modifies a queue by removing the value at the front display Displays the queue elements from front to back Class Invariant 1 The queue elements if any are stored in consecutive positions in myArray beginning at position myFront 2 0 myFront myBack QUEUE CAPACITY 3 Queue s size QUEUE CAPACITY include ifndef QUEUET define QUEUET const int QUEUE CAPACITY 128 template class Queue public Function Members Constructor Queue Construct a Queue object Precondition None Chapter 9 101 Postcondition An empty Queue object has been constructed myFront and myBack are initialized to 1 and myArray is an array with QUEUE CAPACITY elements of type QueueElement bool empty const Check if queue is empty Precondition None Postcondition True is returned if the queue is empty and false is returned otherwise void enqueue const QueueElement Add a value to a queue Precondition value is to be added to this queue Postcondition value is added to back of queue provided there is space otherwise a queue full message is displayed and execution is terminated void display ostream Output the values stored in the queue Precondition ostream out is open Postcondition Queue s contents from front to back have been output to out QueueElement front const Retrieve value at front of queue if any Precondition Queue is nonempty Postcondition Value at front of queue is returned unless queue is empty in that case an error message is displayed and a garbage value is returned void dequeue Remove value at front of queue if any Precondition Queue is nonempty Postcondition Value at front of queue has been removed unless queue is empty in that case an error message is displayed and execution is terminated private Data Members int myFront myBack QueueElement myArray QUEUE CAPACITY Chapter 9 102 end of class declaration Definition of Queue constructor template inline Queue Queue myFront 0 myBack 0 Definition of empty template inline bool Queue empty const return myFront myBack Definition of enqueue template void Queue enqueue const QueueElement if newBack myFront queue isn t full myArray myBack value myBack newBack else cerr Queue full can t add new value n Must increase value of QUEUE CAPACITY in Queue h n exit 1 Definition of display template inline void Queue display ostream i myBack i i 1 QUEUE CAPACITY out myArray i cout endl Definition of front template QueueElement Queue front const if empty return myArray myFront else cerr Queue is empty returning garbage value n QueueElement garbage return garbage Chapter 9 103 Definition of dequeue template void Queue dequeue if empty myFront myFront 1 QUEUE CAPACITY else cerr Queue is empty can t remove a value n exit 1 endif 9 CartesianPoint h ifndef CARTESIANPOINT define CARTESIANPOINT include using namespace std template class CartesianPoint public CartesianPoint CartesianPoint CoordType xVal CoordType yVal CoordType getX const CoordType getY const void setX CoordType xVal void setY CoordType yVal private CoordType myX myY template inline CartesianPoint CartesianPoint myX 0 myY 0 template inline CartesianPoint CartesianPoint CoordType xVal CoordType yVal myX xVal myY yVal template inline CoordType CartesianPoint getX const return myX Chapter 9 104 template inline CoordType CartesianPoint getY const return myY template inline void CartesianPoint setX CoordType xVal myX xVal template inline void CartesianPoint setY CoordType yVal myY yVal template inline ostream return out template inline istream CoordType x y in punc x punc y punc point setX x point setY y return in endif Exercises 9 4 1 number 0 0 number 1 0 number 2 1 number 3 1 number 4 2 number 5 2 number 6 3 number 7 3 number 8 4 number 9 4 2 w 0 0 w 1 0 w 2 0 w 3 0 w 4 0 w 5 0 w 6 0 w 7 0 w 8 0 w 9 0 w 10 0 w 11 0 w 12 1 w 13 1 w 14 2 w 15 2 3 number 0 99 number 1 33 number 2 44 number 3 88 number 4 22 number 5 11 number 6 55 number 7 66 number 8 77 4 number 0 0 number 1 1 number 2 2 number 3 3 number 4 0 number 5 1 number 6 2 number 7 3 number 8 4 number 9 5 5 number 0 33 number 1 33 number 2 88 number 3 88 number 4 11 number 5 11 number 6 66 number 7 66 number 8 77 6 number 0 99 number 1 33 number 2 44 number 3 88 number 4 22 number 5 11 number 6 55 number 7 66 number 8 99 Chapter 9 105 7 number 0 77 number 1 33 number 2 44 number 3 88 number 4 22 number 5 11 number 6 55 number 7 66 number 8 99 8 w 0 0 w 1 0 w 2 0 w 3 0 w 4 0 w 5 0 w 6 0 w 7 0 w 8 0 w 9 0 w 10 119 w 11 53 w 12 64 w 13 108 w 14 42 w 15 31 w 16 75 w 17 86 w 18 97 9 v 0 20 v 1 20 v 2 20 v 3 20 v 4 20 number 0 11 number 1 55 number 2 66 number 3 77 10 number0 22 number 1 11 number 2 55 number 3 66 number 4 77 11 w 0 0 w 1 0 w 2 0 w 3 0 w 4 0 w 5 0 w 6 0 w 7 0 w 8 0 w 9 0 w 10 100 w 11 34 w 12 45 w 13 89 w 14 23 w 15 12 w 16 56 w 17 67 w 18 78 12 vector v for int i 1 i 100 i v push back i 13 vector v for int i 99 i 0 i v push back i 14 vector v 50 for int i 0 i 50 i v i i 2 0 15 template bool ascend const vector index v index 1 return false return true 16 template operators T max v 0 Chapter 9 106 for int index 1 index v size index if v index max max v index return max min Exercises 9 6 Note In 1 8 Table is defined by typedef vector vector Table 1 include using namespace std double rowSum unsigned row const Table double sum 0 0 for int col 0 col aTable row size col sum aTable row col return sum 2 include using namespace std double columnSum unsigned row const Table double sum 0 0 for int row 0 row aTable size row sum aTable row col return sum Chapter 9 107 3 include using namespace std double rowAverage unsigned row const Table else cerr Row is empty returning 0 n return 0 4 include include using namespace std double rowStdDeviation unsigned row const Table for int j 0 j numValues j sum pow aTable row j mean 2 return sqrt sum numValues else cerr Row is empty returning 0 n return 0 Chapter 9 108 5 include using namespace std double columnAverage unsigned col const Table else cerr Column is empty returning 0 n return 0 6 include include using namespace std double columnStdDeviation unsigned col const Table for int i 0 i numValues i sum pow aTable i col mean 2 return sqrt sum numValues else cerr Column is empty returning 0 n return 0 Chapter 9 109 7 Matrix h include ifndef MATRIX define MATRIX class Matrix public Constructor of rows x cols matrix Matrix int rows 0 int cols 0 Input Output void read istream void display ostream Addition and multiplication Matrix operator const Matrix Matrix operator const Matrix private int myRows myCols vector vector myData endif Matrix cpp include include include using namespace std include Matrix h Definition of constructor Matrix Matrix int rows 0 int cols 0 vector vector temp rows vector cols 0 0 myData temp myRows rows myCols cols Definition of read void Matrix read cout myRows myCols cout Enter elements rowwise n double value Chapter 9 110 for int i 0 i myRows i vector aRow for int j 0 j value aRow push back value myData push back aRow Definition of display void Matrix display for int row 0 row myRows row for int col 0 col myCols col cout setw 6 myData row col cout endl Definition of operator Matrix Matrix operator const Matrix Matrix temp myRows myCols for int row 0 row myRows row for int col 0 col myCols col temp myData row col myData row col b myData row col return temp Definition of operator Matrix Matrix operator const Matrix Matrix temp myRows b myCols for int row 0 row myRows row for int col 0 col b myCols rc double sum 0 for int k 0 k myCols k sum myData row k b myData k col temp myData row col sum return temp Chapter 9 111 Exercises 9 8 Bitset Exercises These are solutions to the exercises in the supplementary material on bitsets on the Internet see http cs calvin edu books c ds 2e WebItems Chapter09 Bitsets pdf 1 01010101010101010101 2 00110101000101000101 3 00100000000000000000 4 01110101010101010101 5 01000000010000010000 6 11111111111111111111 7 00000000000000000000 8 001110000000 9 000000000000 10 000000001010 11 111111111111 12 include include using namespace std template class Set public Set Set union const Set Set intersection const Set Set complement void add int void remove int bool member int x bool subset const Set void display Chapter 9 112 private bitset myData int myCardinality Definition of Constructor template Set Set myData reset all bits set to 0 indicating empty set myCardinality 0 Definition of union template Set Set union const Set temp myData myData B myData temp myCardinality temp myData count