《第3章栈和队列 作业(参考答案).doc》由会员分享，可在线阅读，更多相关《第3章栈和队列 作业(参考答案).doc（6页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列 作业1、若按教材P44页图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列 ）。123、132、213、231、321输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出
2、栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。2、试证明：若借助栈由输入序列1、2n得到的输出序列为p1、p2pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，ijk使pjpkpi 如果ij，则对于pipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于ijk，不可能出现pjpkdata=x; s-next=rear-next; /将s结点链入队尾 rear-next=s; rear=s; /rear指向新队尾（2）void DeQueue (LinkedList rear) / rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。 if (rear-next=rear) printf(“队空n”); exit(0); s=rear-next-next; /s指向队头元素， rear-next-next=s-next; /队头元素出队。 printf (“出队元素是”，s-data); if (s=rear) rear=rear-next; /空队列 free(s);
