栈和队列作业参考答案.ppt

《栈和队列作业参考答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第三章栈和队列作业参考答案2作业1.1假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。#defineM100TypedefstructTwsStack{SElemTypestack[M];inttop[2];intbase[2];}3StatusInistack(TwsStack&tws){//初始化tws.base[0]=tws.top

2、[0]=-1;tws.base[1]=tws.top[1]=M;}//InistackStatuspush(TwsStack&tws,inti,SElemTypee){If(tws.top[0]==tws.top[1]-1)exit(ERROR);//堆栈满else{if(i==0)tws.top[0]++;elsetws.top[1]--;tws.stack[tws.top[i]]=e;}//插入堆栈0或1returnOK;}//push4Statuspop(TwsStack&tws,inti,SElemType&e){//出栈if(i==0)if(tws.top[0]==-1

3、)exitERROR//第一个栈空else{e=tws.stack[tws.top[i]];tws.top[0]=tws.top[0]-1;}elseif(tws.top[1]==M)exitERROR//第二个栈空else{e=tws.stack[tws.top[i]];tws.top[1]=tws.top[1]+1;}returnOK;}//pop5作业1.2设有编号1，2，3，4的四辆列车顺序进人一个栈式结构的站台，请写出这四辆列车开出车站的所有可能的顺序。这四辆列车开出车站的所有可能的顺序共有14种，它们分别是：1，2，3，4；1，2，4，3；1，3，2，4；1，3，4，

4、2；2，1，3，4；1，4，3，2；2，l，4，3；2，3，1，4；2，3，4，1；2，4，3，1；3，2，1，4；3，2．4，1；3，4，2，1；4，3，2，16作业1.3假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。TypedefstructQNode{QElemTypedate;structQNode*next;};TypedefstructLinkQueue{structQNode*rear;}7StatusIniQueue(LinkQueue&Q){//初始化Q.rear=(struc

5、tQNode*)malloc(sizeof(QNode));If(!Q.rear)exitERROR;//存储分配失败Q.rear->next=Q.rear;//构造循环链表returnOK;}//IniQueue8StatusEnQueue(LinkQueue&Q,QElemTypee){//入队列p=(structQNode*)malloc(sizeof(QNode));if(!p)exitOVERFLOW;//存储分配失败p->data=e;p->next=Q.rear->next;Q.rear->next=p;Q.rear=p;ReturnOK;}//EnQueue9St

6、atusDeQueue(LinkQueue&Q,QElemType&e){//出队列if(Q.rear->next==Q.rear)returnERROR;//队列为空q=Q.rear->next//q指向头结点p=q->next;e=p->data;q->next=p->next;If(Q.rear==p)Q.rear=q;//删除只有一个元素的队列Free(p);ReturnOK;}10作业1.4回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文字符串：“mada

7、mimadam”11Statushuiwen(charstr[20]){InitStack(S);i=0；m=0;while(str[i]!=’@’)//过滤空格{if(str[i]==‘’)m=m+1;elsestr[i-m]=str[i];i++;}str[i-m]=str[i];//字符串结束符”@”i=0;while(str[i]!=’@’){Push(S,str[i]);i++;}j=0;while(!StackEmpty(S)){Pop(S,e)If(strcmp(s