數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列課件

1、第第3 3章章 棧和隊(duì)列棧和隊(duì)列1.1. 掌握棧和隊(duì)列的掌握棧和隊(duì)列的特點(diǎn)特點(diǎn)，并能在相應(yīng)的應(yīng)用問，并能在相應(yīng)的應(yīng)用問題中正確選用題中正確選用2.2. 熟練掌握棧的熟練掌握棧的兩種存儲結(jié)構(gòu)兩種存儲結(jié)構(gòu)的基本操作實(shí)現(xiàn)的基本操作實(shí)現(xiàn)算法，特別應(yīng)注意算法，特別應(yīng)注意棧滿和?？諚M和?？盏臈l件的條件3.3. 熟練掌握熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)的基本操作實(shí)現(xiàn)算法，特別注意算法，特別注意隊(duì)滿和隊(duì)空隊(duì)滿和隊(duì)空的的條件條件4.4. 理解理解遞歸算法遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程執(zhí)行過程中棧的狀態(tài)變化過程 棧（棧（Stack）1. 1. 定義定義2. 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3.

2、3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式隊(duì)列（隊(duì)列（Queue）1. 1. 定義定義2. 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式3.13.1棧棧定定 義義只能在只能在表的一端表的一端（棧頂棧頂）進(jìn)行插入和刪除運(yùn)算）進(jìn)行插入和刪除運(yùn)算的的線性表線性表邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)與線性表相同，仍為與線性表相同，仍為一對一一對一關(guān)系關(guān)系存儲結(jié)構(gòu)存儲結(jié)構(gòu)用用順序棧順序?；蚧蜴湕ｆ湕４鎯桑皂樞驐８Ｒ姶鎯?，但以順序棧更常見運(yùn)算規(guī)則運(yùn)算規(guī)則只能在只能在棧頂棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照運(yùn)算，且訪問結(jié)點(diǎn)時依

3、照后進(jìn)先出后進(jìn)先出（LIFOLIFO）或或先進(jìn)后出先進(jìn)后出（FILOFILO）的原則的原則實(shí)現(xiàn)方式實(shí)現(xiàn)方式關(guān)鍵是編寫關(guān)鍵是編寫入棧入棧和和出棧出棧函數(shù)，具體實(shí)現(xiàn)依順序函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５牟煌煌瑮；蜴湕５牟煌煌静僮饔谢静僮饔腥霔?、出棧、讀棧頂元素值、建棧、入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、棧空判斷棧滿、棧空等等棧是一種特殊的線性表，它只能在表的一端（棧頂）棧是一種特殊的線性表，它只能在表的一端（棧頂）進(jìn)行插入和刪除運(yùn)算進(jìn)行插入和刪除運(yùn)算棧與一般線性表的區(qū)別：僅在于棧與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則運(yùn)算規(guī)則不同不同一般線性表一般線性表 邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一

4、對一 存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序表、鏈表 運(yùn)算規(guī)則：隨機(jī)運(yùn)算規(guī)則：隨機(jī)、順序存取順序存取棧棧邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：順序棧棧、鏈、鏈棧棧運(yùn)算規(guī)則：運(yùn)算規(guī)則：后進(jìn)先出后進(jìn)先出棧與一般線性表的區(qū)別棧與一般線性表的區(qū)別“進(jìn)進(jìn)” 壓入壓入=PUSH=PUSH（) )“出出” 彈出彈出=POP( )=POP( ) a a1 1 a a2 2 a an n順序棧順序棧S S a ai i表頭表頭表尾表尾棧底棧底basebase棧頂棧頂toptop低地址低地址高地址高地址寫入：寫入：vi= vi= a ai i讀出：讀出：x= vix= vi壓入：壓入：PUSH (

5、PUSH (a an+1n+1) )彈出：彈出：POP (x)POP (x)前提：一定要預(yù)設(shè)棧頂指針前提：一定要預(yù)設(shè)棧頂指針toptop！低地址低地址高地址高地址vivi a a1 1 a a2 2 a ai i a an n 順序表順序表VnVn a an+1n+1順序棧與順序表順序棧與順序表順序棧的表示順序棧的表示空?？諚ase = topbase = top 是棧空標(biāo)志是?？諛?biāo)志stacksize = 4stacksize = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的棧頂元素之上棧頂元素之上

6、的下標(biāo)地址的下標(biāo)地址棧滿時的處理方法：棧滿時的處理方法：1 1、報錯報錯, ,返回操作系統(tǒng)。返回操作系統(tǒng)。2 2、分配更大的空間分配更大的空間，作為棧的存儲空，作為棧的存儲空間間, ,將原棧的內(nèi)容移入新棧。將原棧的內(nèi)容移入新棧。#define MAXSIZE 100typedef structSElemType *base;SElemType *top;int stacksize;SqStack;順序棧的表示順序棧的表示 構(gòu)造一個空棧構(gòu)造一個空棧 步驟：步驟：(1)(1)分配空間并檢查空間分配空間并檢查空間是否分配失敗，若失是否分配失敗，若失敗則返回錯誤敗則返回錯誤順序棧初始化順序棧初始化ba

7、sestacksizetops(2)(2)設(shè)置棧底和棧頂指針設(shè)置棧底和棧頂指針 S.top = S.base;(3)(3)設(shè)置棧大小設(shè)置棧大小Status InitStack( SqStack &S )S.base =new SElemTypeMAXSIZE；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;順序棧初始化順序棧初始化判斷順序棧是否為空判斷順序棧是否為空bool StackEmpty( SqStack S )if(S.top = S.base) return true;

8、 else return false;basetop3120求順序棧的長度求順序棧的長度int StackLength( SqStack S )return S.top S.base;basetopABStatus ClearStack( SqStack S )if( S.base ) S.top = S.base;return OK;清空順序棧清空順序棧basetop3120Status DestroyStack( SqStack &S )if( S.base )delete S.base ;S.stacksize = 0;S.base = S.top = NULL; return

9、OK;銷毀順序棧銷毀順序棧(1)(1)判斷是否棧滿，若滿則出錯判斷是否棧滿，若滿則出錯(2)(2)元素元素e e壓入棧頂壓入棧頂(3)(3)棧頂指針加棧頂指針加1 1順序棧進(jìn)棧順序棧進(jìn)棧Status Push( SqStack &S, SElemType e) if( S.top - S.base= S.stacksize ) / 棧滿棧滿 return ERROR; *S.top+=e;return OK;*S.top=e;S.top+;ABCtopbase(1)(1)判斷是否?？?，若空則出錯判斷是否?？眨艨談t出錯(2)(2)獲取棧頂元素獲取棧頂元素e e(3)(3)棧頂指針減棧頂

10、指針減1 1順序棧出棧順序棧出棧Status Pop( SqStack &S, SElemType &e) if( S.top = S.base ) / 棧空?？?return ERROR; e *-S.top;return OK; -S.top; e=*S.top;ABCtopbase(1)(1) 判斷是否空棧，若空則返回錯誤判斷是否空棧，若空則返回錯誤(2)(2) 否則通過棧頂指針獲取棧頂元素否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素取順序棧棧頂元素Status GetTop( SqStack S, SElemType &e) if( S.top = S.base

11、 ) return ERROR; / ?？諚？?e = *( S.top 1 ); return OK;e = *( S.top - ); ?ABCtopbase435612435612中到了中到了1212順序不能實(shí)現(xiàn)；順序不能實(shí)現(xiàn)；135426135426可以實(shí)現(xiàn)?？梢詫?shí)現(xiàn)。1.1.如果一個棧的輸入序列為如果一個棧的輸入序列為123456123456，能否得到，能否得到435612435612和和135426135426的出棧序列？的出棧序列？練習(xí)練習(xí)練習(xí)練習(xí)i n-in-i+1不確定不確定2.2.若已知一個棧的入棧序列是若已知一個棧的入棧序列是1 1，2 2，3 3，n n，其，其輸出序列

12、為輸出序列為p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，則，則pipi為為練習(xí)練習(xí) top不變不變 top=0 top+ top-D3.3.在一個具有在一個具有n n個單元的順序棧中，假設(shè)以地址高端作個單元的順序棧中，假設(shè)以地址高端作為棧底，以為棧底，以toptop作為棧頂指針，則當(dāng)作進(jìn)棧處理時，作為棧頂指針，則當(dāng)作進(jìn)棧處理時，toptop的變化為的變化為b0 t0 t1 b10 m-1V雙棧共享一個?？臻g雙棧共享一個?？臻g優(yōu)點(diǎn)：互相調(diào)劑，靈活性強(qiáng)，減少溢出機(jī)會優(yōu)點(diǎn)：互相調(diào)劑，靈活性強(qiáng)，減少溢出機(jī)會 將編號為將編號為0 0和和1 1的兩個棧存放于一個數(shù)組空間的兩個棧存放于一

13、個數(shù)組空間VmVm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)谥校瑮５追謩e處于數(shù)組的兩端。當(dāng)?shù)? 0號棧的棧頂號棧的棧頂指針指針top0top0等于等于-1-1時該棧為空，當(dāng)?shù)跁r該棧為空，當(dāng)?shù)? 1號棧的棧頂號棧的棧頂指針指針top1top1等于等于m m時該棧為空。兩個棧均從兩端向時該棧為空。兩個棧均從兩端向中間增長（如下圖所示）中間增長（如下圖所示） 。bot0 top0 top1 bot10 m-1Vtypedef structint top2, bot2; /棧頂和棧底指針棧頂和棧底指針SElemType SElemType * *V; V; /棧數(shù)組棧數(shù)組 int m; int m; /棧最大可

14、容納元素個數(shù)棧最大可容納元素個數(shù)DblStack;DblStack;數(shù)據(jù)結(jié)構(gòu)定義如下數(shù)據(jù)結(jié)構(gòu)定義如下void Dblpush(DblStack &s,SElemType x,int i) ；/把把x插入到棧插入到棧i的棧的棧int Dblpop(DblStack &s,int i,SElemType &x) ； /退掉位于棧退掉位于棧i棧頂?shù)脑貤ｍ數(shù)脑豬nt IsEmpty(DblStack s,int i) ；/判棧判棧i空否空否, 空返回空返回1, 否則返回否則返回0int IsFull(DblStack s) ；/判棧滿否判棧滿否, 滿返回滿返回1, 否則返回

15、否則返回0試編寫判斷?？铡M、進(jìn)棧和出棧四個算試編寫判斷棧空、棧滿、進(jìn)棧和出棧四個算法的函數(shù)法的函數(shù)(函數(shù)定義方式如下）函數(shù)定義方式如下）b0 t0 t1 b10 m-1V?？眨簵？眨簍opi = boti itopi = boti i表示棧的編號表示棧的編號 棧滿：棧滿：top0+1=top1 top0+1=top1 或或top1-1=top0top1-1=top0提示提示鏈棧的表示鏈棧的表示運(yùn)算是受限的單鏈表，只能在鏈表頭部進(jìn)行操作，故運(yùn)算是受限的單鏈表，只能在鏈表頭部進(jìn)行操作，故沒有必要附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針沒有必要附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針 typedef s

16、truct StackNode SElemType data; struct StackNode *next; StackNode, *LinkStack;LinkStack S; data next 棧頂棧頂棧底棧底S鏈棧的初始化鏈棧的初始化void InitStack(LinkStack &S ) S=NULL;S判斷鏈棧是否為空判斷鏈棧是否為空Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; else return FALSE;鏈棧進(jìn)棧鏈棧進(jìn)棧Status Push(LinkStack &S , SElemTy

17、pe e) p=new StackNode; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 鏈棧出棧鏈棧出棧Status Pop (LinkStack &S,SElemType &e) if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 取鏈棧棧頂元素取鏈棧棧頂元素SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else

18、 return Sdata; 3.2 3.2 棧的應(yīng)用棧的應(yīng)用例例1 1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N N）用棧暫存低位值用棧暫存低位值例例2 2：括號匹配的檢驗(yàn)括號匹配的檢驗(yàn)用棧暫存左括號用棧暫存左括號例例3 3：表達(dá)式求值表達(dá)式求值用棧暫存運(yùn)算符用棧暫存運(yùn)算符例例4 4：迷宮求解：迷宮求解 用棧實(shí)現(xiàn)遞歸調(diào)用用棧實(shí)現(xiàn)遞歸調(diào)用簡化了程序設(shè)計(jì)的問題簡化了程序設(shè)計(jì)的問題迷宮求解迷宮求解從入口出發(fā)，按某一方向向未走過的前方探索從入口出發(fā)，按某一方向向未走過的前方探索若能走通，則到達(dá)新點(diǎn)，否則試探下一方向若能走通，則到達(dá)新點(diǎn)，否則試探下一方向 ; ; 若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，若

19、所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個方向再繼續(xù)試探換下一個方向再繼續(xù)試探直到所有可能的通路都探索到，或找到一條通路，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)?；驘o路可走又返回到入口點(diǎn)。求解思想：求解思想：回溯法回溯法迷宮求解迷宮求解需要解決的問題：需要解決的問題：1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)、表示迷宮的數(shù)據(jù)結(jié)構(gòu)2、試探方向、試探方向3、棧的設(shè)計(jì)、棧的設(shè)計(jì)4、防止重復(fù)到達(dá)某點(diǎn)，避免發(fā)生死循環(huán)、防止重復(fù)到達(dá)某點(diǎn)，避免發(fā)生死循環(huán)迷宮求解迷宮求解1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)、表示迷宮的數(shù)據(jù)結(jié)構(gòu)表示一個表示一個m行行n列迷宮：列迷宮：用用mazemn表示，表示，0im,0j

20、x=xx表表3.13.1算符間的優(yōu)先關(guān)系算符間的優(yōu)先關(guān)系【算法思想算法思想】（1）初始化）初始化OPTR棧和棧和OPND棧，將棧，將 “#”壓入壓入OPTR（2）依次讀入字符）依次讀入字符ch，循環(huán)執(zhí)行（，循環(huán)執(zhí)行（3）至（）至（5） （3）取出）取出OPTR的棧頂元素，當(dāng)?shù)臈ｍ斣?，?dāng)OPTR的棧頂元素和的棧頂元素和ch均為均為“#”時，表達(dá)式求值完畢，時，表達(dá)式求值完畢，OPND棧頂元素為表達(dá)式的值棧頂元素為表達(dá)式的值設(shè)定兩棧設(shè)定兩棧 ：OPND-OPND-操作數(shù)或運(yùn)算結(jié)果操作數(shù)或運(yùn)算結(jié)果OPTR-OPTR-運(yùn)算符運(yùn)算符（4） if (ch是操作數(shù)是操作數(shù)) 則則ch進(jìn)進(jìn)OPND，讀入下一

21、字符，讀入下一字符ch（5） else 比較比較OPTR棧頂元素和棧頂元素和ch的優(yōu)先級的優(yōu)先級case : 運(yùn)算符運(yùn)算符ch 進(jìn)進(jìn)OPTR，讀入下一字符，讀入下一字符chcase=: 脫括號（彈出左括號），讀入下一字符脫括號（彈出左括號），讀入下一字符chcase : 棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)OPNDOperandType EvaluateExpression( ) InitStack (OPND); ch = getchar( ); while (ch!= # | GetTop(OPTR)! = #) if (! In(ch,OP)Push(OPND,ch)

22、; ch = getchar(); / ch不是運(yùn)算符則進(jìn)棧不是運(yùn)算符則進(jìn)棧 else switch (Precede(GetTop(OPTR),ch) /比較優(yōu)先權(quán)比較優(yōu)先權(quán) case : /彈出彈出OPTR棧頂?shù)倪\(yùn)算符運(yùn)算，并將運(yùn)算結(jié)果入棧棧頂?shù)倪\(yùn)算符運(yùn)算，并將運(yùn)算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; case = : /脫括號并接收下一字符脫括號并接收下一字符 Pop(OPTR,x); ch = getchar(); break; / switc

23、h / while return GetTop(OPND); / EvaluateExpressionOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3.3 3.3 棧與遞歸棧與

24、遞歸n遞歸的定義遞歸的定義 若一個對象部分地包含它若一個對象部分地包含它自己自己, , 或用它自己給自己定義或用它自己給自己定義, , 則稱這個對則稱這個對象是遞歸的；若一個過程象是遞歸的；若一個過程直接地或間接地調(diào)用直接地或間接地調(diào)用自己自己, , 則稱這個過程是遞歸的過程。則稱這個過程是遞歸的過程。當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時, , 遵循遵循后調(diào)用先返回后調(diào)用先返回棧棧n以下三種情況常常用到遞歸方法以下三種情況常常用到遞歸方法遞歸定義的數(shù)學(xué)函數(shù)遞歸定義的數(shù)學(xué)函數(shù)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)可遞歸求解的問題可遞歸求解的問題1. 遞歸定義的數(shù)學(xué)函數(shù)遞歸定義的

25、數(shù)學(xué)函數(shù): 階乘函數(shù)階乘函數(shù): 0n ) 1(0n 1)(若若nFactnnFact 2階階Fibonaci數(shù)列數(shù)列: )2() 1(1n 10n 0)(其它若若nFibnFibnFib 樹樹 2. 2. 具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu): :RootRootLchildLchildRchildRchild 廣義表廣義表 A=(a,A)A=(a,A)3. 3. 可遞歸求解的問題可遞歸求解的問題: : 迷宮問題迷宮問題HanoiHanoi塔問題塔問題 分治法：分治法：對于一個較為復(fù)雜的問題，能夠分解成幾對于一個較為復(fù)雜的問題，能夠分解成幾個相對簡單的且解法相同或類似的子問題來求解個相

26、對簡單的且解法相同或類似的子問題來求解1 1、能將一個問題轉(zhuǎn)變成一個新問題，而新問題與、能將一個問題轉(zhuǎn)變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規(guī)律的且這些處理對象是變化有規(guī)律的2 2、可以通過上述轉(zhuǎn)化而使問題簡化、可以通過上述轉(zhuǎn)化而使問題簡化3 3、必須有一個明確的遞歸出口，或稱遞歸的邊界、必須有一個明確的遞歸出口，或稱遞歸的邊界用分治法求解遞歸問題用分治法求解遞歸問題必備的三個條件必備的三個條件分治法求解遞歸問題算法的一般形式：分治法求解遞歸問題算法的一般形式： void p (參數(shù)表參數(shù)表)

27、 if （遞歸結(jié)束條件）可直接求解步驟；（遞歸結(jié)束條件）可直接求解步驟；-基本項(xiàng)基本項(xiàng) else p（較小的參數(shù)）；（較小的參數(shù)）；-歸納項(xiàng)歸納項(xiàng) long Fact ( long n ) if ( n = 0) return 1;/基本項(xiàng)基本項(xiàng) else return n * Fact (n-1); /歸納項(xiàng)歸納項(xiàng)返回返回 2參數(shù)參數(shù) 2 計(jì)算計(jì)算 2*Fact(1)返回返回 1參數(shù)參數(shù) 1 計(jì)算計(jì)算 1*Fact(0)返回返回 1參數(shù)參數(shù) 0 直接定值直接定值 = 1if ( n = 0 ) return 1;else return n * Fact (n-1); 求解階乘求解階乘 n!

28、n! 的過程的過程 main : Fact(4)返回返回 24 參數(shù)參數(shù) 4 計(jì)算計(jì)算 4*Fact(3)返回返回 6參數(shù)參數(shù) 3 計(jì)算計(jì)算 3*Fact(2)設(shè)有一個遞歸算法如下設(shè)有一個遞歸算法如下:int X(int n) if(n=3) return 1; else return X(n-2)+X(n-4)+1則計(jì)算則計(jì)算X(X(8)時需要計(jì)算時需要計(jì)算X函數(shù)函數(shù) 次次.D練習(xí)練習(xí)A. 8 B.9 C.16 D.18規(guī)則規(guī)則: :(1) (1) 每次只能移動一個圓盤每次只能移動一個圓盤(2) (2) 圓盤可以插在圓盤可以插在A,BA,B和和C C中的任一塔座上中的任一塔座上(3) (3)

29、 任何時刻不可將較大任何時刻不可將較大圓盤壓在較小圓盤之上圓盤壓在較小圓盤之上Hanoi塔問題塔問題ABCHanoi塔問題塔問題 n = 1n = 1，則直接從，則直接從 A A 移到移到 C C。否則。否則 (1)用用 C 柱做過渡，將柱做過渡，將 A 的的(n-1)個移到個移到 B(2)將將 A 最后一個直接最后一個直接移到移到 C (3)用用 A 做過渡，將做過渡，將 B 的的 (n-1) 個移到個移到 C#includeint c=0;void move(char x,int n,char z)cout+c,n,x,zc調(diào)用前調(diào)用前, , 系統(tǒng)完成系統(tǒng)完成: :(1)(1)將將實(shí)參實(shí)參

30、, ,返回地址返回地址等傳遞給被調(diào)用函數(shù)等傳遞給被調(diào)用函數(shù)(2)(2)為被調(diào)用函數(shù)的為被調(diào)用函數(shù)的局部變量局部變量分配存儲區(qū)分配存儲區(qū)(3)(3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口入口調(diào)用后調(diào)用后, , 系統(tǒng)完成系統(tǒng)完成: :(1)(1)保存被調(diào)用函數(shù)的計(jì)算保存被調(diào)用函數(shù)的計(jì)算結(jié)果結(jié)果(2)(2)釋放被調(diào)用函數(shù)的釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)(3)(3)依照被調(diào)用函數(shù)保存的依照被調(diào)用函數(shù)保存的返回地址返回地址將控制轉(zhuǎn)移到將控制轉(zhuǎn)移到調(diào)用函數(shù)調(diào)用函數(shù)“層次層次”主函數(shù)主函數(shù)第第1 1次調(diào)用次調(diào)用第第 i i 次調(diào)用次調(diào)用0 0層層1 1層層i i 層層“遞歸工作棧遞歸工作棧”“工

31、作記錄工作記錄”實(shí)在參數(shù)實(shí)在參數(shù), ,局部變量局部變量, ,返回地址返回地址遞歸函數(shù)調(diào)用的實(shí)現(xiàn)遞歸函數(shù)調(diào)用的實(shí)現(xiàn)空間效率空間效率時間效率時間效率O(2n)與遞歸樹的結(jié)點(diǎn)數(shù)成正比與遞歸樹的結(jié)點(diǎn)數(shù)成正比與遞歸樹的深度成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析遞歸算法的效率分析 1 2 3 4f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15f(n) = 2f(n-1)+1f(n-1) = 2f(n-2)+1f(n-2) = 2f(n-3)+1.f(3) = 2f(2)+1f(2) = 2f(1)+120f(n) = 21f(n-1)+202

32、1f(n-1) = 22f(n-2)+2122f(n-2) = 23f(n-3)+22.2n-3f(3) = 2n-2f(2)+ 2n-32n-2f(2) = 2n-1f(1)+ 2n-2f(n) = 20+21+2n-2+ 2n-1f(1) = 2n-1遞歸算法的效率分析遞歸算法的效率分析6464片金片移動次數(shù)：片金片移動次數(shù)：假如每秒鐘一次，共需多長時間呢？假如每秒鐘一次，共需多長時間呢？一年大約有一年大約有31536926秒，移完這些金片需要秒，移完這些金片需要多億年多億年世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅 !優(yōu)點(diǎn)：結(jié)構(gòu)清晰，程序易讀優(yōu)點(diǎn)：結(jié)構(gòu)清晰，

33、程序易讀缺點(diǎn)：每次調(diào)用要生成工作記錄，保存狀缺點(diǎn)：每次調(diào)用要生成工作記錄，保存狀態(tài)信息，入棧；返回時要出棧，恢復(fù)狀態(tài)信息，入棧；返回時要出棧，恢復(fù)狀態(tài)信息。時間開銷大。態(tài)信息。時間開銷大。遞歸的優(yōu)缺點(diǎn)遞歸的優(yōu)缺點(diǎn)遞歸遞歸非遞歸非遞歸3.4 3.4 隊(duì)列隊(duì)列隊(duì)列是一種先進(jìn)先出隊(duì)列是一種先進(jìn)先出(FIFO) 的線性表的線性表. 它只允許在它只允許在表的一端進(jìn)行插入表的一端進(jìn)行插入,而在另一端刪除元素而在另一端刪除元素),(21naaaqa a1 1a a2 2a a3 3a an n.入隊(duì)列入隊(duì)列隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾),(21naaaqa a1 1a a2 2a a3 3a an n.隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾

34、出隊(duì)列出隊(duì)列),(21naaaqa a1 1a a2 2a a3 3a an n.隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾出隊(duì)列出隊(duì)列),(21naaaqa a1 1a a2 2a a3 3a an n.隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾出隊(duì)列出隊(duì)列設(shè)棧設(shè)棧S S和隊(duì)列和隊(duì)列Q Q的初始狀態(tài)為空，元素的初始狀態(tài)為空，元素e1e1、e2e2、e3e3、e4e4、e5e5和和e6e6依次通過依次通過S S，一個元素出棧后即，一個元素出棧后即進(jìn)入進(jìn)入Q Q，若，若6 6個元素出隊(duì)的序列是個元素出隊(duì)的序列是e2e2、e4e4、e3e3、e6e6、e5e5和和e1e1，則棧，則棧S S的容量至少應(yīng)該是（）。的容量至少應(yīng)該是（）。 （A）2 （B

35、）3 （C）4 （D）6練習(xí)練習(xí)B0n , 2 , 1,|niElemSetaaDii數(shù)據(jù)對象數(shù)據(jù)對象:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系:端為隊(duì)列尾端為隊(duì)列頭約定n1111a ,a , 2 , 1,| ,niDaaaaRiiii基本操作基本操作: (1) InitQueue (&Q) /構(gòu)造空隊(duì)列構(gòu)造空隊(duì)列 (2) DestroyQueue (&Q) /銷毀隊(duì)列銷毀隊(duì)列 (3) ClearQueue (&S) /清空隊(duì)列清空隊(duì)列 (4) QueueEmpty(S) /判空判空. 空空-TRUE,ADT Queue 隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的抽象數(shù)據(jù)類型 (5) QueueLength(Q

36、) /取隊(duì)列長度取隊(duì)列長度 (6) GetHead (Q,&e) /取隊(duì)頭元素取隊(duì)頭元素, (7) EnQueue (&Q,e) /入隊(duì)列入隊(duì)列 (8) DeQueue (&Q,&e) /出隊(duì)列出隊(duì)列 (9) QueueTraverse(Q,visit() /遍歷遍歷ADT Queue隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的抽象數(shù)據(jù)類型#define M 100 /最大隊(duì)列長度最大隊(duì)列長度Typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間初始化的動態(tài)分配存儲空間 int front; /頭指針頭指針 int rear; /尾指針尾指針Sq

37、Queue; 隊(duì)列的順序表示用一維數(shù)組隊(duì)列的順序表示用一維數(shù)組baseM隊(duì)列的順序表示用一維數(shù)組隊(duì)列的順序表示用一維數(shù)組baseMQ.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearQ.frontQ.frontQ.rearQ.rearJ J1 1J J2 2J J3 3Q.frontQ.frontQ.rearQ.rearJ J3 3Q.frontQ.frontQ.rearQ.rearJ J5 5J J6 6front=rear=0空隊(duì)標(biāo)志：空隊(duì)標(biāo)志：front= =rear入隊(duì)：入隊(duì)：baserear+=x;出隊(duì)：出隊(duì)：x=basefront+;Q.fron

38、tQ.frontQ.rearQ.rearJ5J5J6J6Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearJ5J5J6J6J1J1J2J2J3J3J4J4存在的問題存在的問題設(shè)數(shù)組大小為設(shè)數(shù)組大小為Mfront=0rear=M時時再入隊(duì)再入隊(duì)真溢出真溢出front 0rear=M時時再入隊(duì)再入隊(duì)假溢出假溢出解決的方法循環(huán)隊(duì)列解決的方法循環(huán)隊(duì)列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在baseM-1之之后后若若rear+1=M則令則令rear=0;實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模?！边\(yùn)算運(yùn)算入隊(duì)：入隊(duì)： baserear=x

39、; rear=(rear+1)%M;出隊(duì)：出隊(duì)： x=basefront; front=(front+1)%M; J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入隊(duì)入隊(duì)隊(duì)空：隊(duì)空：front=rearfront=rear隊(duì)滿：隊(duì)滿：front=rearfront=rear解決方案：解決方案：1.1.另外另外設(shè)一個標(biāo)志設(shè)一個標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿以區(qū)別隊(duì)空、隊(duì)滿2 2. .少用一個元素空間少用一個元素空間： 隊(duì)空：隊(duì)空：front=rearfront=rear 隊(duì)滿：隊(duì)滿：( (rear+1)

40、%M=frontrear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出隊(duì)出隊(duì)rearrear循環(huán)隊(duì)列循環(huán)隊(duì)列#define MAXQSIZE 100 /最大隊(duì)列長度最大隊(duì)列長度Typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間初始化的動態(tài)分配存儲空間 int front; /頭指針頭指針 int rear; /尾指針尾指針SqQueue; Status InitQueue (SqQueue &a

41、mp;Q) Q.base =new QElemTypeMAXQSIZE if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;循環(huán)隊(duì)列初始化循環(huán)隊(duì)列初始化求循環(huán)隊(duì)列的長度求循環(huán)隊(duì)列的長度int QueueLength (SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.r

42、ear=(Q.rear+1)%MAXQSIZE; return OK;循環(huán)隊(duì)列入隊(duì)循環(huán)隊(duì)列入隊(duì)Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;循環(huán)隊(duì)列出隊(duì)循環(huán)隊(duì)列出隊(duì)naaa,21. . . .datadatanextnext隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾Q.frontQ.frontQ.rearQ.rear鏈隊(duì)列鏈隊(duì)列typedef struct QNode QElemType

43、 data; struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front; /隊(duì)隊(duì)頭指針頭指針 QueuePtr rear; /隊(duì)尾指針隊(duì)尾指針LinkQueue; 鏈隊(duì)列鏈隊(duì)列Q.frontQ.rearxQ.frontQ.rearxyQ.frontQ.rearxy(a) 空隊(duì)列空隊(duì)列(b) 元素元素x入入隊(duì)列隊(duì)列(d) 元素元素x出出隊(duì)列隊(duì)列Q.frontQ.rear(c) 元素元素y入入隊(duì)列隊(duì)列鏈隊(duì)列鏈隊(duì)列Status InitQueue (LinkQueue &Q) Q.front=Q.rear=(Queue

44、Ptr) malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;鏈隊(duì)列初始化鏈隊(duì)列初始化Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;銷毀鏈隊(duì)列銷毀鏈隊(duì)列 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); 判斷鏈隊(duì)列是否為空判斷鏈隊(duì)列是否為空S

45、tatus GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;求鏈隊(duì)列的隊(duì)頭元素求鏈隊(duì)列的隊(duì)頭元素Status EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;鏈隊(duì)列入隊(duì)鏈隊(duì)列入隊(duì)Q.frontQ.rearxypStatus DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;鏈隊(duì)列出隊(duì)鏈隊(duì)列出隊(duì)Q.frontQ.rearxyp【例例】汽車加油站汽車加油站隨著城市里汽車數(shù)量的急速增長，汽車加油站