數(shù)據(jù)結(jié)構(gòu)第五講

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第五講第五講數(shù)據(jù)結(jié)構(gòu) 第三章第三章棧和隊(duì)列棧和隊(duì)列第3章 棧 和 隊(duì) 列 內(nèi)容提要： 1 1，本章主要介紹了棧與隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)，本章主要介紹了棧與隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)以及他們的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)方式，并在此以及他們的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)方式，并在此基礎(chǔ)上介紹了一些基于棧與隊(duì)列的應(yīng)用。基礎(chǔ)上介紹了一些基于棧與隊(duì)列的應(yīng)用。 2 2，關(guān)于遞歸程序的設(shè)計(jì)。，關(guān)于遞歸程序的設(shè)計(jì)。本章要點(diǎn)3.1 棧棧3.1.1 棧的定義及運(yùn)算棧的定義及運(yùn)算3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.

2、2 棧的應(yīng)用棧的應(yīng)用 3.2.1 中綴表達(dá)式中綴表達(dá)式 3.2.2 中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 3.2.3 后綴表達(dá)式及求值后綴表達(dá)式及求值3.3 棧與遞歸棧與遞歸 3.3.1 遞歸與遞歸程序的設(shè)計(jì)遞歸與遞歸程序的設(shè)計(jì) 3.3.2 遞歸程序的執(zhí)行過(guò)程遞歸程序的執(zhí)行過(guò)程 3.3.3 遞歸的應(yīng)用舉例遞歸的應(yīng)用舉例3.4 隊(duì)隊(duì) 列列3.4.1 隊(duì)列的定義和運(yùn)算隊(duì)列的定義和運(yùn)算3.4.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.4.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.4.4 隊(duì)列的應(yīng)用舉例隊(duì)列

3、的應(yīng)用舉例本章小結(jié)本章小結(jié)3.1.1 棧的定義棧的定義棧是限制在表的一端進(jìn)行插入和刪除的線性表。棧是限制在表的一端進(jìn)行插入和刪除的線性表。棧的相關(guān)術(shù)語(yǔ)：棧頂、棧底、空棧、進(jìn)棧（壓棧）、出棧等。棧的相關(guān)術(shù)語(yǔ)：棧頂、棧底、空棧、進(jìn)棧（壓棧）、出棧等。 棧頂（棧頂（top）：允許插入和刪除的一端）：允許插入和刪除的一端 棧底（棧底（bottom）：不允許插入和刪除的一端）：不允許插入和刪除的一端進(jìn)棧的順序是進(jìn)棧的順序是e1、e2。出棧的順序?yàn)槌鰲５捻樞驗(yàn)閑2、e1。所以棧又稱(chēng)為后進(jìn)先出線性表所以棧又稱(chēng)為后進(jìn)先出線性表(Last In First Out)，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng) LIFO表表或稱(chēng)先進(jìn)后出線性表。

4、或稱(chēng)先進(jìn)后出線性表。Top1Top0Top1Top0Top1課堂練習(xí)若進(jìn)棧序列為若進(jìn)棧序列為3，5，7，9，進(jìn)棧過(guò)程中可以出棧，進(jìn)棧過(guò)程中可以出棧，則不可能的一個(gè)出棧次序是（則不可能的一個(gè)出棧次序是（ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,33.1.1 棧的運(yùn)算棧的運(yùn)算（1）初始化棧）初始化棧 InitStack(S) 初始條件：初始條件：棧棧S不存在。不存在。 操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S。（2）壓棧（入棧）壓棧（入棧） Push(S, e) 初始條件初始條件：棧：棧S已存在。已存在。 操作結(jié)果：操作結(jié)果：插入

5、元素插入元素e為新的棧頂元素。為新的棧頂元素。（3）出棧）出棧Pop(S, e) 初始條件：初始條件：棧棧S已存在且非空。已存在且非空。 操作結(jié)果：操作結(jié)果：刪除刪除S的棧頂元素，并用的棧頂元素，并用e返回其值。返回其值。（4） GetTop(S, &e) 初始條件：初始條件：棧棧S已存在且非空。已存在且非空。 操作結(jié)果：操作結(jié)果：用用e返回返回S的棧頂元素。的棧頂元素。 （5）StackEmpty(S) 初始條件：初始條件：棧棧S已存在。已存在。 操作結(jié)果：操作結(jié)果：若棧若棧S為空棧，則返回為空棧，則返回TRUE(1)，否則，否則FALSE(0)。課堂練習(xí) 用一維數(shù)組設(shè)計(jì)棧，初態(tài)是用

6、一維數(shù)組設(shè)計(jì)棧，初態(tài)是棧空，?？眨瑃op=-1?，F(xiàn)有輸入序列是現(xiàn)有輸入序列是 a、b、c、d，經(jīng)過(guò)，經(jīng)過(guò) push、push、pop、push、pop、push操作后操作后。輸出序列是（輸出序列是（ ）棧頂指針是（棧頂指針是（ ）b，c1本章要點(diǎn)3.1 棧棧3.1.1 棧的定義及運(yùn)算棧的定義及運(yùn)算3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.2 棧的應(yīng)用棧的應(yīng)用 3.2.1 中綴表達(dá)式中綴表達(dá)式 3.2.2 中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 3.2.3

7、后綴表達(dá)式及求值后綴表達(dá)式及求值3.3 棧與遞歸棧與遞歸 3.3.1 遞歸與遞歸程序的設(shè)計(jì)遞歸與遞歸程序的設(shè)計(jì) 3.3.2 遞歸程序的執(zhí)行過(guò)程遞歸程序的執(zhí)行過(guò)程 3.3.3 遞歸的應(yīng)用舉例遞歸的應(yīng)用舉例3.4 隊(duì)隊(duì) 列列3.4.1 隊(duì)列的定義和運(yùn)算隊(duì)列的定義和運(yùn)算3.4.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.4.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)3.4.4 隊(duì)列的應(yīng)用舉例隊(duì)列的應(yīng)用舉例本章小結(jié)本章小結(jié)3.1.2 順序棧的結(jié)構(gòu)及運(yùn)算順序棧的結(jié)構(gòu)及運(yùn)算(1)棧的順序存儲(chǔ)簡(jiǎn)稱(chēng)順序棧。 通常由一個(gè)一維數(shù)組dataMAXSIZE

8、和一個(gè)記錄棧頂元素位置的變量(top)組成 說(shuō)明：說(shuō)明：toptop指向棧頂元素當(dāng)前位置。指向棧頂元素當(dāng)前位置。012MAXSIZE-1012MAXSIZE-1本章要點(diǎn)4.1 棧4.1.1 棧的抽象數(shù)據(jù)類(lèi)型4.1.2 順序棧順序棧4.1.3 鏈棧4.1.4 棧的應(yīng)用4.2 隊(duì)隊(duì) 列列4.2.1 隊(duì)列的抽象數(shù)據(jù)類(lèi)型4.2.2 順序隊(duì)列4.2.3 鏈隊(duì)列4.2.4 隊(duì)列的應(yīng)用4.3 遞遞 歸歸4.3.1 遞歸算法書(shū)寫(xiě)要點(diǎn)及方法4.3.2 遞歸過(guò)程的調(diào)用和返回4.3.3 遞歸的應(yīng)用 4.3.4 遞歸函數(shù)的非遞歸化本章小結(jié)本章小結(jié)棧的順序存儲(chǔ)示意圖：說(shuō)明：也可以將說(shuō)明：也可以將basebase指向下標(biāo)

9、為指向下標(biāo)為-1-1的位置，的位置，toptop指向棧頂元素當(dāng)前位置。指向棧頂元素當(dāng)前位置。4.1.2 順序棧順序棧(1)012MAXSIZE-1#define MAXSIZE 100typedef struct ElemType dataMAXSIZE; int top;Stack;順序棧的描述順序棧的描述1) 棧的初始化InitStack(Stack *S) void InitStack(Stack *S) s-top=-1; 順序棧的運(yùn)算順序棧的運(yùn)算(1)012MAXSIZE-1Top12) 壓棧(入棧)操作int PushStack(Stack *S,ElemType e) /進(jìn)棧操作

10、 if(S-top=MAXSIZE-1) prinft(“n Stack is full”); return 0; s-top+; s-datas-top=e; return 1;順序棧的運(yùn)算順序棧的運(yùn)算(2)x2X1012MAXSIZE-1Top1eTop23) 判斷棧是否為空判斷棧是否為空 int EmptyStack() /判斷棧是否為空判斷棧是否為空 if (S-top=-1) return 1; else return 0; 順序棧的運(yùn)算順序棧的運(yùn)算(3)012MAXSIZE-1Top12)出棧操作int PopStack(Stack *S,ElemType *e) / if(Emp

11、ty(S) prinft(“n Stack is empty”); return 0; *e=S-datas-top; s-top-; return 1;順序棧的運(yùn)算順序棧的運(yùn)算(4)x2X1012MAXSIZE-1Top15) 取棧頂元素操作int GetTop (Stack *S,ElemType *x)/取棧頂元素操作 if(Empty(S) printf(“Stack is Empty”); return 0; else *x=S-dataS-top; return 1; 順序棧的運(yùn)算順序棧的運(yùn)算(5)x2X1012MAXSIZE-1Top1棧的應(yīng)用舉例棧的應(yīng)用舉例 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換:編寫(xiě)程序?qū)崿F(xiàn)對(duì)于一個(gè)任意的十編寫(xiě)程序?qū)崿F(xiàn)對(duì)于一個(gè)任意的十進(jìn)制數(shù)打印輸出與之等值的八進(jìn)制數(shù)。進(jìn)制數(shù)打印輸出與之等值的八進(jìn)制數(shù)。 十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于“除d求余”原理。 例如：例如：（1348)10 = ( ？ )8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 22504void co