《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)第三章_棧和隊(duì)列

1、1,通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。,線性表 棧 隊(duì)列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,棧和隊(duì)列是兩種常用的數(shù)據(jù)類型,2,第三章 棧和隊(duì)列,3.1 棧,3.2 棧的應(yīng)用舉例,3.4 隊(duì)列,3.3 棧與遞歸的實(shí)現(xiàn),3,學(xué)習(xí)提要： 1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)， 并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。 2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng) 注意棧滿和棧空的條件以及它們的描述方法。 3.

2、熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn) 算法，特別注意隊(duì)滿和隊(duì)空的描述方法。 4.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。 重難點(diǎn)內(nèi)容： 順序棧的相關(guān)操作、循環(huán)隊(duì)列的判空判滿,4,3.1 棧（stack）,3.1.1 棧的類型定義,3.1.2 棧的表示和實(shí)現(xiàn),5,棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。不含元素的空表稱空棧。,特點(diǎn)：后進(jìn)先出（LIFO）,3.1.1 棧的類型定義,表尾棧頂 表頭棧底,6,ADT Stack 數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1

3、端為棧底。,基本操作：, ADT Stack,棧的抽象數(shù)據(jù)類型定義：,7,InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; SqStack;,9,實(shí)現(xiàn)：一維數(shù)組sM,進(jìn)棧Push( top=p,q=top ; top=top-next,16,3.2 棧的應(yīng)用,3.2.1 數(shù)制轉(zhuǎn)換,3.2.2 括號(hào)匹配的檢驗(yàn),3.2.3 行編輯程序問(wèn)題,3.2.4 迷宮求解,3.2.5 表達(dá)式求值,17,3.2.1 數(shù)制轉(zhuǎn)換,十進(jìn)制N和其

4、他d進(jìn)制數(shù)的轉(zhuǎn)換原理: N=( N div d )*d + N mod d 其中：div為整除運(yùn)算， mod為求余運(yùn)算,18,例如： (1348)10=(2504)8，其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,19,void conversion( ) /對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)， /打印輸出與其等值的八進(jìn)制數(shù) initstack ( S ); scanf (“%d”,N); while ( N ) push (S，N%8); N = N / 8; while ( ! Stackempty(s) ) pop

5、( S,e ); printf ( “%d”, e ); /conversion,20,3.3.2 括號(hào)匹配的檢驗(yàn),則 檢驗(yàn)括號(hào)是否匹配的方法可用 “期待的急迫程度”這個(gè)概念來(lái)描述。,假設(shè)在表達(dá)式中 （）或（ ） 等為正確的格式， （ ）或（ ）或 （）)均為不正確的格式。,21,分析可能出現(xiàn)的不匹配的情況:,到來(lái)的右括弧并非是所“期待”的；,例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8,到來(lái)的是“不速之客”；,直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧。,22,算法的設(shè)計(jì)思想：,1）凡出現(xiàn)左括弧，則進(jìn)棧；,2）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？眨瑒t表明該“右括弧”多余， 否

6、則和棧頂元素比較， 若相匹配，則“左括弧出?！?， 否則表明不匹配。,3）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若棧空，則表明表達(dá)式中匹配正確， 否則表明“左括弧”有余。,23,3.2.3 行編輯程序問(wèn)題,如何實(shí)現(xiàn)？,“每接受一個(gè)字符即存入存儲(chǔ)器” ?,不恰當(dāng)!,合理的作法是：,設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，“”為退行符。,24,假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,則實(shí)際有效的是下列兩行： while (*s) putchar(*s+);,25,while (ch != EO

7、F / 從終端接收下一個(gè)字符 ,ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF為全文結(jié)束符,將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的 數(shù)據(jù)區(qū)；,26,3.2.4 迷宮求解,通常用的是“窮舉求解”的方法。,27,求迷宮路徑算法的基本思想是：,若當(dāng)前位置“可通”，則納入路徑， 繼續(xù)前進(jìn);,若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;,若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。,28,設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算

8、法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否則 while (棧不空）；,求迷宮中一條從入口到出口的路徑的算法：, ,29,若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的棧頂位置的下一相鄰塊；,若棧不空但棧頂位置的四周均不可通， 則刪去棧頂位置；/ 從路徑中刪去該通道塊 若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?； ,若?？?，則表明迷宮沒(méi)有通路。,30,typedef struct int ord; / 通道塊在路徑上的“序號(hào)” PosType seat; / 通道塊在迷宮中 的 “坐標(biāo)位置” int di

9、; / 從此通道塊走向下一 通道塊的“方向” SElemType; / 棧的元素類型,31,Status MazePath ( MazeType maze, PosType start, PosType end ) InitStack(S); curpos = start; / 設(shè)定“當(dāng)前位置”為“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊 else while ( !StackEmpty(S) ); return (FALSE); / MazePath,32,FootPrint (curpos)

10、; e = ( curstep, curpos, 1 ); Push (S,e); / 加入路徑 if ( curpos = end ) return (TRUE); / 到達(dá)終點(diǎn) curpos = NextPos ( curpos, 1 ); / 下一位置是當(dāng)前位置的東鄰 curstep+;,33,else / 當(dāng)前位置不能通過(guò) if (!StackEmpty(S) Pop (S,e); while (e.di=4 / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 / if / if / else,34,限于二元運(yùn)算符的表達(dá)式定義: Exp = S1 OP S2 操作數(shù) : 變量、常量、表達(dá)式 運(yùn)算符

11、: 算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、 邏輯運(yùn)算符 界限符：括號(hào)、結(jié)束符,3.2.5 表達(dá)式求值,35,表達(dá)式求值的算法： 算符優(yōu)先法根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行。,36,例：3 * ( 7 2 ),3,*,(,7,2,2,7,5,*,5,3,15,37,例：3 * ( 7 2 ),OPTR棧 OPND棧 輸入 操作 1 # 3 * ( 7 2 ) # PUSH( OPND, 3 ) 2 # 3 * ( 7 2 ) # PUSH( OPTR, * ) 3 # * 3 ( 7 2 ) # PUSH( OPTR, ( ) 4 # * ( 3 7 2 ) # PUSH( OPND, 7

12、 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, ) 6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 ) 8 # * ( 3 5 ) # POP( OPTR ) 9 # * 3 5 # operate( 3, *, 5 ) 10 # 15 # return GetTop( OPND ),38,OperandType EvaluateExpression( ) / 設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。 InitStack (OPTR); Push (OPTR, #);

13、 initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是運(yùn)算符則進(jìn)棧 else / while return GetTop(OPND); / EvaluateExpression, ,39,switch ( precede(GetTop(OPTR), c) case : / 退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operat

14、e(a, theta, b); break; / switch,40,3.3 棧與遞歸的實(shí)現(xiàn),41,當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事: (1)將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存; (2)為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū); (3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。,42,從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成: (1)保存被調(diào)函數(shù)的計(jì)算結(jié)果; (2)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū); (3)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。,43,多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回 此時(shí)的內(nèi)存管理實(shí)行“棧式管理”。,遞歸過(guò)程指向過(guò)程中占用的數(shù)據(jù)區(qū)

15、， 稱之為遞歸工作棧 每一層的遞歸參數(shù)合成一個(gè)記錄， 稱之為遞歸工作記錄 棧頂記錄指示當(dāng)前層的執(zhí)行情況， 稱之為當(dāng)前活動(dòng)記錄 棧頂指針， 稱之為當(dāng)前環(huán)境指針,44,例：遞歸的執(zhí)行情況分析,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); ,運(yùn)行結(jié)果： 1， 2，2， 3，3，3，,45,遞歸調(diào)用執(zhí)行情況如下：,例：n階Hanoi問(wèn)題。 問(wèn)題描述：有X,Y,Z三個(gè)塔座，X上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔，編號(hào)1,2,3n。要求將n個(gè)圓

16、盤從X移到Z，疊放順序不變，移動(dòng)過(guò)程中遵循下列原則： (1)每次只能移一個(gè)圓盤; (2)圓盤可在三個(gè)塔座上任意移動(dòng); (3)任何時(shí)刻都不能將大盤壓到小盤上;,解決方法： n=1時(shí)，直接把圓盤從X移到Z； n1時(shí)，先把上面n-1個(gè)圓盤從X移到Y(jié)，然后將n號(hào)盤從X移到Z，再將n-1個(gè)盤從Y移到Z。即把求解n個(gè)圓盤的Hanoi問(wèn)題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問(wèn)題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問(wèn)題。,void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號(hào)為1至n / 的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔

17、助塔座。 1 2 if (n=1) 3 move(x, 1, z); / 將編號(hào)為的圓盤從x移到z 4 else 5 hanoi(n-1, x, z, y); / 將x上編號(hào)為至n-1的圓 / 盤移到y(tǒng), z作輔助塔 6 move(x, n, z); / 將編號(hào)為n的圓盤從x移到z hanoi(n-1, y, x, z); / 將y上編號(hào)為至n-1的圓 /盤移到z, x作輔助塔 8 9 ,執(zhí)行情況： 遞歸工作棧保存內(nèi)容：形參n, x, y, z和返回地址（返回地址用語(yǔ)句行號(hào)表示）。 工作記錄結(jié)構(gòu)：,void hanoi(int n,char x,char y,char z) 1 2 if(n=

18、1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 han

19、oi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,54,3.4 隊(duì)列,3.4.1 隊(duì)列的類型定義,3.4.2 鏈隊(duì)列,3.4.3 循環(huán)隊(duì)列,55,隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。,隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO),3.4.1 隊(duì)列的類型

20、定義,隊(duì)尾(rear)允許插入的一端 隊(duì)頭(front)允許刪除的一端,56,ADT Queue 數(shù)據(jù)對(duì)象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭， an 端為隊(duì)列尾,基本操作：,隊(duì)列的抽象數(shù)據(jù)類型定義：, ADT Queue,57,隊(duì)列的基本操作：,InitQueue( struct QNode *next ; QNode, *QueuePtr;,typedef struct /鏈隊(duì)列類型 QueuePtr *front ; /隊(duì)頭指針 QueuePtr *rear ; /隊(duì)尾指針

21、 LinkQueue;,3.4.2 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),59,a1,an,Q.front Q.rear,Q.front Q.rear,空隊(duì)列,60,Status InitQueue (LinkQueue ,61,Status EnQueue (LinkQueue ,62,Status DeQueue (LinkQueue ,63,3.4.3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn),#define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 SqQueue;,64,實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)baseM,J1,J2,J3,存在問(wèn)題： 當(dāng)front=0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出真溢出 當(dāng)front0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出假溢出,65,解決方案 隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)浪費(fèi)時(shí)間 循環(huán)隊(duì)列 基本思想：把隊(duì)列設(shè)想成環(huán)形，讓base0接在baseM-1 之后，若rear+1=M,則令rear=0;,實(shí)現(xiàn)：利用“?！边\(yùn)算 入隊(duì)： baserear = e; rear = (rear+1)%M;