数据结构与算法分析 第8章 答案 Larry Nyhoff 清华大学.pdf
Chapter 8 71 Chapter 8:QueuesExercises 8.21.2.myFrontmyArraymyBack0 1 2 3 4qA B C A?14myFrontmyArraymyBack0 1 2 3 4qX Y Z?33 Queue is now empty3.4.myFrontmyArraymyBack0 1 2 3 4qs r q r r31myFrontmyArraymyBack0 1 2 3 4qC A A B B43Error occurs when i=4.After ch=A isinserted in location 2,myBack is 3 andmyFront is 4,which means the queue isfull,so the next enqueue()operationfails.5./*-DQueue.h-This header file defines a Queue data type.Basic operations:constructor:Constructs an empty queue copy constructor:Constructs a copy of a queue =:Assignment operator destructor:Destroys a queue empty:Checks if a queue is empty enqueue:Modifies a queue by adding a value at the back front:Accesses the top stack value;leaves queue unchanged dequeue:Modifies queue by removing the value at the front display:Displays all the queue elements-*/#include#ifndef DQUEUE#define DQUEUEtypedef int QueueElement;Chapter 8 72 class Queue public:/*Function members*/*Constructors*/Queue(int numElements=128);/*-Construct a Queue object.Precondition:None.Postcondition:An empty Queue object has been constructed (myFront and myBack are initialized to 0 and myArray is an array with numElements(default 128)elements of type QueueElement).-*/Queue(const Queue&original);/*-Copy Constructor Precondition:original is the queue to be copied and is received as a const reference parameter.Postcondition:A copy of original has been constructed.-*/*Destructor*/Queue();/*-Class destructor Precondition:None Postcondition:The dynamic array in the queue has been deallocated.-*/*Assignment*/const Queue&operator=(const Queue&rightHandSide);/*-Assignment Operator Precondition:original is the queue to be assigned and is received as a const reference parameter.Postcondition:The current queue becomes a copy of original and a const reference to it is returned.-*/bool empty()const;/*-Check if queue is empty.Precondition:None Postcondition:Returns true if queue is empty and false otherwise.-*/Chapter 8 73 void enqueue(const QueueElement&value);/*-Add a value to a queue.Precondition:value is to be added to this queue Postcondition:value is added at back of queue provided there is space;otherwise,a queue-full message is displayed and execution is terminated.-*/void display(ostream&out)const;/*-Display 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 front of queue(if any).Precondition:Queue is nonempty Postcondition:Value at front of queue is returned,unless the 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 the queue is empty;in that case,an error message is displayed and execution allowed to proceed.-*/private:/*Data members*/int myFront,/front myBack;/and back of queue int myCapacity;/capacity of queue QueueElement*myArray;/dynamic array to store elements;/empty slot used to distinguish /between empty and full;/end of class declaration#endif/*-DQueue.cpp-This file implements Stack member functions.Empty slot used to distinguish between empty and full-*/Chapter 8 74#include#include#include using namespace std;#include DQueue.h/-Definition of Queue constructorQueue:Queue(int numElements)assert(numElements 0);/check precondition myCapacity=numElements;/set queue capacity /allocate array of this capacity myArray=new(nothrow)QueueElementmyCapacity;if(myArray!=0)/memory available myFront=myBack=0;else cerr Inadequate memory to allocate queue n -terminating executionn;exit(1);/or assert(myArray!=0);/-Definition of Queue copy constructorQueue:Queue(const Queue&original):myCapacity(original.myCapacity),myFront(original.myFront),myBack(original.myBack)/-Get new array for copy myArray=new(nothrow)QueueElementmyCapacity;if(myArray!=0)/check if memory available /copy originals array member into this new array for(int i=myFront;i!=myBack;i=(i+1)%myCapacity)myArrayi=original.myArrayi;else cerr *Inadequate memory to allocate queue*n;exit(1);/-Definition of Queue destructorQueue:Queue()delete myArray;/-Definition of assignment operatorconst Queue&Queue:operator=(const Queue&rightHandSide)if(this!=&rightHandSide)/check that not st=st /-Allocate a new array if necessary if(myCapacity!=rightHandSide.myCapacity)delete myArray;/destroy previous array myCapacity=rightHandSide.myCapacity;/copy myCapacityChapter 8 75 myArray=new QueueElementmyCapacity;if(myArray=0)/check if memory available cerr *Inadequate memory*n;exit(1);myFront=rightHandSide.myFront;/copy myFront member myBack=rightHandSide.myBack;/copy myBack member /copy queue elements for(int i=myFront;i!=myBack;i=(i+1)%myCapacity)myArrayi=rightHandSide.myArrayi;return*this;/-Definition of empty()inline bool Queue:empty()const return myFront=myBack;/-Definition of enqueue()void Queue:enqueue(const QueueElement&item)if(myBack+1)%myCapacity=myFront)cerr Queue is full:cannot add to queue.Error!endl;else myArraymyBack=item;myBack=(myBack+1)%myCapacity;/-Definition of front()QueueElement Queue:front()const if(myFront=myBack)cerr Queue is empty:error!Returning garbage valuen;QueueElement garbage;return garbage;else return myArraymyFront;/-Definition of dequeue()void Queue:dequeue()if(myFront=myBack)cerr Queue is empty:cannot remove from queue:error!n;else myFront=(myFront+1)%myCapacity;Chapter 8 76 void Queue:display(ostream&out)const for(int i=myFront;i!=myBack;i=(i+1)%myCapacity)cout myArrayi ;cout myBack)return myBack-myFront+QUEUE_CAPACITY;else return myBack-myFront;8./Prototypeint size(Queue q);/*-Find number of elements in a queue received as a value parameter.Precondition:None Postcondition:Number of queue elements is returned.-*Chapter 8 77/Definitionint size(Queue q)int count=0;while(!q.empty()q.removeQ();count+;return count;/*Here is a version that preserves the parameter q.*/int size(Queue q)Queue temp;int count=0;while(!q.Empty()temp.addQ(q.front();q.removeQ();count+;while(!temp.empty()q.addQ(temp.front();temp.removeQ();return count;9./Prototype:QueueElement back()const;/*-Retrieve the back element of this queue.Precondition:None Postcondition:Back element of the queue is returned,unless there was none,in which case a queue-empty message is displayed.-*/Definition:QueueElement Queue:back()const if(myFront=myBack)cerr Error:queue is empty-returning garbage valuen;QueueElement garbage;return garbage;/else if(myBack=0)return myArrayQUEUE_CAPACITY-1;/else return myArraymyBack-1;Chapter 8 78 10./Prototype:QueueElement back();/*-Retrieve the back element of a queue received as a value parameter.Precondition:None Postcondition:Back element of the queue is returned,unless there was none,in which case a queue-empty message is displayed.-*/Definition:QueueElement back(Queue q)if(q.empty()cerr Error:queue is empty-returning garbage valuen;QueueElement garbage;return garbage;/else QueueElement last;while(!q.empty()last=q.front();q.dequeue();return last;/-Non-destructive version(preserves parameter q)QueueElement back(Queue q)const if(q.empty()cerr Error:queue is empty-returning garbage valuen;QueueElement garbage;return garbage;/else Queue temp;QueueElement last;while(!q.empty()last=q.front();temp.addQ(last);q.removeQ();while(!temp.empty()q.addQ(temp.front();temp.removeQ();return last;Chapter 8 79 11./Prototype:QueueElement nthElement(int n);/*-Retrieve the n-th element of a queue.Precondition:1=n 0&!empty()elem=front();removeQ();n-;if(n 0)cerr Error:insufficient number of elements in the queuen;-returning garbage valuen;QueueElement garbage;return garbage;/else return elem;12./Prototype:QueueElement nthElement(int n)const;/*-Retrieve the n-th element of a queue.Precondition:1=n=number of queue elements Postcondition:n-th element of the queue is returned,unless queue has fewer than n elements,in which case an error message is displayed.-*/Definition:QueueElement Queue:nthElement(int n)const if(myFront myBack&myBack-myFront myBack&QUEUE_CAPACITY-(myFront-myBack)n)cerr Error:insufficient number of elements in the queuen;-returning garbage valuen;QueueElement garbage;return garbage;Chapter 8 80 /else int index_n=(myFront+n-1)%QUEUE_CAPACITY;return myArrayindex_n;13.The algorithm is as follows:1.Create a stack.2.While the queue is not empty,do the following:a.Remove an item from the queue.b.Push this item onto the stack.3.While the stack is not empty,do the following:a.Pop an item from the stack.b.Add this item to the queue.14.(a)For n=3:Possible PermutationsImpossible Permutations123 132 213 231 312321=(b)For n=4:Possible PermutationsImpossible Permutations1234 1324 1342 142312432134 2143 2314 2341 241324313124 3142 34123214 3241 342141234132 4312 4321 4213 4231=(c)For n=5:Possible PermutationsImpossible Permutations12345 12354 12435 12453 125341254313245 13254 13425 13452 135241354214235 14253 1452314325 14352 145321523415243 15324 15342 15423 1543221345 21354 21435 21453 215342154323145 23154 23415 23451 235142354124135 24153 2451324315 24351 245312513425143 25314 25341 25413 2543131245 31254 31425 31452 315243154232145 32154 32415 32451 32514 3254134125 34152 3451234215 34251 345213512435142 35214 35241 35412 35421Chapter 8 81 41235 41253 4152341325 41352 4153242135 42153 42315 42351 42513 4253143125 43152 43215 43251 43512 435214512345132 45213 45231 45312 453215123451243 51324 51342 51423 5143252134 52143 52314 52341 52413 5243153124 53142 53214 53241 53412 5342154123 54132 54213 54231 54312 54321=(d)The rule is:for each digit d in the number,the digits to the right of d that are less than dMUST be in ascending order.15./*Implementation of Queue class.Count of elements used to distinguish between empty and full Add a data member:int myCount;to the private section of the Queue class declaration.*/#include using namespace std;Queue:Queue():myFront(0),myBack(0),myCount(0)bool Queue:empty()const return myCount=0;void Queue:enqueue(const QueueElement&value)if(myCount QUEUE_CAPACITY)myArraymyBack=value;myBack=(myBack+1)%QUEUE_CAPACITY;myCount+;else cerr 0)return myArraymyFront;else Chapter 8 82 cerr 0)myFront=(myFront+1)%QUEUE_CAPACITY;myCount-;else cerr *Queue is empty-cant remove a value*n;16./*Implementation of Queue class.Count of elements used to distinguish between empty and full.No data member myBack is used.Add a data member:int myCount;to the private section of the Queue class declaration and remove:int myBack;*/#include using namespace std;Queue:Queue():myFront(0),myCount(0)bool Queue:empty()const return myCount=0;void Queue:enqueue(const QueueElement&value)if(myCount QUEUE_CAPACITY)int back=(myFront+myCount)%QUEUE_CAPACITY;myArrayback=value;myCount+;else cerr 0)return myArraymyFront;Chapter 8 83 else cerr 0)myFront=(myFront+1)%QUEUE_CAPACITY;myCount-;else cerr *Queue is empty-cant remove a value*n;17./*Implementation of Queue class.Full data member used to distinguish between empty and full Add a data member:bool iAmFull;to the private section of the Queue class declaration.*/#include using namespace std;Queue:Queue():myFront(0),myCount(0),iAmFull(false)bool Queue:empty()const return(myBack=myFront&!iAmFull);void Queue:enqueue(const QueueElement&item)if(!iAmFull)myArraymyBack=item;myBack=(myBack+1)%QUEUE_CAPACITY;iAmFull=(myBack=myFront);else cerr *Queue full-cant add new value*n Must increase value of QUEUE_CAPACITY in Queue.hn;exit(1);Chapter 8 84 QueueElement Queue:front()if(!empty()return myArraymyFront;else cerr *Queue is empty-returning garbage value*n;QueueElement garbage;return garbage;void Queue:dequeue()if(!empty()myFront=(myFront+1)%QUEUE_CAPACITY;iAmFull=false;else cerr Queue is empty:cannot remove from queue.Error!endl;18.This is similar to the use of one buffer for two stacks(Exer.12 in 7.2):If two queues wereto be stored in one array with the front of each being at the ends of the array,then the queuescould grow until the backs met in the middle.Then,one of the queues would have to beshifted back to its end.If each queue size is fixed,wraparound within each queue could beemployed to avoid shifting elements.Exercises 8.31.2.3.myFrontmyBackBCAmyFrontmyBackrrsmyFrontmyBackChapter 8 85 4.5./Prototype:QueueElement back()const;/*-Retrieve the back element of this queue.Precondition:None Postcondition:Back element of the queue is returned,unless there was none,in which case a queue-empty message is displayed.-*/Definition:QueueElement Queue:back()const if(myBack!=0)return*myArray;/else cerr Error:queue is empty-returning garbage valuen;QueueElement garbage;return garbage;6./Prototype:QueueElement nthElement(int n);/*-Retrieve the n-th element of a queue.Precondition:1=n 0&!empty()elem=front();removeQ();n-;if(n 0)cerr Error:insufficient number of elements in the queuen;-returning garbage valuen;QueueElement garbage;return garbage;myFrontmyBackBCABChapter 8 86 /else return elem;7./Prototype:QueueElement nthElement(int n)const;/*-Retrieve the n-th element of a queue.Precondition:1=n=number of queue elements Postcondition:n-th element of the queue is returned,unless queue has fewer than n elements,in which case an error message is displayed.-*/Definition:QueueElement Queue:nthElement(int n)const int count=0;Queue:NodePonter ptr=myFront;for(int count=0;count next;if(ptr!=0)return*ptr;/else cerr Error:insufficient number of elements in the queuen;-returning garbage valuen;QueueElement garbage;return garbage;8./*-CLQueue.h-This header file defines a Queue data type.Basic operations:constructor:Constructs an empty queue copy constructor:Constructs a copy of a queue =:Assignment operator destructor:Destroys a queue empty:Checks if a queue is empty enqueue:Modifies a queue by adding a value at the back front:Accesses the top stack value;leaves queue unchanged dequeue:Modifies queue by removing the value at the front display:Displays all the queue elements A circular linked list is used to store the queue elements.-*/Chapter 8 87#ifndef CLQUEUE#define CLQUEUE#include typedef int QueueElement;class Queue private:class Node public:/-DATA MEMBERS OF Node QueueElement data;Node*next;/-Node OPERATIONS /*-The Node default class constructor initializes a Nodes next member.Precondition:None Postcondition:The next member has been set to 0.-*/Node():next(0)/*-The Node class constructor initializes a Nodes data members.Precondition:None Postcondition:The data and next members have been set to dataValue and 0,respectively.-*/Node(DequeElement dataValue):data(dataValue),next(0);/-end of Node class typedef Node*NodePointer;public:/*Function members*/*Constructors*/Queue();/*-Construct a Queue object.Precondition:None.Postcondition:An empty Queue object has been constructed (myBack is initialized to 0).-*/Chapter 8 88 Queue(const Queue&original);/*-Copy Constructor Precondition:original is the queue to be copied and is received as a const reference parameter.Postcondition:A copy of original has been constructed.-*/*Destructor*/Queue()
