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