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

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

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

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

4、個(gè)指向順序棧的指針： struct seqstack *s; 源程序,運(yùn)行程序(10_1),看源程序(10_1),建棧,分析 首先申請(qǐng)?？臻g，然后初始化棧頂指針。 流程圖 源程序,運(yùn)行程序(10_1),看源程序(10_1),入棧,流程圖 源程序 int push_seqstack (struct seqstack *s, Elemtype x) s-datas-top=x; s-top+; return 1; ,思考：如果不斷入棧，會(huì)出現(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; ,改進(jìn)后的入棧,分析 為了防止上溢發(fā)生，在入棧前先檢查棧是否滿。若未滿，則進(jìn)行入棧操作，否則進(jìn)行溢棧處理或溢棧報(bào)告。 流程圖 源程序,運(yùn)行程序(10_1),看源程序(10_1),出棧,流程圖 源程序 int pop_seqstack (struct seqstack *s, Elemtype *x) s-top-; *x=s-datas-top;

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

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í)所申請(qǐng)的空間即可。 源程序 /*/ /* 函 數(shù) 名：destroy_seqstack */ /* 函數(shù)功能：銷毀棧 */ /* 入口參數(shù)：s棧 */ /* 返 回 值：無(wú) */ /*/ void destroy_seqstack(struct seqstack *s) free(s); ,清除棧,有的情況下只需要清除棧，而不銷毀棧。 清除棧：只是將棧內(nèi)元素清空，棧的存儲(chǔ)空間仍保留。 清除棧的源程序 /*/ /* 函 數(shù) 名：clear_seqstack */ /* 函數(shù)功能：清除棧 */ /* 入口參數(shù)：s棧 */ /* 返 回 值：無(wú) */ /*/ void clear_seqstack(struct seqstack *s) s-top=0; ,運(yùn)行程序(1