ch3顺序队列作业

PAGE16ch3顺序队列作业

第3章顺序队列习题

1

3.1 13.2 43.3 4第3章顺序队列习题3.1用一个数组、头指针和元素个数合在一起所构成的结构来存储顺序队列，设计算法以实现队列的各运算。解：【结构定义和算法描述】//这是一个变形的普通顺序队列结构//数据成员中取消了尾指针rear成员，增加了一个元素个数count成员//定义相关符号#defineMaxLen10typedefintelementType;//顺序队列类描述classQueue{public: Queue();//初始化队列 boolempty();//判断队空 boolfull();//判断队满 boolgetFront(elementType&x);//取队头元素 boolenQueue(elementTypex);//入队 booloutQueue();//出队 voidprint();//打印队列元素（队头到队尾） private: elementTypedata[MaxLen];//存放队列元素 intfront;//队头指针 intcount;//元素个数};////1.初始化顺序队列Queue::Queue(){ front=-1;//初始化空队列 count=0;//队列元素个数为0}////2.判队空boolQueue::empty(){ if(count==0) returntrue;//队空，返回true else returnfalse;}////3.判队满--存在假溢出boolQueue::full(){ if(count==MaxLen) returntrue;//真正队满 elseif(front==MaxLen-1) { cout<<"<--假溢出-->"<<endl; returntrue; } else returnfalse;}////4.取队头元素boolQueue::getFront(elementType&x){ if(count==0) returnfalse;//队空，取队头失败，返回false else { x=data[front+1];//队头元素取到变量x。front指示的下一个单元才是队头元素 returntrue;//取队头成功，返回true }}////5.入队（插入）boolQueue::enQueue(elementTypex){ if(full()) returnfalse;//队满，入队失败，返回false else { data[count]=x;//插入元素 count++; returntrue;//插入成功，返回true。 }}////6.出对（删除）boolQueue::outQueue(){ if(count==0) returnfalse;//队空，出队失败，返回false else { front++;//队头指针后移一个单元，元素并未真正删除 count--; returntrue;//出队成功，返回true }}////7.打印队列元素（从队头到队尾）voidQueue::print(){ inti; if(empty()) cout<<"空队列！"<<endl; else { cout<<"队中元素："; for(i=front+1;i<=front+count;i++) { cout<<data[i]<<"\t"; } } cout<<endl; //打印队中元素个数 cout<<"队中元素个数count="<<count<<endl; cout<<"当前队头指针front="<<front<<endl; }3.2对教材中所讨论的循环队列及其约定，给出求解队列中元素个数的表达式。解：设循环队列为Q，数组最大长度为MaxLen，头指针和尾指针分别为front和rear元素个数=(rear-front+MaxLen)%MaxLen3.3如果对循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。解：【结构定义和算法描述】//这是一种特殊的循环顺序队列结构，用标志tag帮助判定队空和队满//定义相关符号#defineMaxLen10typedefintelementType;////顺序循环队列类描述classQueue{public: Queue();//初始化队列 boolempty();//判断队空 boolfull();//判断队满 boolgetFront(elementType&x);//取队头元素 boolenQueue(elementTypex);//入队 booloutQueue();//出队 voidprint();//打印队列元素（队头到队尾） private: elementTypedata[MaxLen];//存放队列元素 intfront;//队头指针 intrear;//队尾指针 inttag;//tag==1&&front==rear队满；tag==0&&front==rear队空};////1.初始化顺序队列Queue::Queue(){ front=0;//初始化空队列 rear=0; tag=0;//初始化置队空标志}////2.判队空boolQueue::empty(){ if(front==rear&&tag==0) returntrue;//队空，返回true else returnfalse;}////3.判队满boolQueue::full(){ if(front==rear&&tag==1) returntrue;//队满 else returnfalse;}////4.取队头元素boolQueue::getFront(elementType&x){ if(empty()) returnfalse;//队空，取队头失败，返回false else { x=data[(front+1)%MaxLen];//队头元素取到变量x。front指示的下一个单元才是队头元素 //为何要取模呢？ returntrue;//取队头成功，返回true }}////5.入队（插入）boolQueue::enQueue(elementTypex){ if(full()) returnfalse;//队满，入队失败，返回false else { rear=(rear+1)%MaxLen;//队尾指针后移一个单元，为何做摸运算 data[rear]=x;//插入元素 tag=1;//置插入标志 returntrue;//插入成功，返回true。 }}////6.出队（删除）boolQueue::outQueue(){ if(empty()) returnfalse;//队空，出队失败，返回false else { front=(front+1)%MaxLen;//队头指针后移一个单元，元素并未真正删除 tag=0;//置删除标志 returntrue;//出队成功，返回true }}////7.打印队列元素（从队头到队尾）voidQueue::print(){ inti; if(empty()) cout<<"空队列！"<<endl; else { cout<<"队中元素："; i=(front+1)%MaxLen; while(i!=rear) { cout<<data[i]<<"\t"; i=(i+