数据结构及应用算法教程（修订版） 第4章栈和队列习题.ppt

《数据结构及应用算法教程（修订版） 第4章栈和队列习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章栈和队列习题本章要点回顾:1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们;2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法;3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法;4.理解递归算法执行过程中栈的状态变化过程。习题4.1（1）123、132、213、231、321（2）435612出站序列不可能，因4356先出栈说明12已在栈中，则1不可能在某些2之前出栈；135426出站序列可以：1S、1X、2S、3S、3X、4S、5S、5X、4X、2X、6S、6X习题4.2（1）利用辅助数组A将栈S中

2、的数据元素逆置；（2）利用辅助栈T将栈S中所有等于e的元素删除。习题4.3voidTrain_arrange(char*&train)//这里用字符串train表示火车,‘H’表示硬席,‘S’表示软席{ p=train;q=train;InitStack(s);  while(*p)  {   if(*p==‘H’)Push(s,*p);//把‘H’存入栈中else*(q++)=*p;//把‘S’调到前部p++;  }while(!StackEmpty(s))  {Pop(s,c);    *(q++)=c;//把‘H’接在后部}}//Train_arrange习

3、题4.4#include"sqstack.h"voidmain(){SqStackS;InitStack(S);SElemTypee;chara[80];cout<<"放入一个以@为结束符的字符序列";cin>>a;inti=0;while(a[i]!='&'&&a[i]!='@'){Push(S,a[i]);i++;}if(a[i]=='&')i++;while(a[i]!='@'&&!StackEmpty(S)){Pop(S,e);if(e!=a[i])break;i++;}if(a[i]=='@'&&StackEmpty(S))cout<<"属于序列1&序列2的字符

4、序列";elsecout<<"不属于序列1&序列2的字符序列";}习题4.5StatusBracket_Test(char*str)//判别表达式中小括号是否匹配{ count=0;for(p=str;*p;p++)  {if(*p==‘(’)count++;    elseif(*p==‘)’)count--;    if(count<0)returnERROR;  }if(count)returnERROR;//注意括号不匹配的两种情况returnOK;}//Bracket_Test习题4.6T=16W={2,5,8,3,4,6}210531050510

5、5404105304310543052042032032153155154541534315435242432012345习题4.8#include“SqStack.h"intg(intm,intn){SqStackS;InitStack(S);SElemTypee;e.m=m;e.n=n;intresult=0;while(e.m!=0){Push(S,e);e.m=e.m-1;e.n=e.n*2;}while(!StackEmpty(S)){Pop(S,e);result=result+e.n;}returnresult;}习题4.9链队列的结点类型和链队列定义如下:ty

6、pedefstructQNode{QElemTypedata;structQNode*next;}LNode,*QueuePtr;//结点类型typedefstruct//链队列类型{QueuePtrrear;//队尾指针}CLinkQueue;CLinkQueueQ;…...Q.rear习题4.9voidInitCQueue(CLinkQueue&Q))//初始化循环链表表示的队列Q{Q.rear=newLNode;Q.rear->next=Q.rear;}//InitCQueuevoidEnCQueue(CLinkQueue&Q,QElemTypee)//把元素e插入循环

7、链表表示的队列Q{QueuePtrp=newLNode;p->data=e;p->next=Q.rear->next;Q.rear->next=p;Q.rear=p;}//EnCQueue习题4.9boolDeCQueue(CLinkQueue&Q,QElemType&e){QueuePtrp;if(Q.rear->next==Q.rear)returnfalse;p=Q.rear->next->next;e=p->data;Q.rear->next->next=p->next;if(Q.rear==