《栈和队列作业参考答案幻灯片》由会员分享，可在线阅读，更多相关《栈和队列作业参考答案幻灯片（11页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 栈和队列,作业参考答案,2,作业1.1 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。,# define M 100Typedef struct TwsStack SElemType stackM; int top2; int base2; ,3,Status Inistack(TwsStack &tws) /初始化 tws.base0=t
2、ws.top0=-1; tws.base1=tws.top1=M; /InistackStatus push( TwsStack &tws, int i, SElemType e ) If(tws.top0=tws.top1-1) exit(ERROR); /堆栈满 else if ( i=0 ) tws.top0+; else tws.top1-; tws.stack tws.topi=e; /插入堆栈0或1 return OK; /push,4,Status pop( TwsStack &tws, int i , SElemType &e ) / 出栈 if(i= =0) if(tws.t
3、op0= = -1) exit ERROR /第一个栈空 else e=tws.stacktws.topi; tws.top0=tws.top0-1; else if(tws.top1= = M ) exit ERROR /第二个栈空 else e=tws.stacktws.topi; tws.top1=tws.top1+1; return OK; /pop,5,作业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，24，1；3，4，2，1； 4，3，2 ，1,6,作业1.3 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。,Typedef struct QNode QElemType date; struct QNode *next;Typedef struct LinkQueue struct QNode *rear; ,7,Status IniQueue( LinkQueue &Q
5、 ) /初始化 Q.rear= (struct QNode *) malloc( sizeof( QNode ) ); If(! Q.rear ) exit ERROR; /存储分配失败 Q.rear-next=Q.rear; /构造循环链表 return OK; /IniQueue,8,Status EnQueue( LinkQueue &Q, QElemType e ) /入队列 p = ( struct QNode *) malloc (sizeof (QNode ); if(!p) exit OVERFLOW; /存储分配失败 p-data=e; p-next=Q.rear-next;
6、 Q.rear-next=p; Q.rear=p; Return OK; /EnQueue,9,Status DeQueue(LinkQueue &Q, QElemType &e ) /出队列 if( Q.rear-next = = Q.rear ) return ERROR; /队列为空 q=Q.rear-next /q指向头结点 p=q-next; e=p-data; q-next=p-next; If(Q.rear=p) Q.rear=q; /删除只有一个元素的队列 Free(p); Return OK;,10,作业1.4 回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去
7、掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam”,11,Status huiwen( char str20 ) InitStack(S); i=0；m=0; while( stri!=) /过滤空格 if(stri = = ) m=m+1; else stri-m=stri; i+; stri-m= stri; /字符串结束符” i=0; while( stri!=) Push (S, stri); i+; j=0; while ( !StackEmpty(S) ) Pop (S, e) If( strcmp (str j , e) !=0 ) return NO; /不是回文字符 j+; return Yes; / huiwen,
