数据结构答案第4章队列学习指导

24第4章队列4.1知识点分析1．队列的基本概念（1）队列是一种特殊的、只能在表的两端进行插入或删除操作的线性表。允许插入元素的一端称为队尾，允许删除元素的一端称为队首。（2）队列的逻辑结构和线性表相同，其最大特点是“先进先出”。（3）队列的存储结构有顺序队列和链队列之分，要求掌握队列的C语言描述方法。（4）重点掌握在顺序队列和链队列上实现：进队、出队、读队头元素、显示队列元素、判队空和判队满等基本操作。（5）熟悉队列在计算机软件设计中的典型应用，能灵活应用队列的基本原理解决一些实际应用问题。2．顺序队列（1）顺序队列用内存中一组连续的存储单元顺序存放队列中各元素，一般用一维数组作为队列的顺序存储空间。除了队列的数据以外，一般还设有队首和队尾两个指针。typedefstruct{datatypeQ[MAXLEN]；intfront=–1,rear=–1；//定义队头、队尾指针，并置队列为空}Queue；（2）顺序队列缺点是存在“假溢出”现象。3．循环队列（1）为了解决顺序队列中的“假溢出”现象，把数组想象成一个首尾相连的环，即队首的元素Q[0]与队尾的元素Q[MAXLEN–1]连接起来，存储在其中的队列称为循环队列。（2）一般规定：当front==rear，表示循环队列为空；当front==（rear+1）%MAXLEN，表示循环队列为满。（3）在定义结构体时，附设一个存储循环队列中元素个数的变量n，当n==0时表示队空；当n==MAXLEN时为队满。循环队列的结构体类型定义：typedefstruct{datatypedata[MAXLEN]；intfront，rear；intn；//用以记录循环队列中元素的个数}csequeue；//循环队列变量名（4）入队操作时：p-rear=(p-rear+1)%MAXLEN；出队操作时：p-front=(p-front+1)%MAXLEN；4．链队列（1）队列的链式存储结构称为链队列（或链队）。链首结点为队头，链尾结点为队尾。（2）链队列的描述：typedefstructqueuenode{datatypedata;structqueuenode*next;}queuenode;//链队结点的类型datatypetypedefstruct{queuenode*front,*rear;}linkqueue;//将头指针、尾指针封装在一起的链队如下图25（3）若队头指针为Q-front，队尾指针为Q-rear，则队头元素的引用为Q-front-data，队尾元素的引用为Q-rear-data。（4）初始时置Q-front=Q-rear=NULL。（5）入队操作，与链表中链尾插入操作一样；出队操作，与链表中链首删除操作一样。（6）队空标志为Q-front==NULL；对于链队列而言，一般不会出现队满。4.2典型习题分析【例1】线性表、栈、队列有什么异同？分析：n个（同类）数据元素的有限序列称为线性表。线性表的特点是数据元素之间存在“一对一”的关系。栈和队列都是操作受限制的线性表，它们和线性表的相同之处是数据元素之间都存在“一对一”的关系。不同之处是：线性表允许在表中任意位置进行插入或删除操作。栈是只允许在一端（栈顶）进行插入或删除操作的线性表，其最大的特点是“后进先出”；队列是只允许在一端（队尾）进行插入，另一端（队首）进行删除操作的线性表，其最大的特点是“先进先出”。【例2】队列Q，经过下列运算后，x的值是（）。InitQueue(Q)；//初始化队列InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);InQueue(Q,c);OutQueue(Q,x);ReadFront(Q,x);A．aB．bC．cD．1分析：经过三次入队和两次出队运算以后，队中只有一个元素，即c，最后执行读队头元素运算时，输出到x的值就是c，所以选答案C。【例3】设栈s和队列q初态都为空，元素a、b、c、d、e、f依次进栈，元素出栈后即进入队列，若6个元素出队的序列是b、d、c、f、e、a，则要求栈S的容量至少能存多少个元素？分析：队列操作的原则是“先进先出”，按照题意出队的顺序应该是b、d、c、f、e、a，所以入队的顺序也是b、d、c、f、e、a。栈的操作原则是“后进先出”，要得到b、d、c、f、e、a的出栈次序，必须进行如图4-1所示的操作过程。由此可见栈的空间至少为3。a、b进栈b出栈c、d进栈d、c出栈e、f进栈f、e、a出栈dfbceaaa图4-1进栈出栈过程【例4】循环队列存储在数组A[0..MAXLEN-1]中，设front指向队头，rear指向实际队尾的下一个元素的位置，写出通过队头、队尾指针表示的队列长度Qlen的公式。分析：当rear=front时，队列长度：Qlen=rear-front；当rearfront时，队列长度：Qlen=MAXLEN+(rear-front)。上述两种情况可以统一为：Qlen=(MAXLEN+(rear-front))%MAXLEN。【例5】循环队列存储在数组A[0..MAXLEN-1]中，如果只设rear指向队尾的实际位置，Qlen表示队列的长度，则队头元素的位置front将如何表示？26分析：当rear=front时，front=rear-Qlen+1；当rearfront时，front=MAXLEN+rear-Qlen+1。综合上述两种情况，队头元素的位置front可以统一为：front=（MAXLEN+rear-Qlen+1）%MAXLEN。【例6】单元练习4填空题（18）：设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有front=11，rear=19，则循环队列中还有个元素。答案：(N＋rear－front)%N=（40＋19－11）%40=8【例7】设队列q1中已有数据，指出下述程序段的功能。Cirqueueq1,q2;//Datatype为int型intx,i,n=0;Initqueue(&q2);//初始化队列q2While(!Qempty(&q1)){x=OutQueue(&q1);InQueue(&q2,x);n++;}for(i=0;in;i++){x=OutQueue(&q2);InQueue(&q1,x);InQueue(&q2,x);}分析：本程序段第一个循环是通过出队将队列q1的内容复制到队列q2，但此时队列q1已为空，n记录了队列中元素的个数；第二个循环是将队列q2的内容通过出队，将内容同时复制到队列q1和队列q2。答：本程序段的功能是将队列q1的内容复制到队列q2，且q1的内容不变。【例8】单元练习4的第四题：写出程序运行的结果（队列中的元素类型为char）。voidmain(){QueueQ;InitQueue(Q);//初始化队列charx=E;y=C;InQueue(Q,H);InQueue(Q,R);InQueue(Q,y);OutQueue(Q,x);InQueue(Q,x);OutQueue(Q,x);InQueue(Q,A);while(!QEmpty(Q)){OutQueue(Q,y);printf(y);};27printf(x);}分析：本题主要是分清变量的内容进队，还是字符直接进队，以下是进队、出队的一些主要步骤如图4-2所示。CHARRCCHHHHHRRCCx=Hx=R图4-2进队、出队过程执行循环语句输出：CHA；执行printf(x)语句输出变量x的值：R。最后的输出结果是：CHAR。【例9】勒让德多项式如下：1(当n=0)Pn(x)=x(当n=1)((2n-1)Pn-1(x)-(n-1)Pn-2(x))/n(当n)1)试写出它的递归和非递归算法。递归算法如下：floatlrd(floatx,intn){if(n==0)return1;elseif(n==1)returnx;elsereturn(2*n-1)*lrd(x,n-1)-(n-1)*lrd(x,n-2))/n;}非递归算法如下：floatlrd(floatx,intn){floata,b,t,p,s;inti;if(n==0)t=1;else{t=x;s=x;p=1;}for(i=2;i=n;i++){28a=2*i-1;b=i-1;t=(a*s-b*p)/i;p=s;s=t;}returnt;}【例10】已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列中所有元素逆置。分析：先将顺序队列q中所有元素出队并依次进入顺序栈s中，然后出栈并依次入队。设队列中的初始元素序列为：a1，a2，…，an，出队并进栈的次序也是：a1，a2，…，an，出栈并入队的序列为：an，an-1，…，a1，则此时顺序队列q中的元素已逆置了。算法如下：#defineMAXLEN100typedefstruct{intdata[MAXLEN];intfront,rear;}Quere;voidinvert(Quere*q){ints[MAXLEN],top=0;//初始化栈swhile(q-frontq-rear)//q中所有元素出队并依次进入顺序栈s中s[top++]=q-data[++q-front];q-front=-1;//置队空q-rear=0;while(top0)//出栈并依次入队，实现逆置q-data[q-rear++]=s[--top];}4.3单元练习4解答一．判断题答案题目12345678910答案√√×√×√××××二．填空题答案（1）先进先出（2）队列（3）队尾（4）队首（或队头）（5）空（6）满（7）-1（8）循环队列（9）front==rear（10）NULL（11）O(n)（12）O(1)29（13）空（14）front==(rear+1)%MAXLEN（15）front==rear&&front!NULL（16）队尾指针（17）不改变（或不影响）（18）8（19）0（20）a三．选择题答案题目12345678910答案DBACBAABCD题目11121314151617181920答案BBBBAACACB四．答案输出为:CHAR，（分析过程见典型习题分析【例8】）。五．程序填空答案（1）newqu（2）x（3）rear-next（4）s（5）rear-next六.算法设计题答案（1）分析：用一个循环数组Queue[0..n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。【入队程序代码】voidinqueqe(intx){inttemp;if(count==n)printf(队列上溢出\n);else{count++temp=(front+count)%n;Queue[temp]=x}}【出队程序代码】intoutqueue(){inttemp;if(count==0)printf(队列下溢出\n);else{temp=Queue[front];front=(front+1)%n;count--;returntemp;}}（2）分析：队列为空：count==0队列为满：count=MAXLEN队尾第一个元素位置==(front+count)%MAXLEN队首第一个元素位置==(front+1)%MAXLENconstMAXLEN=100;intqueue[MAXLEN];30intfront,count;//定义队头和计数器count【初始化队列程序代码】voidinit(){front=1;count=0;}【判定队空程序代码】intQEmpty(){if(count==0)return(1);elsereturn(0);}【读队头元素程序代码】voidReadFront(intqueue[],x){if(count==0)printf(下溢出\n);else{front=(front+1)%MAXLEN;x=queue[front];}}【入队程序代