《数据结构习题学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构习题学习教案.pptx（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)习题习题第一页，共24页。2第1页/共24页第二页，共24页。33.3.一个一个一个一个(y(y )栈的输入序列为栈的输入序列为栈的输入序列为栈的输入序列为123n123n，若输出序列的，若输出序列的，若输出序列的，若输出序列的第一个第一个第一个第一个(y(y )元素是元素是元素是元素是n n，输出第，输出第，输出第，输出第i i（1=i=n1=idata=x;s-next=null；r-next=s；r=s；第19页/共24页第二十页，共24页。211、利用两个栈、利用两个栈sl,s2模拟一个队列时，模拟一个队列时，如何用栈的运算实现队列的插如何
2、用栈的运算实现队列的插入，删除以及判队空运算。请入，删除以及判队空运算。请简述简述(jin sh)这些运算的算法这些运算的算法思想。思想。第20页/共24页第二十一页，共24页。22栈的特点是后进先出，队列的特点是先进先出。初始栈的特点是后进先出，队列的特点是先进先出。初始栈的特点是后进先出，队列的特点是先进先出。初始栈的特点是后进先出，队列的特点是先进先出。初始时设栈时设栈时设栈时设栈s1s1和栈和栈和栈和栈s2s2均为空。均为空。均为空。均为空。（1 1）用栈）用栈）用栈）用栈s1s1和和和和s2s2模拟一个队列的输入：设模拟一个队列的输入：设模拟一个队列的输入：设模拟一个队列的输入：设s
3、1s1和和和和s2s2容量容量容量容量相等。分以下三种情况相等。分以下三种情况相等。分以下三种情况相等。分以下三种情况(qngkung)(qngkung)讨论：若讨论：若讨论：若讨论：若s1s1未未未未满，则元素入满，则元素入满，则元素入满，则元素入s1s1栈；若栈；若栈；若栈；若s1s1满，满，满，满，s2s2空，则将空，则将空，则将空，则将s1s1全部元全部元全部元全部元素退栈，再压栈入素退栈，再压栈入素退栈，再压栈入素退栈，再压栈入s2s2，之后元素入，之后元素入，之后元素入，之后元素入s1s1栈；若栈；若栈；若栈；若s1s1满，满，满，满，s2s2不空（已有出队列元素），则不能入队。不
4、空（已有出队列元素），则不能入队。不空（已有出队列元素），则不能入队。不空（已有出队列元素），则不能入队。（2 2）用栈）用栈）用栈）用栈s1s1和和和和s2s2模拟队列出队（删除）：若栈模拟队列出队（删除）：若栈模拟队列出队（删除）：若栈模拟队列出队（删除）：若栈s2s2不空，不空，不空，不空，退栈，即是队列的出队；若退栈，即是队列的出队；若退栈，即是队列的出队；若退栈，即是队列的出队；若s2s2为空且为空且为空且为空且s1s1不空，则不空，则不空，则不空，则将将将将s1s1栈中全部元素退栈，并依次压入栈中全部元素退栈，并依次压入栈中全部元素退栈，并依次压入栈中全部元素退栈，并依次压入s2s
5、2中，中，中，中，s2s2栈顶栈顶栈顶栈顶元素退栈，这就是相当于队列的出队。若栈元素退栈，这就是相当于队列的出队。若栈元素退栈，这就是相当于队列的出队。若栈元素退栈，这就是相当于队列的出队。若栈s1s1为为为为空并且空并且空并且空并且s2s2也为空，队列空，不能出队。也为空，队列空，不能出队。也为空，队列空，不能出队。也为空，队列空，不能出队。（3 3）判队空）判队空）判队空）判队空 若栈若栈若栈若栈s1s1为空并且为空并且为空并且为空并且s2s2也为空，才是队列空。也为空，才是队列空。也为空，才是队列空。也为空，才是队列空。第21页/共24页第二十二页，共24页。23讨论：讨论：讨论：讨论：
6、s1s1和和和和s2s2容量之和是队列的最大容量。其操作是，容量之和是队列的最大容量。其操作是，容量之和是队列的最大容量。其操作是，容量之和是队列的最大容量。其操作是，s1s1栈满后，栈满后，栈满后，栈满后，全部退栈并压栈入全部退栈并压栈入全部退栈并压栈入全部退栈并压栈入s2s2（设（设（设（设s1s1和和和和s2s2容量相等）。再入栈容量相等）。再入栈容量相等）。再入栈容量相等）。再入栈s1s1直直直直至至至至s1s1满。这相当队列元素满。这相当队列元素满。这相当队列元素满。这相当队列元素“入队入队入队入队”完毕。出队时，完毕。出队时，完毕。出队时，完毕。出队时，s2s2退栈退栈退栈退栈完毕
7、后，完毕后，完毕后，完毕后，s1s1栈中元素依次退栈到栈中元素依次退栈到栈中元素依次退栈到栈中元素依次退栈到s2s2，s2s2退栈完毕，相当于退栈完毕，相当于退栈完毕，相当于退栈完毕，相当于队列中全部元素出队。队列中全部元素出队。队列中全部元素出队。队列中全部元素出队。在栈在栈在栈在栈s2s2不空情况下，若要求入队操作，只要不空情况下，若要求入队操作，只要不空情况下，若要求入队操作，只要不空情况下，若要求入队操作，只要s1s1不满，就可压不满，就可压不满，就可压不满，就可压入入入入s1s1中。若中。若中。若中。若s1s1满和满和满和满和s2s2不空状态下要求队列的入队时，按出不空状态下要求队列
8、的入队时，按出不空状态下要求队列的入队时，按出不空状态下要求队列的入队时，按出错错错错(ch cu)(ch cu)处理。处理。处理。处理。第22页/共24页第二十三页，共24页。24习题集习题集习题集习题集2424页页页页3.17Int IsReverse()/3.17Int IsReverse()/判断输入的字符串中判断输入的字符串中判断输入的字符串中判断输入的字符串中&前和前和前和前和&后部后部后部后部分是否为逆串，是则返回分是否为逆串，是则返回分是否为逆串，是则返回分是否为逆串，是则返回(f(f nhu)1nhu)1，否则返回，否则返回，否则返回，否则返回(f(f nhu)0.nhu)0
9、.InitStack(s);InitStack(s);While(e=getchar()!=&)While(e=getchar()!=&)If(e=)return 0;/If(e=)return 0;/不允许在不允许在不允许在不允许在&之前出现之前出现之前出现之前出现 Push(s,e);Push(s,e);while(e=getchar()!=)while(e=getchar()!=)if(StackEmpty(s)return 0;if(StackEmpty(s)return 0;pop(s,c);pop(s,c);if(e!=c)return 0;if(e!=c)return 0;If(!StackEmpty(s)return 0;If(!StackEmpty(s)return 0;Return 1;)Return 1;)/IsReverse/IsReverse第23页/共24页第二十四页，共24页。