數(shù)據結構第五講

1、數(shù)據結構數(shù)據結構第五講第五講數(shù)據結構 第三章第三章棧和隊列棧和隊列第3章 棧 和 隊 列 內容提要： 1 1，本章主要介紹了棧與隊列兩種數(shù)據結構，本章主要介紹了棧與隊列兩種數(shù)據結構以及他們的順序存儲與鏈式存儲方式，并在此以及他們的順序存儲與鏈式存儲方式，并在此基礎上介紹了一些基于棧與隊列的應用?；A上介紹了一些基于棧與隊列的應用。 2 2，關于遞歸程序的設計。，關于遞歸程序的設計。本章要點3.1 棧棧3.1.1 棧的定義及運算棧的定義及運算3.1.2 棧的順序存儲結構及基本運算的實現(xiàn)棧的順序存儲結構及基本運算的實現(xiàn)3.1.3 棧的鏈式存儲結構及基本運算的實現(xiàn)棧的鏈式存儲結構及基本運算的實現(xiàn)3.

2、2 棧的應用棧的應用 3.2.1 中綴表達式中綴表達式 3.2.2 中綴表達式轉換為等價的后綴表達式中綴表達式轉換為等價的后綴表達式 3.2.3 后綴表達式及求值后綴表達式及求值3.3 棧與遞歸棧與遞歸 3.3.1 遞歸與遞歸程序的設計遞歸與遞歸程序的設計 3.3.2 遞歸程序的執(zhí)行過程遞歸程序的執(zhí)行過程 3.3.3 遞歸的應用舉例遞歸的應用舉例3.4 隊隊 列列3.4.1 隊列的定義和運算隊列的定義和運算3.4.2 隊列的順序存儲結構及基本運算的實現(xiàn)隊列的順序存儲結構及基本運算的實現(xiàn)3.4.3 隊列的鏈式存儲結構及基本運算的實現(xiàn)隊列的鏈式存儲結構及基本運算的實現(xiàn)3.4.4 隊列的應用舉例隊列

3、的應用舉例本章小結本章小結3.1.1 棧的定義棧的定義棧是限制在表的一端進行插入和刪除的線性表。棧是限制在表的一端進行插入和刪除的線性表。棧的相關術語：棧頂、棧底、空棧、進棧（壓棧）、出棧等。棧的相關術語：棧頂、棧底、空棧、進棧（壓棧）、出棧等。 棧頂（棧頂（top）：允許插入和刪除的一端）：允許插入和刪除的一端 棧底（棧底（bottom）：不允許插入和刪除的一端）：不允許插入和刪除的一端進棧的順序是進棧的順序是e1、e2。出棧的順序為出棧的順序為e2、e1。所以棧又稱為后進先出線性表所以棧又稱為后進先出線性表(Last In First Out)，簡稱，簡稱 LIFO表表或稱先進后出線性表。

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

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

6、一維數(shù)組設計棧，初態(tài)是棧空，棧空，top=-1?，F(xiàn)有輸入序列是現(xiàn)有輸入序列是 a、b、c、d，經過，經過 push、push、pop、push、pop、push操作后操作后。輸出序列是（輸出序列是（ ）棧頂指針是（棧頂指針是（ ）b，c1本章要點3.1 棧棧3.1.1 棧的定義及運算棧的定義及運算3.1.2 棧的順序存儲結構及基本運算的實現(xiàn)棧的順序存儲結構及基本運算的實現(xiàn)3.1.3 棧的鏈式存儲結構及基本運算的實現(xiàn)棧的鏈式存儲結構及基本運算的實現(xiàn)3.2 棧的應用棧的應用 3.2.1 中綴表達式中綴表達式 3.2.2 中綴表達式轉換為等價的后綴表達式中綴表達式轉換為等價的后綴表達式 3.2.3

7、后綴表達式及求值后綴表達式及求值3.3 棧與遞歸棧與遞歸 3.3.1 遞歸與遞歸程序的設計遞歸與遞歸程序的設計 3.3.2 遞歸程序的執(zhí)行過程遞歸程序的執(zhí)行過程 3.3.3 遞歸的應用舉例遞歸的應用舉例3.4 隊隊 列列3.4.1 隊列的定義和運算隊列的定義和運算3.4.2 隊列的順序存儲結構及基本運算的實現(xiàn)隊列的順序存儲結構及基本運算的實現(xiàn)3.4.3 隊列的鏈式存儲結構及基本運算的實現(xiàn)隊列的鏈式存儲結構及基本運算的實現(xiàn)3.4.4 隊列的應用舉例隊列的應用舉例本章小結本章小結3.1.2 順序棧的結構及運算順序棧的結構及運算(1)棧的順序存儲簡稱順序棧。 通常由一個一維數(shù)組dataMAXSIZE

8、和一個記錄棧頂元素位置的變量(top)組成 說明：說明：toptop指向棧頂元素當前位置。指向棧頂元素當前位置。012MAXSIZE-1012MAXSIZE-1本章要點4.1 棧4.1.1 棧的抽象數(shù)據類型4.1.2 順序棧順序棧4.1.3 鏈棧4.1.4 棧的應用4.2 隊隊 列列4.2.1 隊列的抽象數(shù)據類型4.2.2 順序隊列4.2.3 鏈隊列4.2.4 隊列的應用4.3 遞遞 歸歸4.3.1 遞歸算法書寫要點及方法4.3.2 遞歸過程的調用和返回4.3.3 遞歸的應用 4.3.4 遞歸函數(shù)的非遞歸化本章小結本章小結棧的順序存儲示意圖：說明：也可以將說明：也可以將basebase指向下標

9、為指向下標為-1-1的位置，的位置，toptop指向棧頂元素當前位置。指向棧頂元素當前位置。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; 順序棧的運算順序棧的運算(1)012MAXSIZE-1Top12) 壓棧(入棧)操作int PushStack(Stack *S,ElemType e) /進棧操作

10、 if(S-top=MAXSIZE-1) prinft(“n Stack is full”); return 0; s-top+; s-datas-top=e; return 1;順序棧的運算順序棧的運算(2)x2X1012MAXSIZE-1Top1eTop23) 判斷棧是否為空判斷棧是否為空 int EmptyStack() /判斷棧是否為空判斷棧是否為空 if (S-top=-1) return 1; else return 0; 順序棧的運算順序棧的運算(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;順序棧的運算順序棧的運算(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; 順序棧的運算順序棧的運算(5)x2X1012MAXSIZE-1Top1棧的應用舉例棧的應用舉例 例一、例一、 數(shù)制轉換數(shù)制轉換:編寫程序實現(xiàn)對于一個任意的十編寫程序實現(xiàn)對于一個任意的十進制數(shù)打印輸出與之等值的八進制數(shù)。進制數(shù)打印輸出與之等值的八進制數(shù)。 十進制數(shù)N和其他d進制數(shù)的轉換是計算機實現(xià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