考研期末數(shù)據(jù)結(jié)構(gòu)第三章棧和隊列

1、中國海洋大學(xué)信息學(xué)院中國海洋大學(xué)信息學(xué)院 魏振鋼魏振鋼Telelmail:Email: 通常稱，棧和隊列是限定插入和刪除只能插入和刪除只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。 線性表線性表 棧棧 隊列隊列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棧和隊列是兩種常用的數(shù)據(jù)類型棧和隊列是兩種常用的數(shù)據(jù)類型3.1 3.1 棧棧3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 3.3 棧與遞歸

2、的實現(xiàn)棧與遞歸的實現(xiàn)3.4 3.4 隊列隊列3.5 3.5 離散事件模擬離散事件模擬本章主要內(nèi)容：本章主要內(nèi)容：3.1 3.1 棧棧 棧（棧（StackStack）是限定僅在表尾進(jìn)行插入或刪除操）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。通常稱其表尾為棧頂（作的線性表。通常稱其表尾為棧頂（toptop），表頭端），表頭端稱為棧底（稱為棧底（bottombottom）。）。 假設(shè)棧假設(shè)棧S= aS= ai i | a | ai i ElemSetElemSet, i=1,2,.,n, , i=1,2,.,n, n0 n0 ，則稱，則稱a a1 1為棧底元素，為棧底元素，a an n為棧頂元素，棧

3、中元為棧頂元素，棧中元素按素按a a1 1,a,a2 2, ,a an n的次序進(jìn)棧，退棧的第一個元素應(yīng)為的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為進(jìn)行的。因此，棧又稱為后進(jìn)先出后進(jìn)先出（last in first last in first outout）的線性表（簡稱）的線性表（簡稱LIFOLIFO表）。表）。 3.1.1 3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 ADT StackADT Stack 數(shù)據(jù)對象數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,

4、n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT Stack棧的棧的抽象數(shù)據(jù)類型定義：抽象數(shù)據(jù)類型定義：數(shù)據(jù)對象：D=ai| aiElemSet, i=1,2,n, n0數(shù)據(jù)關(guān)系：R1=|ai-1, aiD, i=1,2,n 約定an端為棧頂，a1 端為棧底基本操作： InitStack(& &S) 操作結(jié)果：構(gòu)造一個空棧 S。 DestroyStack(& &S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。 ADT Stack StackEmpty(S)初始條件：棧 S 已存在。操作

5、結(jié)果：若棧 S 為空棧，則返TRUE，否則 FALE。 StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回 S 的元素個數(shù)，即棧的長度。 ClearStack(& &S)初始條件：棧 S 已存在。操作結(jié)果：將 S 清為空棧。 GetTop(S, & &e)初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。a1a2an Push(& &S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的棧頂元素。a1a2ane Pop(& &S, & &e)初始條件：棧 S 已存在且非空。操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值a1a2anan

6、-1 StackTraverse (S, visit()初始條件：棧 S 已存在。操作結(jié)果：從棧底到棧頂依次對S 的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。 ADT Stack3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; SqStack 其中，其中， stacksizestacksize指示棧的當(dāng)前可使用的最大指示棧的當(dāng)前可使用的最大容量。容量。TopTop為棧頂指針，其初值指向棧底，每當(dāng)插為棧頂指針，其初

7、值指向棧底，每當(dāng)插入新元素，指針入新元素，指針toptop加加1 1，刪除棧頂元素時，刪除棧頂元素時，指針指針toptop減減1 1。非空棧中，。非空棧中，toptop始終指向棧頂元素的下一始終指向棧頂元素的下一個位置。個位置。順序棧的定義：順序棧的定義：以下是順序棧的模塊說明。/-ADT Stack的表示與實現(xiàn)-/-棧的順序存儲表示-#define STACK_ INIT_ SIZE 100; /存儲空間初始分配量#define STACKINCREMENT 10; /存儲空間分配增量typedef struct SElemType *base; /在棧構(gòu)造之前和銷毀之后， base的值為N

8、ULL SElemType *top; /棧頂指針 int stacksize; /當(dāng)前已分配的存儲空間，以元素為單位 SqStack-基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明-Status InitStack (SqStack &S ); / 構(gòu)造一個空棧S Status DestroyStack (SqStack &S ); / 銷毀棧S，S不再存在 Status ClearStack (SqStack &S ); / 重置S 為空棧Status StackEmpty (SqStack S ); /若棧為空棧，則返回TRUE，否則 返回FALSEint StackLength (SqS

9、tack S ); /返回S的元素個數(shù)，即棧的長度 Status Status GetTop (SqStack S , SElemType &e )/若棧不空，則用e返回S的棧頂元素，并返回OK，否則返回ERRORStatus Status Push (SqStack & &S , SElemType e )/ 插入元素e為新的棧頂元素Status Status Pop (SqStack & &S , SElemType &e )/若棧不空，則刪除S的棧頂元素，并用e返回其值，并返回OK，否則返回ERRORStatusStatus StackTraverse (SqStack & &S , S

10、tatusStatus(* *visit)() ); /從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗/-基本操作的算法描述（部分）-StatusStatus InitStack (SqStack & &S ); / 構(gòu)造一個空棧S S.base = (SElemType*) mallocmalloc (STACK_INIT_SIZE sizeofsizeof (ElemType); if if (! ! S.base) exitexit(OVERFLOW); /存儲分配失敗存儲分配失敗 S.top =S.base; S.stacksize =STAC

11、K_INIT_SIZE; return return OK;/InitStackStatus Status GetTop (SqStack S , SElemType &e ) /若棧不空，則用e返回S的棧頂元素，并 /返回OK，否則返回ERROR if(S.top =S.base) return ERROR; e=*(S.top-1); return return OK;/ GetTopStatus Status Push (SqStack & &S , SElemType e ) / 插入元素e為新的棧頂元素if(S.top -S.base = S.stacksize) / 當(dāng)前存儲空間已

12、滿，增加分配 S.base = (ElemType = (ElemType * *)realloc()realloc(S.base, , ( (S.stacksize+e+STACKINCREMENT)INCREMENT)* *sizeof sizeof (ElemType(ElemType);); if if (! S.base ) exitexit(OVERFLOW); / 存儲分配失敗 S.top =S.base+S.stacksize e; S.stacksize e+=+= STACKINCREMENT INCREMENT /增加存儲容量 *S.top+=e; return retu

13、rn OK;/ PushStatus Status Pop (SqStack & &S , SElemType &e ) /若棧不空，則刪除S的棧頂元素，并 /用e返回其值，并返回OK，否則返回 /ERROR if(S.top =S.base) return ERROR; e=*-S.top; return return OK;/ Pop3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗括號匹配的檢驗3.2.3 行編輯程序問題行編輯程序問題3.2.4 迷宮求解迷宮求解3.2.5 表達(dá)式求值表達(dá)式求值3.2.1 3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 十進(jìn)制數(shù)N

14、和其它d進(jìn)制數(shù)的轉(zhuǎn)換的算法基于原理： N = (N div d)N = (N div d)d + N mod dd + N mod d 其中，其中，div div 相除取整，相除取整，mod mod 相除取余。相除取余。 例如：例如：（1348)10 = (2504)8 ，其運(yùn)算過程如下： N N div 8 N mod 8N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序 由于上述計算過程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從高位到低位進(jìn)行，恰好和計算過程相反。因此，若將計算過程中得

15、到的八進(jìn)制數(shù)的各位順序進(jìn)棧，則按出棧序列打印輸出的即為與輸入對應(yīng)的八進(jìn)制數(shù)。具體方法見算法具體方法見算法3.13.1void conversion () /對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)， /打印輸出與其等值的八進(jìn)制數(shù)打印輸出與其等值的八進(jìn)制數(shù) InitStack(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算法算法 3.13.1 則 檢驗括號是否匹配的方法可用“

16、期待的急迫程度”這個概念來描述。3.2.2 3.2.2 括號匹配的檢驗括號匹配的檢驗 假設(shè)在表達(dá)式中，（）或（ ），等為正確的格式，（ ）或（ ）或 （）) 均為不正確的格式。 分析可能出現(xiàn)的不匹配不匹配的情況: : 到來的右括弧并非是所“期待”的；例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客”； 直到結(jié)束，也沒有到來所“期待”的括弧。算法的設(shè)計思想：算法的設(shè)計思想：1 1）凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧；2 2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空, 若?？諚？?，則表明該“右括弧右括弧”多余多余，否則和棧頂元素和棧頂元素比較，若相匹配相匹配，則“左括弧

17、出棧左括弧出?！?” ，否則表明不匹不匹配配。3 3）表達(dá)式表達(dá)式檢驗結(jié)束時結(jié)束時，若?？諚？?，則表明表達(dá)式中匹配正確匹配正確，否則表明“左括弧左括弧”有余有余。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch of expi case 左括弧:Push(S,expi); i+; break; case”)”: /右括號情況 if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); i+; /匹配成功 else state = 0; break; /其

18、它類型括號類似處理其它類型括號類似處理 if (StackEmpty(S)&state) return OK; .3.2.3 行編輯程序問題行編輯程序問題 問題：一個簡單的行編輯程序的功能是：接問題：一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)。 如何實現(xiàn)如何實現(xiàn)？“每接受一個字符即存入存儲每接受一個字符即存入存儲器器” ” ? ?這樣做并不恰當(dāng)！這樣做并不恰當(dāng)！ 應(yīng)該是，在用戶輸入一行的過程中，允許用應(yīng)該是，在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。戶輸入出差錯，并在發(fā)現(xiàn)有誤時

19、可以及時更正。 設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”#”為退格符，為退格符，“”為退行符。為退行符。合理的作法是：假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whwhli#li#ililr#r#e e（s#s#* *s)s) outchaoutchaputcharputchar( (* *s s=#=#+);+);則實際有效的是下列兩行：則實際有效的是下列兩行： while (while (* *s)s) putchar putchar( (* *s+

20、);s+); while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; /僅當(dāng)棧非空時退棧 case : ClearStack(S); break; / 重置S為空棧 default : Push(S, ch); break; /有效字符進(jìn)棧，未考慮棧滿情形 ch = getchar(); / 從終端接收下一個字符 while (ch != EOF) /EOF為全文結(jié)束符Void LineEdit () /利用字符棧S，從終端接受 /一行并傳送至調(diào)用過程的數(shù)據(jù)區(qū)。InitStack (S); /構(gòu)造空棧Sch = ge

21、tchar (); /從終端接收第一個字符 ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar(); DestroyStack (S);/LineEdit 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；算法算法 3.23.23.2.4 迷宮求解迷宮求解通常用的是“窮舉求解窮舉求解”的方法# #$# #$# $# # # # # #求迷宮路徑算法的基本思想基本思想是： 若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)，則納入路徑，繼續(xù)前進(jìn); ; 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方向繼續(xù)，則后退，換方向繼續(xù)探索探索; ; 若四

22、周若四周“均無通路均無通路”，則將當(dāng)前位置從路徑中，則將當(dāng)前位置從路徑中刪除出去。刪除出去。設(shè)定當(dāng)前位置的初值為入口位置； dodo 若當(dāng)前位置可通若當(dāng)前位置可通， 則則將當(dāng)前位置插入棧頂插入棧頂；/納入路徑 若若該位置是出口位置，則則結(jié)束；/求得路徑存放在棧中 否則切換否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則否則 , ,求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：若若棧不空且棧頂位置尚有其他方向未被探索棧不空且棧頂位置尚有其他方向未被探索， 則則設(shè)定新的當(dāng)前位置為: 沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的

23、四周均不可通棧不空但棧頂位置的四周均不可通，則則刪去棧頂位置；/ 從路徑中刪去該通道塊 若若棧不空，則則重新測試新的棧頂位置， 直至直至找到一個可通的相鄰塊或出棧至?？?； while(while(棧不空棧不空) )若若?？諚？?，則則表明迷宮沒有通路。typedef struct int ord; /通道塊在路經(jīng)上的“序號” PosType seat; /通道塊在迷宮中的“坐標(biāo)位置” int di; /從此通道塊走向下一通道塊的“方向”SElemType; /棧的元素類型Status MazePath (MazeType maze, PosType start, PosType end) /若迷

24、宮maze中存在從入口start到出口end的通道，則求 /得一條存放在棧中（從棧底到棧頂），并返回 / TRUE；否則返回FALSE InitStack (S); curpos=start; /設(shè)定“當(dāng)前位置”為“入口位置” curstep=1; /探索第一步do if (Pass (curpos) /當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootPrint (curpos); /留下足跡 e = (curstep, curpos, 1); Push (S,e); /加入路經(jīng) if(curpos=end) return (TRUE); /到達(dá)出口（終點(diǎn)） curpos = NextPos

25、 (curpos, 1); /下一位置是當(dāng)前位置的東鄰 curstep+; /探索下一步/ifelse /當(dāng)前位置不能通過 if (!StackEmpty(S) Pop (S, e); while (e.di=4& !StackEmpty(S) MarkPrint (e.seat); Pop (S, e); /留下不能通過的標(biāo)記，并退回一步 /while if (e.di4) e.di+; Push (S, e); /換下一個方向探索 curpos = NextPos (e.seat e.di); /設(shè)定當(dāng)前位置是該新方向上的相鄰快 /if /if /else while (!StackEmp

26、ty(S) ; return (FALSE);/MazePath算法算法 3.33.3 限于二元運(yùn)算符的表達(dá)式定義: 表達(dá)式表達(dá)式 := (操作數(shù)操作數(shù)) + (運(yùn)算符運(yùn)算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡單變量簡單變量 | 表達(dá)式表達(dá)式 簡單變量簡單變量 : = 標(biāo)識符標(biāo)識符 | 無符號整數(shù)無符號整數(shù)3.2.5 3.2.5 表達(dá)式求值表達(dá)式求值 表達(dá)式的三種標(biāo)識方法：表達(dá)式的三種標(biāo)識方法：設(shè)設(shè) Exp = S1 + OP + S2則稱則稱 OP + S1 + S2 為前綴表示法前綴表示法 S1 + OP + S2 為中綴表示法中綴表示法 S1 + S2 + OP 為后綴表示法

27、后綴表示法 例如: 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）中綴式丟失了括弧信息， 致使運(yùn)算的次序不確定;3)前綴式的運(yùn)算規(guī)則前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個操作數(shù)和在它們連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一之前且緊靠它們的運(yùn)算符構(gòu)成一個最小表達(dá)式個最小表達(dá)式; 4)后綴式的運(yùn)算規(guī)則后綴式的運(yùn)算規(guī)則為: 運(yùn)算符在式中出現(xiàn)的順序恰為運(yùn)算符在式中出現(xiàn)的順序恰為 表達(dá)式的運(yùn)算順序表達(dá)

28、式的運(yùn)算順序; 每個運(yùn)算符和在它之前出現(xiàn)每個運(yùn)算符和在它之前出現(xiàn) 且且 緊靠它的兩個操作數(shù)構(gòu)成一個最小緊靠它的兩個操作數(shù)構(gòu)成一個最小 表達(dá)式。表達(dá)式。例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) fl如何從原表達(dá)式求得后綴式？如何從原表達(dá)式求得后綴式？ 每個運(yùn)算符的運(yùn)算次序要由它之后的一個運(yùn)算它之后的一個運(yùn)算符符來定，在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。 分析 “原表達(dá)式” 和 “后綴式”中的運(yùn)算符: 原表達(dá)式: a + b c d / e f 后綴式: a b c + d e / f 從原表達(dá)式求得后綴式的規(guī)律為：從原表達(dá)式求得后綴式的規(guī)律

29、為：1) 設(shè)立操作符棧；棧；2) 設(shè)表達(dá)式的結(jié)束符為“#”，予設(shè)運(yùn)算符棧的棧底為“#”；3) 若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。4) 若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧；5) 否則，退出棧頂運(yùn)算符發(fā)送給后綴式； 6) “(” 對它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。void transform(char suffix , char exp ) /已知表達(dá)式exp，求其后綴表達(dá)式suffix InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch,

30、OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree /見下頁見下頁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,

31、c); if ( ch!= # ) Push( S, ch); break; / switch算符優(yōu)先算法求表達(dá)式值過程為：算符優(yōu)先算法求表達(dá)式值過程為：1) 設(shè)立操作符棧棧OPTROPTR，操作數(shù)或運(yùn)算結(jié)果棧操作數(shù)或運(yùn)算結(jié)果棧OPNDOPND；2) 設(shè)表達(dá)式的結(jié)束符為“#”，予設(shè)運(yùn)算符棧的棧底為“#”，操作數(shù)棧為空棧；3) 依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為#）。OperandType EvaluateExpression() /算術(shù)表達(dá)式求值的算符

32、優(yōu)先算法。設(shè)OPTR和OPND /分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。 InitStack (OPTR); Push(OPTR,#); initStack (OPND); c=getchar(); while (c!=#|GetTop(OPTR)!=#) if (!In (c, OP) Push (OPND, c); c= getchar(); /不是運(yùn)算符則進(jìn)棧 else switch (Precede( GetTop (OPTR), c) case: /退棧并將運(yùn)算結(jié)果入棧 Pop (OPTR, theta); Pop (OPND, b); Pop (OPND, a); Push

33、(OPND, Operate (a, theta, b); break; /switch /while return GetTop(OPND);/EvaluateExpression算法算法 3.43.43.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) 階乘函數(shù)：1、遞歸 一個對象如果部分地由它自身來定義（或描述），則稱其為遞歸。例如：Fact(n)= 1 n=0n*Fact(n-1) n=1 二階Fibonacci數(shù)列：Fib(n)= 0 n=0 1 n=1Fib(n-1)+ Fib(n-2) n12、遞歸函數(shù)、遞歸函數(shù) 一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱作遞歸函數(shù)。 將所有

34、的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存； 為被調(diào)用函數(shù)的局部變量分配存儲區(qū)； 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。 當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一個函數(shù)時，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項任務(wù)： 保存被調(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ù)：多個函數(shù)嵌套調(diào)用的規(guī)則是：此時的內(nèi)存管理實行“棧式管理棧式管理”后調(diào)用先返回后調(diào)用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數(shù)據(jù)區(qū)函數(shù)a的

35、數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū) 遞歸工作棧：遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數(shù)合成一個記錄。當(dāng)前活動記錄：當(dāng)前活動記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)同一函數(shù)進(jìn)行嵌套調(diào)用，例如： 一、問題的定義是遞歸的。例如，數(shù)學(xué)中的階乘函數(shù)、二階Fibonacci函數(shù)等。 遞歸是程序設(shè)計中一個強(qiáng)有力的工具。那么，遞歸是程序設(shè)計中一個強(qiáng)有力的工具。那么，如何設(shè)計遞歸過程呢？可根據(jù)以下幾種情況考慮：如何設(shè)計遞歸過程呢？可根據(jù)以下幾種情況考慮：int Fact(int n) if(n=0

36、) return 1; else return n*Fact(n-1);n階階乘的遞歸函數(shù)如下： 二、有的數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸的描述。 三、有些問題，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡單。如八皇后問題、Hanoi塔問題等。int Fib(int n) if(n=0) return 0; else if(n=1) return 1; else return Fib(n-1)+Fib(n-2);求二階Fibonacci數(shù)列的遞歸函數(shù)如下： 1、每次只能移動一個圓盤；例3-2 （n階Hanoi塔問題）假設(shè)有三個分別命名為

37、X、Y和Z的塔座，在X上插有n個直徑大小各不相同、依小到大編號為1，2，n的圓盤（如圖3.5所示）?，F(xiàn)要求將X軸上的n個圓盤移至Z上并仍按同樣的順序疊排，圓盤移動時必須遵循下列規(guī)則：2、圓盤可以插在X、Y和Z中的任一塔座上；3、任何時候都不能將一個較大的圓盤壓在較小的圓盤之上。XYZ圖圖3.5 33.5 3階階HanoiHanoi塔問題塔問題 1、將壓在編號為n 的圓盤之上的n-1個圓盤從塔座X（依照上述法則）移至塔座Y上； 如何實現(xiàn)移動圓盤的操作呢？當(dāng)n=1時，問題比較簡單，只需將編號為1的圓盤從塔座X直接移至塔座Z上即可；當(dāng)n1時，該如何考慮呢？ 2、將編號為n 的圓盤從塔座X移至塔座Z上

38、； 3、再將塔座Y上的n-1個圓盤（依照上述法則）移至塔座Z上； 其中，將n-1個圓盤從一個塔座移至另一塔座的問題是一個和原問題相同的問題，只是問題的規(guī)模小1void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n / 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。 /搬動操作搬動操作move(xmove(x, n, z), n, z)可定義為可定義為(c(c是初值為是初值為0 0的全局的全局 /變變量，對搬動計數(shù)量，對搬動計數(shù)) )：printf(“%i.Move disk %i from / %c to %c

39、n”, +c, n, x, z);1 2 if (n=1)3 move(x, 1, z); / 將編號為的圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號為n的圓盤從x移到z7 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔8 9 算法算法 3.53.50 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char

40、z) 1 if (n=1)2 move(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 假設(shè)主函數(shù)的返回地址假設(shè)主函數(shù)的返回地址為為0 0，以遞歸函數(shù)的語句行以遞歸函數(shù)的語句行號號為為返回地址。返回地址。 隊列（隊列（queue )是一種先進(jìn)先出(first in first out，簡稱FIFO表)的線性表。它只允許在表的一端進(jìn)行插入，而在另一端刪除元素。 在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端稱為隊頭(front)。 假設(shè)隊列為q= （a a1 1,

41、a,a2 2, ,a an n），則a1為隊頭元素，an為隊尾元素。3.4 3.4 隊列隊列3.4.1 抽象數(shù)據(jù)類型隊列的定義 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定：其中a1 端為隊列頭隊列頭， an 端為隊列尾隊列尾基本操作：基本操作： ADT Queue抽象數(shù)據(jù)類型隊列的定義InitQueue(&QInitQueue(&Q) ) 操作結(jié)果：操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&QDestroyQueue(&Q) ) 初始條件：初始

42、條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：隊列Q被銷毀，不再存在。 QueueEmpty(QQueueEmpty(Q) ) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。隊列的基本操作：隊列的基本操作： QueueLength(QQueueLength(Q) ) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。 GetHead(QGetHead(Q, &e), &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：用e返回Q的隊頭元素。a1a2an ClearQueue(&QClear

43、Queue(&Q) ) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊列。 EnQueue(&QEnQueue(&Q, e), e) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q 的新的隊尾元素。a1a2ane DeQueue(&QDeQueue(&Q, &e), &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an typedef struct QNode / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊

44、列鏈隊列: 用鏈表表示的隊列簡稱為鏈隊列。 一個鏈隊列需要兩個分別指示隊投合隊尾的指針（分別稱為頭指針和尾指針）才能惟一確定。3.4.2 3.4.2 鏈隊列鏈隊列隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊列-基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明-Status InitQueue (LinkQueue &Q ); / 構(gòu)造一個空的隊列Q St

45、atus DestroyQueue (LinkQueue &Q ); / 銷毀隊列Q，Q不再存在 Status ClearQueue (LinkQueue &Q ); / 重置Q為空隊列Status QueueEmpty (LinkQueue Q ); /若為空隊列，則返回TRUE，否則 返回FALSEint QueueLength (LinkQueue Q ); /返回Q的元素個數(shù)，即隊列的長度 Status GetHead (LinkQueue Q , QElemType &e )/若隊列不空，則用e返回Q的隊頭元素，并返回OK，否則返回ERRORStatus EnQueue (LinkQ

46、ueue &Q , QElemType e )/ 插入元素e為新的隊尾元素Status DeLinkQueue (LinkQueue &Q , QElemType &e )/若隊列不空，則刪除Q的隊頭元素，并用e返回其值，并返回OK，否則返回ERRORStatus Queue Traverse (LinkQueue &Q , visit() ); /從隊尾到隊頭依次對隊列中每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗 StatusStatus InitQueue (LinkQueue & &Q) / 構(gòu)造一個空隊列Q Q.front = Q.rear = (QueuePt

47、r)mallocmalloc(sizeofsizeof(QNode); ifif (! !Q.front) exit exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULLNULL; returnreturn OK; StatusStatus DestroyQueue (LinkQueue & &Q) / 銷毀隊列Q while (Q.front) Q.rear = Q.front-next; freefree (Q.front) ; Q.front = Q.rear; returnreturn OK; StatusStatus EnQueue (LinkQu

48、eue & &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) mallocmalloc (sizeofsizeof (QNode); ifif(!p!p) exit exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; returnreturn OK; StatusStatus DeQueue (LinkQueue & &Q, QElemType & &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ER

49、ROR ifif (Q.front = Q.rear) returnreturn ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; ifif (Q.rear = p) Q.rear = Q.front; free free (p); returnreturn OK; 在隊列的順序存儲結(jié)構(gòu)中，需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。在此約定：初始化建空隊列時，令front=rear=0，每當(dāng)插入新的隊尾元素時，尾指針加1，每當(dāng)刪除隊頭元素時， 頭指針加1。因此，在非空隊列中，頭指針始終指向隊列頭

50、元素，而尾指針始終指向隊尾元素的下一個位置。 3.4.3 循環(huán)隊列循環(huán)隊列隊列的隊列的順序表示和實現(xiàn)順序表示和實現(xiàn)J1J2J3Q.frontQ.rearJ5J6Q.frontQ.rear圖圖3.123.12 頭、尾指針和隊列中元素之間的關(guān)系頭、尾指針和隊列中元素之間的關(guān)系#define#define MAXQSIZE 100 /最大隊列長度 typedef structtypedef struct QElemType QElemType *base; / 動態(tài)分配存儲空間 intint front; / 頭指針，若隊列不空， / 指向隊列頭元素 intint rear; / 尾指針，若隊列不空

51、， /指向隊列尾元素的下一個位置 SqQueue;循環(huán)隊列循環(huán)隊列類型的模塊說明如下：類型的模塊說明如下： StatusStatus InitQueue (SqQueue & &Q) / 構(gòu)造一個空隊列Q Q.base = (ElemType * *) mallocmalloc (MAXQSIZE *sizeofsizeof (ElemType); ifif (! !Q.base) exitexit (OVERFLOW); / 存儲分配失敗 Q.front = Q.rear = 0; returnreturn OK; StatusStatus EnQueue (SqQueue & &Q, El

52、emType e) / 插入元素e為Q的新的隊尾元素 ifif (Q.rear+1) % % MAXQSIZE = Q.front) returnreturn ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % % MAXQSIZE; returnreturn OK; StatusStatus DeQueue (SqQueue & &Q, ElemType & &e) / 若隊列不空，則刪除Q的隊頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if if (Q.front = Q.rear) returnreturn ERROR

53、; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE;Q.front = (Q.front+1) % MAXQSIZE; returnreturn OK; 第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二項式系數(shù)值（楊輝三角）設(shè)第 i-1行的值：(a0=0) a1.ai (ai+1=0)則第 i 行的值：bj = aj-1+aj, j=1,2,i+1利用循環(huán)隊列計算二項式的過程：假設(shè)只計算三行，則隊列的最大容量為 5。1 1 00q.frontq.rear1 1 001q.frontq.r

54、ear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.frontq.rear1 0 121q.frontq.rear1 0 123q.frontq.rear1 0 133q.frontq.rear1 0 133q.frontq.reardo DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); while (e!=0);3.5 3.5 離散事件模擬離散事件模擬 假設(shè)某銀行有假設(shè)某銀行有4 4個窗口營業(yè)，從早晨銀

55、行開門個窗口營業(yè)，從早晨銀行開門起不斷有客戶進(jìn)入銀行。每個窗口每一時刻只能接起不斷有客戶進(jìn)入銀行。每個窗口每一時刻只能接待一個客戶，對于剛進(jìn)入銀行的客戶，如果某個窗待一個客戶，對于剛進(jìn)入銀行的客戶，如果某個窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若4 4個窗口均有客戶所占，他會排在人數(shù)最少的隊伍個窗口均有客戶所占，他會排在人數(shù)最少的隊伍后面?，F(xiàn)要編制一個程序以模擬銀行的這種業(yè)務(wù)活后面?，F(xiàn)要編制一個程序以模擬銀行的這種業(yè)務(wù)活動并計算一天客戶在銀行逗留的平均時間。動并計算一天客戶在銀行逗留的平均時間。 客戶逗留時間客戶逗留時間= =客戶離開時間客戶離

56、開時間- -客戶到達(dá)時間客戶到達(dá)時間 客戶離開時間客戶離開時間= = 同一隊列前一個客戶離開時間同一隊列前一個客戶離開時間+ +客戶處理業(yè)務(wù)時客戶處理業(yè)務(wù)時間間 客戶到達(dá)時間客戶到達(dá)時間= = 上個客戶到達(dá)時間上個客戶到達(dá)時間+ +兩個客戶到來的時間間隔。兩個客戶到來的時間間隔。 事件事件= =客戶到來事件客戶到來事件+ +客戶離開事件客戶離開事件 平均時間平均時間= =客戶逗留時間之和客戶逗留時間之和/ /客戶人數(shù)客戶人數(shù)隨機(jī)產(chǎn)生：客戶處理業(yè)務(wù)時間 客戶到來的時間間隔void Bank_ Simulation (int CloseTime) /銀行業(yè)務(wù)模擬，統(tǒng)計一天內(nèi)客戶在銀行逗留的平均時間

57、 OpenForDay (); /初始化 while (MoreEvent) EventDrived (OccurTime, EventType); /事件驅(qū)動 switch (EventType) caseA:CustomerArrived(); break; /處理客戶到達(dá)事件 caseD:CustomerDeparture(); break; /處理客戶到離開事件 default: Invalid(); /switch /while CloseForDay; /計算平均逗留時間/ Bank_ Simulation 算法算法 3.63.6事件的主要信息是：事件的主要信息是：事件類型事件類型

58、和和事件發(fā)生的時刻事件發(fā)生的時刻。事件表應(yīng)是：有序表，其主要操作是插入和刪除事件。事件表應(yīng)是：有序表，其主要操作是插入和刪除事件。表示客戶排隊的是：隊列，表示客戶排隊的是：隊列，隊列中有關(guān)客戶的主要信息是：隊列中有關(guān)客戶的主要信息是： 客戶到達(dá)的時刻和客戶辦理業(yè)務(wù)所需時間客戶到達(dá)的時刻和客戶辦理業(yè)務(wù)所需時間。每個隊列的隊頭客戶即為正在窗口辦理事務(wù)的客戶，他辦每個隊列的隊頭客戶即為正在窗口辦理事務(wù)的客戶，他辦完事務(wù)離開隊列的時刻就是即將發(fā)生的客戶離開事件的時刻。完事務(wù)離開隊列的時刻就是即將發(fā)生的客戶離開事件的時刻。在任何時刻即將發(fā)生的事件只有下列在任何時刻即將發(fā)生的事件只有下列5種可能種可能：1

59、）新的客）新的客戶到達(dá)，戶到達(dá)，2）-5）1-4號窗口客戶離開。號窗口客戶離開。 在模擬程序中只需要兩種數(shù)據(jù)類型：有序鏈表和隊列。他們的定義如下：typedef struct int OccurTime; /事件發(fā)生時刻 int NType; /事件類型，0表示到達(dá)事件，1至 /4表示四個窗口的離開事件Event, ElemType; /事件類型，有序鏈表LinkList /的數(shù)據(jù)元素類型Typedef LinkList EventList /事件鏈表類型，定義為有序鏈表typedef struct int ArrivalTime; /到達(dá)時刻 int Duration; /辦理事務(wù)所需時間Q

60、ElemType; /隊列的數(shù)據(jù)元素類型 現(xiàn)在分析算法3.6中兩個主要操作步驟是如何實現(xiàn)的？ 先看對新客戶到達(dá)事件的處理。不失一般性，假設(shè)第一個客戶進(jìn)門時刻為0，即是模擬程序處理的第一個事件，之后每個客戶的到達(dá)時刻由前一個客戶到達(dá)時設(shè)定。因此在客戶到達(dá)事件發(fā)生時需先產(chǎn)生兩個隨機(jī)數(shù)：其一為到達(dá)客戶辦理事務(wù)所需時間durtime，其二為下一客戶將到達(dá)的時間間隔intertime，假設(shè)當(dāng)前事件發(fā)生的時刻為occurtime，則下一客戶到達(dá)事件發(fā)生的時刻為occurtime+ intertime，由此應(yīng)產(chǎn)生一個新的客戶到達(dá)事件插入事件表；剛到達(dá)的客戶應(yīng)插入到當(dāng)前所含元素最少的隊列中；若該隊列在插入前為