严蔚敏数据结构c语言版习题集答案第三章栈与队列.docx

《严蔚敏数据结构c语言版习题集答案第三章栈与队列.docx》由会员分享，可在线阅读，更多相关《严蔚敏数据结构c语言版习题集答案第三章栈与队列.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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; tws0=tws.base0; tws1=tws.base1; return OK;/Init_Stack Status push(BDStacktype &tws,int i,E

2、lemtype x)/x入栈,i=0表示低端栈,i=1表示高端栈 if(tws0tws1) return OVERFLOW; /留意此时的栈满条件 if(i=0) *tws0+=x; else if(i=1) *tws1-=x; else return ERROR; return OK;/push Status pop(BDStacktype &tws,int i,Elemtype &x)/x出栈,i=0表示低端栈,i=1表示高端栈 if(i=0) if(tws0=tws.base0) return OVERFLOW; x=*-tws0; else if(i=1) if(tws1=tws.ba

3、se1) return OVERFLOW; x=*+tws1; else return ERROR; 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); *(q+)=c; /把H接在后部/Train_arrange 3.17 int I

4、sReverse()/推断输入的字符串中&前和&后局部是否为逆串,是则返回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 Status Bracket_Test(char *str)/判别表达式中小括号是否匹配 count=0; for(p=str;*p;p+) if(*p=(

5、) 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+g(m-1,2*n); else return ERROR; return OK;/g 3

6、.25 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的元素类型为struct int a;int b; while(n!=0) a=n;b=n/2; push(s,a,b); n=b; /whi

7、le 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版),作者不再具体写出. 3.28 void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q Q=(CiL

8、Node*)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; /修改尾指针Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素x if(Q=Q-next)

9、 return INFEASIBLE; /队列已空 p=Q-next-next; x=p-data; Q-next-next=p-next; free(p); return OK;/DeCiQueue 3.29 Status EnCyQueue(CyQueue &Q,int x)/带tag域的循环队列入队算法 if(Q.front=Q.rear&Q.tag=1) /tag域的值为0表示空,1表示满 return OVERFLOW; Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front=Q.rear) Q.tag=1; /队列满/EnCyQu

10、eue 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分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值. 3.30 Status EnCyQueue(CyQueue &Q,int x)/带length域

11、的循环队列入队算法 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.rear-Q.length+1)%MAXSIZE; /详见书后注释 x=Q.basehead; Q.length-;/DeCyQueue 3.31 int Pal

12、indrome_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 ERROR; return OK;/Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)/求k阶斐波那契序列的前n+1项 InitCyQueue(Q); /其MAXSIZ

13、E设置为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)%MAXSIZE; /插入在队尾 else Q.front=(Q.front-1)%MAXSIZE; Q.baseQ.front=x; /插入在队头 return OK;/EnDQueue Status DeDQueue(DQu

14、eue &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_Rearrange(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 while(!DQueueEmpty(Q) printf(D); DeDQueue(Q); /while /从头端出队列的车厢必定是先S后H的依次 /Train_Rearrange第 17 页