2021第三章 棧和隊列習題答案

《2021第三章 棧和隊列習題答案》由會員分享，可在線閱讀，更多相關《2021第三章 棧和隊列習題答案（19頁珍藏版）》請在裝配圖網上搜索。

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

2、序列為：1324 (2)不能得到1423序列。因為要得到14的出棧序列，則應做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種排列中，可通過相應入出棧操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

3、 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2 鏈棧中為何不設置頭結點? 答：鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。 3.3 循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿? 答：循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的"假上溢"現象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設一布爾變量來區(qū)別隊列的空和滿

4、。二是少用一個元素的空間,每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設置一計數器記錄隊列中元素總數，不僅可判別空或滿，還可以得到隊列中元素的個數。 3.4 設長度為n的鏈隊用單循環(huán)鏈表表示，若設頭指針，則入隊出隊操作的時間為何? 若只設尾指針呢? 答：當只設頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指元素，所以出隊時不需要遍歷整個隊列。 3.5 指出下述程序段的功能是什么? (1) void Demo1

5、(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i} //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,

6、x); } (3) void Demo2( SeqStack *S, int m) { // 設DataType 為int 型 SeqStack 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; Init

7、Stack( &S); while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s)) { x=Pop(&S); EnQueue( Q,x );} }// Demo3 (5) CirQueue Q1, Q2; // 設DataType 為int 型 int x, i , n= 0; ... // 設Q1已有內容，Q2已初始化過 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} f

8、or (i=0; i{ x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂的元素放到棧底，棧底的元素放到棧頂。此棧中元素個數限制在64個以內。 (2)程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去。 (3)程序段的功能是利用棧T，將一個非空棧S中值等于m的元素全部刪去。 (4)程序段的功能是將一個循環(huán)隊列Q經過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。 (5)這段程序的功能是將隊列1的所有元素復制

9、到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2，然后再把隊列2的元素復制到隊列1中。 二、算法設計題 3.6 回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 解：根據提示，算法可設計為： //以下為順序棧的存儲結構定義 #define StackSize 100 //假定預分配的?？臻g最多為100個元素 typedef char DataType;//假定棧元素的數據類型為字符 typedef struct{ DataType data[Sta

10、ckSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判斷t字符向量是否為回文，若是，返回1，否則返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量長度 for ( i=0; iPush( &s, t[i]); while( !EmptyStack( &s)) {// 每彈出一個字符與相應字符比較 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等則返回0 else

11、i++; } return 1 ; // 比較完畢均相等則返回1 } 3.7 利用棧的基本操作，寫一個將棧S中所有結點均刪去的算法void ClearStack( SeqStack *S)，并說明S為何要作為指針參數? 解：算法如下 void ClearStack (SeqStack *S) { // 刪除棧中所有結點 S->Top = -1; //其實只是將棧置空 } 因為要置空的是棧S，如果不用指針來做參數傳遞，那么函數進行的操作不能對原來的棧產生影響，系統(tǒng)將會在內存中開辟另外的單元來對形參進行函數操作。結果等于什么也沒有做。所以想要把函數操作的結果返回給實參的話，就只

12、能用指針來做參數傳遞了。 3.8 利用棧的基本操作，寫一個返回S中結點個數的算法int StackSize( SeqStack S),并說明S為何不作為指針參數? 解：算法如下： int StackSize (SeqStack S) {//計算棧中結點個數 int n=0; if(!EmptyStack(&S)) { Pop(&S); n++; } return n; } 上述算法的目的只要得到S棧的結點個數就可以了。并不能改變棧的結構。所以S不用指針做參數，以避免對原來的棧中元素進行任何改變。系統(tǒng)會把原來的棧按值傳遞給形參，函數只對形參進行操作，最后返回元素個數。

13、 3.9 設計算法判斷一個算術表達式的圓括號是否正確配對。(提示：對表達式進行掃描，凡遇到(就進棧，遇)就退掉棧頂的(，表達式被掃描完畢，棧應為空。 解：根據提示，可以設計算法如下： int PairBracket( char *SR) {//檢查表達式ST中括號是否配對 int i; SeqStack S; //定義一個棧 InitStack (&s); for (i=0; i{ if ( S[i]==( ) Push(&S, SR[i]); //遇(時進棧 if ( S[i]==) ) //遇) if (!StackEmpty(S))//棧不為空時，將棧頂元素出棧 P

14、op(&s); else return 0;//不匹配，返回0 } if EmptyStack(&s) return 1;// 匹配，返回1 else return 0;//不匹配，返回0 } 3.10 一個雙向棧S是在同一向量空間內實現的兩個棧，它們的棧底分別設在向量空間的兩端。試為此雙向棧設計初始化InitStack ( S ) 、入棧Push( S , i , x) 和出棧Pop( S , i )等算法，其中i為0 或1，用以表示棧號。 解：雙向棧其實和單向棧原理相同，只是在一個向量空間內，好比是兩個頭對頭的棧放在一起，中間的空間可以充分利用。雙向棧的算法設計如下： //

15、雙向棧的棧結構類型與以前定義略有不同 #define StackSize 100 // 假定分配了100個元素的向量空間 #define char DataType typedef struct{ DataType Data[StackSize] int top0; //需設兩個指針 int top1; }DblStack void InitStack( DblStack *S ) { //初始化雙向棧 S->top0 = -1; S->top1 = StackSize; //這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯 } int EmptySta

16、ck( 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); } void Push(DblStack *S, int i, DataType x) { //進棧(棧號i) if (FullStack( S )) Error("Stack overflow");//上溢、退出

17、運行 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");//下溢退出 if( i==0 ) return ( S->Data[ S->top0--] );//返回棧頂元素，指針值減1 if( i==1 ) return ( S->Data[ S->top

18、1++] ); //因為這個棧是以另一端為底的，所以指針值加1。 } 3.11 Ackerman 函數定義如下：請寫出遞歸算法。 ┌ n+1當m=0時 AKM ( m , n ) = │ AKM( m-1 ,1) 當m≠0 ，n=0時 └ AKM( m-1, AKM( m,n-1)) 當m≠0, n ≠ 0時 解：算法如下 int AKM( int m, int n) { if ( m== 0) return n+1; if ( mif ( m} 3.12 用第二種方法，即少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設計置空隊，判隊空，判隊滿、出隊、入隊及取隊

19、頭元素等六個基本操作的算法。 解：算法設計如下: //循環(huán)隊列的定義 #define QueueSize 100 typedef char Datatype ; //設元素的類型為char型 typedef struct { int front; int rear; DataType Data[QueueSize]; }CirQueue; (1)置空隊 void InitQueue ( CirQueue *Q) { // 置空隊 Q->front=Q->rear=0; } (2)判隊空 int EmptyQueue( CirQueue *Q) { //判隊空

20、 return Q->front==Q->rear; } (3)判隊滿 int FullQueue( CirQueue *Q) { // 判隊滿//如果尾指針加1后等于頭指針，則認為滿 return (Q->rear+1)%QueueSize== Q->front; } (4)出隊 DataType DeQueue( CirQueue *Q) { //出隊 DataType temp; if(EmptyQueue(Q)) Error("隊已空，無元素可以出隊"); temp=Q->Data[Q->front] ;//保存元素值 Q->front= ( Q->fron

21、t+1 ) %QueueSize;//循環(huán)意義上的加1 return temp; //返回元素值 } (5)入隊 void EnQueue (CirQueue *Q, DataType x) { // 入隊 if( FullQueue( Q)) Error ("隊已滿，不可以入隊"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一個空元素位置} (6)取隊頭元素 DataType FrontQueue( CirQueue *Q) { //取隊頭元素 if (EmptyQueue( Q))

22、 Error( "隊空，無元素可取"); return Q->Data[Q->front]; } 3.13 假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素站點(注意不設頭指針) ，試編寫相應的置空隊、判隊空、入隊和出隊等算法。 解：算法如下： //先定義鏈隊結構: typedef struct queuenode{ Datatype data; struct queuenode *next; }QueueNode; //以上是結點類型的定義 typedef struct{ queuenode *rear; }LinkQueue; //只設一個指向隊尾元素

23、的指針 (1)置空隊 void InitQueue( LinkQueue *Q) { //置空隊：就是使頭結點成為隊尾元素 QueueNode *s; Q->rear = Q->rear->next;//將隊尾指針指向頭結點 while (Q->rear!=Q->rear->next)//當隊列非空，將隊中元素逐個出隊 {s=Q->rear->next; Q->rear->next=s->next; free(s); }//回收結點空間 } (2)判隊空 int EmptyQueue( LinkQueue *Q) { //判隊空 //當頭結點的next指針指向自己

24、時為空隊 return Q->rear->next->next==Q->rear->next; } (3)入隊 void EnQueue( LinkQueue *Q, Datatype x) { //入隊 //也就是在尾結點處插入元素 QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申請新結點 p->data=x; p->next=Q->rear->next;//初始化新結點并鏈入 Q-rear->next=p; Q->rear=p;//將尾指針移至新結點 } (4)出隊 Datatype DeQueue

25、( LinkQueue *Q) {//出隊,把頭結點之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error("Queue underflow"); p=Q->rear->next->next; //p指向將要摘下的結點 x=p->data; //保存結點中數據 if (p==Q->rear) {//當隊列中只有一個結點時，p結點出隊后，要將隊尾指針指向頭結點 Q->rear = Q->rear->next; Q->rear->next=p->next;} else Q->rear->next->next=p

26、->next;//摘下結點p free(p);//釋放被刪結點 return x; } 3.14 對于循環(huán)向量中的循環(huán)隊列，寫出求隊列長度的公式。 解： 公式如下(設采用第二種方法，front指向真正的隊首元素，rear指向真正隊尾后一位置，向量空間大?。篞ueueSize Queuelen=(QueueSize+rear-front)%QueueSize 3.15 假設循環(huán)隊列中只設rear和quelen 來分別指示隊尾元素的位置和隊中元素的個數，試給出判別此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊頭元素。 解：根據題意，可定義該循環(huán)隊列的存儲結構

27、： #define QueueSize 100 typedef char Datatype ; //設元素的類型為char型 typedef struct { int quelen; int rear; Datatype Data[QueueSize]; }CirQueue; CirQueue *Q; 循環(huán)隊列的隊滿條件是：Q->quelen==QueueSize 知道了尾指針和元素個數，當然就能計算出隊頭元素的位置。算法如下： (1)判斷隊滿 int FullQueue( CirQueue *Q) {//判隊滿,隊中元素個數等于空間大小 return Q->que

28、len==QueueSize; } (2)入隊 void EnQueue( CirQueue *Q, Datatype x) {// 入隊 if(FullQueue( Q)) Error("隊已滿，無法入隊"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize;//在循環(huán)意義上的加1 Q->quelen++; } (3)出隊 Datatype DeQueue( CirQueue *Q) {//出隊 if(Q->quelen==0) Error("隊已空，無元素可出隊"); int tmpfront; //設一個臨時隊頭指針 tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//計算頭指針位置 Q->quelen--; return Q->Data[tmpfront]; }