第三章 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課后答案-棧與隊(duì)列

1、第三章 棧與隊(duì)列3.15typedef structElemtype *base2;Elemtype *top2;BDStacktype; /雙向棧類型Status Init_Stack(BDStacktype &tws,int m)/初始化一個(gè)大小為m的雙向棧tws tws.base0=(Elemtype*)malloc(sizeof(Elemtype);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;return OK;/Init_StackStatus push(BDStacktype &tws,int i,Elem

2、type x)/x入棧,i=0表示低端棧,i=1表示高端棧if(tws.top0tws.top1) return OVERFLOW; /注意此時(shí)的棧滿條件 if(i=0) *tws.top0+=x;else if(i=1) *tws.top1-=x;else return ERROR;return OK;/pushStatus 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(

3、tws.top1=tws.base1) return OVERFLOW;x=*+tws.top1;else return ERROR;return OK;/pop3.16void 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調(diào)到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c; /把H接在后部/Train_arrange3.17in

4、t IsReverse()/判斷輸入的字符串中&前和&后部分是否為逆串,是則返回1,否則返回0InitStack(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;/IsReverse3.18Status Bracket_Test(char *str)/判別表達(dá)式中小括號(hào)是否匹配count=0;for(p=str;*p;p+)if(*p=() count+;el

5、se if(*p=) count-;if (count1)if(gx-1y=old)gx-1y=color;EnQueue(Q,x-1,y); /修改左鄰點(diǎn)的顏色if(y1)if(gxy-1=old)gxy-1=color;EnQueue(Q,x,y-1); /修改上鄰點(diǎn)的顏色if(xm)if(gx+1y=old)gx+1y=color;EnQueue(Q,x+1,y); /修改右鄰點(diǎn)的顏色if(y=0) s=0;else if(m0&n=0) s=n+g(m-1,2*n);else return ERROR;return OK;/g3.25Status F_recursive(int n,i

6、nt &s)/遞歸算法if(n0) return ERROR;if(n=0) s=n+1;elseF_recurve(n/2,r);s=n*r;return OK;/F_recursiveStatus F_nonrecursive(int n,int s)/非遞歸算法if(n0) return ERROR;if(n=0) s=n+1;elseInitStack(s); /s的元素類型為struct int a;int b;while(n!=0)a=n;b=n/2;push(s,a,b);n=b;/whiles=1;while(!StackEmpty(s)pop(s,t);s*=t.a;/whi

7、lereturn OK;/F_nonrecursive3.26float Sqrt_recursive(float A,float p,float e)/求平方根的遞歸算法if(abs(p2-A)=e)p=(p+A/p)/2;return p;/Sqrt_nonrecursive3.27這一題的所有算法以及棧的變化過程請(qǐng)參見數(shù)據(jù)結(jié)構(gòu)(pascal版),作者不再詳細(xì)寫出.3.28void InitCiQueue(CiQueue &Q)/初始化循環(huán)鏈表表示的隊(duì)列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueuevoid EnCiQue

8、ue(CiQueue &Q,int x)/把元素x插入循環(huán)鏈表表示的隊(duì)列Q,Q指向隊(duì)尾元素,Q-next指向頭結(jié)點(diǎn),Q-next-next指向隊(duì)頭元素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)/從循環(huán)鏈表表示的隊(duì)列Q頭部刪除元素x if(Q=Q-next) return INFEASIBLE; /隊(duì)列已空p=Q-next-next;x=p-data;Q-next-next=p-next;fr

9、ee(p);return OK;/DeCiQueue3.29Status EnCyQueue(CyQueue &Q,int x)/帶tag域的循環(huán)隊(duì)列入隊(duì)算法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; /隊(duì)列滿/EnCyQueueStatus DeCyQueue(CyQueue &Q,int &x)/帶tag域的循環(huán)隊(duì)列出隊(duì)算法 if(Q.front=Q.rear&Q.tag=0)

10、 return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.baseQ.front;if(Q.front=Q.rear) Q.tag=1; /隊(duì)列空return OK;/DeCyQueue分析:當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí),此種表示方法可以節(jié)約較多的存儲(chǔ)空間,較有價(jià)值.3.30Status EnCyQueue(CyQueue &Q,int x)/帶length域的循環(huán)隊(duì)列入隊(duì)算法 if(Q.length=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x

11、;Q.length+;return OK;/EnCyQueueStatus DeCyQueue(CyQueue &Q,int &x)/帶length域的循環(huán)隊(duì)列出隊(duì)算法 if(Q.length=0) return INFEASIBLE;head=(Q.rear-Q.length+1)%MAXSIZE; /詳見書后注釋x=Q.basehead;Q.length-;/DeCyQueue3.31int Palindrome_Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0 InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c)

12、;EnQueue(Q,c); /同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test3.32void GetFib_CyQueue(int k,int n)/求k階斐波那契序列的前n+1項(xiàng)InitCyQueue(Q); /其MAXSIZE設(shè)置為kfor(i=0;ik-1;i+) Q.basei=0;Q.basek-1=1; /給前k項(xiàng)賦初值for(i=0;ik;i+) printf(%d,Q.basei);for(i=k;i=n;i+)m=i%

13、k;sum=0;for(j=0;j=avr) /根據(jù)x的值決定插入在隊(duì)頭還是隊(duì)尾Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE; /插入在隊(duì)尾elseQ.front=(Q.front-1)%MAXSIZE;Q.baseQ.front=x; /插入在隊(duì)頭return OK;/EnDQueueStatus DeDQueue(DQueue &Q,int &x)/輸出受限的雙端隊(duì)列的出隊(duì)操作 if(Q.front=Q.rear) return INFEASIBLE; /隊(duì)列空x=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;/DeDQueue3.34void Train_Rearrange(char *train)/這里用字符串train表示火車,P表示硬座,H表示硬臥,S表示軟臥,最終按PSH的順序排列r=train;InitDQueue(Q);while(*r)if(*r=P)printf(E);printf(D); /