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

《第三章 棧和隊(duì)列習(xí)題答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《第三章 棧和隊(duì)列習(xí)題答案（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第三章 棧和隊(duì)列習(xí)題答案 一、基礎(chǔ)知識(shí)題 3.1 設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問(wè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?并說(shuō)明為什么不能得到或者如何得到。? 　　(3)請(qǐng)分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過(guò)相應(yīng)的入出棧操作得到的。? 答：(1)出棧序列

2、為：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種排列中，可通過(guò)相應(yīng)入出棧操作得到的序列是： 　　??? 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3

3、241,3421,4321 ????? 不能得到的序列是： 　　　　1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2 鏈棧中為何不設(shè)置頭結(jié)點(diǎn)? 答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。 3.3 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿?? 答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的"空"或"滿"不能以頭尾指針是否相等來(lái)確定，一般是通過(guò)以

4、下幾種方法：一是另設(shè)一布爾變量來(lái)區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間,每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。 3.4 設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢?? 答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1，而入隊(duì)的時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈兀猿鲫?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。 3.5 指出下述程

5、序段的功能是什么?? (1) void Demo1(SeqStack *S){ 　　　　int i; arr[64] ; n=0 ; 　　　　while ( StackEmpty(S)) arr[n++]=Pop(S); 　　　　for (i=0, i< n; i++) Push(S, arr[i]); 　　　} //Demo1 (2) SeqStack S1, S2, tmp; 　　DataType x; 　　...//假設(shè)棧tmp和S2已做過(guò)初始化 　　while ( ! StackEmpty (&S1)) 　　　{x=Pop(&S1) ; 　　　　Push(&tmp

6、,x); 　　　} 　　while ( ! StackEmpty (&tmp) ) 　　　{x=Pop( &tmp);? 　　　　Push( &S1,x); 　　　　Push( &S2, x); 　　　} (3) void Demo2( SeqStack *S, int m)? 　　　{ // 設(shè)DataType 為int 型 　　　　SeqStack T; int i; 　　　　InitStack (&T); 　　　　while (! StackEmpty( S)) 　　　　　if(( i=Pop(S)) !=m) Push( &T,i); 　　　　while (!

7、 StackEmpty( &T)) 　　　　　{ 　　　　　　i=Pop(&T); Push(S,i); 　　　　　} 　　　} (4)void Demo3( CirQueue *Q) 　　　{ // 設(shè)DataType 為int 型 　　　　int x; SeqStack S; 　　　　InitStack( &S); 　　　　while (! QueueEmpty( Q )) 　　　　　{x=DeQueue( Q); Push( &S,x);} 　　　　while (! StackEmpty( &s)) 　　　　　{ x=Pop(&S); EnQueue( Q,x )

8、;} 　　　}// Demo3 (5) CirQueue Q1, Q2; // 設(shè)DataType 為int 型 　　int x, i , n= 0; 　　... // 設(shè)Q1已有內(nèi)容， Q2已初始化過(guò) 　　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)程序段的功能是將一棧中的

9、元素按反序重新排列，也就是原來(lái)在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。 　　(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。 　　(3)程序段的功能是利用棧T，將一個(gè)非空棧S中值等于m的元素全部刪去。 　　(4)程序段的功能是將一個(gè)循環(huán)隊(duì)列Q經(jīng)過(guò)S棧的處理，反向排列，原來(lái)的隊(duì)頭變成隊(duì)尾，原來(lái)的隊(duì)尾變成隊(duì)頭。 　　(5)這段程序的功能是將隊(duì)列1的所有元素復(fù)制到隊(duì)列2中去，但其執(zhí)行過(guò)程是先把隊(duì)列1的元素全部出隊(duì)，進(jìn)入隊(duì)列2，然后再把隊(duì)列2的元素復(fù)制到隊(duì)列1中。 二、算法設(shè)計(jì)題 3.6 回文是指正讀反讀均相同的

10、字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)? 解：根據(jù)提示，算法可設(shè)計(jì)為： 　//以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義 　#define StackSize 100 //假定預(yù)分配的?？臻g最多為100個(gè)元素 　typedef char DataType;//假定棧元素的數(shù)據(jù)類型為字符 　typedef struct{ 　　DataType data[StackSize]; 　　int top; 　}SeqStack;? 　int IsHuiwen( char *t) 　　{//判斷t

11、字符向量是否為回文，若是，返回1，否則返回0 　　　SeqStack s; 　　　int i , len; 　　　char temp; 　　　InitStack( &s); 　　　len=strlen(t); //求向量長(zhǎng)度 　　　for ( i=0; i

12、　else i++; 　　　　}? 　　　return 1 ; // 比較完畢均相等則返回 1 　　} 3.7 利用棧的基本操作，寫一個(gè)將棧S中所有結(jié)點(diǎn)均刪去的算法void ClearStack( SeqStack *S)，并說(shuō)明S為何要作為指針參數(shù)?? 解：?算法如下 　　void ClearStack (SeqStack *S) 　　　{ // 刪除棧中所有結(jié)點(diǎn) 　　　　S->Top = -1; //其實(shí)只是將棧置空 　　　}? 　　因?yàn)橐每盏氖菞，如果不用指針來(lái)做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對(duì)原來(lái)的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)存中開辟另外的單元來(lái)對(duì)形參進(jìn)行函數(shù)操作

13、。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來(lái)做參數(shù)傳遞了。 3.8 利用棧的基本操作， 寫一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法 int StackSize( SeqStack S),并說(shuō)明S為何不作為指針參數(shù)?? 解：算法如下： 　　int StackSize (SeqStack S) 　　　{//計(jì)算棧中結(jié)點(diǎn)個(gè)數(shù) 　　　　int n=0; 　　　　if(!EmptyStack(&S)) 　　　　　{ 　　　　　　Pop(&S); 　　　　　　n++; 　　　　　} 　　　　return n; 　　　} 　　上述算法的目的只要得到S棧的結(jié)點(diǎn)個(gè)數(shù)

14、就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對(duì)原來(lái)的棧中元素進(jìn)行任何改變。系統(tǒng)會(huì)把原來(lái)的棧按值傳遞給形參，函數(shù)只對(duì)形參進(jìn)行操作，最后返回元素個(gè)數(shù)。 3.9 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì)。 (提示： 對(duì)表達(dá)式進(jìn)行掃描，凡遇到'('就進(jìn)棧，遇')'就退掉棧頂?shù)?('，表達(dá)式被掃描完畢，棧應(yīng)為空。? 解：根據(jù)提示，可以設(shè)計(jì)算法如下： 　int PairBracket( char *SR) 　　{//檢查表達(dá)式ST中括號(hào)是否配對(duì) 　　　int i; 　　　SeqStack S; //定義一個(gè)棧 　　　InitStack (&s); 　　　for (i=0

15、; i

16、間內(nèi)實(shí)現(xiàn)的兩個(gè)棧，它們的棧底分別設(shè)在向量空間的兩端。 試為此雙向棧設(shè)計(jì)初始化InitStack ( S ) 、入棧Push( S , i , x) 和出棧Pop( S , i )等算法， 其中i為0 或1， 用以表示棧號(hào)。? 解：雙向棧其實(shí)和單向棧原理相同，只是在一個(gè)向量空間內(nèi)，好比是兩個(gè)頭對(duì)頭的棧放在一起，中間的空間可以充分利用。雙向棧的算法設(shè)計(jì)如下： 　//雙向棧的棧結(jié)構(gòu)類型與以前定義略有不同 　#define StackSize 100 // 假定分配了100個(gè)元素的向量空間 　#define char DataType 　typedef struct{ 　? DataTyp

17、e Data[StackSize] ??? int top0; //需設(shè)兩個(gè)指針 　　int top1; 　}DblStack 　void InitStack( DblStack *S ) 　　{ //初始化雙向棧 　　　S->top0 = -1; 　　　S->top1 = StackSize; //這里的top2也指出了向量空間，但由于是作為棧底，因此不會(huì)出錯(cuò) 　　}? 　int EmptyStack( DblStack *S, int i ) 　　{ //判?？?棧號(hào) i) 　　　　return (i == 0 && S->top0 == -1|| i == 1 &&

18、 S->top1== StackSize) ; 　　} 　int FullStack( DblStack *S) 　　{ //判棧滿,滿時(shí)肯定兩頭相遇 　　　return (S->top0 == S-top1-1); 　　} 　void Push(DblStack *S, int i, DataType x) 　　{ //進(jìn)棧(棧號(hào)i) 　　　if (FullStack( S )) 　　　　Error("Stack overflow");//上溢、退出運(yùn)行 　　　if ( i == 0) S->Data[ ++ S->top0]= x; //棧0入棧 　　　if ( i

19、== 1) S->Data[ -- S->top1]= x; // 棧1入棧 　　} 　DataType Pop(DblStack *S, int i) 　　{ //出棧(棧號(hào)i) 　　　if (EmptyStack ( S,i) ) 　　　　Error("Stack underflow");//下溢退出 　　　if( i==0 )? 　　　　return ( S->Data[ S->top0--] );//返回棧頂元素，指針值減1 　　　if( i==1 ) 　　　　return ( S->Data[ S->top1++] ); //因?yàn)檫@個(gè)棧是以另一端為底的，所以指針值加

20、1。 　　} 3.11 Ackerman 函數(shù)定義如下：請(qǐng)寫出遞歸算法。? 　　　　　　　　┌ n+1　　　 當(dāng)m=0時(shí)? AKM ( m , n ) = │ AKM( m-1 ,1) 當(dāng)m≠0 ，n=0時(shí)? 　　　　　　　　└ AKM( m-1, AKM( m,n-1)) 當(dāng)m≠0, n ≠ 0時(shí)? 解：算法如下 　　int AKM( int m, int n) 　　　{ 　　　　if ( m== 0) return n+1; 　　　　if ( m<>0 && n==0 ) return AKM( m-1, 1); 　　　　if ( m<>0 && n<>0 ) r

21、eturn AKM( m-1, AKM( m, n-1)); 　　　} 3.12 用第二種方法 ，即少用一個(gè)元素空間的方法來(lái)區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試為其設(shè)計(jì)置空隊(duì)，判隊(duì)空，判隊(duì)滿、出隊(duì)、入隊(duì)及取隊(duì)頭元素等六個(gè)基本操作的算法。? 解：算法設(shè)計(jì)如下: ? //循環(huán)隊(duì)列的定義 ? #define QueueSize 100? 　typedef char Datatype ; //設(shè)元素的類型為char型 　typedef struct { 　　int front; 　　int rear; 　　DataType Data[QueueSize]; ? }CirQueue; ?

22、 (1)置空隊(duì) 　　void InitQueue ( CirQueue *Q) 　　　{ // 置空隊(duì) 　　　　Q->front=Q->rear=0; 　　　} 　(2)判隊(duì)空 　　int EmptyQueue( CirQueue *Q) 　　　{ //判隊(duì)空 　　　　return Q->front==Q->rear; 　　　} 　(3)判隊(duì)滿 　　int FullQueue( CirQueue *Q) 　　　{ // 判隊(duì)滿//如果尾指針加1后等于頭指針，則認(rèn)為滿 　　　　return (Q->rear+1)%QueueSize== Q->front; 　　　}

23、 　(4)出隊(duì) 　　DataType DeQueue( CirQueue *Q) 　　　{ //出隊(duì) 　　　　DataType temp; 　　　　if(EmptyQueue(Q)) 　　　　　Error("隊(duì)已空，無(wú)元素可以出隊(duì)"); 　　　　temp=Q->Data[Q->front] ;//保存元素值 　　　　Q->front= ( Q->front+1 ) %QueueSize;//循環(huán)意義上的加1 　　　　return temp; //返回元素值 　　　} 　(5)入隊(duì) 　　void EnQueue (CirQueue *Q, DataType x) 　　　{

24、 // 入隊(duì) 　　　　if( FullQueue( Q)) 　　　　　Error ("隊(duì)已滿，不可以入隊(duì)"); 　　　　Q->Data[Q->rear]=x;? 　　　　Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一個(gè)空元素位置 　　　} 　(6)取隊(duì)頭元素 　　DataType FrontQueue( CirQueue *Q) 　　　{ //取隊(duì)頭元素 　　　　if (EmptyQueue( Q)) 　　　　　Error( "隊(duì)空，無(wú)元素可取"); 　　　　return Q->Data[Q->front]; 　　　} 3.13

25、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針) ，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空 、入隊(duì)和出隊(duì)等算法。? 解：算法如下： 　//先定義鏈隊(duì)結(jié)構(gòu): 　typedef struct queuenode{ 　　　Datatype data; 　　　struct queuenode *next; 　　}QueueNode; //以上是結(jié)點(diǎn)類型的定義 　typedef struct{ 　　　queuenode *rear; 　　}LinkQueue; //只設(shè)一個(gè)指向隊(duì)尾元素的指針 　(1)置空隊(duì) 　　void InitQueue( LinkQ

26、ueue *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ì)中元素逐個(gè)出隊(duì) 　　　　　{s=Q->rear->next; 　　　　　　Q->rear->next=s->next; 　　　　　　free(s); 　　　　　}//回收結(jié)點(diǎn)空間 　　　} 　(2)判隊(duì)空? 　　int EmptyQueue( LinkQueue *Q) 　　　{ //判隊(duì)空 　　　　

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

28、　　Q->rear=p;//將尾指針移至新結(jié)點(diǎn) 　　　} 　(4)出隊(duì) 　　Datatype DeQueue( LinkQueue *Q) 　　　{//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下 　　　　Datatype t; 　　　　QueueNode *p; 　　　　if(EmptyQueue( Q )) 　　　　　　Error("Queue underflow"); 　　　　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ì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)

29、點(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)p 　　　　free(p);//釋放被刪結(jié)點(diǎn) 　　　　return x; 　　　} 3.14 對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出求隊(duì)列長(zhǎng)度的公式。? 解： 　　公式如下(設(shè)采用第二種方法，front指向真正的隊(duì)首元素，rear指向真正隊(duì)尾后一位置，向量空間大?。篞ueueSize 　　　　Queuelen=(QueueSize+rear-

30、front)%QueueSize 3.15 假設(shè)循環(huán)隊(duì)列中只設(shè)rear和quelen 來(lái)分別指示隊(duì)尾元素的位置和隊(duì)中元素的個(gè)數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法，要求出隊(duì)時(shí)需返回隊(duì)頭元素。? 解：根據(jù)題意，可定義該循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)： 　#define QueueSize 100? 　typedef char Datatype ; //設(shè)元素的類型為char型 　typedef struct { 　　　int quelen; 　　　int rear; 　　　Datatype Data[QueueSize]; 　　}CirQueue;? 　Cir

31、Queue *Q; 　　循環(huán)隊(duì)列的隊(duì)滿條件是：Q->quelen==QueueSize 　　知道了尾指針和元素個(gè)數(shù)，當(dāng)然就能計(jì)算出隊(duì)頭元素的位置。算法如下： 　(1)判斷隊(duì)滿 　　　int FullQueue( CirQueue *Q) 　　　　{//判隊(duì)滿,隊(duì)中元素個(gè)數(shù)等于空間大小 　　　　　　return Q->quelen==QueueSize; 　　　　} 　(2)入隊(duì) 　　　void EnQueue( CirQueue *Q, Datatype x) 　　　　{// 入隊(duì) 　　　　　if(FullQueue( Q)) 　　　　　　Error("隊(duì)已滿，

32、無(wú)法入隊(duì)"); 　　　　　Q->Data[Q->rear]=x; 　　　　　Q->rear=(Q->rear+1)%QueueSize;//在循環(huán)意義上的加1 　　　　　Q->quelen++; 　　　　} 　(3)出隊(duì) 　　　Datatype DeQueue( CirQueue *Q) 　　　　{//出隊(duì) 　　　　　if(Q->quelen==0) 　　　　　　Error("隊(duì)已空，無(wú)元素可出隊(duì)"); 　　　　　int tmpfront; //設(shè)一個(gè)臨時(shí)隊(duì)頭指針 　　　　　tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//計(jì)算頭指針位置 　　　　　Q->quelen--; 　　　　　return Q->Data[tmpfront]; 　　　　}