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

1、第三章 棧和隊列習(xí)題答案一、基礎(chǔ)知識題3.1 設(shè)將整數(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種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。 答：(1)出棧序列為：1324(2)不能得到1423序列。因

2、為要得到14的出棧序列，則應(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,

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

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

5、arrn+=Pop(S);for (i=0, i n; i+) Push(S, arri); /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, x);(3) void Demo2( SeqStack *S, int m) / 設(shè)DataType 為int 型SeqStack T; int i;In

6、itStack (&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;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(

7、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+;for (i=0; i n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);答：(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個數(shù)限制在64個以內(nèi)。(2)程序段的功能是利用tmp棧將一

8、個非空棧s1的所有元素按原樣復(fù)制到一個棧s2當中去。(3)程序段的功能是利用棧T，將一個非空棧S中值等于m的元素全部刪去。(4)程序段的功能是將一個循環(huán)隊列Q經(jīng)過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。(5)這段程序的功能是將隊列1的所有元素復(fù)制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2，然后再把隊列2的元素復(fù)制到隊列1中。二、算法設(shè)計題3.6 回文是指正讀反讀均相同的字符序列，如abba和abdba均是回文，但good不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)解：根據(jù)提示，算法可設(shè)計為：/以下為順序棧的存儲結(jié)構(gòu)定義

9、#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; iTop = -1; /其實只是將棧置空因為要置空的是棧S，如果不用指針來做參數(shù)傳

10、遞，那么函數(shù)進行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)將會在內(nèi)存中開辟另外的單元來對形參進行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實參的話，就只能用指針來做參數(shù)傳遞了。3.8 利用棧的基本操作， 寫一個返回S中結(jié)點個數(shù)的算法 int StackSize( SeqStack S),并說明S為何不作為指針參數(shù)?解：算法如下：int StackSize (SeqStack S)/計算棧中結(jié)點個數(shù)int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;上述算法的目的只要得到S棧的結(jié)點個數(shù)就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對

11、原來的棧中元素進行任何改變。系統(tǒng)會把原來的棧按值傳遞給形參，函數(shù)只對形參進行操作，最后返回元素個數(shù)。3.9 設(shè)計算法判斷一個算術(shù)表達式的圓括號是否正確配對。 (提示： 對表達式進行掃描，凡遇到(就進棧，遇)就退掉棧頂?shù)?，表達式被掃描完畢，棧應(yīng)為空。解：根據(jù)提示，可以設(shè)計算法如下：int PairBracket( char *SR)/檢查表達式ST中括號是否配對int i;SeqStack S; /定義一個棧InitStack (&s);for (i=0; itop0 = -1;S-top1 = StackSize; /這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯 int E

12、mptyStack( 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);/上溢、退出運行if ( i = 0) S-Data + S-top0= x; /棧0

13、入棧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- );/返回棧頂元素，指針值減1if( i=1 )return ( S-Data S-top1+ ); /因為這個棧是以另一端為底的，所以指針值加1。 3.11 Ackerman 函數(shù)定義如下：請寫出遞歸算法。 n+1 當m=0時AKM ( m , n ) = AKM(

14、m-1 ,1) 當m0 ，n=0時 AKM( m-1, AKM( m,n-1) 當m0, n 0時解：算法如下int AKM( int m, int n)if ( m= 0) return n+1;if ( m0 & n=0 ) return AKM( m-1, 1);if ( m0 & n0 ) return AKM( m-1, AKM( m, n-1);3.12 用第二種方法 ，即少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設(shè)計置空隊，判隊空，判隊滿、出隊、入隊及取隊頭元素等六個基本操作的算法。解：算法設(shè)計如下:/循環(huán)隊列的定義#define QueueSize 100type

15、def char Datatype ; /設(shè)元素的類型為char型typedef struct int front;int rear;DataType DataQueueSize;CirQueue;(1)置空隊void InitQueue ( CirQueue *Q) / 置空隊Q-front=Q-rear=0;(2)判隊空int EmptyQueue( CirQueue *Q) /判隊空return Q-front=Q-rear;(3)判隊滿int FullQueue( CirQueue *Q) / 判隊滿/如果尾指針加1后等于頭指針，則認為滿 return (Q-rear+1)%Queue

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

17、ear+1)%QueueSize; /rear 指向下一個空元素位置 (6)取隊頭元素DataType FrontQueue( CirQueue *Q) /取隊頭元素if (EmptyQueue( Q)Error( 隊空，無元素可取);return Q-DataQ-front;3.13 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素站點(注意不設(shè)頭指針) ，試編寫相應(yīng)的置空隊、判隊空 、入隊和出隊等算法。解：算法如下：/先定義鏈隊結(jié)構(gòu):typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode;

18、/以上是結(jié)點類型的定義typedef structqueuenode *rear;LinkQueue; /只設(shè)一個指向隊尾元素的指針(1)置空隊void InitQueue( LinkQueue *Q) /置空隊：就是使頭結(jié)點成為隊尾元素QueueNode *s;Q-rear = Q-rear-next;/將隊尾指針指向頭結(jié)點while (Q-rear!=Q-rear-next)/當隊列非空，將隊中元素逐個出隊s=Q-rear-next;Q-rear-next=s-next;free(s);/回收結(jié)點空間(2)判隊空int EmptyQueue( LinkQueue *Q) /判隊空/當頭結(jié)點

19、的next指針指向自己時為空隊return Q-rear-next-next=Q-rear-next;(3)入隊void EnQueue( LinkQueue *Q, Datatype x) /入隊/也就是在尾結(jié)點處插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申請新結(jié)點p-data=x; p-next=Q-rear-next;/初始化新結(jié)點并鏈入Q-rear-next=p;Q-rear=p;/將尾指針移至新結(jié)點(4)出隊Datatype DeQueue( LinkQueue *Q)/出隊,把頭結(jié)點之后的元素摘下Dataty

20、pe t;QueueNode *p;if(EmptyQueue( Q )Error(Queue underflow);p=Q-rear-next-next; /p指向?qū)⒁碌慕Y(jié)點x=p-data; /保存結(jié)點中數(shù)據(jù)if (p=Q-rear)/當隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點Q-rear = Q-rear-next; Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下結(jié)點pfree(p);/釋放被刪結(jié)點return x;3.14 對于循環(huán)向量中的循環(huán)隊列，寫出求隊列長度的公式。解：公式如下(設(shè)采用第二種方法，front指向真正的隊首元素，rear指向真正隊尾后一位置，向量空間大?。篞ueueSizeQueuelen=(QueueSize+rear-front)%QueueSize3.15 假設(shè)循環(huán)隊列中只設(shè)rear和quelen 來分別指示隊尾元素的位置和隊中元素的個數(shù)