第3章习题及解答

《第3章习题及解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列?栈的特点是先进后出，所以在解决实际问题涉及到后进先出的情况时，可以考虑使用栈。例如表达式地括号匹配问题等。队列的特点是先进先出，所以在解决实际问题涉及到先进先出的情况时，可以考虑使用队列。例如操作系统中的作业排队等。2•设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序(每辆车可能入站，可能不入站，时间也可能不等)。所有可能得出栈顺序：4321,3421,3241,3214,2431,2341,2314,2143,2134,1432,1342,

2、1324,1243,1234。所有不可能得出栈顺序：4312,4231,4213,4132,4123,3412,3142,3124,2413,14233•试证明：若借助栈由输入序列1,2,,n得到输出序列为PiP2-Pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

3、t_queue(Q);cin»c;while(c!=@)push_stack(s,c);in_queue(Q,c);cin»c;while(!empty_stack(s))pop_stack(s,&a);out_queue(Q,&b);if(a!=b)return(O);if(empty_stack(s))return(l);5•设以数组se[m]存放循环队列的元素，同时设变量re^r和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。⑴循环队列入队算法intin_queue(datatypese[m],intre

4、ar,intfront,datatypee)if((rear+1)%m==front)return(-l);rear=(rear+1)%m;se[rear]=e;return(l);⑵循环队列出队算法intout_queue(datatypese[m],intrear,intfront,datatype*e){if(rear==front)return(-l);front=(front+l)%m;*e=se[front];return(l);6•假设以数组se[m]存放循环队列的元素，同时设变量rear和num分别作为队尾指针和队中元素个数记录，试给出判别此循环队

5、列的队满条件，并写出相应入队和出队的算法。⑴入队算法intin_queue(datatypese[m],intrear,intnum,datatypee)if(num==m)return(-l);rear=(rear+l)%m;se[rear]=e;num++;retum(l);}⑵岀队算法intout_queue(datatypese[m]Jntrear,intnum,datatype*e){if(num==O)return(-l);*e=se[(rear-num+l)%m];num—;retum(l);}7.假设以带头结点的循坏链表表示一个队列，并且只设一个队

6、尾指针指向尾元素结点(注意不设头指针)，试写出相应的置空队、入队、出队的算法。⑴队列初始化算法linklistinit_queue(){rear=newInode;rear->next=rear;return(rear);}⑵入队算法linklistin_queue(linklistrear,datatypex){s=newInode;s->data=x;s->next=rear->next;rear->next=s;rear=s;return(rear);}⑶岀队算法linklistout_queue(linklistrear,datatype*x)if(rea

7、r->next==rear)return(NULL);q=rear->next->next;if(q==rear){rear=rear->next;rear->next=rear;}else{rear->next->next=q->next;}*x=q->data;deleteq;return(rear);}8•设计一个算法判别一个算术表达式的圆括号是否正确配对。intprocess(){init_stack(s);cin»c;while(c!=@){if(c='(‘)push_stack(s,c);if(c』)‘){if(!empty_stack(s))pop_

8、stack