《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》d(3)

1、.第 2 頁(yè)3.1 3.1 棧棧3.1.1 棧的概念棧的概念一、什么是棧一、什么是棧(stack)棧是僅能在棧是僅能在表尾表尾進(jìn)行插入、刪除操作的線(xiàn)性表。進(jìn)行插入、刪除操作的線(xiàn)性表。（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除 能進(jìn)行插入和刪除的一端稱(chēng)為能進(jìn)行插入和刪除的一端稱(chēng)為棧頂棧頂(top)(top)，另一端稱(chēng)為另一端稱(chēng)為棧底棧底(bottom)(bottom)。 稱(chēng)插入操作為稱(chēng)插入操作為進(jìn)棧進(jìn)棧(push)(push)，刪除操作為，刪除操作為出棧出棧(pop)(pop)。進(jìn)棧出棧操作只能在棧頂進(jìn)行。進(jìn)棧出棧操作只能在棧頂進(jìn)行。第 3 頁(yè)3.

2、1 3.1 棧棧出棧出棧進(jìn)棧進(jìn)棧棧的特點(diǎn)棧的特點(diǎn)后進(jìn)先出后進(jìn)先出第一個(gè)進(jìn)棧的元素在棧底第一個(gè)進(jìn)棧的元素在棧底最后一個(gè)進(jìn)棧的元素在棧頂最后一個(gè)進(jìn)棧的元素在棧頂?shù)谝粋€(gè)出棧的元素為棧頂元素第一個(gè)出棧的元素為棧頂元素最后一個(gè)出棧的元素為棧底元素最后一個(gè)出棧的元素為棧底元素棧的示意圖棧的示意圖棧頂棧頂棧底棧底a an na a2 2a a1 1后進(jìn)先出后進(jìn)先出表表（LIFO表表 Last_in First_out）第 4 頁(yè)3.1 3.1 棧棧二、棧的基本操作二、棧的基本操作1 1）初始化操作）初始化操作 InitStackInitStack(&S)(&S) 功能：構(gòu)造一個(gè)空棧功能：構(gòu)造

3、一個(gè)空棧S S。2 2）銷(xiāo)毀棧操作銷(xiāo)毀棧操作 DestroyStackDestroyStack(&S)(&S) 功能：銷(xiāo)毀一個(gè)已存在的棧。功能：銷(xiāo)毀一個(gè)已存在的棧。3 3）置空棧操作）置空棧操作 ClearStackClearStack(&S)(&S) 功能：將棧功能：將棧S S置為空棧。置為空棧。4 4）判空操作）判空操作 StackEmptyStackEmpty(S)(S) 功能：若棧功能：若棧S S為空，則返回為空，則返回TrueTrue，否則，棧不否則，棧不空返回空返回FalseFalse。第 5 頁(yè)3.1 3.1 棧棧二、棧的基本操作二、棧的基本操作5

4、 5）進(jìn)棧操作）進(jìn)棧操作 PushPush(&S, e)(&S, e) 功能：元素功能：元素e e進(jìn)棧。進(jìn)棧。6 6）退棧操作）退棧操作 PopPop(&S, &e)(&S, &e) 功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e e返回。返回。7 7）取棧頂元素操作）取棧頂元素操作 GetTopGetTop(S, &e)(S, &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e e 返回。返回。第 6 頁(yè)3.1 3.1 棧棧3.1.2 棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)和實(shí)現(xiàn)一、棧的順序存儲(chǔ)結(jié)構(gòu)一、棧的順序存儲(chǔ)結(jié)構(gòu)# #de

5、fine STACK_INIT_SIZE 100define STACK_INIT_SIZE 100 / / 棧存儲(chǔ)空間的初始分配量棧存儲(chǔ)空間的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10 / / 空間的分配增量空間的分配增量typedef structtypedef struct ElemType ElemType * *base;base; /棧空間基址?？臻g基址 ElemType ElemType * *top;top; /棧頂指針棧頂指針 int stacksize;int stacksize; /當(dāng)前分配的?？臻g大小

6、當(dāng)前分配的?？臻g大小 SqStack;SqStack;第 7 頁(yè)3.1 3.1 棧棧3.1.2 棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)和實(shí)現(xiàn)順序棧的圖示順序棧的圖示1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1當(dāng)棧用順序結(jié)構(gòu)存當(dāng)棧用順序結(jié)構(gòu)存儲(chǔ)時(shí)，棧的基本操儲(chǔ)時(shí)，棧的基本操作如建空棧、進(jìn)棧、作如建空棧、進(jìn)棧、出棧等如何實(shí)現(xiàn)？出棧等如何實(shí)現(xiàn)？約定：棧頂指針指向約定：棧頂指針指向棧頂元素的下一個(gè)位置棧頂元素的下一個(gè)位置第 8 頁(yè)3.1 3.1 棧棧3.1.2 棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)和實(shí)現(xiàn)toptopbasebasebasebas

7、etoptopA AB BC CD DE E空?？諚asebasetoptopA AA A進(jìn)棧進(jìn)棧B C D EB C D E進(jìn)棧進(jìn)棧basebasetoptopA AB BE D CE D C出棧出棧稱(chēng)為：棧滿(mǎn)稱(chēng)為：棧滿(mǎn) top top = = basebase top-base top-base = = stacksizestacksize ( (無(wú)可分配空間無(wú)可分配空間) )第 9 頁(yè)12340ABCDE3.1 3.1 棧棧l不可擴(kuò)充棧的操作不可擴(kuò)充棧的操作top=012340?？諚？諚ｍ斨羔槜ｍ斨羔榯op，指向指向?qū)嶋H棧頂實(shí)際棧頂后的空位后的空位置，初值為置，初值為 basetop進(jìn)

8、棧進(jìn)棧A棧滿(mǎn)棧滿(mǎn)BCDE設(shè)數(shù)組大小為設(shè)數(shù)組大小為Mtop=M，棧滿(mǎn)棧滿(mǎn)，此此時(shí)入棧，則時(shí)入棧，則上溢上溢 (overflow)toptoptoptoptoptoptoptoptoptop棧空?？誸op=base，?？諚？眨藭r(shí)出棧，則此時(shí)出棧，則下溢下溢(underflow)top12340出棧出棧第 10 頁(yè)12340ABCDE3.1 3.1 棧棧l可擴(kuò)充棧的操作可擴(kuò)充棧的操作棧頂指針棧頂指針top，指指向?qū)嶋H棧頂向?qū)嶋H棧頂后的下后的下一個(gè)位置，初值為一個(gè)位置，初值為 top=basetop進(jìn)棧進(jìn)棧A出棧出棧棧當(dāng)前空間棧當(dāng)前空間不足，需擴(kuò)充不足，需擴(kuò)充BCDE 設(shè)棧的初始分配量為設(shè)棧的初始分

9、配量為 Stacksize = STACK_INIT_SIZE。 若若 top = Stacksize，棧滿(mǎn)，此時(shí)棧滿(mǎn)，此時(shí)入棧，則需擴(kuò)充?？臻g，每次擴(kuò)充入棧，則需擴(kuò)充?？臻g，每次擴(kuò)充 STACK_INCREMENT； 若無(wú)可利用的存儲(chǔ)空間，則若無(wú)可利用的存儲(chǔ)空間，則上溢上溢 (overflow)。toptoptoptoptoptoptoptoptoptop?？諚？杖羧魌op=base, 棧空，此時(shí)出?？?，此時(shí)出棧，則棧，則下溢下溢(underflow)base?？諚？誸opbase base top1234012340第 11 頁(yè)3.1 3.1 棧棧二、順序?；静僮鞯乃惴ǘ?、順序?；静僮?/p>

10、的算法1）初始化操作）初始化操作 InitStack ( SqStack &S )參數(shù)：參數(shù)：S是存放棧的結(jié)構(gòu)變量是存放棧的結(jié)構(gòu)變量功能：功能：建一個(gè)空棧建一個(gè)空棧SS.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0第 12 頁(yè)3.1 3.1 棧棧初始化操作算法初始化操作算法Status InitStack ( SqStack &S ) /構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S S.base = ( ElemType *) malloc ( STACK_INIT_SIZE * sizeof(

11、ElemType) ); /為順序棧動(dòng)態(tài)分配存儲(chǔ)空間為順序棧動(dòng)態(tài)分配存儲(chǔ)空間 if ( ! S. base) exit( OVERFLOW ); /分配失敗分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; / InitStack第 13 頁(yè)9999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1S.stacksizeS.stacksizeS.topS.topS.baseS.base2 2） 銷(xiāo)毀棧操作銷(xiāo)毀棧操作 DestroyStack(SqStack &SSqS

12、tack &S)功能：功能：銷(xiāo)毀一個(gè)已存在的棧銷(xiāo)毀一個(gè)已存在的棧100100nullnull0 0nullnull3.1 3.1 棧棧第 14 頁(yè)Status DetroyStack ( SqStack &S ) if ( ! S.base ) return ERROR; /若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g） free ( S.base ); /回收?？臻g回收棧空間 S.base = S.top = NULL; S.stacksize = 0; return OK; /DetroyStack 銷(xiāo)毀操作算法銷(xiāo)毀操作算法3.1 3.1 棧棧第 15 頁(yè)3 3）

13、置空棧操作置空棧操作ClearStack (SqStack &S)功能功能：將棧將棧S置為空棧置為空棧 S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 13.1 3.1 棧棧第 16 頁(yè)Status ClearStack ( SqSt

14、ack &S ) if ( ! S.base ) return ERROR; / 若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g） S.top = S.base; return OK; /ClearStack 置空操作算法置空操作算法3.1 3.1 棧棧第 17 頁(yè)e ea an nS.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 14 4）取棧頂元素操作）取棧頂元素操作GetTop ( SqStack S, ElemType

15、&e )功能：功能：取棧頂元素，并用取棧頂元素，并用e e返回返回3.1 3.1 棧棧第 18 頁(yè)Status GetTop ( SqStack S, ElemType &e ) if ( S.top=S.base ) return ERROR; /?？諚？?e = e = * *(S.top-1);(S.top-1); return OK; /GetTop取棧頂元素操作算法取棧頂元素操作算法3.1 3.1 棧棧第 19 頁(yè)5 5）進(jìn)棧操作進(jìn)棧操作 Push ( SqStack &S, ElemType e SqStack &S, ElemType e )功能：

16、功能：元素元素 e e 進(jìn)棧。進(jìn)棧。S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1e e進(jìn)棧前進(jìn)棧前e e進(jìn)棧后進(jìn)棧后S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0e ea an na an-1n-1a a2 2a a1 13.1 3.1 棧棧* S.top = e;S.top +;第 20 頁(yè)進(jìn)棧操作算法進(jìn)棧操作算法Status Pu

17、sh ( SqStack &S, ElemType e ) /將元素將元素e插入棧中，使其成為新的棧頂元素插入棧中，使其成為新的棧頂元素 if ( S.top-S.base=S.stacksize ) / 若棧滿(mǎn)則追加存儲(chǔ)空間若棧滿(mǎn)則追加存儲(chǔ)空間 S.base = (ElemType * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType); if ( ! S. base ) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top = S.base + S.stacksize; S.sta

18、cksize += STACKINCREMENT; * * S.top + = e S.top + = e; /元素元素e 插入棧頂，后修改棧頂指針插入棧頂，后修改棧頂指針 return OK; /Push3.1 3.1 棧棧第 21 頁(yè)出棧操作前出棧操作前S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 16 6）出）出棧操作棧操作 Pop Pop ( SqStack &S, ElemType &e )( SqStack &a

19、mp;S, ElemType &e )功能：功能：棧頂元素退棧，并用棧頂元素退棧，并用 e e 返回。返回。3.1 3.1 棧棧e ea an n出棧操作后出棧操作后S.stacksizeS.stacksizeS.topS.topS.baseS.base1001009999n nn-1n-1n-2n-21 10 0a an-1n-1a a2 2a a1 1S.top -;e = * S.top;第 22 頁(yè)Status Pop ( SqStack &S, ElemType &e )=S.base ) return ERROR; / 棧空?？?e = e = * * -;

20、 ; / -S.top; e=S.top; e=* *S.top;S.top; return OK; /Pop出棧操作算法出棧操作算法3.1 3.1 棧棧另一種約定：棧頂指針指向另一種約定：棧頂指針指向棧頂元素棧頂元素。該如何處理？。該如何處理？第 23 頁(yè)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱(chēng)鏈棧。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱(chēng)鏈棧。棧頂棧頂棧底棧底 在前面學(xué)習(xí)了線(xiàn)在前面學(xué)習(xí)了線(xiàn)性鏈表的插入、刪除性鏈表的插入、刪除操作算法，不難寫(xiě)出操作算法，不難寫(xiě)出鏈?zhǔn)綏３跏蓟?、進(jìn)棧鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法、出棧等操作的算法。3 3.1.3 .1.3 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)3.1 3.1 棧棧Data n

21、extData nextS Sa an-1n-1a a1 1a an n第 24 頁(yè)順序棧和鏈?zhǔn)綏５谋容^順序棧和鏈?zhǔn)綏５谋容^l棧的特點(diǎn)：后進(jìn)先出棧的特點(diǎn)：后進(jìn)先出體現(xiàn)了元素之間的透明性體現(xiàn)了元素之間的透明性l時(shí)間效率時(shí)間效率所有操作都只需常數(shù)時(shí)間所有操作都只需常數(shù)時(shí)間順序棧和鏈?zhǔn)綏Ｔ跁r(shí)間效率上難分伯仲順序棧和鏈?zhǔn)綏Ｔ跁r(shí)間效率上難分伯仲l空間效率空間效率順序棧須說(shuō)明一個(gè)固定的長(zhǎng)度順序棧須說(shuō)明一個(gè)固定的長(zhǎng)度鏈?zhǔn)綏５拈L(zhǎng)度可變，但增加結(jié)構(gòu)性開(kāi)銷(xiāo)鏈?zhǔn)綏５拈L(zhǎng)度可變，但增加結(jié)構(gòu)性開(kāi)銷(xiāo)第 25 頁(yè)順序棧和鏈?zhǔn)綏５谋容^順序棧和鏈?zhǔn)綏５谋容^l實(shí)際應(yīng)用中，順序棧比鏈?zhǔn)綏Ｓ玫酶鼜V泛實(shí)際應(yīng)用中，順序棧比鏈?zhǔn)綏Ｓ玫酶鼜V泛

22、 順序棧容易根據(jù)棧頂位置，進(jìn)行相對(duì)位移，快順序棧容易根據(jù)棧頂位置，進(jìn)行相對(duì)位移，快速定位并讀取棧的內(nèi)部元素速定位并讀取棧的內(nèi)部元素 順序棧讀取內(nèi)部元素的時(shí)間為順序棧讀取內(nèi)部元素的時(shí)間為O(1)O(1)，而鏈?zhǔn)綏?，而鏈?zhǔn)綏t需要沿著指針鏈游走，顯則需要沿著指針鏈游走，顯然然慢些，讀取第慢些，讀取第k k個(gè)個(gè)元素需要時(shí)間為元素需要時(shí)間為O(k) O(k) l一般來(lái)說(shuō)，棧不允許一般來(lái)說(shuō)，棧不允許“讀取內(nèi)部元素讀取內(nèi)部元素”，只能，只能在棧頂操作在棧頂操作 第 26 頁(yè)1.1.數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換2.2.括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)3.3.行編輯程序行編輯程序4.4.迷宮求解迷宮求解5.5.表達(dá)式求值表達(dá)

23、式求值3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 27 頁(yè)3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例1.1.數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換l十進(jìn)制數(shù)十進(jìn)制數(shù)到八進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)中的基本問(wèn)題到八進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)中的基本問(wèn)題l算法可基于下列原理：算法可基于下列原理： N=(N div d)d+Nmod d第 28 頁(yè)例如：(1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下 商 余數(shù) N Ndiv8 Nmod8 1348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序輸出逆序第 29 頁(yè)void conversion( ) /輸入一個(gè)非負(fù)十進(jìn)制數(shù)，輸出八進(jìn)制數(shù) InitStack(S);

24、 /建空棧 scanf(“%d”, N); /輸入一個(gè)非負(fù)十進(jìn)制整數(shù) while(N) / N不等于零循環(huán) Push(S, N%8); / 余數(shù)進(jìn)棧 N=N/8; /整除運(yùn)算,N=商 while(! StackEmpty) /輸出棧中的八制數(shù)位 Pop(S, e); Printf(“%d”, e); DestroyStack(S); / /conversion 第 30 頁(yè) 迷宮求解迷宮求解3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例入口入口出口出口如何走出如何走出迷宮？迷宮？第 31 頁(yè) 求迷宮路徑算法求迷宮路徑算法 若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)；則納入路徑，繼續(xù)前進(jìn)；

25、 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，后退一個(gè)位置，換方向繼后退一個(gè)位置，換方向繼續(xù)探索；續(xù)探索； 若四周若四周“均已探索均已探索”，則后退一步，將當(dāng)前位置則后退一步，將當(dāng)前位置從路徑中刪除出去，換方從路徑中刪除出去，換方向繼續(xù)探索。向繼續(xù)探索。3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 32 頁(yè) 求迷宮路徑算法求迷宮路徑算法 若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)；則納入路徑，繼續(xù)前進(jìn)； 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，后退一個(gè)位置，換方向繼后退一個(gè)位置，換方向繼續(xù)探索；續(xù)探索； 若四周若四周“均已探索均已探索”，則后退一步，將當(dāng)前位置則后退一步，將當(dāng)前位置從路徑中刪

26、除出去，換方從路徑中刪除出去，換方向繼續(xù)探索。向繼續(xù)探索。3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例1 233入口入口出口出口6 4859第 33 頁(yè)l求迷宮中一條從入口到出口的路徑的算法求迷宮中一條從入口到出口的路徑的算法設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，且沒(méi)被訪(fǎng)問(wèn)過(guò) 則 當(dāng)前位置插入棧頂； /保存在路徑中 若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的第一個(gè)相鄰方塊為新 的當(dāng)前位置； 否則/當(dāng)前位置不可通或在已走過(guò)的路徑上 while(棧不空）；第 34 頁(yè) 若棧不空 棧頂位置退棧；新的當(dāng)前位置為退棧位置 若棧不空且當(dāng)前位置的四周均已探索過(guò)， 則 棧頂位置退棧；新的

27、當(dāng)前位置為退棧位置 直至找到不是四周均已探索過(guò)的位置或?？? 若當(dāng)前位置尚有未被探索的方向, 則設(shè)定新的當(dāng)前位置為: 按（下、右、左、上）的順序找到的當(dāng)前位置的下一相鄰塊；若?？胀顺鰓hile循環(huán)，表明迷宮沒(méi)有通路。/當(dāng)前位置不可通或在已走過(guò)的路徑上第 35 頁(yè)1 1）問(wèn)題的提出）問(wèn)題的提出從鍵盤(pán)一次性輸入一串算術(shù)表達(dá)式，給出計(jì)算結(jié)果。從鍵盤(pán)一次性輸入一串算術(shù)表達(dá)式，給出計(jì)算結(jié)果。2+32+3* *(5-4)=5(5-4)=5棧的應(yīng)用舉例表達(dá)式求值棧的應(yīng)用舉例表達(dá)式求值3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 36 頁(yè)2 2）表達(dá)式的構(gòu)成）表達(dá)式的構(gòu)成 操作數(shù)操作數(shù)+ +運(yùn)算符運(yùn)算符+ +界

28、符界符1 12 23 34 4如何確定運(yùn)算符的運(yùn)算順序？如何確定運(yùn)算符的運(yùn)算順序？常數(shù)常數(shù)+ +、- -、* *、/ /( )( )、# #3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3 3）表達(dá)式的求值）表達(dá)式的求值： 例：例：5+65+6 (1+2)-4(1+2)-4 按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為：按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為： 5+6 5+6 (1+2)-4 = 5+6(1+2)-4 = 5+6 3-4 = 5+18-4 = 23-4 = 193-4 = 5+18-4 = 23-4 = 19第 37 頁(yè)4 4）算符優(yōu)先關(guān)系表）算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運(yùn)算符表達(dá)

29、式中任何相鄰運(yùn)算符 1 1、 2 2 的優(yōu)先關(guān)系有：的優(yōu)先關(guān)系有： 1 1 2 2： 1 1的優(yōu)先級(jí)的優(yōu)先級(jí) 高于高于 2 2+ 2 1 - -* */( () )#+ - - * * / ( ( ) ) # = 注：注：1 1、2 2是相鄰算符，是相鄰算符，1 1在左，在左，2 2在右在右3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 38 頁(yè)5 5）算符優(yōu)先算法）算符優(yōu)先算法從左向右掃描表達(dá)式：從左向右掃描表達(dá)式： 遇操作數(shù)遇操作數(shù)保存；保存； 遇運(yùn)算符號(hào)遇運(yùn)算符號(hào) j j與前面的剛掃描過(guò)的運(yùn)算符與前面的剛掃描過(guò)的運(yùn)算符 i i比較：比較： 若若 i i j j 則保存則保存 j j（因此已保

30、存的運(yùn)算符的優(yōu)先關(guān)系為因此已保存的運(yùn)算符的優(yōu)先關(guān)系為 1 1 2 2 3 3 j j 則說(shuō)明則說(shuō)明 i i是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算可進(jìn)行運(yùn)算 若若 i i= = j j 則說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)則說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào) 5 + 4 (1 + 2) - 6后面也許有優(yōu)先級(jí)后面也許有優(yōu)先級(jí)更高的算符更高的算符+ +(后保存的算符優(yōu)先級(jí)高后保存的算符優(yōu)先級(jí)高用兩個(gè)棧分別保存掃描過(guò)程中用兩個(gè)棧分別保存掃描過(guò)程中遇到的操作數(shù)和運(yùn)算符遇到的操作數(shù)和運(yùn)算符3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 39 頁(yè) 在算符優(yōu)先算法中，

31、建立了兩個(gè)工作棧。一個(gè)在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是是OPTROPTR棧，用以保存棧，用以保存運(yùn)算符運(yùn)算符；一個(gè)是；一個(gè)是OPNDOPND棧，用以棧，用以保存保存操作數(shù)操作數(shù)或運(yùn)算或運(yùn)算結(jié)果結(jié)果。算法的基本思想是：算法的基本思想是： 1 1、首先置、首先置操作數(shù)棧操作數(shù)棧為空棧，表達(dá)式起始符為空棧，表達(dá)式起始符“# #”為為運(yùn)算符棧運(yùn)算符棧的棧底元素。的棧底元素。 2 2、依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)，、依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)，則進(jìn)則進(jìn)OPNDOPND棧；若是運(yùn)算符，則與棧；若是運(yùn)算符，則與OPTROPTR棧的棧頂運(yùn)算棧的棧頂運(yùn)算符比較優(yōu)先級(jí)后作相應(yīng)操作。符比

32、較優(yōu)先級(jí)后作相應(yīng)操作。 直至整個(gè)表達(dá)式求值完畢（即直至整個(gè)表達(dá)式求值完畢（即OPTROPTR棧的棧頂元棧的棧頂元素和當(dāng)前讀入的字符均為素和當(dāng)前讀入的字符均為“# #”）。）。3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 40 頁(yè)表達(dá)式求值示意：表達(dá)式求值示意：5 + 6 5 + 6 ( 1 + 2 ) - 4( 1 + 2 ) - 4toptopbasebaseOPTROPTR棧棧# #OPNDOPND棧棧toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptopt

33、optoptoptop3 3toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5讀入表達(dá)式過(guò)程：讀入表達(dá)式過(guò)程：+ + 6 6 ( ( 1 1 + + 2 2 ) ) - - 4 4 # #= = 19191+2=31+2=36 63=183=185+18=235+18=2323-4=1923-4=193.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例第 41 頁(yè)3.3 3.3 棧與遞歸棧與遞歸l遞歸

34、函數(shù)遞歸函數(shù)l遞歸算法執(zhí)行過(guò)程及棧的作用遞歸算法執(zhí)行過(guò)程及棧的作用第 42 頁(yè)A( ) A( ); C( ) B（） B( ) C( ); l遞歸函數(shù)遞歸函數(shù)第 43 頁(yè)l遞歸是很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多遞歸是很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多領(lǐng)域中都會(huì)用到。領(lǐng)域中都會(huì)用到。l任何一個(gè)遞歸程序都可以任何一個(gè)遞歸程序都可以通過(guò)棧操作使用非遞歸通過(guò)棧操作使用非遞歸程序?qū)崿F(xiàn)。程序?qū)崿F(xiàn)。3.3 3.3 棧與遞歸棧與遞歸l棧棧在實(shí)現(xiàn)函數(shù)遞歸調(diào)用中所發(fā)揮的作用在實(shí)現(xiàn)函數(shù)遞歸調(diào)用中所發(fā)揮的作用 棧的一個(gè)最廣泛的應(yīng)用隱藏在用戶(hù)看不到的地棧的一個(gè)最廣泛的應(yīng)用隱藏在用戶(hù)看不到的地方：高級(jí)語(yǔ)言方：高級(jí)語(yǔ)

35、言運(yùn)行時(shí)環(huán)境運(yùn)行時(shí)環(huán)境提供的提供的函數(shù)調(diào)用機(jī)制函數(shù)調(diào)用機(jī)制。 運(yùn)行時(shí)環(huán)境運(yùn)行時(shí)環(huán)境指的是目標(biāo)計(jì)算機(jī)上用來(lái)管理存儲(chǔ)指的是目標(biāo)計(jì)算機(jī)上用來(lái)管理存儲(chǔ)器并保存指令執(zhí)行過(guò)程中所需信息的寄存器及存器并保存指令執(zhí)行過(guò)程中所需信息的寄存器及存儲(chǔ)器的結(jié)構(gòu)。儲(chǔ)器的結(jié)構(gòu)。 第 44 頁(yè)函數(shù)調(diào)用過(guò)程函數(shù)調(diào)用過(guò)程 在非遞歸情況下，數(shù)據(jù)區(qū)的分配可以在程在非遞歸情況下，數(shù)據(jù)區(qū)的分配可以在程序運(yùn)行前進(jìn)行，直到整個(gè)程序運(yùn)行結(jié)束才釋放，序運(yùn)行前進(jìn)行，直到整個(gè)程序運(yùn)行結(jié)束才釋放，這種分配稱(chēng)為這種分配稱(chēng)為靜態(tài)分配靜態(tài)分配。 采用靜態(tài)分配時(shí)，函數(shù)的調(diào)用和返回處理采用靜態(tài)分配時(shí)，函數(shù)的調(diào)用和返回處理比較簡(jiǎn)單，不需要每次分配和釋放被調(diào)函數(shù)

36、的數(shù)比較簡(jiǎn)單，不需要每次分配和釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)。據(jù)區(qū)。3.3 3.3 棧與遞歸棧與遞歸第 45 頁(yè)函數(shù)的遞歸調(diào)用過(guò)程函數(shù)的遞歸調(diào)用過(guò)程 在遞歸調(diào)用的情況下，被調(diào)函數(shù)的在遞歸調(diào)用的情況下，被調(diào)函數(shù)的局部變量局部變量不能靜態(tài)地分配某些固定單元，而必須每調(diào)用一不能靜態(tài)地分配某些固定單元，而必須每調(diào)用一次就分配一份次就分配一份新的新的局部變量局部變量，以存放當(dāng)前函數(shù)所，以存放當(dāng)前函數(shù)所使用的數(shù)據(jù)，當(dāng)函數(shù)結(jié)束返回時(shí)隨即釋放。使用的數(shù)據(jù)，當(dāng)函數(shù)結(jié)束返回時(shí)隨即釋放。 故其存儲(chǔ)分配只能在執(zhí)行調(diào)用時(shí)（故其存儲(chǔ)分配只能在執(zhí)行調(diào)用時(shí)（程序運(yùn)行程序運(yùn)行過(guò)程中過(guò)程中）才能進(jìn)行，即所謂的）才能進(jìn)行，即所謂的動(dòng)態(tài)分配動(dòng)

37、態(tài)分配。 在內(nèi)存中要開(kāi)辟一個(gè)稱(chēng)為在內(nèi)存中要開(kāi)辟一個(gè)稱(chēng)為運(yùn)行棧（運(yùn)行棧（runtime runtime stackstack）的足夠大的動(dòng)態(tài)區(qū)，以處理運(yùn)行數(shù)據(jù)。的足夠大的動(dòng)態(tài)區(qū)，以處理運(yùn)行數(shù)據(jù)。3.3 3.3 棧與遞歸棧與遞歸第 46 頁(yè)函數(shù)運(yùn)行時(shí)的動(dòng)態(tài)分配過(guò)程函數(shù)運(yùn)行時(shí)的動(dòng)態(tài)分配過(guò)程 用作動(dòng)態(tài)數(shù)據(jù)分配的存儲(chǔ)區(qū)可用作動(dòng)態(tài)數(shù)據(jù)分配的存儲(chǔ)區(qū)可按多種方式組織。典型的組織是按多種方式組織。典型的組織是將這個(gè)存儲(chǔ)器分為將這個(gè)存儲(chǔ)器分為棧（棧（stackstack）區(qū)域和區(qū)域和堆（堆（heapheap）區(qū)域：區(qū)域： 棧棧區(qū)域用于分配發(fā)生在后進(jìn)先區(qū)域用于分配發(fā)生在后進(jìn)先出出LIFOLIFO風(fēng)格中的數(shù)據(jù)（諸如函

38、數(shù)風(fēng)格中的數(shù)據(jù)（諸如函數(shù)的調(diào)用）。的調(diào)用）。 堆堆區(qū)域則用于不符合區(qū)域則用于不符合LIFOLIFO（諸（諸如指針的分配）的動(dòng)態(tài)分配。如指針的分配）的動(dòng)態(tài)分配。3.3 3.3 棧與遞歸棧與遞歸堆堆自由空間自由空間代碼區(qū)域代碼區(qū)域全程全程/ /靜態(tài)區(qū)域靜態(tài)區(qū)域棧棧第 47 頁(yè)函數(shù)活動(dòng)記錄（函數(shù)活動(dòng)記錄（activation activation recordrecord） 是動(dòng)態(tài)存儲(chǔ)分配中一個(gè)重是動(dòng)態(tài)存儲(chǔ)分配中一個(gè)重要要的的結(jié)構(gòu)結(jié)構(gòu)。 當(dāng)調(diào)用或激活函數(shù)時(shí)，函當(dāng)調(diào)用或激活函數(shù)時(shí)，函數(shù)的數(shù)的活動(dòng)記錄活動(dòng)記錄包含了為其局包含了為其局部數(shù)據(jù)分配的存儲(chǔ)空間。部數(shù)據(jù)分配的存儲(chǔ)空間。3.3 3.3 棧與遞歸棧與

39、遞歸用作局部用作局部臨時(shí)變量的空間臨時(shí)變量的空間自變量（參數(shù)）空間自變量（參數(shù)）空間用作薄記信息的空間，用作薄記信息的空間，諸如返回地址諸如返回地址用作局部變量的空間用作局部變量的空間第 48 頁(yè)運(yùn)行棧的動(dòng)態(tài)變化運(yùn)行棧的動(dòng)態(tài)變化 每次調(diào)用時(shí)，執(zhí)行進(jìn)棧操作，把被調(diào)函數(shù)的活每次調(diào)用時(shí)，執(zhí)行進(jìn)棧操作，把被調(diào)函數(shù)的活動(dòng)信息壓入棧中，即當(dāng)進(jìn)行一個(gè)新的函數(shù)調(diào)用時(shí)，動(dòng)信息壓入棧中，即當(dāng)進(jìn)行一個(gè)新的函數(shù)調(diào)用時(shí)，都要在棧的頂部為新的活動(dòng)記錄分配空間。都要在棧的頂部為新的活動(dòng)記錄分配空間。 在每次從函數(shù)返回時(shí)，執(zhí)行出棧操作，釋放本在每次從函數(shù)返回時(shí)，執(zhí)行出棧操作，釋放本次的活動(dòng)記錄，恢復(fù)到上次調(diào)用所分配的數(shù)據(jù)區(qū)次

40、的活動(dòng)記錄，恢復(fù)到上次調(diào)用所分配的數(shù)據(jù)區(qū)中。中。 被調(diào)函數(shù)中變量地址全部采用相對(duì)于棧頂?shù)南啾徽{(diào)函數(shù)中變量地址全部采用相對(duì)于棧頂?shù)南鄬?duì)地址來(lái)表示。對(duì)地址來(lái)表示。3.3 3.3 棧與遞歸棧與遞歸第 49 頁(yè)一個(gè)函數(shù)在運(yùn)行棧上可以有若干不同的活動(dòng)記錄，一個(gè)函數(shù)在運(yùn)行棧上可以有若干不同的活動(dòng)記錄，每個(gè)活動(dòng)記錄都代表了一次不同的調(diào)用每個(gè)活動(dòng)記錄都代表了一次不同的調(diào)用 對(duì)于遞歸函數(shù)來(lái)說(shuō)，遞歸的深度就決定了其在對(duì)于遞歸函數(shù)來(lái)說(shuō)，遞歸的深度就決定了其在運(yùn)行棧中活動(dòng)記錄的數(shù)目。運(yùn)行棧中活動(dòng)記錄的數(shù)目。 當(dāng)函數(shù)遞歸調(diào)用時(shí)，函數(shù)體的同一個(gè)局部變量，當(dāng)函數(shù)遞歸調(diào)用時(shí)，函數(shù)體的同一個(gè)局部變量，在不同的遞歸層次要分配不同

41、的存儲(chǔ)空間，放在在不同的遞歸層次要分配不同的存儲(chǔ)空間，放在內(nèi)部棧的不同位置。內(nèi)部棧的不同位置。3.3 3.3 棧與遞歸棧與遞歸第 50 頁(yè)函數(shù)調(diào)用時(shí)的三個(gè)步驟函數(shù)調(diào)用時(shí)的三個(gè)步驟 調(diào)用函數(shù)發(fā)送調(diào)用信息調(diào)用函數(shù)發(fā)送調(diào)用信息。調(diào)用信息包括調(diào)用。調(diào)用信息包括調(diào)用方要傳送給被調(diào)方的信息，諸如實(shí)參、返回地址方要傳送給被調(diào)方的信息，諸如實(shí)參、返回地址等。等。 為被調(diào)函數(shù)分配需要的局部數(shù)據(jù)區(qū)為被調(diào)函數(shù)分配需要的局部數(shù)據(jù)區(qū)，用來(lái)存，用來(lái)存放被調(diào)方定義的局部變量、形參變量（存放實(shí)放被調(diào)方定義的局部變量、形參變量（存放實(shí)參）、返回地址等，并接受調(diào)用方傳送來(lái)的調(diào)用參）、返回地址等，并接受調(diào)用方傳送來(lái)的調(diào)用信息。信息

42、。 調(diào)用方暫停，調(diào)用方暫停，把計(jì)算控制轉(zhuǎn)到被調(diào)方把計(jì)算控制轉(zhuǎn)到被調(diào)方，即自，即自動(dòng)轉(zhuǎn)移到被調(diào)用的函數(shù)的程入口。動(dòng)轉(zhuǎn)移到被調(diào)用的函數(shù)的程入口。3.3 3.3 棧與遞歸棧與遞歸第 51 頁(yè)當(dāng)被調(diào)方結(jié)束運(yùn)行，返回到調(diào)用方時(shí)，其返回處當(dāng)被調(diào)方結(jié)束運(yùn)行，返回到調(diào)用方時(shí)，其返回處理也分解為三步進(jìn)行理也分解為三步進(jìn)行 傳送返回信息傳送返回信息，包括被調(diào)方要傳回給調(diào)用方，包括被調(diào)方要傳回給調(diào)用方的信息，諸如計(jì)算結(jié)果等。的信息，諸如計(jì)算結(jié)果等。 釋放分配給被調(diào)方的數(shù)據(jù)區(qū)釋放分配給被調(diào)方的數(shù)據(jù)區(qū)。 按返回地址把按返回地址把控制轉(zhuǎn)回調(diào)用方控制轉(zhuǎn)回調(diào)用方。3.3 3.3 棧與遞歸棧與遞歸第 52 頁(yè)以階乘為例：以階乘

43、為例：#include #include main( )main( ) int x;int x;scanf(scanf(”%d%d”, &x), &x)；printf(printf(”%dn%dn”, factorial(4);, factorial(4); long factorial( long n ) long factorial( long n ) if ( n if ( n = 0 ) 0 ) return 1; return 1;elseelse return n return n * * factorial( n-1); / factorial( n-1); /

44、遞歸調(diào)用遞歸調(diào)用 3.3 3.3 棧與遞歸棧與遞歸第 53 頁(yè)遞歸函數(shù)調(diào)用過(guò)程遞歸函數(shù)調(diào)用過(guò)程3.3 3.3 棧與遞歸棧與遞歸n: 4控制鏈控制鏈返回地址返回地址第第1次調(diào)用次調(diào)用factorial時(shí)時(shí)的活動(dòng)記錄的活動(dòng)記錄x: 4主程序主程序main的活的活動(dòng)記錄動(dòng)記錄棧生長(zhǎng)棧生長(zhǎng)方向方向n: 4控制鏈控制鏈返回地址返回地址第第1次調(diào)用次調(diào)用factorial時(shí)的時(shí)的活動(dòng)記錄活動(dòng)記錄x: 4主程序主程序main的活動(dòng)記錄的活動(dòng)記錄n: 3控制鏈控制鏈返回地址返回地址第第2次調(diào)用次調(diào)用factorial時(shí)的時(shí)的活動(dòng)記錄活動(dòng)記錄棧生長(zhǎng)棧生長(zhǎng)方向方向第 54 頁(yè)3.3 3.3 棧與遞歸棧與遞歸n:

45、4控制鏈控制鏈返回地址返回地址第第1 1次調(diào)用次調(diào)用factorialfactorial的活動(dòng)記錄的活動(dòng)記錄n: 3控制鏈控制鏈返回地址返回地址n: 2控制鏈控制鏈返回地址返回地址n: 1控制鏈控制鏈返回地址返回地址n: 0控制鏈控制鏈返回地址返回地址0! = 11! = 1*0！=12! = 2*1！= 23! = 3*2！= 64! = 4*3！= 24自由空間自由空間棧生長(zhǎng)方向棧生長(zhǎng)方向x: 4主程序主程序 main main 的的活動(dòng)記錄活動(dòng)記錄返回地址返回地址n: 2控制鏈控制鏈返回地址返回地址返回地址返回地址！第第2 2次調(diào)用次調(diào)用factorialfactorial的活動(dòng)記錄的活

46、動(dòng)記錄第第3 3次調(diào)用次調(diào)用factorialfactorial的活動(dòng)記錄的活動(dòng)記錄第第4 4次調(diào)用次調(diào)用factorialfactorial的活動(dòng)記錄的活動(dòng)記錄第第5 5次調(diào)用次調(diào)用factorialfactorial的活動(dòng)記錄的活動(dòng)記錄第 55 頁(yè)3.4.1 3.4.1 隊(duì)列的概念隊(duì)列的概念一、什么是隊(duì)列（一、什么是隊(duì)列（queue)queue) 隊(duì)列是僅能在表頭進(jìn)行隊(duì)列是僅能在表頭進(jìn)行刪除刪除，表尾進(jìn)行，表尾進(jìn)行插入插入的線(xiàn)性表。的線(xiàn)性表。（a, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除 能進(jìn)行插入的一端稱(chēng)為能進(jìn)行插入的一端稱(chēng)為隊(duì)尾隊(duì)尾(rear)

47、(rear)，能進(jìn)行，能進(jìn)行刪除的一端稱(chēng)為刪除的一端稱(chēng)為隊(duì)頭隊(duì)頭(front)(front)。 稱(chēng)插入操作為稱(chēng)插入操作為入隊(duì)入隊(duì)(enqueue)(enqueue)，刪除操作為，刪除操作為出隊(duì)出隊(duì)(dequeue)(dequeue)。3.4 3.4 隊(duì)列隊(duì)列第 56 頁(yè)a a1 1 a a2 2 a a3 3 a an n隊(duì)隊(duì)頭頭隊(duì)隊(duì)尾尾出隊(duì)列出隊(duì)列隊(duì)列的示意圖隊(duì)列的示意圖隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)先進(jìn)先出先進(jìn)先出第一個(gè)入隊(duì)的元素在第一個(gè)入隊(duì)的元素在隊(duì)頭隊(duì)頭最后一個(gè)入隊(duì)的元素在最后一個(gè)入隊(duì)的元素在隊(duì)尾隊(duì)尾第一個(gè)出隊(duì)的元素為隊(duì)頭元素第一個(gè)出隊(duì)的元素為隊(duì)頭元素最后一個(gè)出隊(duì)的元素為隊(duì)尾元素最后一個(gè)出隊(duì)的元

48、素為隊(duì)尾元素入隊(duì)列入隊(duì)列3.4 3.4 隊(duì)列隊(duì)列第 57 頁(yè)二、隊(duì)列的基本操作二、隊(duì)列的基本操作1 1）初始化操作）初始化操作 InitQueueInitQueue(&Q)(&Q) 功能：構(gòu)造一個(gè)空隊(duì)列功能：構(gòu)造一個(gè)空隊(duì)列Q Q。2 2）銷(xiāo)毀操作銷(xiāo)毀操作 DestroyQueueDestroyQueue(&Q)(&Q) 功能：銷(xiāo)毀已存在隊(duì)列功能：銷(xiāo)毀已存在隊(duì)列Q Q。3 3）置空操作置空操作 ClearQueueClearQueue(&Q)(&Q) 功能：功能：將隊(duì)列將隊(duì)列Q Q置為空隊(duì)列。置為空隊(duì)列。4 4）出隊(duì)操作）出隊(duì)操作 DeQueueD

49、eQueue(&Q,&e)(&Q,&e) 功能：刪除功能：刪除Q Q的隊(duì)頭元素。的隊(duì)頭元素。5 5）取隊(duì)頭元素操作取隊(duì)頭元素操作 GetHeadGetHead(Q,&e)(Q,&e) 功能：取隊(duì)頭元素，并用功能：取隊(duì)頭元素，并用e e返回。返回。3.4 3.4 隊(duì)列隊(duì)列第 58 頁(yè)二、隊(duì)列的基本操作二、隊(duì)列的基本操作6 6）入隊(duì)操作入隊(duì)操作 EnQueueEnQueue(&Q, e )(&Q, e ) 功能：將元素功能：將元素e e插入插入Q Q的隊(duì)尾。的隊(duì)尾。7 7）判空操作）判空操作 QueueEmptyQueueEmpty(

50、Q)(Q) 功能：若隊(duì)列功能：若隊(duì)列Q Q為空，則返回為空，則返回TrueTrue，否則返回否則返回FalseFalse。3.4 3.4 隊(duì)列隊(duì)列第 59 頁(yè)3.4.2 3.4.2 循環(huán)隊(duì)列循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)一、隊(duì)列的順序存貯結(jié)構(gòu)一、隊(duì)列的順序存貯結(jié)構(gòu)# #define MAXSIZE 100 define MAXSIZE 100 /最大隊(duì)列長(zhǎng)度最大隊(duì)列長(zhǎng)度typedef structtypedef struct ElemType ElemType * * base; base; /初始化時(shí)分配初始化時(shí)分配存儲(chǔ)空間的基址存儲(chǔ)空間的基址 intint front;

51、front; /隊(duì)頭隊(duì)頭指針，指向隊(duì)頭元素指針，指向隊(duì)頭元素 int rear; int rear; /隊(duì)尾隊(duì)尾指針，指向隊(duì)尾元素的指針，指向隊(duì)尾元素的下一個(gè)下一個(gè)位置位置 SqQueue;SqQueue;隊(duì)頭隊(duì)頭, ,隊(duì)尾指針隊(duì)尾指針是用整型實(shí)現(xiàn)的是用整型實(shí)現(xiàn)的3.4 3.4 隊(duì)列隊(duì)列第 60 頁(yè)Q.rearQ.rearQ.frontQ.frontJ1J1J2J2J3J3Q.rearQ.rearQ.frontQ.frontJ3J3( (a a) )空隊(duì)列空隊(duì)列(b)J1,J2(b)J1,J2和和J3J3相繼入隊(duì)列相繼入隊(duì)列(c)J1(c)J1和和J2J2相繼出隊(duì)相繼出隊(duì)(d)J4,J5(d)

52、J4,J5和和J6J6相繼相繼入隊(duì)之后入隊(duì)之后, ,J3J3出隊(duì)出隊(duì)Q.rearQ.rearQ.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearQ.frontQ.frontJ6J6J5J5J4J4均為整數(shù)均為整數(shù)用箭頭指示只是為了直觀用箭頭指示只是為了直觀又有又有J7J7入隊(duì)入隊(duì), ,該怎么辦？該怎么辦？3.4 3.4 隊(duì)列隊(duì)列第 61 頁(yè)3.4 3.4 隊(duì)列隊(duì)列l(wèi)隊(duì)列基本操作隊(duì)列基本操作123450隊(duì)空隊(duì)空f(shuō)ront=0rear=0123450frontJ1,J2,J3入隊(duì)入隊(duì)J1J2J3rearJ4,J5,J6入隊(duì)入隊(duì)rear123450J4J5J6fr

53、ont設(shè)兩個(gè)指針：設(shè)兩個(gè)指針：front,rear。rear指指向向隊(duì)尾元素隊(duì)尾元素的下一個(gè)的下一個(gè)位置位置；front指指向向隊(duì)頭元素隊(duì)頭元素。初值初值 frontfront= =rearrear= =0 0隊(duì)空條件：隊(duì)空條件：front=rear 入隊(duì)列：入隊(duì)列：Q.base rear+ = e; 出隊(duì)列：出隊(duì)列：e =Q.base front+ ;rearrearfrontrear123450J1,J2,J3出隊(duì)出隊(duì)J1J2J3frontfrontfront又有又有J7J7入隊(duì)入隊(duì), ,該怎么辦？該怎么辦？第 62 頁(yè)3.4 3.4 隊(duì)列隊(duì)列l(wèi)存在問(wèn)題存在問(wèn)題設(shè)數(shù)組大小為設(shè)數(shù)組大小為M，

54、則：則：當(dāng)當(dāng)front=0，rear= M 時(shí)，再入隊(duì)發(fā)生時(shí)，再入隊(duì)發(fā)生溢出溢出真溢出真溢出當(dāng)當(dāng)front 0，rear= M 時(shí)，再入隊(duì)發(fā)生時(shí)，再入隊(duì)發(fā)生溢出溢出假溢出假溢出l解決方案解決方案隊(duì)首固定，每次出隊(duì)后將剩余元素向隊(duì)首固定，每次出隊(duì)后將剩余元素向下移動(dòng)下移動(dòng)浪費(fèi)時(shí)間浪費(fèi)時(shí)間循環(huán)隊(duì)列循環(huán)隊(duì)列l(wèi)基本思想：把隊(duì)列設(shè)想成環(huán)形，讓基本思想：把隊(duì)列設(shè)想成環(huán)形，讓 Q.baseM-1 接在接在 Q.base0 之后，之后，若若rear+1=M，則令則令rear=0;rear123450J4,J5,J6入隊(duì)入隊(duì)J4J5J6front0M-11frontrear.第 63 頁(yè)3.4 3.4 隊(duì)列隊(duì)列

55、實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模?！边\(yùn)算運(yùn)算入隊(duì)：入隊(duì)：Q.baserear=e; rear=(rear+1)%M; 出隊(duì)：出隊(duì)：e=Q.basefront; front=(front+1)%M; 隊(duì)滿(mǎn)、隊(duì)空判定條件隊(duì)滿(mǎn)、隊(duì)空判定條件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出隊(duì)出隊(duì)J7,J8,J9入隊(duì)入隊(duì)隊(duì)空：隊(duì)空：front=rear解決方案：解決方案：1.另外另外設(shè)一個(gè)標(biāo)志設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿(mǎn)以區(qū)別隊(duì)空、隊(duì)滿(mǎn)2.少用一個(gè)元素空間：少用一個(gè)元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿(mǎn)：

56、隊(duì)滿(mǎn)：(rear+1)%M=front隊(duì)滿(mǎn)：隊(duì)滿(mǎn)：front=rear第 64 頁(yè)3.4 3.4 隊(duì)列隊(duì)列J4,J5,J6出隊(duì)出隊(duì)J7,J8入隊(duì)入隊(duì)隊(duì)滿(mǎn)：隊(duì)滿(mǎn)：front=(rear+1)%Ml 少用一個(gè)元素空間：少用一個(gè)元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿(mǎn)：隊(duì)滿(mǎn)：(rear+1)%M=front隊(duì)空：隊(duì)空：front=rearJ5J6J4012345rearfront012345rearfrontJ7J5J6012345frontJ4J8rear第 65 頁(yè)1 1）初始化操作）初始化操作 InitQueue_Sq ( SqQueue &Q ) 參數(shù)：參數(shù)：Q Q是存放隊(duì)

57、列的結(jié)構(gòu)變量是存放隊(duì)列的結(jié)構(gòu)變量功能：功能：建一個(gè)空隊(duì)列建一個(gè)空隊(duì)列Q Q算法：算法：Status InitQueue_Sq ( SqQueue &Q ) /構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列Q Q.base = ( ElemType * )malloc (MAXSIZE * * sizeof (ElemType); if ( !Q.base ) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 Q.front = Q.rear = 0; Return OK; /InitQueue_Sq二二、循環(huán)隊(duì)列的基本操作算法、循環(huán)隊(duì)列的基本操作算法3.4 3.4 隊(duì)列隊(duì)列Q.frontQ.

58、frontQ.rearQ.rear5 54 4 0 03 3 1 12 2第 66 頁(yè)2 2）入隊(duì)）入隊(duì)操作操作 EnQueue_Sq ( SqQueue &Q, ElemType e )功能：功能：將元素將元素 e e 插入隊(duì)尾插入隊(duì)尾Q.frontQ.frontQ.rearQ.rear5 54 4 0 03 3 1 12 2J1J1J3J3J2J2e eQ.frontQ.frontQ.rearQ.rear5 54 4 0 03 3 1 12 2J1J1J3J3J2J2元素元素e e入隊(duì)前入隊(duì)前元素元素e e入隊(duì)后入隊(duì)后3.4 3.4 隊(duì)列隊(duì)列第 67 頁(yè)入隊(duì)入隊(duì)操作操作算法：算法：

59、 Status EnQueue_Sq ( SqQueue &Q, ElemType e ) /將元素將元素e插入隊(duì)尾插入隊(duì)尾 if ( (Q.rear+1)%MAXSIZE= =Q.front ) return ERROR ; /隊(duì)滿(mǎn)隊(duì)滿(mǎn) Q.baseQ.rear = e ; /將元素將元素e插入隊(duì)尾插入隊(duì)尾 Q.rear = (Q.rear+1)%MAXSIZE; /修改隊(duì)尾指針修改隊(duì)尾指針 return OK; /EnQueue_Sq3.4 3.4 隊(duì)列隊(duì)列第 68 頁(yè)3 3) )出隊(duì)出隊(duì)操作操作 DeQueue_Sq (SqQueue &Q, QElemType &

60、;e )功能：功能：刪除隊(duì)頭元素，用刪除隊(duì)頭元素，用e e返回其值返回其值Q.frontQ.frontQ.rearQ.rear5 54 4 0 03 3 1 12 2J1J1J3J3J2J2Q.frontQ.frontQ.rearQ.rear5 54 4 0 03 3 1 12 2J1J1J3J3J2J2出隊(duì)操作前出隊(duì)操作前出隊(duì)操作后出隊(duì)操作后e eJ1J13.4 3.4 隊(duì)列隊(duì)列第 69 頁(yè)出隊(duì)出隊(duì)操作操作算法算法 ：Status DeQueue_Sq ( SqQueue &Q, ElemType &e ) /刪除隊(duì)頭元素，用刪除隊(duì)頭元素，用e返回其值，并返回返回其值，并返回OK；否則返否則返回回ERROR if ( (Q.rear= =Q.front ) return ERROR ; /隊(duì)空隊(duì)空 e = Q.baseQ.front ; / 取隊(duì)頭元素取隊(duì)頭元素 e Q.front = (Q.front+1)%MAXSIZE; /修改隊(duì)頭指針修改隊(duì)頭指針 return OK; /EnQueue_Sq3.4 3.4 隊(duì)列隊(duì)列第 70 頁(yè)3.4.3 3.4.3 鏈隊(duì)列鏈隊(duì)列隊(duì)