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

《数据结构与算法分析 第9章 答案 Larry Nyhoff 清华大学.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析 第9章 答案 Larry Nyhoff 清华大学.pdf（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,DataType c)DataType ma

2、x=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 length,DataType&min,DataType&max)min=max=x0;for(i

3、nt 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./*-ListT.h-This header file defines the data type List for processing lists.Basic operations are:C

4、onstructor 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 class List public:/*Function Members*/*Class constructor*/List();/*-Construct a List object.Precondition:No

5、ne 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);/*-In

6、sert 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 le

7、gal 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(ostr

8、eam&out)const;/*-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 myArrayCAPACITY;/array to store list elements;/-end of List

9、 class template/-Prototype of output operatortemplate ostream&operator(ostream&out,const List&aList);#endifChapter 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

10、 inline void List:display(ostream&out)const for(int i=0;i mySize;i+)out myArrayi ;/-Definition 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)c

11、err *No space for list element-terminating execution*n;exit(1);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=

12、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+)myArrayi=myArrayi+1;/Decrease list size mySize-;8./*QueueT.h contains the declaration of class template Queue.Basic operati

13、ons: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

14、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.Queues size QUEUE_CAPACITY-*/#include#ifndef QUEUET#define QUEUETconst int QUEUE_CAPACITY=128;template class Queue public:/*Function Membe

15、rs*/*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 e

16、mpty.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 back of queue provided there is space;otherw

17、ise,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 to out.-*/QueueElement front()const;/*-Retrieve value at fro

18、nt 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.Postconditi

19、on: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 myArrayQUEUE_CAPACITY;Chapter 9 102;/end of class declaration/-Definition of Queue constructortemplate i

20、nline 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&value)int newBack=(myBack+1)%QUEUE_CAPACITY;if(newBack!=myFront)/queue isnt full myArraymyBack=value;m

21、yBack=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:display(ostream&out)const for(int i=myFront;i!=myBack;i=(i+1)%QUEUE_CAPACITY)out myArrayi ;cout endl;/-Definition of front()template

22、QueueElement Queue:front()const if(!empty()return(myArraymyFront);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-cant re

23、move a value*n;exit(1);#endif9./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

24、(CoordType yVal);private:CoordType myX,myY;templateinline 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 CoordTy

25、pe 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&operator(ostream&out,const CartesianPoint&point)out (point.getX(),point.getY();return out;template inline

26、 istream&operator(istream&in,CartesianPoint&point)char punc;CoordType 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 w

27、9=0 w10=0 w11=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 number2=88 number3=88 number4=11number5

28、=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 number6=55 number7=66 number8=998.w0=0 w1=0 w2=0 w3=0 w4=0w5=0 w6=0 w7=0 w8=0 w9=0w1

29、0=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 number1=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 w1

30、8=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(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

31、vector&v)T min=v0;T max=v0;Chapter 9 106 for(int index=1;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

32、row in a Table object.Receive:row,a 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 r

33、ow,const Table&aTable)/*-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;return su

34、m;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)return rowSum(row,

35、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 aTable,a Table object Return:the

36、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:n;return 0;Chapter 9 108 5.#include using namespace std;doubl

37、e 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-*/assert(col 0)return ColumnSum(col,aTable)/numValues;/else cerr Column i

38、s 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.Receive:col,a column index and aTable,a Table object Return:the standard deviation of the

39、 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+)sum+=pow(aTableicol-mean,2);return sqrt(sum/numValues);/else cerr Column is empty-returning 0:n;return 0;Chapter

40、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(istream&in);void display(ostream&out);/-Addition and multiplication Matrix operator+(const Matrix&b);Matrix operator*(const Matrix&b);p

41、rivate:int myRows,myCols;vectorvector myData;#endif/-Matrix.cpp#include#include#include using namespace std;#include Matrix.h/-Definition of constructorMatrix: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:re

42、ad()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)m

43、yDatarowcol;cout endl;/-Definition of operator+()Matrix Matrix:operator+(const Matrix&b)assert(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*()

44、Matrix Matrix:operator*(const Matrix&b)assert(myCols=b.myRows);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 ExercisesThes

45、e 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.010101010101010101012.001101010001010001013.001000000000000000004.011101010101010101015.010000000100000100006.111111111111111111117.000000

46、000000000000008.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 display

47、();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.myCardinality=temp.myData.cou

48、nt();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=myData.flip();temp.myCardinality=temp.myData.co

49、unt();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,0);/-Definition of subset()templatebool Set:subset(const

50、 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 supplementary material on valarrays on the Internet(see http:/cs.calvin.edu/books/c+/ds