工學(xué)數(shù)據(jù)結(jié)構(gòu)ppt課件-展示頁
2024-11-12 20:39本頁面
【正文】 STACK_INI_SIZE 。 if (!) exit (OVERFLOW)。e) // 取棧頂元素 棧 棧的表示和實(shí)現(xiàn) ? 棧初始化 算法描述： Status InitStack (SqStack amp。S， amp。S) // 構(gòu)造棧 Push(amp。不限制出棧 的時間，則下面哪一種出棧順序不可能。 s為一個順序棧的變量。 //棧的容量 (已分配的存儲空間 ) } SqStack。 //棧底指針即棧的基址 SElemType *top。 棧 棧的表示和實(shí)現(xiàn) 順序棧 ： (棧的順序存儲結(jié)構(gòu) )利用一組 地址連續(xù) 的 存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。 表尾 (允許插入和刪除 )—棧頂，表頭 —棧底 特點(diǎn)： 后進(jìn)先出（ LIFO） an a1 a2 ……... 棧底 棧頂 ... 出棧 進(jìn)棧 棧 s=(a1,a2,……,an) 棧的定義 棧 ? 棧的抽象數(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 } 約定 an 端為棧頂， a1 端為棧底。 線性表 棧 隊列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 棧和隊列是限定插入和刪除只能在表的 “端點(diǎn)” 進(jìn)行的 線性表 ——限定性數(shù)據(jù)結(jié)構(gòu)。 3. 熟練掌握循環(huán)隊列和鏈隊列的基本操作實(shí)現(xiàn)算法。? 實(shí)驗安排 時間： 815周 單周：周四 6節(jié) 雙周：周二 6節(jié) 地點(diǎn)： 2班 軟 419 4班 軟 420 第 3章 棧和隊列 棧和隊列是兩種常用的線性結(jié)構(gòu) 【學(xué)習(xí)目標(biāo)】 1. 掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 2. 熟練掌握棧類型的兩種實(shí)現(xiàn)方法。 【重點(diǎn)和難點(diǎn)】 棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。 ? 棧 ? 隊列 棧 棧 定義： 限定僅在 表尾 進(jìn)行插入或刪除操作的線性表 。 基本操作 ： …… } ADT Stack 建棧、入棧、出棧、 讀棧頂元素、判斷棧滿或棧空等。 // 棧的順序存儲表示 typedef struct { SElemType *base。 //指向棧頂元素的上一個位置 int stacksize。 棧頂元素的說明 棧 棧的表示和實(shí)現(xiàn) 如： SqStack s。 s的存儲空間為： s. stacksize [0] [stacksize1] 該空間的申請由初始化 操作實(shí)現(xiàn) … 棧 ?？粘鰲?，則 下溢 (underflow) 棧滿入棧，則 上溢 (overflow) 棧的表示和實(shí)現(xiàn) base 1 2 3 4 5 0 棧空 top 棧頂指針 top初值指向 棧底： top=base 1 2 3 4 5 0 進(jìn)棧 base A top B top C top D top E top F top 出棧 1 2 3 4 5 0 A B C D E F base top top top top top top top 棧滿 :top base = stacksize ?？? top *++ = e e = * 棧 思考 ：如果進(jìn)棧順序為 1， 2， 3， 4。 (1) 1, 2, 3, 4 (2) 2, 1, 4, 3 (3) 3, 1, 2, 4 (4) 4, 3, 2, 1 棧的表示和實(shí)現(xiàn) 棧 棧的表示和實(shí)現(xiàn) ? 棧的基本操作在 順序棧 中的實(shí)現(xiàn) InitStack(amp。S， e) // 入棧 Pop(amp。e) // 出棧 GetTop(S， amp。S){ // 構(gòu)造一個空順序棧 S = (SElemType *)mallo
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1