次課-棧的性質(zhì)、棧的基本操作.ppt

1、,首頁,遇到困難時,請發(fā)揮集體的智慧!,有所收獲,教案,主要內(nèi)容,棧的概念 棧的基本操作 棧的存儲 順序棧的實現(xiàn),引例,在日常生活中，有一些這樣的例子。 例1：食堂師傅把洗好的飯盒按順序放好，最后洗的飯盒總是放在一疊飯盒的最上面。同學們到食堂就餐時，拿飯盒總是按照由上到下的順序拿，即總是拿一疊飯盒中最頂上的一個。 例2：有一個盒子，我們在里頭放了一疊書。當我們要用書的時候，只能從第一本開始拿；當我們要把書本放進去時，總是放在最上面。 請問：上面的例子中有什么共同的特點？,后放進去的，先拿出來。,棧的概念和特點,什么是棧？ 棧是一種特殊的線性表，它只在線性表的一端進行插入和刪除操作。 棧中允許插

2、入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。 當表中沒有元素時稱為空棧。 棧的特點 “先進后出”（First In Last Out） 或“后進先出”（Last In First Out）,返回,棧的基本操作,棧主要有建棧、入棧、出棧和銷毀棧四個基本操作。 建棧：新建一個空棧，向操作系統(tǒng)申請一組存儲單元，用于存儲棧中的元素。 入棧：將元素壓入棧內(nèi)，存儲在棧頂。 出棧：從棧中取出棧頂元素，也稱為彈出棧。 銷毀棧：把存儲單元歸還給操作系統(tǒng)。 為了實時了解棧的情況，還需要有輸出棧這樣的操作。 輸出棧：顯示棧的內(nèi)容。,返回,棧的存儲,回顧：前面介紹的線性表是采用什么方式存儲數(shù)據(jù)的？ 棧與前面介紹過

3、的線性表一樣，也可以采用順序存儲結(jié)構(gòu)（數(shù)組）或者鏈式存儲結(jié)構(gòu)（鏈表）。,順序棧,鏈棧（單鏈表）,棧的表示 可以用一個棧頂指針（top）來指示棧頂元素存放的位置，用一個棧底指針（bottom）來指示棧底元素的存放位置。由于棧底位置相對不變，通常不用bottom。,順序棧的示意圖,鏈棧的示意圖,返回,順序棧的實現(xiàn),【例】先建棧，然后輸入一個整型元素后入棧，顯示棧的內(nèi)容。接下來進行出棧操作，再顯示棧的內(nèi)容。最后銷毀棧。 數(shù)據(jù)結(jié)構(gòu)描述 順序棧的類型描述如下： #define MAXSIZE 200 struct seqstack Elemtype dataMAXSIZE; int top; ; 定義一

4、個指向順序棧的指針： struct seqstack *s; 源程序,運行程序(10_1),看源程序(10_1),建棧,分析 首先申請棧空間，然后初始化棧頂指針。 流程圖 源程序,運行程序(10_1),看源程序(10_1),入棧,流程圖 源程序 int push_seqstack (struct seqstack *s, Elemtype x) s-datas-top=x; s-top+; return 1; ,思考：如果不斷入棧，會出現(xiàn)什么情況？(10_2),上溢出,檢查棧是否滿的子函數(shù),源程序 /*/ /* 函 數(shù) 名：full_seqstack */ /* 函數(shù)功能：檢查棧是否滿 */

5、/* 入口參數(shù)：s棧 */ /* 返 回 值：棧滿返回1，否則返回0 */ /*/ int full_seqstack(struct seqstack *s) if (s-top = MAXSIZE) return 1; else return 0; ,改進后的入棧,分析 為了防止上溢發(fā)生，在入棧前先檢查棧是否滿。若未滿，則進行入棧操作，否則進行溢棧處理或溢棧報告。 流程圖 源程序,運行程序(10_1),看源程序(10_1),出棧,流程圖 源程序 int pop_seqstack (struct seqstack *s, Elemtype *x) s-top-; *x=s-datas-top;

6、 return 1; ,思考：如果不斷出棧，會出現(xiàn)什么情況？(10_2),下溢出,檢查棧是否為空的子函數(shù),源程序 /*/ /* 函 數(shù) 名：empty_seqstack */ /* 函數(shù)功能：檢查棧是否為空 */ /* 入口參數(shù)：s棧 */ /* 返 回 值：棧空返回1，否則返回0 */ /*/ int empty_seqstack(struct seqstack *s) if (s-top = 0) return 1; else return 0; ,改進后的出棧,分析 為了防止下溢發(fā)生，在出棧前先檢查棧是否為空。若不空，則進行出棧操作，否則進行溢棧處理或溢棧報告。 流程圖 源程序,運行程序

7、(10_1),看源程序(10_1),顯示棧,源程序 void display_seqstack(struct seqstack *s) int i; if (empty_seqstack(s) printf(目前棧為空!n); return; printf(目前棧的內(nèi)容為：); for (i=0; itop-1;i+) printf(%d ,s-datai); printf(n); ,銷毀棧,分析 只要釋放建棧時所申請的空間即可。 源程序 /*/ /* 函 數(shù) 名：destroy_seqstack */ /* 函數(shù)功能：銷毀棧 */ /* 入口參數(shù)：s棧 */ /* 返 回 值：無 */ /*/ void destroy_seqstack(struct seqstack *s) free(s); ,清除棧,有的情況下只需要清除棧，而不銷毀棧。 清除棧：只是將棧內(nèi)元素清空，棧的存儲空間仍保留。 清除棧的源程序 /*/ /* 函 數(shù) 名：clear_seqstack */ /* 函數(shù)功能：清除棧 */ /* 入口參數(shù)：s棧 */ /* 返 回 值：無 */ /*/ void clear_seqstack(struct seqstack *s) s-top=0; ,運行程序(1