數(shù)據(jù)結(jié)構(gòu)與算法分析（C++語言版）-張琨版第三章棧和隊(duì)列課后習(xí)題答案2704

數(shù)據(jù)結(jié)構(gòu)與算法分析（C++語?版）_張琨版第三章棧和隊(duì)列課后習(xí)題答案?、選擇題1.DA2.A3.C4.D5.C6.B7.C8.C9.C10.A?、填空題1.棧頂2.鏈棧3.空4.不可能5.O(1)6.AD7.設(shè)所創(chuàng)建的鏈棧為s則s=NULL8.鏈棧頭鏈棧頭9.設(shè)所創(chuàng)建的鏈隊(duì)指針為p則p->next=NULL10．LiQueue*qu=(LiQueue*)malloc(sizeof(LiQueue));//申請空間qu->front=qu->rear=NULL;//隊(duì)頭隊(duì)尾指針置為NULL三、判斷題1.×當(dāng)棧中只有?個(gè)元素時(shí)，這個(gè)元素也稱棧底元素，它可以刪除2.×順序棧是指?順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，棧中的元素不?定是有序的3.×?如進(jìn)棧序列是123出棧序列可以是1324.√當(dāng)棧中只有?個(gè)元素時(shí)就是這種情況5.×可以進(jìn)?任意多次的進(jìn)棧、出棧操作，但棧中最多只有m個(gè)元素6.×可以進(jìn)?任意多次的進(jìn)棧、出棧操作7.√8.×只要棧不滿就可以進(jìn)?進(jìn)棧操作，只要棧不空就可以進(jìn)?出棧操作，并不規(guī)定進(jìn)棧、出棧操作的次序9.×空棧是指棧中沒有元素，但?定有棧頂元素10.√因?yàn)?論出隊(duì)還是?隊(duì)，都要進(jìn)?求余運(yùn)算，將隊(duì)?指針和隊(duì)尾指針轉(zhuǎn)化為有效的順序隊(duì)下標(biāo)值，另外，循環(huán)順序隊(duì)中的元素可以平?移動(dòng)，所以本敘述是正確的四、簡答題1.可能的次序?yàn)镃DBAE、CDEBA、CDBEA2.?級(jí)語?變量名的定義規(guī)則是：以字母開頭的字母數(shù)字串。?棧次序?yàn)?23PA,以A最先出棧的序列為AP321,以P最先出棧的序列為P321A，P32A1，P3A21，PA321。所以可以作為?級(jí)語?的變量名的序列為AP321，P321A，P32A1，P3A21，PA321。3.1）能得到輸出順序?yàn)?25641的序列，其操作序列為：AAADDAADADDD2)不能得到輸出順序?yàn)?54623的序列；執(zhí)?ADAAAADDAD,得到輸出序列1546后，棧中元素從棧頂?shù)綏５诪?2，不能讓2先出棧，所以得不到輸出序列154632。4.證明過程如下圖所?：5.證明過程如下圖所?：五、計(jì)算題1.設(shè)置?個(gè)棧st，掃描表達(dá)式exp，遇到‘(’、‘[’、‘{’，則將其?棧，遇到‘)’，若棧頂是‘(’，則繼續(xù)處理，否則以不匹配返回0；遇到‘]’，若棧頂是‘[’，則繼續(xù)處理，否則以不匹配返回0；遇到‘}’，若棧頂是‘{’，則繼續(xù)處理，否則以不匹配返回0；在exp掃描完畢后，若棧不空，則以不配對返回0；否則以括號(hào)配對返回1.對應(yīng)算法如下：intmatch(charexp[],intn){charst[MaxSize];inttop=-1;inti=0,tag=1;while(i<n&&tag==1){if(exp[i]=='('||exp[i]=='['||exp[i]=='{'){top++;st[top]=exp[i];}if(exp[i]==')'){if(st[top]=='(')top--;elsetag=0;}if(exp[i]==']'){if(st[top]=='[')top--;elsetag=0;}if(exp[i]=='}'){if(st[top]=='{')top--;elsetag=0;}i++;}if(top>=0)tag=0;returntag;}2.過程如下：Voidprocess(intm,inta[],intcurp)為了簡單，棧運(yùn)算只設(shè)計(jì)了基本的處理過程。完整程序如下#include<stdio.h>#defineMaxSize10structstacknode{intdata[MaxSize];inttop;}st;inttotal=4;charstr[]="1234";intsum=0;voidinitstack(){st.top=-1;}voidpush(intn){st.top++;st.data[st.top]=n;}intpop(){inttemp;temp=st.data[st.top];st.top--;returntemp;}boolempty(){if(st.top==-1)returntrue;returnfalse;}voidprocess(intm,inta[],intcurp){{intx,i;if(m>total&&empty()){printf("");for(i=0;i<curp;i++)printf("%c",str[a[i]-1]);printf("\n");sum++;}if(m<=total){push(m);process(m+1,a,curp);pop();}if(!empty()){x=pop();a[curp]=x;curp++;process(m,a,curp);push(x);}}voidmain(){inta[MaxSize];initstack();printf("所有出棧序列：\n");process(1,a,0);printf("出棧序列個(gè)數(shù)%d\n",sum);}該程序的執(zhí)?結(jié)果如下：3.解析過程如下：typedefstruct{ElemTypeS[MaxSize];inttop1,top2;}StackType;voidInitStack1(StackType&st){st.top1=-1;st.top2=MaxSize;}intStackEmpty1(StackTypest,inti)//i==11i==2棧2棧{if(i==1)//i==1return(st.top==-1);else//i==2return(st.top==MaxSize);}intPush1(StackType&st,inti,ElemTypex){if(st.top1==st.top2-1){return0;}if(i==1)//1棧{st.top1++;st.S[st.top1]=x;}else//2棧{st.top2--;st.S[st.top2]=x;}else//參數(shù)錯(cuò)誤return0;return1；}intPop1（StackType&st,inti,ElemType&x）{if(i==1){if(st.top1==-1)return0;else{x=st.S[st.top1];st.top1--;}}elseif(i==2){if(st.top2==MaxSize)return0;else{x=st.S[st.top2];st.top2++;}}elsereturn0;return1;}4.假定采?順序棧結(jié)構(gòu)，先退棧st中所有元素，利??個(gè)臨時(shí)棧tmps存放從st棧中退棧的元素，最后的?個(gè)元素即為所求，然后將臨時(shí)棧tmps中的元素逐?出棧并進(jìn)棧到st中，這樣恢復(fù)st棧中原來的元素。相關(guān)代碼如下：intGetBottom(SqStackst,ElemType&x){ElemTypee;SqStacktmpst;initstack(tmpst);if(StackEmpty(st)){return0;}while(!StackEmpty(st)){Pop(st,x);Push(tmpst,x);}while(!StackEmpty(tmpst)){Pop(tmpst,x);Push(st,e);}return1;}5.代碼如下#include<stdio.h>#include<malloc.h>typedefstructqnode{intdata;structqnode*next;}QNode;/*鏈隊(duì)結(jié)點(diǎn)類型*/typedefstruct{QNode*front,*rear;}QuType;/*鏈隊(duì)類型*/voidSeeDoctor(){intsel,flag=1,find,no;QuType*qu;QNode*p;qu=(QuType*)malloc(sizeof(QuType));qu->front=qu->rear=NULL;/*創(chuàng)建空隊(duì)*/while(flag==1){/*循環(huán)執(zhí)?*/printf("1:排隊(duì)2:就診3:查看排隊(duì)4.不再排隊(duì),余下依次就診5:下班請選擇:");scanf("%d",&sel);switch(sel){case1:printf(">>輸?病歷號(hào):");do{scanf("%d",&no);find=0;p=qu->front;while(p!=NULL&&!find){if(p->data==no)find=1;elsep=p->next;}if(find)printf(">>輸?的病歷號(hào)重復(fù),重新輸?:");}while(find==1);p=(QNode*)malloc(sizeof(QNode));/*創(chuàng)建結(jié)點(diǎn)*/p->data=no;p->next=NULL;if(qu->rear==NULL)/*第?個(gè)病?排隊(duì)*/{qu->front=qu->rear=p;}else{qu->rear->next=p;qu->rear=p;/*將*p結(jié)點(diǎn)?隊(duì)*/}break;case2:if(qu->front==NULL)printf(">>沒有排隊(duì)的病?!\n");/**/隊(duì)空else/*隊(duì)不空*/{p=qu->front;printf(">>病?%d就診\n",p->data);if(qu->rear==p){/*只有?個(gè)病?排隊(duì)的情況*/qu->front=qu->rear=NULL;}elsequ->front=p->next;free(p);}break;case3:if(qu->front==NULL)printf(">>沒有排列的病?!\n");/**/隊(duì)空else/*隊(duì)不空*/{p=qu->front;printf(">>排隊(duì)病?:");while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}break;case4:if(qu->front==NULL)printf(">>沒有排列的病?!\n");/**/隊(duì)空else/*隊(duì)不空*/{p=qu->front;printf(">>病?按以下順序就診:");while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}flag=0;/**/退出break;case5:if(qu->front!=NULL)printf(">>請排隊(duì)的病?明天就醫(yī)!\n");/