数据结构习题.pptx

《数据结构习题.pptx》由会员分享，可在线阅读，更多相关《数据结构习题.pptx（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第1页/共24页23.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=idata=x;s-next=null；r-next=s；r=s；第19页/共24页201、利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。第20页/共24页21栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。（1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出

2、队列元素），则不能入队。（2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。（3）判队空 若栈s1为空并且s2也为空，才是队列空。第21页/共24页22讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。在栈s2不空情况

3、下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。第22页/共24页23习题集24页3.17Int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串，是则返回1，否则返回0.InitStack(s);While(e=getchar()!=&)If(e=)return 0;/不允许在&之前出现 Push(s,e);while(e=getchar()!=)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;If(!StackEmpty(s)return 0;Return 1;)/IsReverse第23页/共24页数据结构24感谢您的观看！第24页/共24页