ch3顺序队列作业.doc

第3章 顺序队列习题13.113.243.34第3章 顺序队列习题3.1用一个数组、头指针和元素个数合在一起所构成的结构来存储顺序队列，设计算法以实现队列的各运算。解：【结构定义和算法描述】/这是一个变形的普通顺序队列结构/数据成员中取消了尾指针rear成员，增加了一个元素个数count成员/定义相关符号#define MaxLen 10typedef int elementType;/顺序队列类描述class Queuepublic:Queue(); /初始化队列bool empty(); /判断队空bool full(); /判断队满 bool getFront(elementType &x); /取队头元素bool enQueue(elementType x); /入队 bool outQueue(); /出队void print(); /打印队列元素（队头到队尾） private:elementType dataMaxLen; /存放队列元素int front; /队头指针int count; /元素个数;/-/1. 初始化顺序队列Queue:Queue()front=-1; /初始化空队列count=0; /队列元素个数为0/-/2. 判队空bool Queue:empty()if(count=0)return true; /队空，返回trueelsereturn false;/-/3. 判队满-存在假溢出bool Queue:full()if( count=MaxLen )return true; /真正队满 else if(front=MaxLen-1)coutendl;return true;elsereturn false;/-/4. 取队头元素bool Queue:getFront(elementType &x)if(count=0)return false; /队空，取队头失败，返回falseelsex=datafront+1; /队头元素取到变量x。front指示的下一个单元才是队头元素 return true; /取队头成功，返回true /-/5. 入队（插入）bool Queue:enQueue(elementType x)if(full()return false; /队满，入队失败，返回falseelse datacount=x; /插入元素count+;return true; /插入成功，返回true。/-/6. 出对（删除）bool Queue:outQueue()if(count=0)return false; /队空，出队失败，返回falseelsefront+; /队头指针后移一个单元，元素并未真正删除count-;return true; /出队成功，返回true/-/7. 打印队列元素（从队头到队尾）void Queue:print()int i;if(empty()cout空队列！endl;elsecout队中元素：;for(i=front+1; i=front+count; i+)coutdatait;coutendl;/打印队中元素个数cout队中元素个数 count=countendl; cout当前队头指针 front=frontendl;3.2对教材中所讨论的循环队列及其约定，给出求解队列中元素个数的表达式。解：设循环队列为Q，数组最大长度为MaxLen，头指针和尾指针分别为front和rear元素个数=(rear-front+MaxLen) % MaxLen3.3如果对循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。解：【结构定义和算法描述】/这是一种特殊的循环顺序队列结构，用标志tag帮助判定队空和队满/定义相关符号#define MaxLen 10typedef int elementType;/-/顺序循环队列类描述class Queuepublic:Queue(); /初始化队列bool empty(); /判断队空bool full(); /判断队满 bool getFront(elementType &x); /取队头元素bool enQueue(elementType x); /入队 bool outQueue(); /出队void print(); /打印队列元素（队头到队尾） private:elementType dataMaxLen; /存放队列元素int front; /队头指针int rear; /队尾指针int tag; /tag=1 & front=rear队满；tag=0 & front=rear队空 ;/-/1. 初始化顺序队列Queue:Queue()front=0; /初始化空队列rear=0;tag=0; /初始化置队空标志 /-/2. 判队空bool Queue:empty()if(front=rear & tag=0)return true; /队空，返回trueelsereturn false;/-/3. 判队满bool Queue:full()if( front=rear & tag=1 )return true; /队满 elsereturn false;/-/4. 取队头元素bool Queue:getFront(elementType &x)if(empty()return false; /队空，取队头失败，返回falseelsex=data(front+1)%MaxLen; /队头元素取到变量x。front指示的下一个单元才是队头元素 /为何要取模呢？return true; /取队头成功，返回true /-/5. 入队（插入）bool Queue:enQueue(elementType x)if(full()return false; /队满，入队失败，返回falseelserear=(rear+1)%MaxLen; /队尾指针后移一个单元，为何做摸运算 datarear=x; /插入元素tag=1; /置插入标志 return true; /插入成功，返回true。/-/6. 出队（删除）bool Queue:outQueue()if(empty()return false; /队空，出队失败，返回falseelsefront=(front+1)%MaxLen; /队头指针后移一个单元，元素并未真正删除tag=0; /置删除标志 return true; /出队成功，返回true/-/7. 打印队列元素（从队头到队尾）void Queue:print()int i;if(empty()cout空队列！endl;elsecout队中元素：;i=(front+1)%MaxLen;while(i!=rear)coutdatait;i=(i+1)%MaxLen;coutd