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

Chapter 6 26 Chapter 6:ListsExercises 6.31-6./-Polynomial.h-#include#ifndef POLYNOMIAL#define POLYNOMIALconst int MAX_DEGREE=100;typedef double CoefType;class Polynomial public:void read(istream&in);void display(ostream&out)const;Polynomial operator+(const Polynomial&poly);Polynomial operator*(const Polynomial&poly);CoefType evaluate(double value);private:int myDegree;CoefType myCoeffMAX_DEGREE+1;istream&operator(istream&in,Polynomial&p);ostream&operator(ostream&out,const Polynomial&p);#endif/-Polynomial.cpp-#include#include using namespace std;#include Polynomial.h/-Definition of istream&operator(istream&in,Polynomial&p)p.read(in);return in;/-Definition of read()void Polynomial:read(istream&in)cout Enter the degree(=MAX_DEGREE myDegree;/the degree of this polynomial assert(myDegree=MAX_DEGREE);Chapter 6 27 CoefType co;/the coefficients in ascending order cout Enter coefficients in ascending order:n;for(int index=0;index co;myCoeffindex=co;/-Definition of ostream&operator(ostream&out,const Polynomial&p)p.display(out);return out;/-Definition of display()void Polynomial:display(ostream&out)const for(int index=0;index myDegree;index+)out myCoeffindex x index +;out myCoeffmyDegree x myDegree endl;/-Definition of evaluate()CoefType Polynomial:evaluate(CoefType value)CoefType power=1,result=0;for(int index=0;index=myDegree;index+)result+=myCoeffindex*power;power*=value;return result;/-Definition of+Polynomial Polynomial:operator+(const Polynomial&b)Polynomial c;if(myDegree b.myDegree)c=b;for(int i=0;i=myDegree;i+)c.myCoeffi+=myCoeffi;c.myDegree=b.myDegree;else c=*this;Chapter 6 28 for(int i=0;i=b.myDegree;i+)c.myCoeffi+=b.myCoeffi;while(c.myCoeffc.myDegree=0)c.myDegree-;return c;/-Definition of*Polynomial Polynomial:operator*(const Polynomial&b)Polynomial c;c.myDegree=myDegree+b.myDegree;for(int i=0;i=c.myDegree;i+)c.myCoeffi=0;for(int i=0;i=myDegree;i+)for(int j=0;j data and ptr-next refer to the data part andthe next part,respectively,of the node pointed to by ptr.1.Algorithm to count the nodes in a linked listcount=0;ptr=first;while(ptr!=null_value)count+;ptr=ptr-next;2.Algorithm to compute average value in a linked list of real numberstotal=0.0;count=0;ptr=first;while(ptr!=null_value)count+;total+=ptr-data;ptr=ptr-next;Chapter 6 29 if(count=0)average=0.0;else average=total/count;3.Algorithm to append a node at the end of a linked listGet a node pointed to by newPtr;newPtr-data=item;if(first=null_value)first=newPtr;newPtr-next=null_valueelse ptr=first;while(ptr-next!=null_value)ptr=ptr-next;newPtr-next=ptr;4.Algorithm to determine if the nodes in a linked list are in non-decreasing order.ptr=first;if(ptr=null_value|/note short-circuit eval newPtr-next=null_value)return true;else nextPtr=ptr-next;for(;)if(nextPtr=null_value)return true;if(ptr-data nextPtr-data)return false;/else ptr=nextPtr;nextPtr=nextPtr-next;5.All algorithms in exercises#1-#4 require a scan of the entire linked list.Hence,they areO(n).Chapter 6 30 6.Algorithm to search a linked list for a given item.ptr=first;prevPtr=null_valuefor(;)if(ptr=null_value)return null_value;if(ptr-data=item)return prevPtr;/else prevPtr=ptr;ptr=ptr-next;7.Algorithm to insert a node pointed to by newPtr after the nth node.ptr=first;num=1;Get a node pointed to by newPtr;if(n=0)newPtr-next=ptr;first=newPtr;else while(ptr!=null_value&num next;if(ptr!=null_value)newPtr-next=ptr-next;ptr=newPtr;else Signal error:fewer than n elements in list8.Algorithm to delete the nth node in a linked list.ptr=first;num=1;if(n=1)tempPtr=ptr;first=ptr-next;delete tempPtr;Chapter 6 31 else while(ptr!=null_value&num next;if(ptr!=null_value&/note short-circuit eval ptr-next!=null_value)tempPtr=ptr-next;ptr-next=temPtr-next;Delete node pointed to by tempPtr;else Signal error:fewer than n elements in list9.Algorithm to perform a shuffle-merge of two linked listsGet a node pointed to by mergePtr;/temporary head nodelast=mergePtr;ptr1=first1;/runs through first listptr2=first2;/runs through second listwhile(ptr1!=null_value&ptr2!=null_value)Get a node pointed to by tempPtr;tempPtr-data=ptr1-data;last-next=tempPtr;last=tempPtr;ptr1=ptr1-next;Get a node pointed to by tempPtr;tempPtr-data=ptr2-data;last-next=tempPtr;last=tempPtr;ptr2=ptr2-next;while(ptr1!=null_value)Get a node pointed to by tempPtr;tempPtr-data=ptr1-data;last-next=tempPtr;last=tempPtr;ptr1=ptr1-next;Chapter 6 32 while(ptr2!=null_value)Get a node pointed to by tempPtr;tempPtr-data=ptr2-data;last-next=tempPtr;last=tempPtr;ptr2=ptr2-next;/Delete temporary headnodetempPtr=mergePtr;mergePtr=mergePtr-next;Delete tempPtr;10.Algorithm to perform a shuffle-merge without copyingif(first1=null_value)mergePtr=first2;else mergePtr=first1;ptr1=first1;/runs through first list ptr2=first2;/runs through second list while(ptr1!=null_value&ptr2!=null_value)tempPtr=ptr1;ptr1=tempPtr-next;tempPtr-next=ptr2;if(ptr2!=null_value)tempPtr=ptr2;ptr2=tempPtr-next;tempPtr-next=ptr1;if(ptr1=null_value)tempPtr-next=ptr2;11.Algorithm to merge two non-decreasing listsGet a node pointed to by mergePtr;/temporary head nodelast=mergePtr;ptr1=first1;ptr2=first2;while(ptr1!=null_value&ptr2!=null_value)Get a node pointed to by tempPtr;Chapter 6 33 if(ptr1-data data);tempptr-data=ptr1-data;last-next=tempPtr;last=tempptr;ptr1=ptr1-next;else tempptr-data=ptr2-data;last-next=tempptr;last=tempptr;ptr2=ptr2-next;while(ptr1!=null_value)Get a node pointed to by tempPtr;tempptr-data=ptr1-data;last-next=tempptr;last=tempptr;ptr1=ptr1-next;while(ptr2!=null_value)Get a node pointed to by tempPtr;tempptr-data=ptr2-data;last-next=tempptr;last=tempptr;ptr2=ptr2-next;tempptr=mergePtr;mergePtr=mergePtr-next;/Delete temporary headnodeDelete node pointed to by tempptr;12.Algorithm to reverse a linked list without copying.currentPtr=first;prevPtr=null_value;while(currentPtr!=null_value)nextPtr=currentPtr-next;currentPtr-next=prevPtr;prevPtr=currentPtr;currentPtr=nextPtr;first=prevPtr;Chapter 6 34 Exercises 6.51.123 4562.34 343.34 344.Error because the next field of p2 is a null pointer5.12 343434346.111 2222221117.34 34348.9.10.11.p4-next is a null pointer,so an error occurs when we attempt to access its data part.p1=p2CatDogEweRatp2=p2p3=p2p4=p2p4=p2CatDogEweRatp1=p2p2=p2p3=p2CatDogEweRatp2=p2p3=p2p4=p2p1=p2Chapter 6 35 12.13.14.15.16.17.CatDogEweRatp2=p2p3=p2p4=p2p1=p2CatDogEweRatp2=p2p3=p2p4=p2p1=p2CatDogEweRatp2=p2p3=p2p4=p2p1=p2p1=p2CatDogEweRatp2=p2p3=p2p4=p2CatDogEweRatp2=p2p3=p2p4=p2p1=p2CatDogEweRatp2=p2p3=p2p4=p2p1=p2Chapter 6 36 18-21./-List.h-#ifndef LINKEDLIST#define LINKEDLIST#include using namespace std;typedef int ElementType;class Listprivate:class Node public:/-Node DATA MEMBERS ElementType data;Node*next;/-Node OPERATIONS /-Default constrctor:initializes next member to Node():next(0)/-Explicit-value constructor:initializes data member to dataValue /-and next member to 0 Node(ElementType dataValue):data(dataValue),next(0);/-end of Node class typedef Node*NodePointer;public:/-List OPERATIONS List();/*-Default constructor:builds an empty List object.Precondition:None Postcondition:first is 0 and mySize is 0.-*/List(const List&origList);/*-Copy constructor Precondition:A copy of origList is needed.Postcondition:A distincr copy of origList has been constructed.-*/Chapter 6 37 List();/*-Destructor Precondition:This lists lifetime is over.Postcondition:This list has been destroyed.-*/const List&operator=(const List&rightSide);/*-Assignment operator Precondition:This list must be assigned a value.Postcondition:A copy of rightSide has been assigned to this list.-*/bool List:empty();/*-Check if this list is empty Precondition:None.Postcondition:true is returned if this list is empty,false if not.-*/void insert(ElementType dataVal,int index);/*-Insert a value into a list at a given index.Precondition:index is a valid list index:0=index=mySize,Postcondition:dataVal has been inserted into the list at position index,provided index is valid.-*/void erase(int index);/*-Remove a value from a list at a given index.Precondition:index is a valid list index:0=index mySize Postcondition:dataVal at list position index has been removed,provided index is valid.-*/int search(ElementType dataVal);/*-Search for an data value in this list.Precondition:None Postcondition:Index of node containing dataVal is returned if such a node is found,-1r if not.-*/Chapter 6 38 void display(ostream&out)const;/*-Display the contensts of this list.Precondition:ostream out is open Postcondition:Elements of this list have been output to out.-*/int nodeCount();/*-Count the elements of this list.Precondition:None Postcondition:Number of elements in this list is returned.-*/void reverse();/*-Reverse this list.Precondition:None Postcondition:Elements in this list have been reversed.-*/bool ascendingOrder();/*-Check if the elements of this list are in ascending order.Precondition:None Postcondition:true is returned if the list elements are in ascending order,false if not.-*/private:/-DATA MEMBERS NodePointer first;int mySize;/-end of List classostream&operator(istream&in,List&aList);#endif/-List.cpp-#include using namespace std;#include List.h/-Definition of the class constructorList:List():first(0),mySize(0)Chapter 6 39/-Definition of the copy constructorList:List(const List&origList)mySize=origList.mySize;first=0;if(mySize=0)return;List:NodePointer origPtr,lastPtr;first=new Node(origList.first-data);/copy first node lastPtr=first;origPtr=origList.first-next;while(origPtr!=0)lastPtr-next=new Node(origPtr-data);origPtr=origPtr-next;lastPtr=lastPtr-next;/-Definition of the destructorinline List:List()List:NodePointer prev=first,ptr;while(prev!=0)ptr=prev-next;delete prev;prev=ptr;/Definition of empty()bool List:empty()return mySize=0;/-Definition of the assignment operatorconst List&List:operator=(const List&rightSide)mySize=rightSide.mySize;first=0;if(mySize=0)return*this;if(this!=&rightSide)this-List();List:NodePointer origPtr,lastPtr;first=new Node(rightSide.first-data);/copy first node lastPtr=first;origPtr=rightSide.first-next;Chapter 6 40 while(origPtr!=0)lastPtr-next=new Node(origPtr-data);origPtr=origPtr-next;lastPtr=lastPtr-next;return*this;/-Definition of insert()void List:insert(ElementType dataVal,int index)if(index mySize)cerr Illegal location to insert-index next=first;first=newPtr;else for(int i=1;i next;newPtr-next=predPtr-next;predPtr-next=newPtr;/-Definition of erase()void List:erase(int index)if(index=mySize)cerr Illegal location to delete-index next;delete ptr;Chapter 6 41 else for(int i=1;i next;ptr=predPtr-next;predPtr-next=ptr-next;delete ptr;/-Definition of search()int List:search(ElementType dataVal)int loc;List:NodePointer tempP=first;for(loc=0;loc data=dataVal)return loc;else tempP=tempP-next;return-1;/-Definition of display()void List:display(ostream&out)const List:NodePointer ptr=first;while(ptr!=0)out data next;/-Definition of the output operatorostream&operatornext;return count;Chapter 6 42/-Definition of reverse()void List:reverse()NodePointer prevP=0,currentP=first,nextP;while(currentP!=0)nextP=currentP-next;currentP-next=prevP;prevP=currentP;currentP=nextP;first=prevP;/new head of(reversed)linked list/-Definition of ascendingOrder()bool List:ascendingOrder()if(mySize next;while(tempP!=0&prevP-data data)prevP=tempP;tempP=tempP-next;if(tempP!=0)return false;/else return true;Exercises 6.61.a.List:B,C,J,Pb.Storage pool:M,Z,K,Q,?,?2.first=4;free=1nodedatanext0J31Z62C53P-14B25F06K77Q88?99?-1Chapter 6 43 3.first=4;free=0nodedatanext0J51Z62C33P-14B25M16K77Q88?99?-14.first=-1;free=4nodedatanext0J51Z62C33P04B25M16K77Q88?99?-15.first=5,free=2nodedatanext0J31Z72C13K-14B05A46K87Q98?109?0NOTE:The following are definitions of function members in a List class whose data memberis a pointer first to the first node in the linked list.Chapter 6 44 6./*Find number of nodes in linked list*/int List:nodeCount()int count=0;int ptr=first;while(ptr!=NULL_VALUE)count+;ptr=nodeptr.next;return count;7./*Check if list in ascending order*/bool List:ascendingOrder()if(numNodes()=1)/empty or one element list return true;/else int prevP=first,tempP=nodefirst.next;while(tempP!=NULL_VALUE&nodeprevP.data=nodetempP.data)prevP=tempP;tempP=nodetempP.next;if(tempP!=NULL_VALUE)return false;/else return true;8./*Find last node*/int List:lastNode()int currentPtr=first,lastPtr=first;while(currentPtr!=NULL_VALUE)lastPtr=currentPtr;currentPtr=nodecurrentPtr.next;return lastPtr;Chapter 6 45 9./*Reverse the linked list*/void List:reverse()int prev=NULL_VALUE,currentP=first,nextP;while(currentP!=NULL_VALUE)nextP=nodecurrentP.next;nodecurrentP.next=prev;prev=currentP;currentP=nextP;first=prev;