[ppt模板]隊(duì)列棧的操作-展示頁
2025-01-28 09:12本頁面
【正文】 隊(duì)列的結(jié)構(gòu)定義define MAXQSIZE 100 // 最大隊(duì)列長度typedef struct { QElemType *base。v 循環(huán)隊(duì)列216。v當(dāng) front?0,rear=M1時(shí)，再有元素入隊(duì)發(fā)生溢出 —— 假溢出。出隊(duì)列： x=sq[++front]。}Date 20Data Structure隊(duì)列的順序存儲結(jié)構(gòu)用 一組地址連續(xù)的存儲單元 依次存放從隊(duì)頭到隊(duì)尾的元素。e)初始條件： Q 為非空隊(duì)列。DeQueue(amp。Q,e)初始條件：隊(duì)列 Q 已存在。操作結(jié)果：用 e 返回 Q的隊(duì)頭元素。Date 19Data StructureGetHead(Q,amp。QueueLength(Q)初始條件：隊(duì)列 Q 已存在。QueueEmpty(Q)初始條件：隊(duì)列 Q 已存在。Q)初始條件：隊(duì)列 Q 已存在。操作結(jié)果：隊(duì)列 Q 被銷毀，不再存在。DestroyQueue(amp。 a1 a2 a3…………………….an 入隊(duì)出隊(duì)front rearQ=(a1,a2,……,an)Date 17Data Structure隊(duì)列的抽象數(shù)據(jù)類型定義ADT Queue {數(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} 基本操作 ：InitQueue(amp。v 隊(duì)頭 ：允許刪除的一端。} //PopDate 14Data Structure鏈棧 (棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) ) Date 15Data Structure入棧算法 ^…...棧底toptopxp出棧算法top ^…...棧底topqDate 16Data Structure 隊(duì)列q隊(duì)列v 只允許在 一端進(jìn)行插入 而在 另一端進(jìn)行刪除 的線性表。 //空棧e = *()。S, ElemType amp。 // 插入新的元素return OK。 +=STACKINCREMENT。 if(!) exit(OVERFLOW)。} //GetTopDate 12Data Structure Status Push (SqStack amp。 // 空棧e = *()。} //InitStack Date 11Data Structure Status GetTop (SqStack S, SElemType amp。 = STACK_INIT_SIZE。if(!) exit(OVERFLOW)。Date 10Data Structure基本操作的算法描述Status InitStack (SqStack amp。//若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 TRUE； 否則返回 FALSE。S, SElemType amp。//若棧的存儲空間不滿，則插入元素 e ， 并返回 TRUE； 否則返回 FALSE。bool Push (SqStack amp。e)。//返回 S的元素個(gè)數(shù)，即棧的長度。//若棧 S 為空棧 。//將 S 置為空棧。void ClearStack (SqStack amp。S)。//構(gòu)造一個(gè)空棧 S。 Date 8Data Structurebase123450?？諚ｍ斨羔?top,指向?qū)嶋H棧頂后的空位置， top==basetop 123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組大小為 Mtop==base,棧空，此時(shí)出棧，則 下溢 （ underflow)Topbase=6,棧滿，此時(shí)入棧，則 上溢 （ overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空topbasebaseDate 9Data Structure基本操作接口 (函數(shù)聲明 )void InitStack (SqStack amp。 // 棧頂指針int stacksize。 // 存儲空間分配增量 typedef struct { SElemType *base。q結(jié)構(gòu)定義：define STACK_INIT_SIZE 100。操作結(jié)果：從棧底到棧頂依次對 S的每個(gè)元素調(diào)用函數(shù) visit( )， 一旦 visit( )失敗，則操作失敗。操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。S, amp。操作結(jié)果：插入元素 e 為新的棧頂元素。Push(amp。e)初始條件：棧 S 已存在且非空。操作結(jié)果：返回棧 S 中元素個(gè)數(shù)，即棧的長度。操作結(jié)果：若棧 S 為空棧，則返回 TRUE， 否則返回 FALSE。S)初始條件：棧 S 已存在。操作結(jié)果：棧 S 被銷毀。 DestroyStack(amp。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。v 棧底 (bottom)： 不允許插入和刪除的另一端。Date 2Data Structure 棧q棧v 限定 只能在表的一端進(jìn)行插入和刪除操作 的線性表。q與線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。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)用問題中正確使用。v 熟練掌握 循環(huán)隊(duì)列 和 鏈隊(duì)列 的基本 操作實(shí)現(xiàn)算法 。Data Structureq學(xué)習(xí)目標(biāo)v 掌握 棧和隊(duì)列 這兩種抽象數(shù)據(jù)類型的 特點(diǎn) ，并能在相應(yīng)的應(yīng)用問題中正確選用它們。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1