數據結構與算法分析（C++語言版）-張琨版第三章棧和隊列課后習題答案2704

數據結構與算法分析（C++語?版）_張琨版第三章棧和隊列課后習題答案?、選擇題1.DA2.A3.C4.D5.C6.B7.C8.C9.C10.A?、填空題1.棧頂2.鏈棧3.空4.不可能5.O(1)6.AD7.設所創(chuàng)建的鏈棧為s則s=NULL8.鏈棧頭鏈棧頭9.設所創(chuàng)建的鏈隊指針為p則p->next=NULL10．LiQueue*qu=(LiQueue*)malloc(sizeof(LiQueue));//申請空間qu->front=qu->rear=NULL;//隊頭隊尾指針置為NULL三、判斷題1.×當棧中只有?個元素時，這個元素也稱棧底元素，它可以刪除2.×順序棧是指?順序存儲結構實現(xiàn)的棧，棧中的元素不?定是有序的3.×?如進棧序列是123出棧序列可以是1324.√當棧中只有?個元素時就是這種情況5.×可以進?任意多次的進棧、出棧操作，但棧中最多只有m個元素6.×可以進?任意多次的進棧、出棧操作7.√8.×只要棧不滿就可以進?進棧操作，只要棧不空就可以進?出棧操作，并不規(guī)定進棧、出棧操作的次序9.×空棧是指棧中沒有元素，但?定有棧頂元素10.√因為?論出隊還是?隊，都要進?求余運算，將隊?指針和隊尾指針轉化為有效的順序隊下標值，另外，循環(huán)順序隊中的元素可以平?移動，所以本敘述是正確的四、簡答題1.可能的次序為CDBAE、CDEBA、CDBEA2.?級語?變量名的定義規(guī)則是：以字母開頭的字母數字串。?棧次序為123PA,以A最先出棧的序列為AP321,以P最先出棧的序列為P321A，P32A1，P3A21，PA321。所以可以作為?級語?的變量名的序列為AP321，P321A，P32A1，P3A21，PA321。3.1）能得到輸出順序為325641的序列，其操作序列為：AAADDAADADDD2)不能得到輸出順序為154623的序列；執(zhí)?ADAAAADDAD,得到輸出序列1546后，棧中元素從棧頂到棧底為32，不能讓2先出棧，所以得不到輸出序列154632。4.證明過程如下圖所?：5.證明過程如下圖所?：五、計算題1.設置?個棧st，掃描表達式exp，遇到‘(’、‘[’、‘{’，則將其?棧，遇到‘)’，若棧頂是‘(’，則繼續(xù)處理，否則以不匹配返回0；遇到‘]’，若棧頂是‘[’，則繼續(xù)處理，否則以不匹配返回0；遇到‘}’，若棧頂是‘{’，則繼續(xù)處理，否則以不匹配返回0；在exp掃描完畢后，若棧不空，則以不配對返回0；否則以括號配對返回1.對應算法如下：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)為了簡單，棧運算只設計了基本的處理過程。完整程序如下#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("出棧序列個數%d\n",sum);}該程序的執(zhí)?結果如下：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//參數錯誤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.假定采?順序棧結構，先退棧st中所有元素，利??個臨時棧tmps存放從st棧中退棧的元素，最后的?個元素即為所求，然后將臨時棧tmps中的元素逐?出棧并進棧到st中，這樣恢復st棧中原來的元素。相關代碼如下：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;/*鏈隊結點類型*/typedefstruct{QNode*front,*rear;}QuType;/*鏈隊類型*/voidSeeDoctor(){intsel,flag=1,find,no;QuType*qu;QNode*p;qu=(QuType*)malloc(sizeof(QuType));qu->front=qu->rear=NULL;/*創(chuàng)建空隊*/while(flag==1){/*循環(huán)執(zhí)?*/printf("1:排隊2:就診3:查看排隊4.不再排隊,余下依次就診5:下班請選擇:");scanf("%d",&sel);switch(sel){case1:printf(">>輸?病歷號:");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(">>輸?的病歷號重復,重新輸?:");}while(find==1);p=(QNode*)malloc(sizeof(QNode));/*創(chuàng)建結點*/p->data=no;p->next=NULL;if(qu->rear==NULL)/*第?個病?排隊*/{qu->front=qu->rear=p;}else{qu->rear->next=p;qu->rear=p;/*將*p結點?隊*/}break;case2:if(qu->front==NULL)printf(">>沒有排隊的病?!\n");/**/隊空else/*隊不空*/{p=qu->front;printf(">>病?%d就診\n",p->data);if(qu->rear==p){/*只有?個病?排隊的情況*/qu->front=qu->rear=NULL;}elsequ->front=p->next;free(p);}break;case3:if(qu->front==NULL)printf(">>沒有排列的病?!\n");/**/隊空else/*隊不空*/{p=qu->front;printf(">>排隊病?:");while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}break;case4:if(qu->front==NULL)printf(">>沒有排列的病?!\n");/**/隊空else/*隊不空*/{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(">>請排隊的病?明天就醫(yī)!\n");/