第3章_棧和隊(duì)列(1) (1)

1、第三章 棧和隊(duì)列(1)(1)郭大慶郭大慶 電子科技大學(xué)生命科學(xué)與技術(shù)學(xué)院電子科技大學(xué)生命科學(xué)與技術(shù)學(xué)院神經(jīng)信神經(jīng)信息教育部重點(diǎn)實(shí)驗(yàn)室息教育部重點(diǎn)實(shí)驗(yàn)室約瑟夫問題15個(gè)教徒和個(gè)教徒和15 個(gè)非教徒在深海上遇險(xiǎn)，必須個(gè)非教徒在深海上遇險(xiǎn)，必須將一半的人投入海中，其余的人才能幸免于將一半的人投入海中，其余的人才能幸免于難，于是想了一個(gè)辦法：難，于是想了一個(gè)辦法：30個(gè)人圍成一圓圈個(gè)人圍成一圓圈，從第一個(gè)人開始依次報(bào)數(shù)，每數(shù)到第九個(gè)，從第一個(gè)人開始依次報(bào)數(shù)，每數(shù)到第九個(gè)人就將他扔入大海，如此循環(huán)進(jìn)行直到僅余人就將他扔入大海，如此循環(huán)進(jìn)行直到僅余15個(gè)人為止。問怎樣排法，才能使每次投入個(gè)人為止。問怎樣排

2、法，才能使每次投入大海的都是非教徒。大海的都是非教徒。第三章 棧和隊(duì)列 本章學(xué)習(xí)兩種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它們特殊在定本章學(xué)習(xí)兩種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它們特殊在定義的操作不同，即插入和刪除操作只能在線性表的兩端義的操作不同，即插入和刪除操作只能在線性表的兩端進(jìn)行。進(jìn)行。 只能在一端進(jìn)行的只能在一端進(jìn)行的- 棧棧 分別在兩端進(jìn)行的分別在兩端進(jìn)行的- 隊(duì)列隊(duì)列 線性表線性表 棧棧 隊(duì)列隊(duì)列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in內(nèi)容提要：3.4

3、隊(duì)列的定義及邏輯結(jié)構(gòu)隊(duì)列的定義及邏輯結(jié)構(gòu)3.5 循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.6 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.1 3.1 棧的定義及邏輯結(jié)構(gòu)：定義和邏輯特性n特殊的線性表：操作受限n限定僅在表尾進(jìn)行插入或刪除操作的線性表,允許插入或刪除的一端稱為棧頂(top),另一端稱為棧底(bottom)n老派觀點(diǎn)認(rèn)為棧是“下推表” n新派觀點(diǎn)認(rèn)為棧底不動(dòng) - n元素插入棧稱為“入?！被颉皦簵！保╬ush）n刪除元素稱為“出?！被颉皬棾觥保╬op）進(jìn)棧進(jìn)棧 出棧出棧an.a1棧頂棧頂棧底棧底一個(gè)有關(guān)入棧、出棧的習(xí)題例題：假設(shè)有例題：假設(shè)有A ， B

4、, C , D 四個(gè)元素；它們?nèi)霔５拇涡驗(yàn)樗膫€(gè)元素；它們?nèi)霔５拇涡驗(yàn)锳 B C D，出，出棧次序任意，請問不可能得到下面哪些出棧序列？棧次序任意，請問不可能得到下面哪些出棧序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D( 5 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D 答案：答案：( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D( 5 ) A C B D ( 6 ) D B A C ( 7 ) A D C

5、 B ( 8 ) C A B D 棧的ADTADT描述ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象：D = ai | ai屬于屬于Elemset, (i=1,2,n, n0) 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 = ai-1,ai|ai-1,ai屬于屬于D,(i=2,3,n) 約定約定an 為棧頂為棧頂, a1為棧底。為棧底。 基本操作基本操作 (9個(gè)個(gè))： InitStack(&S); DestroyStack(&S); ClearStack(&S); StackEmpty(S); StackLength(S) ; GetTop(S,&e); Push(&S,e);

6、Pop(&S,&e); StackTraverse(S,visit () ADT Stack棧的四個(gè)重要基本操作 初始條件：棧初始條件：棧s不存在。不存在。 操作結(jié)果：構(gòu)造了一個(gè)空棧。操作結(jié)果：構(gòu)造了一個(gè)空棧。 初始條件：棧初始條件：棧s已存在已存在 。 操作結(jié)果：在棧操作結(jié)果：在棧s的頂部插入一個(gè)新元素的頂部插入一個(gè)新元素e， e成為新的棧頂成為新的棧頂 元素。棧發(fā)生變化。元素。棧發(fā)生變化。 初始條件：棧初始條件：棧s存在且非空。存在且非空。 操作結(jié)果：將棧操作結(jié)果：將棧s的棧頂元素從棧中刪除，并用的棧頂元素從棧中刪除，并用e返回其值。棧發(fā)返回其值。棧發(fā) 生變化。生變化。 初

7、始條件：棧初始條件：棧s存在且非空。存在且非空。 操作結(jié)果：讀棧頂元素并用操作結(jié)果：讀棧頂元素并用e返回其值。棧不變化。返回其值。棧不變化。棧是一種特殊的線性表，因此棧也可采用兩種存儲(chǔ)結(jié)構(gòu)：棧是一種特殊的線性表，因此棧也可采用兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序棧p 順序棧的存儲(chǔ)結(jié)構(gòu)順序棧的存儲(chǔ)結(jié)構(gòu)順序棧是指順序棧是指，即利用一組，即利用一組的數(shù)據(jù)元素，同時(shí)附設(shè)指針的數(shù)據(jù)元素，同時(shí)附設(shè)指針，指示指示在順序棧中的在順序棧中的。棧頂棧頂(top) 棧底棧底(base)棧中元素?cái)?shù)目：棧中元素?cái)?shù)目：n = top - base順序棧p 類型定義（類型定義（） 注意注意to

8、p的含義的含義約定約定 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct ElemType *base; ElemType*top; int stacksize; SqStack;順序棧的基本操作：構(gòu)建一個(gè)空棧S SStatus InitStack(SqStack *s) s.base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s.base) return(OVERFLOW); s.top = s.base; s.stack

9、size = STACK_INIT_SIZE; return OK; /* InitStack */順序棧的基本操作：進(jìn)棧操作Status Push(SqStack *s, SElemType e) if (s.top s.base = s.stacksize) l_temp=(SElemType*)realloc (s.base,(s.stacksize+STACKINCREMENT) *sizeof(SElemType); if (!l_temp) return(OVERFLOW); s.base = l_temp; s.top = s.base + s.stacksize; s.stac

10、ksize += STACKINCREMENT; *(s.top+) = e; return OK; / /* Push */順序棧的基本操作：出棧操作 Status Pop(SqStack *s, SElemType *e) if (s.top = s.base) return ERROR; *e = *(-s.top); return OK; /* Pop */順序棧的基本操作：取( (棧頂) )元素 Status GetTop(SqStack *s, SElemType *e) if (s.top = s.base) return ERROR; *e = *(s.top-1); retu

11、rn OK; /* Pop */鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（概略）n鏈棧鏈棧: :同一般線性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)基本相同。但是應(yīng)同一般線性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)基本相同。但是應(yīng)該確定鏈表的哪端對應(yīng)于棧頂，如果鏈表尾作為棧頂，則該確定鏈表的哪端對應(yīng)于棧頂，如果鏈表尾作為棧頂，則入、出棧操作的時(shí)間復(fù)雜性為入、出棧操作的時(shí)間復(fù)雜性為O( n ) . n無棧滿問題(除非分配不出內(nèi)存), 空間可擴(kuò)充n棧頂-鏈表的表頭n可以不必引入頭結(jié)點(diǎn)n入棧相當(dāng)于在單鏈表的第一個(gè)結(jié)點(diǎn)之前進(jìn)行插入操作n出棧相當(dāng)于在單鏈表中刪除第一個(gè)結(jié)點(diǎn)/* 鏈棧結(jié)點(diǎn)鏈棧結(jié)點(diǎn)*/typedef struct StackNode SElemType

12、data; struct StackNode *next; StackNode,*LinkStackPtr;鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)/* 構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S */Status InitStack(LinkStack *S) S-top=NULL; /將棧頂指向空，表示為空棧將棧頂指向空，表示為空棧 S-count=0; return OK;/* 鏈棧頭指針鏈棧頭指針*/typedef struct LinkStackPtr top; int count; LinkStack;鏈棧結(jié)構(gòu)鏈棧結(jié)構(gòu) Status Push(LinkStack *S,SElemType e) LinkStackP

13、tr s=(LinkStackPtr)malloc(sizeof(StackNode); s-data=e; s-next=S-top; S-top=s S-count+; return OK;自己考慮出棧自己考慮出棧的操作怎樣實(shí)現(xiàn)的操作怎樣實(shí)現(xiàn)順序棧和鏈棧的比較，以及為什么要用棧？n順序棧和鏈棧的比較：順序棧和鏈棧的比較：n順序棧和鏈棧的進(jìn)棧push和出棧pop操作；n順序棧需要事先確定一個(gè)固定的長度，可能會(huì)存在內(nèi)存；n鏈棧要求，這也會(huì)，但棧的了； 棧的使用過程中，棧的使用過程中，。n為什么要用棧：為什么要用棧：n棧的引入，。n此外，許多高級(jí)語言，比如Java、C#等都有對棧結(jié)構(gòu)的封裝，可以

14、直接使用棧的push和pop方法，非常方便。在n非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成其它進(jìn)制的數(shù)的一種簡單方法：n轉(zhuǎn)換原理：N=(N div d)*d + N mod d div整除，mod求余q例，十進(jìn)制轉(zhuǎn)換成八進(jìn)制：(66)10=(102)8 結(jié)果為余數(shù)的逆序結(jié)果為余數(shù)的逆序( (出棧順序出棧順序) )：n先求得的余數(shù)在寫出結(jié)果時(shí)最后寫出，最后求出的余數(shù)最先寫出，先求得的余數(shù)在寫出結(jié)果時(shí)最后寫出，最后求出的余數(shù)最先寫出，符合棧的先入后出性質(zhì)，故可用棧來實(shí)現(xiàn)數(shù)制轉(zhuǎn)換。符合棧的先入后出性質(zhì)，故可用棧來實(shí)現(xiàn)數(shù)制轉(zhuǎn)換。n同理，一個(gè)非負(fù)十進(jìn)制整數(shù)同理，一個(gè)非負(fù)十進(jìn)制整數(shù)N N轉(zhuǎn)換為另一個(gè)等價(jià)的基為轉(zhuǎn)換為另一個(gè)等價(jià)的基

15、為B B的的B B進(jìn)制數(shù)，進(jìn)制數(shù)，可以采用可以采用 來解決來解決 20166/8=8 66/8=8 余余 2 28/8=1 8/8=1 余余 0 01/8=0 1/8=0 余余 1 1void conversion() InitStack(&s); /初始化一個(gè)空棧初始化一個(gè)空棧 scanf(“%d”,&N); while(N) Push(&s, N%8); /將余數(shù)依次壓入棧將余數(shù)依次壓入棧 N = N/8; /做整除得到下一次求余操作的整數(shù)做整除得到下一次求余操作的整數(shù) while(!StackEmpty(s) /判斷是否為空棧判斷是否為空棧 Pop(&s,

16、&e); /若不為空，將棧頂元素出棧若不為空，將棧頂元素出棧 printf(“%d”,e); /* conversion */數(shù)制轉(zhuǎn)換算法：數(shù)制轉(zhuǎn)換算法：n中綴表達(dá)式：中綴表達(dá)式：n運(yùn)算符在中間n需要括號(hào)改變優(yōu)先級(jí)n 9+(3-1)3+10/2n后綴表達(dá)式（逆波蘭法）后綴表達(dá)式（逆波蘭法）n運(yùn)算符在后面n完全不需要括號(hào)n9 3 1- 3 * + 10 2 / + 運(yùn)算規(guī)則：依次順序讀入表達(dá)式的符號(hào)序列（假設(shè)以作為輸入序運(yùn)算規(guī)則：依次順序讀入表達(dá)式的符號(hào)序列（假設(shè)以作為輸入序列的結(jié)束），并根據(jù)讀入的元素符號(hào)逐一分析：列的結(jié)束），并根據(jù)讀入的元素符號(hào)逐一分析： 當(dāng)遇到的是一個(gè)操作數(shù)，則壓入

17、棧頂； 當(dāng)遇到的是一個(gè)運(yùn)算符, 就從棧中兩次取出棧頂，按照運(yùn)算符對這兩個(gè)操作數(shù)進(jìn)行計(jì)算。然后將計(jì)算結(jié)果壓入棧頂。 如此繼續(xù)，直到結(jié)束如此繼續(xù)，直到結(jié)束, 這時(shí)棧頂?shù)闹稻褪禽斎氡磉_(dá)式的值這時(shí)棧頂?shù)闹稻褪禽斎氡磉_(dá)式的值 后綴表達(dá)式后綴表達(dá)式: 9 3 1- 3 * + 10 2 / +3-1=22*3=69+6=1510/2=515+5=20空棧空棧一個(gè)關(guān)鍵問題：如何將一個(gè)關(guān)鍵問題：如何將？答案：可以通過答案：可以通過來完成轉(zhuǎn)換。來完成轉(zhuǎn)換。 轉(zhuǎn)換規(guī)則：從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào)，并做以下轉(zhuǎn)換規(guī)則：從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào)，并做以下操作：操作：1.若是若是，即成為后綴表達(dá)

18、式的一部分；，即成為后綴表達(dá)式的一部分；2.若是若是，則，則。 如此繼續(xù)，一直到最終輸出后綴表達(dá)式為止。如此繼續(xù)，一直到最終輸出后綴表達(dá)式為止。99 3 19 3 1 -9 3 1 3 *+9 3 1 3 *+109 3 1 3 *+10 29 3空棧空棧9 3 1 - 3# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # $(x, y)=(0, 0)01234567890 1 2 3 4 5 6 7 8 9 求迷宮中一條從

19、入口到出口的路徑的算法可簡單描述如下求迷宮中一條從入口到出口的路徑的算法可簡單描述如下:設(shè)定當(dāng)前位置的初值為入口位置設(shè)定當(dāng)前位置的初值為入口位置:do 若當(dāng)前位置可通若當(dāng)前位置可通,則則 將當(dāng)前位置插入堆棧頂將當(dāng)前位置插入堆棧頂; 若該位置是出口位置若該位置是出口位置,則結(jié)束則結(jié)束; 否則切換當(dāng)前位置的東鄰塊為新的當(dāng)前位置否則切換當(dāng)前位置的東鄰塊為新的當(dāng)前位置; 否則否則 若堆棧不空且棧頂位置尚有其他方向未經(jīng)探索若堆棧不空且棧頂位置尚有其他方向未經(jīng)探索; 則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向轉(zhuǎn)到的棧頂位置的下一相則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向轉(zhuǎn)到的棧頂位置的下一相 鄰塊鄰塊; 若棧不空但棧頂位置

20、的四周均不可通若棧不空但棧頂位置的四周均不可通, 則則 刪去棧頂位置刪去棧頂位置; 若棧不空若棧不空,則重新測試新的棧頂位置則重新測試新的棧頂位置, 直至找到一個(gè)可通的相鄰或出棧至?？罩敝琳业揭粋€(gè)可通的相鄰或出棧至棧空; (棧不空棧不空)遞歸：在高級(jí)語言中，調(diào)用自己和其他函數(shù)并沒有本質(zhì)的不同。我遞歸：在高級(jí)語言中，調(diào)用自己和其他函數(shù)并沒有本質(zhì)的不同。我們把們把。遞歸。遞歸。 求階乘時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)當(dāng)當(dāng) 1 ,)!1( 0 , 1!nnnnn求解階乘函數(shù)的遞歸算法求解階乘函數(shù)的遞歸算法: 1. long fact ( long n ) 2. if ( n = 0 ) return 1; / 3. e

21、lse return n * fact (n- -1); 4. main( ): fact(4)參參數(shù)數(shù)傳傳遞遞結(jié)結(jié)果果返返回回 fact(4): fact(3): fact(2): fact(1): fact(0): 1直接定值為直接定值為1 1計(jì)算計(jì)算 4*fact(3)計(jì)算計(jì)算 3*fact(2)計(jì)算計(jì)算 2*fact(1)計(jì)算計(jì)算 1*fact(0)12624以主程序中調(diào)用以主程序中調(diào)用FACT(4)(4)為例：為例：n: 4控制鏈返回地址控制鏈返回地址第第1次調(diào)用次調(diào)用fact時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄x: 4主程序主程序main的的活動(dòng)記錄活動(dòng)記錄棧生長方向棧生長方向棧生長方向棧生長

22、方向n: 4控制鏈返回地址控制鏈返回地址第第1次調(diào)用次調(diào)用fact時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄x: 4主程序主程序main的的活動(dòng)記錄活動(dòng)記錄n: 3控制鏈返回地址控制鏈返回地址第第2次調(diào)用次調(diào)用fact時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄棧生長方向棧生長方向n: 4控制鏈返回地址控制鏈返回地址第第1次調(diào)用次調(diào)用fact 時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄x: 4主程序主程序main 的活動(dòng)記錄的活動(dòng)記錄n: 3控制鏈返回地址控制鏈返回地址第第2次調(diào)用次調(diào)用fact 時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄n: 2控制鏈返回地址控制鏈返回地址n: 1控制鏈返回地址控制鏈返回地址第第3次調(diào)用次調(diào)用fact 時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄第第4次調(diào)用次調(diào)用fact 時(shí)的活動(dòng)記錄時(shí)的活動(dòng)記錄自由空間自由空間1! = 12! = 2*1! =