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

1、第3章棧和隊(duì)列習(xí)題練習(xí)答案3.1 設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問(wèn)題： (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?并說(shuō)明為什么不能得到或者如何得到。 (3)請(qǐng)分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過(guò)相應(yīng)的入出棧操作得到的。 答：(1)出棧序列為：13

2、24    (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種排列中，可通過(guò)相應(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é)點(diǎn)?答：    鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(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ì)列

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

5、開始查找，找到最后一個(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(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已做過(guò)初始化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已初始化過(guò)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)程序段的功能是將一棧中的元素按反序重新排列，也就是原來(lái)在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。(2)程序段的功能是利用t

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

10、半字符入棧) 解：根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素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); /求向量長(zhǎng)度f(wàn)o

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

12、Stack *S) / 刪除棧中所有結(jié)點(diǎn)S->Top = -1; /其實(shí)只是將棧置空 因?yàn)橐每盏氖菞，如果不用指針來(lái)做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對(duì)原來(lái)的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)存中開辟另外的單元來(lái)對(duì)形參進(jìn)行函數(shù)操作。結(jié)果等于什么也沒(méi)有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來(lái)做參數(shù)傳遞了。3.8 利用棧的基本操作， 寫一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法 int StackSize( SeqStack S),并說(shuō)明S為何不作為指針參數(shù)? 解：算法如下：int StackSize (SeqStack S)/計(jì)算棧中結(jié)點(diǎn)個(gè)數(shù)int n=0;if(!Empt

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

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

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

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

17、S->top1= StackSize) ;int FullStack( DblStack *S) /判棧滿,滿時(shí)肯定兩頭相遇return (S->top0 = S-top1-1);void Push(DblStack *S, int i, DataType x) /進(jìn)棧(棧號(hào)i)if (FullStack( S )Error("Stack overflow");/上溢、退出運(yùn)行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) /出棧(棧號(hào)i)if (EmptyStack ( S,i) )Error("Stack underflow");/下溢退出if( i=0 ) return ( S->Data S->top0- );/返回棧頂元素，指針值減1if( i=1 )return ( S->Data S->top1+ ); /因?yàn)檫@個(gè)棧是以另一端為底的，所以指針值加1。3.11 Ackerman 函數(shù)定義如下：請(qǐng)寫出遞歸算法。  n+1 當(dāng)m=0時(shí) AKM ( m , n ) = AKM

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

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

21、Q) /判隊(duì)空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ì)已空，無(wú)元素可以出隊(duì)");temp=Q->DataQ->front ;/保存元素值Q->front= ( Q->front

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

23、隊(duì)空，無(wú)元素可取");return Q->DataQ->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 queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是結(jié)點(diǎn)類型的定義typedef structqueuenode *rear;LinkQueue; /只設(shè)一個(gè)指向隊(duì)尾元素的指針(1)置空隊(duì)void InitQueue(

24、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指針指向自己時(shí)為空隊(duì)return Q->rear->n

25、ext->next=Q->rear->next;(3)入隊(duì)void EnQueue( LinkQueue *Q, Datatype x) /入隊(duì)/也就是在尾結(jié)點(diǎn)處插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申請(qǐng)新結(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( LinkQueue *Q)/出隊(duì),把頭結(jié)點(diǎn)之

26、后的元素摘下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->next;/摘下結(jié)點(diǎn)pfree(p);/釋放被刪結(jié)點(diǎn)return x;3.14 對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出求隊(duì)列長(zhǎng)度的公式。 解：公式如下(設(shè)采用第二種方法，front指向真正的隊(duì)首