《数据结构与算法分析 第9章 答案 Larry Nyhoff 清华大学》由会员分享，可在线阅读，更多相关《数据结构与算法分析 第9章 答案 Larry Nyhoff 清华大学（19页珍藏版）》请在金锄头文库上搜索。
1、Chapter 9 96 Chapter 9: ADT Implementations: Templates and Standard ContainersExercises 9.31. 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, Data
2、Type 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 = x0; for (int index = 1; index length; index+) sum += xindex; return sum;Chapter 9 97 5. template void arrayMaxMin(DataType x, int l
3、ength, DataType & min, DataType & max) min = max = x0; for (int i = 1; i length; i+) if (xi max) max = xi; 6. template int search(DataType x, int length, DataType target) for (int index = 0; index length; index+) if (xindex = target) return index; return -1; / index of -1 denotes not found7. /*- Lis
4、tT.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 LISTTconst int CAPACITY = 1024;template cla
5、ss 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 Pos
6、tcondition: 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 sat
7、isfies 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 sat
8、isfies 0 = pos mySize. Postcondition: element at the position determined by pos has been removed (provided pos is a legal position). -*/ /* output */ void display(ostream & out) const; /*- Display a list. Precondition: The ostream out is open. Postcondition: The list represented by this List object
9、has been inserted into out. -*/ private: /* Data Members */ int mySize; / current size of list stored in myArray ElementType myArrayCAPACITY; / array to store list elements; /- end of List class template/- Prototype of output operatortemplate ostream & operator (ostream & out, const List & aList);#e
10、ndifChapter 9 99 /- Definition of class constructortemplate 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 & out) const for (int i = 0; i mySize; i+) out myArrayi ;/- D
11、efinition of output operatortemplate inline ostream & operator(ostream & out, const List & aList) aList.display(out); 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);
12、if (pos mySize) cerr * Illegal location to insert - pos pos; i-) myArrayi = myArrayi - 1; / Now insert item at position pos and increase list size myArraypos = item; mySize+;Chapter 9 100 /- Definition of erase()template void List:erase(int pos) if (mySize = 0) cerr * List is empty *n; return; if (p
13、os = 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+) myArrayi = myArrayi + 1; / Decrease list size mySize-;8. /* QueueT.h contains the declaration of class template Queue. Basic operations: Constr
14、uctor: 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 bac
15、k 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. Queues size QUEUE_CAPACITY-*/#include #ifndef QUEUET#define QUEUETconst int QUEUE_CAPACITY = 128;template class Queue public: /* F
16、unction 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()
17、 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 & value); /*- Add a value to a queue. Precondition: value is to be added to this queue. Postcondition: value is added to
18、 back of queue provided there is space; otherwise, a queue-full message is displayed and execution is terminated. -*/ void display(ostream & out) const; /*- Output the values stored in the queue. Precondition: ostream out is open. Postcondition: Queues contents, from front to back, have been output
19、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(); /*- Remo
20、ve 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 myArrayQUEU
21、E_CAPACITY;Chapter 9 102 ; / end of class declaration/- Definition of Queue constructortemplate 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 QueueEleme
22、nt & value) int newBack = (myBack + 1) % QUEUE_CAPACITY; if (newBack != myFront) / queue isnt full myArraymyBack = value; myBack = newBack; else cerr * Queue full - cant add new value *n Must increase value of QUEUE_CAPACITY in Queue.hn; exit(1); /- Definition of display()template inline void Queue:
23、display(ostream & out) const for (int i = myFront; i != myBack; i = (i + 1)%QUEUE_CAPACITY) out myArrayi ; cout endl;/- Definition of front()template QueueElement Queue:front() const if ( !empty() ) return (myArraymyFront); else cerr * Queue is empty - returning garbage value *n; QueueElement garbag
24、e; return garbage; Chapter 9 103 /- Definition of dequeue()template void Queue:dequeue() if ( !empty() ) myFront = (myFront + 1) % QUEUE_CAPACITY; else cerr * Queue is empty - cant remove a value *n; exit(1); #endif9. /CartesianPoint.h#ifndef CARTESIANPOINT#define CARTESIANPOINT#include using namesp
25、ace 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;templateinline CartesianPoint:CartesianPoint(): myX(0), my
26、Y(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
27、xVal) myX = xVal; template inline void CartesianPoint:setY(CoordType yVal) myY = yVal; template inline ostream & operator(ostream & out, const CartesianPoint & point) out ( point.getX() , point.getY() ); return out;template inline istream & operator(istream & in, CartesianPoint & point) char punc; C
28、oordType x, y; in punc x punc y punc; point.setX(x); point.setY(y); return in;#endifExercises 9.41.number0 = 0 number1 = 0 number2 = 1 number3 = 1 number4 = 2number5 = 2 number6 = 3 number7 = 3 number8 = 4 number9 = 42.w0 = 0 w1 = 0 w2 = 0 w3 = 0 w4 = 0w5 = 0 w6 = 0 w7 = 0 w8 = 0 w9 = 0 w10 = 0 w11
29、= 0 w12 = 1 w13 = 1 w14 = 2w15 = 23.number0 = 99 number1 = 33 number2 = 44 number3 = 88 number4 = 22number5 = 11 number6 = 55 number7 = 66 number8 = 774.number0 = 0 number1 = 1 number2 = 2 number3 = 3 number4 = 0number5 = 1 number6 = 2 number7 = 3 number8 = 4 number9 = 55.number0 = 33 number1 = 33 n
30、umber2 = 88 number3 = 88 number4 = 11number5 = 11 number6 = 66 number7 = 66 number8 = 776.number0 = 99 number1 = 33 number2 = 44 number3 = 88 number4 = 22number5 = 11 number6 = 55 number7 = 66 number8 = 99Chapter 9 105 7.number0 = 77 number1 = 33 number2 = 44 number3 = 88 number4 = 22number5 = 11 nu
31、mber6 = 55 number7 = 66 number8 = 998.w0 = 0 w1 = 0 w2 = 0 w3 = 0 w4 = 0w5 = 0 w6 = 0 w7 = 0 w8 = 0 w9 = 0w10 = 119 w11 = 53 w12 = 64 w13 = 108 w14 = 42w15 = 31 w16 = 75 w17 = 86 w18 = 979.v0 = 20 v1 = 20 v2 = 20 v3 = 20 v4 = 20number0 = 11 number1 = 55 number2 = 66 number3 = 7710.number0 = 22 numbe
32、r1 = 11 number2 = 55 number3 = 66number4 = 7711.w0 = 0 w1 = 0 w2 = 0 w3 = 0 w4 = 0w5 = 0 w6 = 0 w7 = 0 w8 = 0 w9 = 0w10 = 100 w11 = 34 w12 = 45 w13 = 89 w14 = 23w15 = 12 w16 = 56 w17 = 67 w18 = 7812.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(
33、i);14.vector v(50);for (int i = 0; i 50; i+) vi = (i % 2 = 0);15.template bool ascend(const vector & v) for (int index = 0; index = vindex+1) return false; return true;16.template /operators = & - must be defined for TT range(const vector & v) T min = v0; T max = v0;Chapter 9 106 for (int index = 1;
34、 index v.size(); index+) if (vindex max) max = vindex; return max - min;Exercises 9.6Note: In #1-8, Table is defined by: typedef vector vector Table;1.#include using namespace std;double rowSum(unsigned row, const Table & aTable)/*- Sum the elements of a given row in a Table object. Receive: row, a
35、row index and aTable, a Table object Return: the sum of the elements in the row-th row of aTable -*/ assert(row aTable.size(); double sum = 0.0; for (int col = 0; col aTablerow.size(); col+) sum += aTablerowcol; return sum;2.#include using namespace std;double columnSum(unsigned row, const Table & a
36、Table)/*- Sum the elements of a given column in a Table object. Receive: col, a column index and aTable, a Table object Return: the sum of the elements in the col-th column of aTable -*/ assert(col aTable0.size(); double sum = 0.0; for (int row = 0; row aTable.size(); row+) sum += aTablerowcol; retu
37、rn sum;Chapter 9 107 3.#include using namespace std;double rowAverage(unsigned row, const Table & aTable)/*- Average the elements of a given row in a Table object. Receive: row, a row index and aTable, a Table object Return: the average of the elements in the row-th row of aTable -*/ assert(row 0) r
38、eturn rowSum(row, aTable) / numValues ; /else cerr Row is empty - returning 0:n; return 0;4.#include #include using namespace std;double rowStdDeviation(unsigned row, const Table & aTable)/*- Find the standard deviation of the elements of a given row in a Table object. Receive: row, a row index and
39、aTable, a Table object Return: the standard deviation of the elements in the row-th row of aTable -*/ assert(row 0) double mean = rowAverage(row, aTable), sum = 0.0; for (int j = 0; j numValues; j+) sum += pow(aTablerowj - mean, 2); return sqrt(sum / numValues); /else cerr Row is empty - returning 0
40、:n; return 0;Chapter 9 108 5.#include using namespace std;double columnAverage(unsigned col, const Table & aTable)/*- Average the elements of a given column in a Table object. Receive: col, a column index and aTable, a Table object Return: the average of the elements in the col-th column of aTable -
41、*/ assert(col 0) return ColumnSum(col, aTable) / numValues; /else cerr Column is empty - returning 0:n; return 0;6.#include #include using namespace std;double columnStdDeviation(unsigned col, const Table & aTable)/*- Find the standard deviation of the elements of a given column in a Table object. R
42、eceive: col, a column index and aTable, a Table object Return: the standard deviation of the elements in the col-th column of aTable -*/double columnStdDeviation(unsigned col, const Table & aTable) assert(col 0) double mean = columnAverage(row, aTable), sum = 0.0; for (int i = 0; i numValues; i+) su
43、m += pow(aTableicol - 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 MATRIXclass Matrix public: /- Constructor of rows x cols matrix Matrix(int rows = 0, int cols = 0); /- Input/Output void read(
44、istream & in); void display(ostream & out); /- Addition and multiplication Matrix operator+(const Matrix & b); Matrix operator*(const Matrix & b); private: int myRows, myCols; vectorvector myData;#endif/ - Matrix.cpp#include #include #include using namespace std;#include Matrix.h/- Definition of con
45、structorMatrix:Matrix(int rows = 0, int cols = 0) vectorvector 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;
46、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) myDatarowcol; cout endl; /- Definition of operator+()Matrix Matrix:operator+(const Matrix& b) a
47、ssert(myRows = b.myRows & myCols = b.myCols); Matrix temp(myRows, myCols); for (int row = 0; row myRows; row+) for (int col = 0; col myCols; col+) temp.myDatarowcol = myDatarowcol + b.myDatarowcol; return temp;/- Definition of operator*()Matrix Matrix:operator*(const Matrix & b) assert(myCols = b.my
48、Rows); 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 += myDatarowk * b.myDatakcol; temp.myDatarowcol = sum; return temp;Chapter 9 111 Exercises 9.8Bitset ExercisesThese are solutions to the ex
49、ercises in the supplementary material on bitsets on the Internet( see http:/cs.calvin.edu/books/c+/ds/2e/WebItems/Chapter09/Bitsets.pdf )1. 010101010101010101012. 001101010001010001013. 001000000000000000004. 011101010101010101015. 010000000100000100006. 111111111111111111117. 000000000000000000008.
50、 0011100000009. 00000000000010. 00000000101011. 11111111111112. #include #include using namespace std;templateclass Set public: Set(); Set union(const Set & B); Set intersection(const Set & B); Set complement(); void add(int); void remove(int); bool member(int x); bool subset(const Set & B); void di
51、splay();Chapter 9 112 private: bitset myData; int myCardinality;/- Definition of ConstructortemplateSet:Set() myData.reset(); / all bits set to 0, indicating empty set myCardinality = 0;/- Definition of union()templateSet Set:union(const Set & B) Set temp; temp.myData = myData | B.myData; temp.myCar
52、dinality = temp.myData.count(); return temp;/- Definition of intersection()templateSet Set:intersection(const Set & B) Set temp; temp.myData = myData & B.myData; temp.myCardinality = temp.myData.count(); return temp;/- Definition of complement()templateSet Set:complement() Set temp; temp.myData = my
53、Data.flip(); temp.myCardinality = temp.myData.count(); return temp;/- Definition of member()templatebool Set:member(int x) return myData.test(x-1);/- Definition of add()templatevoid Set:add(int x) myData.set(x-1, 1);Chapter 9 113 /- Definition of remove()templatevoid Set:remove(int x) myData.set(x-1
54、, 0);/- Definition of subset()templatebool Set:subset(const Set & B) return (myData & B.myData) = myData;/- Definition of display()templatevoid Set:display() for (int i = 0; i myData.size(); i+) if (myDatai) cout i + 1 ; cout endl;Valarray ExercisesThese are solutions to the exercises in the supplem
55、entary material on valarrays on the Internet( see http:/cs.calvin.edu/books/c+/ds/2e/WebItems/Chapter09/Valarrays.pdf )1.#include using namespace std;void display(const valarray & data) for (int index = 0; index data.size(); index+) cout dataindex ; cout endl;2.#include using namespace std;void read
56、(valarray & data) cout Input your data.size() real numbers: endl; for (int index = 0; index dataindex;Chapter 9 114 3.#include #include using namespace std;double magnitude(const valarray & data) double sum = 0.0; for (int index = 0; index data.size(); index+) sum += dataindex* dataindex; return sqrt(sum);4.#include using namespace std;double dotProduct(const valarray & a, const valarray & b) double sum = 0.0; for (int index = 0; index a.size(); index+) sum += aindex* bindex; return sum;
