资源描述：
《数据结构第3章 栈和队列习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、习题课第3章栈和队列3.1(1)123,132,213,231,321(2)435612不能得到（6出站时，12必须在站中，只能出站成21，无法得到12）135426可以1S1X2S3S3X4S5S5X4X2X6S6X（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?（2）如果进站的车厢序列为123456，则能否得到435612和135426出站序列，并请说明为什么不能得到或如何得到。3.4简述以下算法的功能分析：while循环将栈中数据依次出栈到A数组for循环将数组A中元素依次入栈结果：将堆栈中的元素逆序（1）statusalgol(Sta
2、ckS){intI,n,A[255];n=0;while(!Stackempty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}3.4简述以下算法的功能分析：第一个while循环：将S栈中不等于e的元素放入T栈。最后S为空栈第二个while循环：将T栈中元素出栈到S栈结果：将堆栈S中不等于e的元素逆序（2）statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}
3、while(!Stackempty(T)){Pop(T,d);Push(S,d);}}3.12写出以下程序段的输出结果分析：[队列]xy1.[h]ec2.[hr]ec3.[hrc]ec4.[rc]hc5.[rch]hc6.[ch]rc7.[cha]rc结果：charVoidmain(){QueueQ;InitQueue(Q);charx=‘e’,y=‘c’;EnQueue(Q,’h’);//1EnQueue(Q,’r’);//2EnQueue(Q,y);//3DeQueue(Q,x);//4Enqueue(Q,x);//5DeQueue(Q,x);//6EnQ
4、ueue(Q,’a’);//7while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);}3.14以1234作为双端队列的输入序列，分别求出满足以下条件的输出序列解：可能的组合（24种）1234，1243，1324，1342，1423，1432，2134，2143，2314，2341，2413，2431，3124，3142，3214，3241，3412，3421，4123，4132，4213，4231，4312，4321输入受限不能得到:42134231输出受限不能得到:41324231都不能得到:4231
5、(1)4213(2)4132(3)4231（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列3.16n节硬席或软席车厢调度成软席在硬席之前HSSHS=>SSSHH思路：判断每节车厢，如果是H的只入栈，如果是S则入栈后出栈InitStack(T);while(入口有车厢e){if(e==‘H’)push(T,e);else{push(T,e);pop(T,e);}}While(!Empty
6、Stack(T))pop(T,e);3.28带头指针的循环链表表示队列，并且只设一个指针指向队尾结点，编写队列初始化、入队列和出队列算法typedefstructQNode{QElemTypedata;StructQnode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&T){//构造一个带表头结点的只有一个尾指针的空队列TT.rear=(QueuePtr)malloc(sizeof(QNode);if(!T.rear)return“E
7、RROR”;T->next=T;returnOK;}3.28带头指针的循环链表表示队列，并且只设一个指针指向队尾结点，编写队列初始化、入队列和出队列算法StatusEnQueue(LinkQueue&T,QElemTypee){//插入元素e为队列T的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=T.rear->next;T.rear->next=p;T.rear=p;returnOK:}//EnQueue3.28带头指针的循环链表表示队列，并且只设
8、一个指针指向队尾结点，编写队列初始化、
