數(shù)據(jù)結(jié)構(gòu)線性表ppt課件-展示頁
2025-05-08 02:43本頁面
【正文】 ACK_INIT_SIZE。 //為順序棧動(dòng)態(tài)分配存儲(chǔ)空間 if ( ! S. base) exit(OVERFLOW)。S ) 參數(shù)： S是存放棧的結(jié)構(gòu)變量 功能：建一個(gè)空棧 S 100 99 n n1 n2 1 0 第 12 頁 棧 初始化操作算法 Status InitStack ( SqStack amp。 若 top == Stacksize， 棧滿，此時(shí)入棧，則需擴(kuò)充棧空間，每次擴(kuò)充 STACK_INCREMENT； 若無可利用的存儲(chǔ)空間，則 上溢 (overflow)。 //當(dāng)前分配的?？臻g大小 }SqStack。 //?？臻g基址 ElemType *top。 7）判空操作 StackEmpty(S) 功能：若棧 S為空，則返回 True， 否則，棧不空返回 False。S, amp。S, e) 功能：元素 e進(jìn)棧。e) 功能：取棧頂元素，并用 e 返回。S) 功能：將棧 S置為空棧。S) 功能：銷毀一個(gè)已存在的棧。S) 功能：構(gòu)造一個(gè)空棧 S。進(jìn)棧出棧操作只能在棧頂進(jìn)行。第 2 頁 棧 棧的概念 一、什么是棧 棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表 （ a1, a2, ... , ai 1, ai , ai+1, …, a n ） 插入 刪除 能進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。 稱插入操作為進(jìn)棧，刪除操作為出棧。 第 3 頁 棧 出棧 進(jìn)棧 棧的特點(diǎn) 后進(jìn)先出 第一個(gè)進(jìn)棧的元素在棧底 最后一個(gè)進(jìn)棧的元素在棧頂 第一個(gè)出棧的元素為棧頂元素 最后一個(gè)出棧的元素為棧底元素 棧的示意圖 棧頂 棧底 an a2 a1 第 4 頁 棧 二、棧的基本操作 1）初始化操作 InitStack(amp。 2） 銷毀棧操作 DestroyStack(amp。 3）置空棧操作 ClearStack(amp。 4）取棧頂元素操作 GetTop(S, amp。 第 5 頁 棧 二、棧的基本操作 5）進(jìn)棧操作 Push(amp。 6）退棧操作 Pop(amp。e) 功能：棧頂元素退棧，并用 e返回。 第 6 頁 棧 棧的順序存儲(chǔ)和實(shí)現(xiàn) 一、棧的順序存儲(chǔ)結(jié)構(gòu) define STACK_INIT_SIZE 100 // 棧存儲(chǔ)空間的初始分配量 define STACKINCREMENT 10 // 空間的分配增量 typedef struct { ElemType *base。 //棧頂指針 int stacksize。 第 7 頁 棧 棧的順序存儲(chǔ)和實(shí)現(xiàn) 順序棧的圖示 100 99 n n1 n2 1 0 an an1 a2 a1 約定棧頂指針指向 棧頂元素的下一個(gè)位置 當(dāng)棧用順序結(jié)構(gòu)存 儲(chǔ)時(shí)，棧的基本操 作如建空棧、進(jìn)棧、 出棧等如何實(shí)現(xiàn)？ 第 8 頁 棧 棧的順序存儲(chǔ)和實(shí)現(xiàn) top base base top A B C D E 空棧 base top A A進(jìn)棧 B C D E進(jìn)棧 base top A B E D C出棧 稱為：棧滿 空棧 top = base 棧滿 topbase = stacksize (無可分配空間 ) 第 9 頁 1 2 3 4 0 A B C D E 棧 ? 不可擴(kuò)充棧的操作 top=0 1 2 3 4 0 ?？? 棧頂指針 top， 指向?qū)嶋H棧頂 后的空位置，初值為 base top 進(jìn)棧 A 棧滿 B C D E 設(shè)數(shù)組大小為 M top=M， 棧滿 ， 此時(shí)入棧，則上溢 (overflow) top top top top top top top top top top 棧空 top==base， ?？?，此時(shí)出棧，則下溢(underflow) top 1 2 3 4 0 出棧 第 10 頁 1 2 3 4 0 A B C D E 棧 ? 可擴(kuò)充棧的操作 棧頂指針 top， 指向?qū)嶋H棧頂 后的下一個(gè)位置，初值為 top=base top 進(jìn)棧 A 出棧 棧當(dāng)前空間 不足，需擴(kuò)充 B C D E 設(shè)棧的初始分配量為 Stacksize = STACK_INIT_SIZE。 top top top top top top top top top top ?？? 若 top==base, ?？眨藭r(shí)出棧，則下溢(underflow) base ?？? top base base top 1 2 3 4 0 1 2 3 4 0 第 11 頁 棧 二、順序棧基本操作的算法 1）初始化操作 InitStack ( SqStack amp。S ) { //構(gòu)造一個(gè)空棧 S = ( ElemType *) malloc ( STACK_INIT_SIZE * sizeof(ElemType) )。 //分配失敗 = 。 return OK。S) 功能：銷毀一個(gè)已存在的棧 100 null 0 null 棧 第 14 頁 Status DetroyStack ( SqStack amp。 //若棧未建立（尚未分配?？臻g） free ( )。 = 0。 } //DetroyStack 銷毀操作算法 棧 第 15 頁 3） 置空棧操作 ClearStack (SqStack amp。S ) { if ( ! ) return ERROR。 return OK。e ) 功能： 取棧頂元素，并用 e返回 棧 第 18 頁 Status GetTop ( SqStack S, ElemType amp。 //棧
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1