2022年数据结构课后习题解答栈与队列 .pdf

《2022年数据结构课后习题解答栈与队列 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课后习题解答栈与队列 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章栈与队列3.15 typedef struct Elemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型Status Init_Stack(BDStacktype&tws,int m)/初始化一个大小为m 的双向栈 tws tws.base0=(Elemtype*)malloc(sizeof(Elemtype);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;return OK;/Init_Stack Status push(BDStacktype&tws,int i,Elemt

2、ype x)/x入栈,i=0 表示低端栈,i=1 表示高端栈 if(tws.top0tws.top1)return OVERFLOW;/注意此时的栈满条件 if(i=0)*tws.top0+=x;else if(i=1)*tws.top1-=x;else return ERROR;return OK;/push Status pop(BDStacktype&tws,int i,Elemtype&x)/x出栈,i=0 表示低端栈,i=1 表示高端栈 if(i=0)if(tws.top0=tws.base0)return OVERFLOW;x=*-tws.top0;else if(i=1)if(t

3、ws.top1=tws.base1)return OVERFLOW;x=*+tws.top1;else return ERROR;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 12 页 -return OK;/pop 3.16 void Train_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);

4、*(q+)=c;/把H接在后部 /Train_arrange 3.17 int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回 1,否则返回 0 InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;if(!StackEmpty(s)return 0;return 1;/IsReverse 3.18 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 12 页 -Status Br

5、acket_Test(char*str)/判别表达式中小括号是否匹配 count=0;for(p=str;*p;p+)if(*p=()count+;else if(*p=)count-;if(count1)if(gx-1y=old)gx-1y=color;EnQueue(Q,x-1,y);/修改左邻点的颜色 if(y1)if(gxy-1=old)gxy-1=color;EnQueue(Q,x,y-1);/修改上邻点的颜色 if(xm)if(gx+1y=old)gx+1y=color;EnQueue(Q,x+1,y);/修改右邻点的颜色 if(y=0)s=0;else if(m0&n=0)s=n

6、+g(m-1,2*n);else return ERROR;return OK;/g 3.25 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 12 页 -Status F_recursive(int n,int&s)/递归算法 if(n0)return ERROR;if(n=0)s=n+1;else F_recurve(n/2,r);s=n*r;return OK;/F_recursive Status F_nonrecursive(int n,int s)/非递归算法 if(n0)return ERROR;if(n=0)s=n+1;else InitStack(s);/s 的

7、元素类型为struct int a;int b;while(n!=0)a=n;b=n/2;push(s,a,b);n=b;/while s=1;while(!StackEmpty(s)pop(s,t);s*=t.a;/while return OK;/F_nonrecursive 3.26 float Sqrt_recursive(float A,float p,float e)/求平方根的递归算法 if(abs(p2-A)=e)p=(p+A/p)/2;return p;/Sqrt_nonrecursive 3.27 这一题的所有算法以及栈的变化过程请参见数据结构(pascal 版),作者不再

8、详细写出.3.28 void InitCiQueue(CiQueue&Q)/初始化循环链表表示的队列Q Q=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueue void EnCiQueue(CiQueue&Q,int x)/把元素 x 插入循环链表表示的队列Q,Q 指向队尾元素,Q-next 指向头结点,Q-next-next 指向队头元素 p=(CiLNode*)malloc(sizeof(CiLNode);p-data=x;p-next=Q-next;/直接把 p 加在 Q 的后面 Q-next=p;Q=p;/修改尾指针 Statu

9、s DeCiQueue(CiQueue&Q,int x)/从循环链表表示的队列Q 头部删除元素x if(Q=Q-next)return INFEASIBLE;/队列已空 p=Q-next-next;x=p-data;Q-next-next=p-next;free(p);return OK;/DeCiQueue 3.29 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 12 页 -Status EnCyQueue(CyQueue&Q,int x)/带 tag域的循环队列入队算法 if(Q.front=Q.rear&Q.tag=1)/tag域的值为 0 表示空,1 表示 满 retu

10、rn OVERFLOW;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front=Q.rear)Q.tag=1;/队列满/EnCyQueue Status DeCyQueue(CyQueue&Q,int&x)/带 tag 域的循环队列出队算法 if(Q.front=Q.rear&Q.tag=0)return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.baseQ.front;if(Q.front=Q.rear)Q.tag=1;/队列空 return OK;/DeCyQueue 分析:当循环队列容量较小而队列

11、中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.3.30 Status EnCyQueue(CyQueue&Q,int x)/带 length 域的循环队列入队算法 if(Q.length=MAXSIZE)return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;Q.length+;return OK;/EnCyQueue Status DeCyQueue(CyQueue&Q,int&x)/带 length 域的循环队列出队算法 if(Q.length=0)return INFEASIBLE;head=(Q.rea

12、r-Q.length+1)%MAXSIZE;/详见书后注释 x=Q.basehead;Q.length-;/DeCyQueue 3.31 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 12 页 -int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回 1,否则返回 0 InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);/同时使用栈和队列两种结构 while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)return ERR

13、OR;return OK;/Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)/求 k 阶斐波那契序列的前n+1 项 InitCyQueue(Q);/其 MAXSIZE 设置为 k for(i=0;ik-1;i+)Q.basei=0;Q.basek-1=1;/给前 k 项赋初值 for(i=0;ik;i+)printf(%d,Q.basei);for(i=k;i=n;i+)m=i%k;sum=0;for(j=0;j=avr)/根据 x 的值决定插入在队头还是队尾 Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSI

14、ZE;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 12 页 -/插入在队尾 else Q.front=(Q.front-1)%MAXSIZE;Q.baseQ.front=x;/插入在队头 return OK;/EnDQueue Status DeDQueue(DQueue&Q,int&x)/输出受限的双端队列的出队操作 if(Q.front=Q.rear)return INFEASIBLE;/队列空 x=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;/DeDQueue 3.34 void Train_Rearrang

15、e(char*train)/这里用字符串train 表示火车,P表示硬座,H表示硬卧,S表示软卧,最终按 PSH的顺序排列 r=train;InitDQueue(Q);while(*r)if(*r=P)printf(E);printf(D);/实际上等于不入队列,直接输出 P 车厢 else if(*r=S)printf(E);EnDQueue(Q,*r,0);/0 表示把 S 车厢从头端入队列 else printf(A);EnDQueue(Q,*r,1);/1 表示把 H 车厢从尾端入队列 /while 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 12 页 -while(!DQueueEmpty(Q)printf(D);DeDQueue(Q);/while/从头端出队列的车厢必然是先S 后 H 的顺序/Train_Rearrange 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 12 页 -