數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列棧ppt課件

1、武漢科技大學(xué)Wuhan University of Science and Technology張 凱計算機(jī)學(xué)院 軟件工程系2019年3月12日:隊列類型的定義和實現(xiàn)第第3 3章章 棧和隊列棧和隊列棧的類型定義棧的運用舉例棧類型的實現(xiàn):3.1 棧的類型定義棧的類型定義:3.1 棧的類型定義棧的類型定義:3.1 棧的類型定義棧的類型定義:v棧表示圖棧表示圖3.1 棧的類型定義棧的類型定義 a1 a2 a3 an棧頂棧底 :v棧的相關(guān)概念棧的相關(guān)概念3.1 棧的類型定義棧的類型定義1.定義與同線性表一樣，仍為一對一關(guān)系。用順序?；蜴湕４鎯?，但以順序棧更常見只能在棧頂運算，且訪問結(jié)點時按照后進(jìn)先

2、出LIFO的原那么。關(guān)鍵是編寫入棧和出棧函數(shù)，詳細(xì)實現(xiàn)依順序?；蜴湕５牟煌煌?3.存儲構(gòu)造4.運算規(guī)那么5.實現(xiàn)方式 2.邏輯構(gòu)造限定只能在表的一端進(jìn)展插入和刪除運算的線性表只能在棧頂操作:v棧與普通線性表有什么不同棧與普通線性表有什么不同3.1 棧的類型定義棧的類型定義棧與普通線性表的區(qū)別：僅在于運算規(guī)那么不同。 普通線性表普通線性表 棧棧邏輯構(gòu)造：一對一邏輯構(gòu)造：一對一 邏輯構(gòu)造：邏輯構(gòu)造：一對一一對一存儲構(gòu)造：順序表、鏈表存儲構(gòu)造：順序表、鏈表 存儲構(gòu)造：順序存儲構(gòu)造：順序棧、鏈棧棧、鏈棧運算規(guī)那么：隨機(jī)存取運算規(guī)那么：隨機(jī)存取 運算規(guī)那運算規(guī)那么：后進(jìn)先出么：后進(jìn)先出(LIFO)

3、(LIFO)“進(jìn) 壓入=PUSHx)“出 彈出=POP ( y ):v棧的相關(guān)概念棧的相關(guān)概念3.1 棧的類型定義棧的類型定義棧 是僅在表尾進(jìn)展插入、刪除操作的線性表。表尾(即an端)稱為棧頂 Top；表頭(即a1端)稱為棧底Base例如： 棧 s = (a1, a2, a3, an-1, an) a1稱為棧底元素 an稱為棧頂元素插入元素到棧頂(即表尾)的操作，稱為入棧。從棧頂(即表尾)刪除最后一個元素的操作，稱為出棧。:v思索題思索題v一個棧的入棧序列是一個棧的入棧序列是a, b, c, d, e，那么棧，那么棧的不能夠的輸出序列是的不能夠的輸出序列是 。3.1 棧的類型定義棧的類型定義A

4、 e d c b a B d e c b a C d c e a b D a b c d e:v棧的籠統(tǒng)數(shù)據(jù)類型定義棧的籠統(tǒng)數(shù)據(jù)類型定義3.1 棧的類型定義棧的類型定義ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,.,n) 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: R=|ai-1,aiD,i=2,.,n) 商定商定an端為棧頂，端為棧頂，a1端為棧底端為棧底 根本操作：根本操作： InitStack( &S ) 操作結(jié)果：構(gòu)造空棧操作結(jié)果：構(gòu)造空棧S DestroyStack( &S ) 初始條件：棧初始條件：棧S已存在已存在 操作結(jié)果：銷毀棧操作結(jié)果：銷毀棧S

5、ClearStack( &S ) 初始條件：棧初始條件：棧S已存在已存在 操作結(jié)果：將操作結(jié)果：將S置為空棧置為空棧 StackEmpty( S ) 初始條件：棧初始條件：棧S已存在已存在 操作結(jié)果：判別棧操作結(jié)果：判別棧S能否為空棧能否為空棧 StackLength( S ) 初始條件：棧初始條件：棧S已存在已存在 操作結(jié)果：前往棧操作結(jié)果：前往棧S中元素個數(shù)中元素個數(shù)(棧長棧長) GetTop( S,&e ) 初始條件：棧初始條件：棧S已存在且非空已存在且非空 操作結(jié)果：用操作結(jié)果：用e前往前往S的棧頂元的棧頂元素素 Push( &S, e ) 初始條件：棧初始條件

6、：棧S已存在已存在 操作結(jié)果：插入元素操作結(jié)果：插入元素e為新的棧頂元素為新的棧頂元素 Pop( &S, &e ) 初始條件：棧初始條件：棧S已存在已存在 操作結(jié)果：刪除操作結(jié)果：刪除S的棧頂元素，用的棧頂元素，用e前往前往值值 ADT Stack:v棧的物理存儲棧的物理存儲v棧的物理存儲可以用順序存儲構(gòu)造，也可棧的物理存儲可以用順序存儲構(gòu)造，也可用鏈?zhǔn)酱鎯?gòu)造。相應(yīng)地，棧的存儲方式用鏈?zhǔn)酱鎯?gòu)造。相應(yīng)地，棧的存儲方式也分為兩種，即順序棧和鏈棧。也分為兩種，即順序棧和鏈棧。 3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn):v順序棧的定義順序棧的定義3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)#d

7、efine STACK_INIT_SIZE 100; / 存儲空間初始分配量#define STACKINCREMENT 10; / 存儲空間分配增量typedef struct SElemType *base; / base的初值為NULL，闡明棧構(gòu)造不存在 SElemType *top; / 棧頂指針，初值指向棧底， / 即top=base作為?？盏臉?biāo)志 int stacksize; / 當(dāng)前已分存儲空間，即指示當(dāng)前棧 / 可運用的最大容量，以元素為單位 SqStack; :v棧頂指針和棧中元素之間的關(guān)系棧頂指針和棧中元素之間的關(guān)系3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)1空棧中的棧頂指針的指

8、向和棧底指針一致2非空棧中的棧頂指針一直在棧頂元素的下一個位置AABCDABbasetopbasetopbasetopbasetop:v棧在籠統(tǒng)類型中的幾種操作舉例棧在籠統(tǒng)類型中的幾種操作舉例3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)例1：構(gòu)造一個空棧Status InitStack(SqStack &s) /構(gòu)造一個空棧S s.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemtype); If (!s.base) exit (OVERFLOW); /存儲分配失敗 s=s.base; s.stacksize= STACK_INI

9、T_SIZE; return OK; / InitStack;:v棧在籠統(tǒng)類型中的幾種操作舉例棧在籠統(tǒng)類型中的幾種操作舉例3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)例2：取棧頂元素Status GetTop(SqStack s, SElemtype &e) /假設(shè)棧不空，用e前往S的棧頂元素 if (s = = s.base) return ERROR; e = * (s - 1); /操作后s不變，并將當(dāng)前棧頂元素賦給e return OK; / GetTop;等同于刪除棧頂元素出棧，區(qū)別在于： e = * - - s; /操作后stop減，并將當(dāng)前出棧的元素賦給etopbaseACBDb

10、asetoptop-1e=D:v棧在籠統(tǒng)類型中的幾種操作舉例棧在籠統(tǒng)類型中的幾種操作舉例3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)例3：插入新棧頂元素即入棧Status Push(SqsTack & s, SElemType e) /插入元素e為新的棧頂元素 if (s - s.base = s.stacksize) /棧滿，追加存儲空間 s.base=(SElemtype *)realloc(s.base, s.stacksize + STACKINCREMENT) * sizeof( Selemtype ); if (!s.base) exit (OVERFLOW); /存儲分配失敗 s

11、 = s.base + s.stacksize; s.stacksize += STACKINCREMENT; * s + = e; /*s =e; s+;棧頂指針一直在棧頂元素的下一個位置 return OK; / Push;acbdtope:v棧在籠統(tǒng)類型中的幾種操作舉例棧在籠統(tǒng)類型中的幾種操作舉例3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)例4：刪除棧頂元素即出棧Status Pop(SqStack & s, SElemType &e) / 假設(shè)棧不空，刪除S的棧頂元素，用e前往其/ 值 ，并前往0K，否那么前往ERROR if (s = = s.base) return (ER

12、ROR); e = * - - s; /-s; e=*stop;棧頂指針一直在棧頂元素的下一位置 return OK; / Pop;topbaseERRORACBDbasetope=D:v棧的鏈?zhǔn)酱鎯?gòu)造棧的鏈?zhǔn)酱鎯?gòu)造v棧的鏈?zhǔn)酱鎯?gòu)造稱為鏈棧，它是運算是棧的鏈?zhǔn)酱鎯?gòu)造稱為鏈棧，它是運算是受限的單鏈表，插入和刪除操作僅限制在受限的單鏈表，插入和刪除操作僅限制在表頭位置上進(jìn)展。由于只能在表頭進(jìn)展操表頭位置上進(jìn)展。由于只能在表頭進(jìn)展操作，故沒必要附加頭結(jié)點，棧頂指針就是作，故沒必要附加頭結(jié)點，棧頂指針就是鏈表的頭指針。鏈表的頭指針。 3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn):v棧的鏈?zhǔn)酱鎯?gòu)造棧的

13、鏈?zhǔn)酱鎯?gòu)造3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)鏈棧表示圖 an an-1 a1 / Top棧頂棧底:v鏈棧的類型闡明如下鏈棧的類型闡明如下3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)typedef struct StackNode ElemType data struct StackNode *next StackNode; typedef struct StackNode *top LinkStack;Data next an an-1 a1 / Top:v鏈棧的根本操作鏈棧的根本操作3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)Void InitStack(LinkStack *s) /初始化鏈棧 sto

14、p=null; Int StackEmpty(LinkStack *s) /判別能否空棧 return stop=null; ElemType Gettop(LinkStack *s) /前往棧頂元素 if(StackEmpty(s) return (ERROR); return stopdata; :v鏈棧插入新棧頂元素即入棧鏈棧插入新棧頂元素即入棧3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)Status Push(LinkStack *s, ElemType e) /插入元素e為新的棧頂元素 q=(StackNode*)malloc(sizeof(StackNode); qdata=e; qnex

15、t=stop; stop=q; :v鏈棧刪除棧頂元素即出棧鏈棧刪除棧頂元素即出棧3.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)Status Pop( LinkStack *s, ElemType &e) /假設(shè)棧不空，那么刪除鏈棧棧頂元素，用e前往其值 if (StackEmpty(s) return (Error); q=stop; e=qdata; stop=qnext; free(q); return OK; :v1.數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換v2.括號匹配的檢驗括號匹配的檢驗v3.行編輯程序行編輯程序v4.迷宮求解迷宮求解v5.表達(dá)式求值表達(dá)式求值3.3 棧的運用舉例棧的運用舉例:v數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)

16、換3.3 棧的運用舉例棧的運用舉例十進(jìn)制數(shù) N 和其它 D 進(jìn)制數(shù)的轉(zhuǎn)換 N = ( N div d )d + N mod d (其中：div 為整除運算，mod 為求余運算:v數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.3 棧的運用舉例棧的運用舉例例如：(1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 8 對應(yīng)的8進(jìn)制數(shù) 1348 168 4 4 168 21 0 0 21 2 5 5 2 0 2 2:v數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.3 棧的運用舉例棧的運用舉例void Conversion ( ) / 對于輸入的恣意一個非負(fù)十進(jìn)制整數(shù)，輸出等值的八進(jìn)制數(shù) InitStack(&

17、;S); / 構(gòu)造空棧 scanf (%d,N); while (N) Push(&S, N % 8); N = N/8; while (!StackEmpty(S) Pop(&S,&e); printf ( %d, e ); / conversion:v括號匹配的檢驗括號匹配的檢驗3.3 棧的運用舉例棧的運用舉例 假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，即： 1.或 為正確格式； 2. 為錯誤格式； 3. 或 ( ) )為錯誤格式。:v括號匹配的檢驗括號匹配的檢驗3.3 棧的運用舉例棧的運用舉例思索以下括號序列： ( ) 1 2 3 4 5 6

18、 7 8 ( ( ) 分析能夠出現(xiàn)的不匹配的情況以“(為例：到來的右括弧不是所“等待的,如“；直到終了，也沒有到來右括弧“；:v算法思想算法思想3.3 棧的運用舉例棧的運用舉例1)凡出現(xiàn)左括弧，那么進(jìn)棧2)凡出現(xiàn)右括弧，首先檢查棧能否空 是：該“右括弧多余； 否：和棧頂元素比較，假設(shè)相匹配，那么“左括弧 出棧，否那么闡明不匹配；3)表達(dá)式檢驗終了時， 假設(shè)?？?，匹配正確； 否那么闡明“左括弧有余。:v括號匹配的檢驗括號匹配的檢驗3.3 棧的運用舉例棧的運用舉例status matching(string &exp) / 檢驗表達(dá)式中所含括弧能否正確嵌套， int state = 1;

19、while ( i -*/(#=21:v表達(dá)式求值表達(dá)式求值3.3 棧的運用舉例棧的運用舉例 +、-、*、/為1時的優(yōu)先性均低于“(但高于“) 當(dāng)1=2時，“#是表達(dá)式的終了符。為了算法簡約，在表達(dá)式的最左邊也虛設(shè)一個“#構(gòu)成整個表達(dá)式的一對括號 “(=“)表示括號內(nèi)的運算曾經(jīng)完成 “#=“#表示整個表達(dá)式求值終了 “)與“(、“#與“)以及“(與“#之間無優(yōu)先關(guān)系，可以為出了現(xiàn)語法錯誤:3.3 棧的運用舉例棧的運用舉例步驟OPTR棧OPND棧輸入字符主要操作1#3*(7-2)#PUSH(OPND,3)2#3 *(7-2)#PUSH(OPTR,*)3#*3 (7-2)#PUSH(OPTR,()

20、4#*(3 7-2)#PUSH(OPND,7)5#*(3 7 -2)#PUSH(OPTR,-)6#*(-3 7 2)#PUSH(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):3.3 棧的運用舉例棧的運用舉例OperandType EvaluateExpression() /設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧，OP為運算符集合 InitStack(OPTR); Push(OPTR,#); InitStack(OPND)

21、; c=getchar(); while(c!=#|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch(Precede(GetTop(OPTR),c) case : /退棧并將運算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; /switch /while return GetTop(OPND);/ EvaluateExpression:v表達(dá)式的三種標(biāo)識方法表達(dá)式的三種標(biāo)識方

22、法3.3 棧的運用舉例棧的運用舉例設(shè) Exp = S1 + OP + S2那么稱 OP + S1 + S2 為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 :例如例如: Exp = a b + (c d / e) f前綴式前綴式: + a b c / d e f中綴式中綴式: a b + c d / e f后綴式后綴式: a b c d e / f + 結(jié)論結(jié)論:1操作數(shù)之間的相對次序不變操作數(shù)之間的相對次序不變;2運算符的相對次序不同運算符的相對次序不同;3中綴式喪失了括弧信息，中綴式喪失了括弧信息， 致使運算的次序不確定致使運算的次序不確定;4

23、)前綴式的運算規(guī)那么為前綴式的運算規(guī)那么為:延續(xù)出現(xiàn)的兩個操作數(shù)和在它們延續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一之前且緊靠它們的運算符構(gòu)成一個最小表達(dá)式個最小表達(dá)式; 5)后綴式的運算規(guī)那么為后綴式的運算規(guī)那么為: 運算符在式中出現(xiàn)的順序恰為運算符在式中出現(xiàn)的順序恰為 表達(dá)式的運算順序表達(dá)式的運算順序; 每個運算符和在它之前出現(xiàn)每個運算符和在它之前出現(xiàn) 且且 緊靠它的兩個操作數(shù)構(gòu)成一個最小緊靠它的兩個操作數(shù)構(gòu)成一個最小 表達(dá)式。表達(dá)式。:v如何從后綴式求值如何從后綴式求值3.3 棧的運用舉例棧的運用舉例先找運算符，再找操作數(shù)例如： a b c d e / f +abd/ec-d

24、/e(c-d/e)f:v如何從原表達(dá)式求得后綴式如何從原表達(dá)式求得后綴式3.3 棧的運用舉例棧的運用舉例 每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數(shù)高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。分析 “原表達(dá)式 和 “后綴式中的運算符:原表達(dá)式: a + b c d / e f 后綴式: a b c + d e / f :v從原表達(dá)式求得后綴式的規(guī)律為從原表達(dá)式求得后綴式的規(guī)律為3.3 棧的運用舉例棧的運用舉例1) 設(shè)立操作數(shù)棧；2) 設(shè)表達(dá)式的終了符為“#，預(yù)設(shè)運算符棧的棧底為“#3) 假設(shè)當(dāng)前字符是操作數(shù)，那么直接發(fā)送給后綴式。4) 假設(shè)當(dāng)前運算符的優(yōu)先數(shù)高于棧頂運算符，那么進(jìn)

25、棧；5) 否那么，退出棧頂運算符發(fā)送給后綴式； 6) “( 對它之前后的運算符起隔離作用，“)可視為自相應(yīng)左括弧開場的表達(dá)式的終了符。:v從原表達(dá)式求得后綴式的規(guī)律為從原表達(dá)式求得后綴式的規(guī)律為3.3 棧的運用舉例棧的運用舉例void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch

26、); Pass(Suffix, ch); / while / CrtExptree:v從原表達(dá)式求得后綴式的規(guī)律為從原表達(dá)式求得后綴式的規(guī)律為3.3 棧的運用舉例棧的運用舉例switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S,

27、ch); break; / switch:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) 當(dāng)求解一個問題時，是經(jīng)過求解與它同樣解法的子問題而得到的，這就是遞歸。 或了解為子程序或函數(shù)反復(fù)的調(diào)用本人，并傳入不同的變量來執(zhí)行的一種程序設(shè)計技巧。 遞歸是程序設(shè)計及解題的一種有力的、重要的工具，協(xié)助程序設(shè)計者處理復(fù)雜問題，并精簡程序構(gòu)造。:v例：設(shè)計一個乘法器，可以計算出兩個數(shù)例：設(shè)計一個乘法器，可以計算出兩個數(shù)相乘的乘積。但是此時計算機(jī)不能提供乘相乘的乘積。但是此時計算機(jī)不能提供乘法運算僅知道任何數(shù)乘法運算僅知道任何數(shù)乘 1，其值不變，其值不變，那么獨一可以運用的運算方式就是加法運那么獨一可以運用的運算方式就

28、是加法運算。算。3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) 11 3是 11 連加 3 次 (11 3) = 11 + 11 2 = 11 + 11 + 11 1) = 11 + 11 + 11 = 11 + 22 = 33:v運用遞歸的一個重要問題運用遞歸的一個重要問題v一個遞歸的求解問題必然包含有終止遞歸一個遞歸的求解問題必然包含有終止遞歸的條件，當(dāng)滿足一定條件時就終止向下遞的條件，當(dāng)滿足一定條件時就終止向下遞歸，從而使問題得以處理。歸，從而使問題得以處理。3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn):v運用遞歸的一個重要問題運用遞歸的一個重要問題v處理遞歸問題的算法稱遞歸算法，在遞歸處理遞歸問題的算法

29、稱遞歸算法，在遞歸算法中需求根據(jù)遞歸條件直接或間接地調(diào)算法中需求根據(jù)遞歸條件直接或間接地調(diào)用算法本身，當(dāng)滿足某種條件時終了遞歸用算法本身，當(dāng)滿足某種條件時終了遞歸調(diào)用。當(dāng)然對于一些簡單的遞歸問題，很調(diào)用。當(dāng)然對于一些簡單的遞歸問題，很容易把它轉(zhuǎn)換為循環(huán)問題處理，從而使編容易把它轉(zhuǎn)換為循環(huán)問題處理，從而使編寫出的算法更為有效。寫出的算法更為有效。3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn):v實現(xiàn)遞歸實現(xiàn)遞歸3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)將一切的實參、前往地址等信息傳送給被調(diào)用函數(shù)保管;為被調(diào)用函數(shù)的部分變量分配存儲區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。 當(dāng)在一個函數(shù)的運轉(zhuǎn)期間調(diào)用另一個函數(shù)時，在運轉(zhuǎn)

30、該被調(diào)用函數(shù)之前，需先完成三項義務(wù)：:v實現(xiàn)遞歸實現(xiàn)遞歸3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)保管被調(diào)函數(shù)的計算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);按照被調(diào)函數(shù)保管的前往地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。 從被調(diào)用函數(shù)前往調(diào)用函數(shù)之前，應(yīng)該完成以下三項義務(wù)：:v多個函數(shù)嵌套調(diào)用的規(guī)那么是多個函數(shù)嵌套調(diào)用的規(guī)那么是3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)此時的內(nèi)存管理實行“棧式管理后調(diào)用先前往 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū):v實現(xiàn)遞歸實現(xiàn)遞歸3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)遞

31、歸任務(wù)棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸任務(wù)記錄：每一層的遞歸參數(shù)合成一個記錄。當(dāng)前活動記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸任務(wù)棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)展嵌套調(diào)用，例如：:v例：采用遞歸算法求解正整數(shù)例：采用遞歸算法求解正整數(shù)n的階乘的階乘(n!)3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)用C言語編寫出求解n!的遞歸函數(shù)為： long f (int n) if n = = 0 return 1; else return n * fn 1; :v進(jìn)展進(jìn)展f (4)調(diào)用的系統(tǒng)棧的變化形狀調(diào)用的系統(tǒng)棧的變化形狀3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)4r13r

32、24r12r33r24r10r41r42r33r24r11r42r33r24r1:v進(jìn)展進(jìn)展f (4)調(diào)用的系統(tǒng)棧的變化形狀調(diào)用的系統(tǒng)棧的變化形狀3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)4r13r24r12r33r24r11r42r33r24r1:v例：最大公因子問題例：最大公因子問題v數(shù)學(xué)上利用輾轉(zhuǎn)相除法處理。同時此種方數(shù)學(xué)上利用輾轉(zhuǎn)相除法處理。同時此種方法也稱為歐幾理德定理，其定義為：法也稱為歐幾理德定理，其定義為：3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)GCD(M，N) =GCDN，M % N N0M N=0:v寫出求解最大公因子的遞歸函數(shù)為寫出求解最大公因子的遞歸函數(shù)為3.4 棧與遞歸的實現(xiàn)棧

33、與遞歸的實現(xiàn)long GCD( int M，int N ) / 前提條件：MN if N = = 0 /遞歸終了條件 return M ； else return GCD( N，M % N )； :v漢諾漢諾( hanoi )塔問題塔問題v漢諾塔問題是印度的一個古老的傳說。開天漢諾塔問題是印度的一個古老的傳說。開天辟地的神勃拉瑪在一個廟里留下了三根金剛辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著石的棒，第一根上面套著64個圓的金片，最個圓的金片，最大的一個在底下，其他一個比一個小，依次大的一個在底下，其他一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地疊上去，廟里的眾僧

34、不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為協(xié)助，但每次只能搬一個，而的一根棒作為協(xié)助，但每次只能搬一個，而且大的不能放在小的上面。且大的不能放在小的上面。3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn):v漢諾漢諾( hanoi )塔問題塔問題v假設(shè)有三個分別命名為假設(shè)有三個分別命名為X、Y、Z的塔座，在的塔座，在塔座塔座X上插有上插有n個直徑大小各不一樣、依小到個直徑大小各不一樣、依小到大編號為大編號為1、2、n的圓盤?，F(xiàn)要求將的圓盤。現(xiàn)要求將X軸上軸上的的n個圓盤移到塔座個圓盤移到塔座Z上并仍按同樣的順序疊上并仍按同樣的順序疊排，圓盤挪

35、動時必需遵照以下規(guī)那么：排，圓盤挪動時必需遵照以下規(guī)那么：v 1每次只能挪動一個圓盤；每次只能挪動一個圓盤；v 2圓盤可以插在圓盤可以插在X、Y、Z的任一塔座上；的任一塔座上；v 3任何時辰都不能將一個較大的圓盤壓任何時辰都不能將一個較大的圓盤壓在較在較 小的圓盤上。小的圓盤上。3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn):3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)void hanoi (int n, char x, char y, char z)/ 將塔座x上按直徑由小到大且至上而下編號為1至n/ 的n個圓盤按規(guī)那么搬到塔座z上，y可用作輔助塔座。 if (n=1) move(x, 1, z); / 將編

36、號為的圓盤從x移到z else hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔 move(x, n, z); / 將編號為n的圓盤從x移到z hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔 123456789:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc主函數(shù)： 執(zhí)行調(diào)用語句hanoi (3,a,b,c) ，入棧。層1： 執(zhí)行1,2,4,5語句，產(chǎn)生向下調(diào)用，進(jìn)層2。:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)層2 入

37、棧，記錄層1的前往地址6等信息； 執(zhí)行2層的1,2,4,5語句，執(zhí)行到語句再向下調(diào)用，進(jìn)入層3遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c層3 入棧，記錄層2的前往地址6等信息； 執(zhí)行1,2,3,9語句，過程執(zhí)行完。:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)層2 第3層調(diào)用終了，出棧，前往第2層； 從第2層的斷點語句6執(zhí)行； 執(zhí)行到語句7，又開場向下遞歸調(diào)用到第3層。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)層3 入棧,記錄層2的前往地址8等信息； 執(zhí)行語句1,2,3,9,過程執(zhí)行完。 出棧，前往第2層斷點語句8。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b8, 1, c, a, b:3.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)層 從第3層前往后，從斷點開場執(zhí)行，執(zhí)行語句8,9，過