第三章 棧與隊列 習題及答案

1、第三章 棧與隊列 習題及答案一、基礎知識題3.1 設將整數(shù)1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：(1)若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何(這里Push(i)表示i進棧，Pop( )表示出棧)?(2) 能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。(3)請分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應的入出棧操作得到的。3.2 鏈棧中為何不設置頭結點?答：鏈棧不需要在頭部附加

2、頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。3.3 循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿?答：循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的"假上溢"現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設一布爾變量來區(qū)別隊列的空和滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設置一計數(shù)器記錄隊列中元素總數(shù)，不僅可判

3、別空或滿，還可以得到隊列中元素的個數(shù)。3.4 設長度為n的鏈隊用單循環(huán)鏈表表示，若設頭指針，則入隊出隊操作的時間為何? 若只設尾指針呢?答：當只設頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指元素，所以出隊時不需要遍歷整個隊列。3.5 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0

4、, i< n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假設棧tmp和S2已做過初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(3) void Demo2( SeqStack *S, int m) / 設DataType 為int 型SeqStack

5、T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);(4)void Demo3( CirQueue *Q) / 設DataType 為int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &am

6、p;s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 設DataType 為int 型int x, i , m = 0;. / 設Q1已有內(nèi)容， Q2已初始化過while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m+;for (i=0; i< n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);二、算法設計題3.6 回文是指

7、正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)3.7 利用棧的基本操作，寫一個將棧S中所有結點均刪去的算法void ClearStack( SeqStack *S)，并說明S為何要作為指針參數(shù)?3.8 利用棧的基本操作， 寫一個返回S中結點個數(shù)的算法 int StackSize( SeqStack S),并說明S為何不作為指針參數(shù)?3.9 設計算法判斷一個算術表達式的圓括號是否正確配對。 (提示： 對表達式進行掃描，凡遇到&#

8、39;('就進棧，遇')'就退掉棧頂?shù)?#39;('，表達式被掃描完畢，棧應為空。3.10 一個雙向棧S是在同一向量空間內(nèi)實現(xiàn)的兩個棧，它們的棧底分別設在向量空間的兩端。 試為此雙向棧設計初始化InitStack ( S ) 、入棧Push( S , i , x) 和出棧Pop( S , i )等算法， 其中i為0 或1， 用以表示棧號。3.11 Ackerman 函數(shù)定義如下：請寫出遞歸算法。 n+1 當m=0時AKM ( m , n ) = AKM( m-1 ,1) 當m0 ，n=0時 AKM( m-1, AKM( m,n-1) 當m0, n 0時3.12

9、用第二種方法 ，即少用一上元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設計置空隊，判隊空，判隊滿、出隊、入隊及取隊頭元素等六個基本操作的算法。3.13 假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素站點(注意不設頭指針) ，試編寫相應的置空隊、判隊空 、入隊和出隊等算法。3.14 對于循環(huán)向量中的循環(huán)隊列，寫出求隊列長度的公式。3.15 假設循環(huán)隊列中只設rear和quelen 來分別指示隊尾元素的位置和隊中元素的個數(shù)，試給出判別此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊頭元素。答案：3.2 答：鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作

10、的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。3.3 答：循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的"假上溢"現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設一布爾變量來區(qū)別隊列的空和滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設置一計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。3.4答：當只設頭指針時，出隊的時間為

11、1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指元素，所以出隊時不需要遍歷整個隊列。3.5 答： (1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個數(shù)限制在64個以內(nèi)。(2)程序段的功能是利用tmp棧將一個非空棧的所有元素按原樣復制到一個空棧當中去。(3)程序段的功能是將一個非空棧中值等于m的元素全部刪去。(4)程序段的功能是將一個循環(huán)隊列反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。(5)首先指

12、出程序可能有印刷錯誤，for語句中的n應為m才對。這段程序的功能是將隊列1的所有元素復制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2，然后再把隊列2的元素復制到隊列1中。3.6 解：根據(jù)提示，算法可設計為：/ishuiwen.h 存為頭文件int IsHuiwen( char *S)SeqStack T;int i , l;char t;InitStack( &T);l=strlen(S); /求向量長度for ( i=0; i<l/2; i+) /將一半字符入棧 Push( &T, Si);while( !EmptyStack( &T)/ 每

13、彈出一個字符與相應字符比較 t=Pop (&T);if( t!=Sl-i) return 0 ;/ 不等則返回0 i-;return -1 ; / 比較完畢均相等則返回 -1 / 以下程序用于驗證上面的算法/以下是棧定義( 存為stack.h)/出錯控制函數(shù)#include <stdlib.h>#include <stdio.h>void Error(char * message)fprintf(stderr, "Error: %sn",message); exit(1);/ 定義棧類型#define StackSize 100typedef

14、 char Datatype;typedef structDatatype dataStackSize;int Top; SeqStack;void InitStack( SeqStack *S)/初始化(置空棧)S->Top=-1;int EmptyStack(SeqStack *S) /判?？誶eturn S->Top = -1; int FullStack (SeqStack *S) / 判棧滿return S->Top=StackSize-1; void Push (SeqStack *S , Datatype x) /進棧if(FullStack(S)Error(&

15、quot;Stack overflow"); S->data+S->Top=x; Datatype Pop(SeqStack *S) / 出棧(退棧)if (EmptyStack( S) )Error( "Stack underflow"); return S->dataS->Top-; /取棧頂元素(略)/- /以下是主程序#include <string.h>#include <malloc.h>#include "stack.h>#include "ishuiwen.h"vo

16、id main( )char Str100=""printf("輸入一個字符串:n"); scanf("%s",Str);if( IsHuiwen(Str)printf(" n這個字符串是回文。");else printf("n這個字符串不是回文。");3.7解： 算法如下void ClearStack (SeqStack *S) / 刪除棧中所有結點S->Top = -1; /其實只是將棧置空因為我們要置空的是棧S，如果不用指針來做參數(shù)傳遞，那么函數(shù)進行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)

17、將會在內(nèi)存中開辟另外的單元來對形參進行函數(shù)操作。結果等于什么也沒有做。所以想要把函數(shù)操作的結果返回給實參的話，就只能用指針來做參數(shù)傳遞了。3.8 解：算法如下：int StackSize (SeqStack S)/計算棧中結點個數(shù)int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;類似于上面的原因，我們要計算棧中元素個數(shù)就要彈出元素才能"數(shù)"得出來，那如果用指針做參數(shù)的話，就會把原來的棧中元素"彈"光，要恢復還得用別的辦法給它裝回去，而不用指針做參數(shù)，則可以避免對原來的棧中元素進行任何操作，系統(tǒng)會把

18、原來的棧按值傳遞給形參，函數(shù)只對形參進行操作，最后返回元素個數(shù)就可以了。3.9 解：根據(jù)提示，可以設計算法如下：#include <string.h>#include "stack.h"int PairBracket( char *S)/檢查表達式中括號是否配對int i;SeqStack T; /定義一個棧InitStack (&T);for (i=0; i<strlen(S) ; i+)if ( Si='(' ) Push(&T, Si); /遇'('時進棧if ( Si=')' ) Po

19、p(&T); /遇')'時出棧return !EmptyStack(&T); / 由棧空否返回正確配對與否3.10 解：雙向棧其實和單向棧原理相同，只是在一個向量空間內(nèi)，好比是兩個頭對頭的棧放在一起，中間的空間可以充分利用。雙向棧的算法設計如下：/雙向棧的棧結構類型與以前定義略有不同#define StackSize 100 / 假定分配了100個元素的向量空間#define char Datatypetypedef structDatatype DataStackSizeint top0; /需設兩個指針int top1;DblStackvoid InitSt

20、ack( DblStack *S ) /初始化雙向棧S->top0 = -1;S->top1 = StackSize; /這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯int EmptyStack( DblStack *S, int i ) /判棧空(棧號 i)return (i = 0 && S->top0 = -1| i = 1 && S->top1= StackSize) ;int FullStack( DblStack *S) /判棧滿,滿時肯定兩頭相遇return (S->top0 = S-top1-1);

21、void Push(DblStack *S, int i, Datatype x) /進棧(棧號i)if (FullStack( S )Error("Stack overflow");/上溢、退出運行if ( i = 0) S->Data + S->top0= x; /棧0入棧if ( i = 1) S->Data - S->top1= x; / 棧1入棧Datatype Pop(DblStack *S, int i) /出棧(棧號i)if (EmptyStack ( S,i) )Error("Stack underflow");

22、/下溢退出if( i=0 )return ( S->Data S->top0- );/返回棧頂元素，指針值減1if( i=1 )return ( S->Data S->top1+ ); /因為這個棧是以另一端為底的，所以指針值加1。 /其余算法略 ,以上算法沒有上機調(diào)試過，請學友自行驗證一下。主要是我們理解了算法也就可以了。3.11 解：算法如下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 &

23、amp;& n<>0 ) return AKM( m-1, AKM( m, n-1);3.12 解：算法設計如下:/存為Queue2.h文件void InitQueue ( CirQueue *Q) / 置空隊Q->front=Q->rear=0;int EmptyQueue( CirQueue *Q) /判隊空return Q->front=Q->rear;int FullQueue( CirQueue *Q) / 判隊滿/如果尾指針加1后等于頭指針，則認為滿return (Q->rear+1)%QueueSize= Q->front;

24、Datatype DeQueue( CirQueue *Q) /出隊if(EmptyQueue(Q)Error("隊已空，無元素可以出隊");Datatype temp;temp=Q->DataQ->front ;/保存元素值Q->front= ( Q->front+1 ) %QueueSize;/循環(huán)意義上的加1return temp; /返回元素值void EnQueue (CirQueue *Q, Datatype x) / 入隊if( FullQueue( Q)Error ("隊已滿，不可以入隊");Q->DataQ

25、->rear=x;Q->rear=(Q->rear+1)%QueueSize; /rear 指向下一個空元素位置 Datatype FrontQueue( CirQueue *Q) /取隊頭元素if (EmptyQueue( Q)Error( "隊空，無元素可取");return Q->DataQ->front;/為了驗證上述算法是否正確，曉津設計了以下程序/循環(huán)隊列的定義 存入StructQ.h文件中#define QueueSize 10 /為便與驗證，這里假設為10個元素的空間 typedef char Datatype ; /設元素的類

26、型為char型typedef struct int front;int rear;Datatype DataQueueSize;CirQueue;/以下是主程序,用來驗證算法#include <stdio.h>#include <string.h>#include "StrctQ.h" / 包含隊列結構#include "Queue2.h"/包含算法頭文件/-出錯控制程序#include <stdlib.h>void Error(char * message)fprintf(stderr, "Error: %

27、sn",message);exit(1);/-主函數(shù)-void main( )int i;CirQueue Q;/ 定義一個循環(huán)隊列InitQueue( &Q );/初始化隊列printf("please enter characters:n");for (i=0; i< QueueSize-1 ; i+)EnQueue(&Q, getchar();printf("n");if(!EmptyQueue(&Q) /先輸出一個頭元素printf("frontData is %c", FrontQue

28、ue(&Q);printf("n");while(!EmptyQueue(&Q) /如果非空就把隊列中的元素輸出printf("%c",DeQueue(&Q);printf("nPlease enter characters again:n");for(i=0; i<QueueSize ; i+) /執(zhí)行后將產(chǎn)生上溢出錯，為什么呢?EnQueue(&Q, getchar();/上機時可以輸入字符，也可以直接輸入回車的次數(shù)來驗證，注意：一個回車也是一個字符。3.13 解：算法如下：/先定義鏈隊結構:

29、typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是結點類型的定義typedef structqueuenode *rear;LinkQueue; /只設一個指向隊尾元素的指針/linkQ.h 相應算法void InitQueue( LinkQueue *Q) /置空隊：就是使頭結點成為隊尾元素Q->rear = Q->rear->next;/頭結點成為尾結點Q->rear->next = Q->rear;/形成循環(huán)鏈表int EmptyQueue( Link

30、Queue *Q) /判隊空/當頭結點的next指針指向自己時為空隊return Q->rear->next->next=Q->rear->next;void EnQueue( LinkQueue *Q, Datatype x) /入隊/也就是在尾結點處插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申請新結點 p->data=x; p->next=NULL;/初始化結點Q-rear->next->next=p; / 將新結點鏈入p->next=Q->rear; /形成循環(huán)鏈表Q->r