资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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=tws.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.top0= = -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,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 ) /初始化 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; 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.去掉空格(原串)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,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号