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

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

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

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種排列中，可通過相應(yīng)入出棧操作得到的序列是： 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 鏈棧中為何不設(shè)置頭結(jié)點(diǎn)? 答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對頭結(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ì)列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿

4、。二是少用一個(gè)元素的空間,每次入隊(duì)前測試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。 3.4 設(shè)長度為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 指出下述程序段的功能是什么? (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; ...//假設(shè)棧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) { // 設(shè)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) { // 設(shè)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; // 設(shè)DataType 為int 型 int x, i , n= 0; ... // 設(shè)Q1已有內(nèi)容，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)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?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)過S棧的處理，反向排列，原來的隊(duì)頭變成隊(duì)尾，原來的隊(duì)尾變成隊(duì)頭。 (5)這段程序的功能是將隊(duì)列1的所有元素復(fù)制

9、到隊(duì)列2中去，但其執(zhí)行過程是先把隊(duì)列1的元素全部出隊(duì)，進(jìn)入隊(duì)列2，然后再把隊(duì)列2的元素復(fù)制到隊(duì)列1中。 二、算法設(shè)計(jì)題 3.6 回文是指正讀反讀均相同的字符序列，如"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[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)) {// 每彈出一個(gè)字符與相應(yīng)字符比較 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等則返回0 else

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

12、能用指針來做參數(shù)傳遞了。 3.8 利用棧的基本操作，寫一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法int StackSize( SeqStack S),并說明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ù)就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對原來的棧中元素進(jìn)行任何改變。系統(tǒng)會(huì)把原來的棧按值傳遞給形參，函數(shù)只對形參進(jìn)行操作，最后返回元素個(gè)數(shù)。

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

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

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

16、ck( DblStack *S, int i ) { //判?？?棧號i) return (i == 0 && S->top0 == -1|| i == 1 && S->top1== StackSize) ; } int FullStack( DblStack *S) { //判棧滿,滿時(shí)肯定兩頭相遇 return (S->top0 == S-top1-1); } void Push(DblStack *S, int i, DataType x) { //進(jìn)棧(棧號i) if (FullStack( S )) Error("Stack overflow");//上溢、退出

17、運(yùn)行 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++] ); //因?yàn)檫@個(gè)棧是以另一端為底的，所以指針值加1。 } 3.11 Ackerman 函數(shù)定義如下：請寫出遞歸算法。 ┌ 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 ( mif ( m} 3.12 用第二種方法，即少用一個(gè)元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試為其設(shè)計(jì)置空隊(duì)，判隊(duì)空，判隊(duì)滿、出隊(duì)、入隊(duì)及取隊(duì)

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

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

21、t+1 ) %QueueSize;//循環(huán)意義上的加1 return temp; //返回元素值 } (5)入隊(duì) void EnQueue (CirQueue *Q, DataType x) { // 入隊(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))

22、 Error( "隊(duì)空，無元素可取"); return Q->Data[Q->front]; } 3.13 假設(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ì)尾元素

23、的指針 (1)置空隊(duì) void InitQueue( 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ì)中元素逐個(gè)出隊(duì) {s=Q->rear->next; Q->rear->next=s->next; free(s); }//回收結(jié)點(diǎn)空間 } (2)判隊(duì)空 int EmptyQueue( LinkQueue *Q) { //判隊(duì)空 //當(dāng)頭結(jié)點(diǎn)的next指針指向自己

24、時(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));//申請新結(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ì) Datatype DeQueue

25、( 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é)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn) Q->rear = Q->rear->next; Q->rear->next=p->next;} else Q->rear->next->next=p

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

27、： #define QueueSize 100 typedef char Datatype ; //設(shè)元素的類型為char型 typedef struct { int quelen; int rear; Datatype Data[QueueSize]; }CirQueue; CirQueue *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->que

28、len==QueueSize; } (2)入隊(duì) void EnQueue( CirQueue *Q, Datatype x) {// 入隊(duì) if(FullQueue( Q)) Error("隊(duì)已滿，無法入隊(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ì)已空，無元素可出隊(duì)"); int tmpfront; //設(shè)一個(gè)臨時(shí)隊(duì)頭指針 tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//計(jì)算頭指針位置 Q->quelen--; return Q->Data[tmpfront]; }