中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法第3章棧和隊列課后作業(yè)答案

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

2、24    (2)不能得到1423序列。因為要得到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,

3、2134,2143,2314,2341,2431,3214,3241,3421,4321      不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2 鏈棧中為何不設(shè)置頭結(jié)點?答：    鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進(jìn)行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。3.3 循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿? 答：循環(huán)隊列的優(yōu)點是：它可以克服順序隊列

4、的"假上溢"現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊列的空和滿。二是少用一個元素的空間,每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認(rèn)為隊列已滿。三是設(shè)置一計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。3.4 設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊出隊操作的時間為何? 若只設(shè)尾指針呢? 答：當(dāng)只設(shè)頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針

5、開始查找，找到最后一個元素時方可進(jìn)行入隊操作。若只設(shè)尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針?biāo)傅南乱粋€元素就是頭指針?biāo)冈?，所以出隊時不需要遍歷整個隊列。3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假設(shè)棧tmp和S2已做過初始化while ( ! Sta

6、ckEmpty (&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;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 );/ Demo3(5) CirQueue Q1, Q2; / 設(shè)DataType 為int 型int x, i

8、, 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)程序段的功能是利用t

9、mp棧將一個非空棧s1的所有元素按原樣復(fù)制到一個棧s2當(dāng)中去。(3)程序段的功能是利用棧T，將一個非空棧S中值等于m的元素全部刪去。(4)程序段的功能是將一個循環(huán)隊列Q經(jīng)過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。(5)這段程序的功能是將隊列1的所有元素復(fù)制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進(jìn)入隊列2，然后再把隊列2的元素復(fù)制到隊列1中。3.6 回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一

10、半字符入棧) 解：根據(jù)提示，算法可設(shè)計為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的棧空間最多為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); /求向量長度fo

11、r ( i=0; i<len/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si)  return 0 ;/ 不等則返回0else i+; return 1 ; / 比較完畢均相等則返回 13.7 利用棧的基本操作，寫一個將棧S中所有結(jié)點均刪去的算法void ClearStack( SeqStack *S)，并說明S為何要作為指針參數(shù)? 解： 算法如下void ClearStack (Seq

12、Stack *S) / 刪除棧中所有結(jié)點S->Top = -1; /其實只是將棧置空 因為要置空的是棧S，如果不用指針來做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)將會在內(nèi)存中開辟另外的單元來對形參進(jìn)行函數(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(!Empt

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

14、是否配對int i;SeqStack S; /定義一個棧InitStack (&s);for (i=0; i<strlen(SR) ; i+) if ( Si='(' ) Push(&S, SRi); /遇'('時進(jìn)棧if ( Si=')' ) /遇')'if (!StackEmpty(S)/棧不為空時，將棧頂元素出棧Pop(&s);else return 0;/不匹配，返回0if EmptyStack(&s) return 1;/ 匹配，返回1else return 0;/不匹配，

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

16、60; DataType DataStackSize    int top0; /需設(shè)兩個指針int top1;DblStackvoid InitStack( DblStack *S ) /初始化雙向棧S->top0 = -1;S->top1 = StackSize; /這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯 int EmptyStack( DblStack *S, int i ) /判?？?棧號 i)return (i = 0 && S->top0 = -1| i = 1 &&

17、S->top1= StackSize) ;int FullStack( DblStack *S) /判棧滿,滿時肯定兩頭相遇return (S->top0 = S-top1-1);void Push(DblStack *S, int i, DataType x) /進(jìn)棧(棧號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入棧Dat

18、aType 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 當(dāng)m=0時 AKM ( m , n ) = AKM

19、( m-1 ,1) 當(dāng)m0 ，n=0時  AKM( m-1, AKM( m,n-1) 當(dāng)m0, n 0時 解：算法如下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 ) return AKM( m-1, AKM( m, n-1);3.12 用第二種方法 ，即少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設(shè)計置空隊，判隊空，判隊滿、出隊、入隊及取隊

20、頭元素等六個基本操作的算法。 解：  算法設(shè)計如下:  /循環(huán)隊列的定義  #define QueueSize 100 typedef 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 *

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

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

23、隊空，無元素可取");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; /以上是結(jié)點類型的定義typedef structqueuenode *rear;LinkQueue; /只設(shè)一個指向隊尾元素的指針(1)置空隊void InitQueue(

24、LinkQueue *Q) /置空隊：就是使頭結(jié)點成為隊尾元素QueueNode *s;Q->rear = Q->rear->next;/將隊尾指針指向頭結(jié)點while (Q->rear!=Q->rear->next)/當(dāng)隊列非空，將隊中元素逐個出隊s=Q->rear->next;Q->rear->next=s->next;free(s);/回收結(jié)點空間(2)判隊空 int EmptyQueue( LinkQueue *Q) /判隊空/當(dāng)頭結(jié)點的next指針指向自己時為空隊return Q->rear->n

25、ext->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é)點之

26、后的元素摘下Datatype 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)/當(dāng)隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點Q->rear = Q->rear->next; Q->rear->next=p->next;else Q->rear->next->next=p->next;/摘下結(jié)點pfree(p);/釋放被刪結(jié)點return x;3.14 對于循環(huán)向量中的循環(huán)隊列，寫出求隊列長度的公式。 解：公式如下(設(shè)采用第二種方法，front指向真正的隊首