[ppt模板]隊(duì)列棧的操作(已修改)
2025-01-31 09:12 本頁面
【正文】 Data Structureq學(xué)習(xí)目標(biāo)v 掌握 棧和隊(duì)列 這兩種抽象數(shù)據(jù)類型的 特點(diǎn) ，并能在相應(yīng)的應(yīng)用問題中正確選用它們。v 熟練掌握 棧 類型 的兩種實(shí)現(xiàn)方法 。v 熟練掌握 循環(huán)隊(duì)列 和 鏈隊(duì)列 的基本 操作實(shí)現(xiàn)算法 。v 理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。q重點(diǎn)和難點(diǎn)v 棧和隊(duì)列 是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，本章的學(xué)習(xí)重點(diǎn)是掌握這兩種結(jié)構(gòu) 的特點(diǎn) ， 以便能在應(yīng)用問題中正確使用。q知識點(diǎn)v 順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列第三章第三章 棧和隊(duì)列棧和隊(duì)列Date 1Data Structureq棧和隊(duì)列是在程序設(shè)計(jì)中被 廣泛使用 的兩種線性數(shù)據(jù)結(jié)構(gòu)。q與線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。v 線性表允許在表內(nèi) 任一位置 進(jìn)行插入和刪除；v 棧只允許在表尾 一端 進(jìn)行插入和刪除；v 隊(duì)列只允許在表尾 一端 進(jìn)行插入，在表頭 一端 進(jìn)行刪除。Date 2Data Structure 棧q棧v 限定 只能在表的一端進(jìn)行插入和刪除操作 的線性表。v 棧頂 (top)： 允許插入和刪除的一端。v 棧底 (bottom)： 不允許插入和刪除的另一端。v 空棧 ：不含元素的空表。q特點(diǎn)v 先進(jìn)后出（ FILO）v 后進(jìn)先出（ LIFO）ana1a2……...棧底棧頂... 出棧進(jìn)棧Date 3Data Structure棧的抽象數(shù)據(jù)類型定義ADT Stack {數(shù)據(jù)對象 ： D＝ {ai| ai ∈ ElemSet, i=1,2,...,n, n≥0 }數(shù)據(jù)關(guān)系 ： R1＝ { ai1,ai | ai1,ai∈ D, i=2,...,n }基本操作 ：InitStack(amp。S) 操作結(jié)果：構(gòu)造一個空棧 S。 DestroyStack(amp。S)初始條件：棧 S 已存在。操作結(jié)果：棧 S 被銷毀。 Date 4Data StructureClearStack(amp。S)初始條件：棧 S 已存在。操作結(jié)果：將 S 清為空棧StackEmpty(S)初始條件：棧 S 已存在。操作結(jié)果：若棧 S 為空棧，則返回 TRUE， 否則返回 FALSE。StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回棧 S 中元素個數(shù)，即棧的長度。Date 5Data StructureGetTop(S, amp。e)初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S的棧頂元素。Push(amp。S, e)初始條件：棧 S 已存在。操作結(jié)果：插入元素 e 為新的棧頂元素。Pop(amp。S, amp。e)初始條件：棧 S 已存在且非空。操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。Date 6Data StructureStackTraverse(S, visit( ))初始條件：棧 S 已存在且非空， visit( )為元素的訪問 函數(shù)。操作結(jié)果：從棧底到棧頂依次對 S的每個元素調(diào)用函數(shù) visit( )， 一旦 visit( )失敗，則操作失敗。} ADT StackDate 7Data Structure棧的順序存儲（順序棧）q利用 一組地址連續(xù)的存儲單元 依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。q結(jié)構(gòu)定義：define STACK_INIT_SIZE 100。 // 存儲空間初始分配量 define STACKINCREMENT 10。 // 存儲空間分配增量 typedef struct { SElemType *base。 // 存儲空間基址 SElemType *top。 // 棧頂指針int stacksize。 // 當(dāng)前已分配的存儲空間，以元素位單位} SqStack。 Date 8Data Structurebase123450?？諚ｍ斨羔?top,指向?qū)嶋H棧頂后的空位置， top==basetop 123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組大小為 Mtop==base,?？?，此時出棧，則 下溢 （ underflow)Topbase=6,棧滿，此時入棧，則 上溢 （ overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誸opbasebaseDate 9Data Structure基本操作接口 (函數(shù)聲明 )void InitStack (SqStack amp。S)。//構(gòu)造一個空棧 S。void DestroyStack (SqStack amp。S)。//銷毀棧 S， S 不再存在。void ClearStack (SqStack amp。S)。//將 S 置為空棧。bool StackEmpty (SqStack S)。//若棧 S 為空棧 。int StackLength (SqStack S)。//返回 S的元素個數(shù)，即棧的長度。bool GetTop (SqStack S, SElemType amp。e)。//若棧不空，則用 e 返回 S的棧頂元素，并返回 TRUE； 否則返回 FALSE。bool Push (SqStack amp。S, SElemType e)。//若棧的存儲空間不滿，則插入元素 e ， 并返回 TRUE； 否則返回 FALSE。bool Pop (SqStack amp。S, SElemType amp。e)。//若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 TRUE； 否則返回 FALSE。void StackTraverse(SqStack S, Status (*visit())//依次對 S的每個元素調(diào)用函數(shù) visit( )， 一旦 visit( )失敗，操作失敗。Date 10Data Structure基本操作的算法描述Status InitStack (SqStack amp。S){// 構(gòu)造一個空棧 S=(SElemType *)malloc (STACK_INIT_S
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1