棧和隊(duì)列習(xí)習(xí)題答案

PAGE4第三章棧和隊(duì)列習(xí)題答案一、基礎(chǔ)知識題設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：

(1)若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop()表示出棧)

(2)能否得到出棧序列1423和1432并說明為什么不能得到或者如何得到。

(3)請分析1，2，3，4的24種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。

答：(1)出棧序列為：1324

(2)不能得到1423序列。因?yàn)橐玫?4的出棧序列，則應(yīng)做Push(1),Pop(),Push(2),Push

(3),Push(4),Pop()。這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2，3，4的24種排列中，可通過相應(yīng)入出棧操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,4312鏈棧中為何不設(shè)置頭結(jié)點(diǎn)？

答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么如何判別它的空和滿

答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。二是少用一個元素的空間,每次入隊(duì)前測試入隊(duì)后頭尾指針是否會重合，如果會重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個數(shù)。設(shè)長度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時間為何若只設(shè)尾指針呢

答：當(dāng)只設(shè)頭指針時，出隊(duì)的時間為1，而入隊(duì)的時間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個元素時方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€元素就是頭指針?biāo)冈兀猿鲫?duì)時不需要遍歷整個隊(duì)列。指出下述程序段的功能是什么

(1)voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}..//設(shè)Q1已有內(nèi)容，Q2已初始化過

while(!QueueEmpty(&Q1))

{x=DeQueue(&Q1);EnQueue(&Q2,x);n++;}

for(i=0;i<n;i++)

{x=DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);}

答：(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５祝瑮５椎脑胤诺綏ｍ?。此棧中元素個數(shù)限制在64個以內(nèi)。(2)程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復(fù)制到一個棧s2當(dāng)中去。(3)程序段的功能是利用棧T，將一個非空棧S中值等于m的元素全部刪去。(4)程序段的功能是將一個循環(huán)隊(duì)列Q經(jīng)過S棧的處理，反向排列，原來的隊(duì)頭變成隊(duì)尾，原來的隊(duì)尾變成隊(duì)頭。(5)這段程序的功能是將隊(duì)列1的所有元素復(fù)制到隊(duì)列2中去，但其執(zhí)行過程是先把隊(duì)列1的元素全部出隊(duì)，進(jìn)入隊(duì)列2，然后再把隊(duì)列2的元素復(fù)制到隊(duì)列1中。二、算法設(shè)計(jì)題回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)

解：根據(jù)提示，算法可設(shè)計(jì)為：//以下為順序棧的存儲結(jié)構(gòu)定義#defineStackSize100//假定預(yù)分配的?？臻g最多為100個元素typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;

intIsHuiwen(char*t){//判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量長度for(i=0;i<len/2;i++)//將一半字符入棧Push(&s,t[i]);while(!EmptyStack(&s)){//每彈出一個字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=S[i])

return0;//不等則返回0elsei++;}

return1;//比較完畢均相等則返回1}利用棧的基本操作，寫一個將棧S中所有結(jié)點(diǎn)均刪去的算法voidClearStack(SeqStack*S)，并說明S為何要作為指針參數(shù)

解：

算法如下voidClearStack(SeqStack*S){//刪除棧中所有結(jié)點(diǎn)S->Top=-1;//其實(shí)只是將棧置空}

因?yàn)橐每盏氖菞，如果不用指針來做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)將會在內(nèi)存中開辟另外的單元來對形參進(jìn)行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來做參數(shù)傳遞了。利用棧的基本操作，寫一個返回S中結(jié)點(diǎn)個數(shù)的算法intStackSize(SeqStackS),并說明S為何不作為指針參數(shù)

解：算法如下：intStackSize(SeqStackS){//計(jì)算棧中結(jié)點(diǎn)個數(shù)intn=0;if(!EmptyStack(&S)){Pop(&S);n++;}returnn;}上述算法的目的只要得到S棧的結(jié)點(diǎn)個數(shù)就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對原來的棧中元素進(jìn)行任何改變。系統(tǒng)會把原來的棧按值傳遞給形參，函數(shù)只對形參進(jìn)行操作，最后返回元素個數(shù)。設(shè)計(jì)算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對。(提示：對表達(dá)式進(jìn)行掃描，凡遇到'('就進(jìn)棧，遇')'就退掉棧頂?shù)?('，表達(dá)式被掃描完畢，棧應(yīng)為空。

解：根據(jù)提示，可以設(shè)計(jì)算法如下：intPairBracket(char*SR){//檢查表達(dá)式ST中括號是否配對inti;SeqStackS;//定義一個棧InitStack(&s);for(i=0;i<strlen(SR);i++){

if(S[i]=='(')Push(&S,SR[i]);//遇'('時進(jìn)棧if(S[i]==')')//遇')'if(!StackEmpty(S))//棧不為空時，將棧頂元素出棧Pop(&s);elsereturn0;//不匹配，返回0}ifEmptyStack(&s)return1;//匹配，返回1elsereturn0;//不匹配，返回0}一個雙向棧S是在同一向量空間內(nèi)實(shí)現(xiàn)的兩個棧，它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計(jì)初始化InitStack(S)、入棧Push(S,i,x)和出棧Pop(S,i)等算法，其中i為0或1，用以表示棧號。

解：雙向棧其實(shí)和單向棧原理相同，只是在一個向量空間內(nèi)，好比是兩個頭對頭的棧放在一起，中間的空間可以充分利用。雙向棧的算法設(shè)計(jì)如下：//雙向棧的棧結(jié)構(gòu)類型與以前定義略有不同#defineStackSize100//假定分配了100個元素的向量空間#definecharDataTypetypedefstruct{

DataTypeData[StackSize]

inttop0;//需設(shè)兩個指針inttop1;}DblStackvoidInitStack(DblStack*S){//初始化雙向棧S->top0=-1;S->top1=StackSize;//這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯}

intEmptyStack(DblStack*S,inti){//判?？?棧號i)return(i==0&&S->top0==-1||i==1&&S->top1==StackSize);}intFullStack(DblStack*S){//判棧滿,滿時肯定兩頭相遇return(S->top0==S-top1-1);}voidPush(DblStack*S,inti,DataTypex){//進(jìn)棧(棧號i)if(FullStack(S))Error("Stackoverflow");//上溢、退出運(yùn)行if(i==0)S->Data[++S->top0]=x;//棧0入棧if(i==1)S->Data[--S->top1]=x;//棧1入棧}DataTypePop(DblStack*S,inti){//出棧(棧號i)if(EmptyStack(S,i))Error("Stackunderflow");//下溢退出if(i==0)

return(S->Data[S->top0--]);//返回棧頂元素，指針值減1if(i==1)return(S->Data[S->top1++]);//因?yàn)檫@個棧是以另一端為底的，所以指針值加1。}Ackerman函數(shù)定義如下：請寫出遞歸算法。

┌n+1當(dāng)m=0時

AKM(m,n)=│AKM(m-1,1)當(dāng)m≠0，n=0時

└AKM(m-1,AKM(m,n-1))當(dāng)m≠0,n≠0時

解：算法如下intAKM(intm,intn){if(m==0)returnn+1;if(m<>0&&n==0)returnAKM(m-1,1);if(m<>0&&n<>0)returnAKM(m-1,AKM(m,n-1));}用第二種方法，即少用一個元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試為其設(shè)計(jì)置空隊(duì)，判隊(duì)空，判隊(duì)滿、出隊(duì)、入隊(duì)及取隊(duì)頭元素等六個基本操作的算法。

解：算法設(shè)計(jì)如下:

//循環(huán)隊(duì)列的定義

#defineQueueSize100

typedefcharDatatype;//設(shè)元素的類型為char型typedefstruct{intfront;intrear;DataTypeData[QueueSize];

}CirQueue;

(1)置空隊(duì)voidInitQueue(CirQueue*Q){//置空隊(duì)Q->front=Q->rear=0;}(2)判隊(duì)空intEmptyQueue(CirQueue*Q){//判隊(duì)空returnQ->front==Q->rear;}(3)判隊(duì)滿intFullQueue(CirQueue*Q){//判隊(duì)滿//如果尾指針加1后等于頭指針，則認(rèn)為滿return(Q->rear+1)%QueueSize==Q->front;}(4)出隊(duì)DataTypeDeQueue(CirQueue*Q){//出隊(duì)DataTypetemp;if(EmptyQueue(Q))Error("隊(duì)已空，無元素可以出隊(duì)");temp=Q->Data[Q->front];//保存元素值Q->front=(Q->front+1)%QueueSize;//循環(huán)意義上的加1returntemp;//返回元素值}(5)入隊(duì)voidEnQueue(CirQueue*Q,DataTypex){//入隊(duì)if(FullQueue(Q))Error("隊(duì)已滿，不可以入隊(duì)");Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//rear指向下一個空元素位置}(6)取隊(duì)頭元素DataTypeFrontQueue(CirQueue*Q){//取隊(duì)頭元素if(EmptyQueue(Q))Error("隊(duì)空，無元素可取");returnQ->Data[Q->front];}假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。

解：算法如下：//先定義鏈隊(duì)結(jié)構(gòu):typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是結(jié)點(diǎn)類型的定義typedefstruct{queuenode*rear;}LinkQueue;//只設(shè)一個指向隊(duì)尾元素的指針(1)置空隊(duì)voidInitQueue(LinkQueue*Q){//置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素QueueNode*s;Q->rear=Q->rear->next;//將隊(duì)尾指針指向頭結(jié)點(diǎn)while(Q->rear!=Q->rear->next)//當(dāng)隊(duì)列非空，將隊(duì)中元素逐個出隊(duì){s=Q->rear->next;Q->rear->next=s->next;free(s);}//回收結(jié)點(diǎn)空間}(2)判隊(duì)空

intEmptyQueue(LinkQueue*Q){//判隊(duì)空//當(dāng)頭結(jié)點(diǎn)的next指針指向自己時為空隊(duì)returnQ->rear->next->next==Q->rear->next;}(3)入隊(duì)voidEnQueue(LinkQueue*Q,Datatypex){//入隊(duì)//也就是在尾結(jié)點(diǎn)處插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申請新結(jié)點(diǎn)p->data=x;p->next=Q->rear->next;//初始化新結(jié)點(diǎn)并鏈入Q-rear->next=p;

Q->rear=p;//將尾指針移至新結(jié)點(diǎn)}(4)出隊(duì)DatatypeDeQueue(LinkQueue*Q){//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點(diǎn)x=p->data;//保存結(jié)點(diǎn)中數(shù)據(jù)if(p==Q->rear){//當(dāng)隊(duì)列中只有一個結(jié)點(diǎn)時，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)Q->rear=Q->rear->next;Q->rear->next=p->next;}else

Q->rear->next->next=p->next;//摘下結(jié)點(diǎn)pfree(p);//釋放被刪結(jié)點(diǎn)returnx;}對于循環(huán)向量中的循環(huán)隊(duì)列，寫出求隊(duì)列長度的公式。

解：公式如下(設(shè)采用第二種方法，front指向真正的隊(duì)首元素，rear指向真正隊(duì)尾后一位置，向量空間大?。篞ueueSizeQueuelen=(QueueSize+rear-front)%QueueSize假設(shè)循環(huán)隊(duì)列中只設(shè)rear和quelen來分別指示隊(duì)尾元素的位置和隊(duì)中元素的個數(shù)，試給出判別此循環(huán)隊(duì)