1、第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)首頁(yè)首頁(yè)第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)教學(xué)主題教學(xué)主題棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作教學(xué)目標(biāo)教學(xué)目標(biāo) 通過(guò)本次課的學(xué)習(xí)，使學(xué)生掌握棧的概念、通過(guò)本次課的學(xué)習(xí)，使學(xué)生掌握棧的概念、棧的存儲(chǔ)方式、順序棧的實(shí)現(xiàn)。棧的存儲(chǔ)方式、順序棧的實(shí)現(xiàn)。教學(xué)重點(diǎn)教學(xué)重點(diǎn) 棧的順序存儲(chǔ)方式棧的順序存儲(chǔ)方式 順序棧的基本操作順序棧的基本操作教學(xué)難點(diǎn)教學(xué)難點(diǎn) 順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)教案教案第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作

2、C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容主要內(nèi)容 棧的概念棧的概念 棧的根本操作棧的根本操作 棧的存儲(chǔ)棧的存儲(chǔ) 順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)引例引例 在日常生活中，有一些這樣的例子。在日常生活中，有一些這樣的例子。 例例1：食堂師傅把洗好的飯盒按順序放好，最后洗的飯盒：食堂師傅把洗好的飯盒按順序放好，最后洗的飯盒總是放在一疊飯盒的最上面。同窗們到食堂就餐時(shí)，拿飯盒總是放在一疊飯盒的最上面。同窗們到食堂就餐時(shí)，拿飯盒總是按照由上到下的順序拿，即總是拿一疊飯盒中最頂上的總是按照由上到下的順序拿，即總是拿一疊飯盒中最頂上的一個(gè)。一個(gè)

3、。 例例2：有一個(gè)盒子，我們?cè)诶镱^放了一疊書。當(dāng)我們要用：有一個(gè)盒子，我們?cè)诶镱^放了一疊書。當(dāng)我們要用書的時(shí)候，只能從第一本開場(chǎng)拿；當(dāng)我們要把書本放進(jìn)去時(shí)，書的時(shí)候，只能從第一本開場(chǎng)拿；當(dāng)我們要把書本放進(jìn)去時(shí)，總是放在最上面。總是放在最上面。 請(qǐng)問(wèn)：上面的例子中有什么共同的特點(diǎn)？請(qǐng)問(wèn)：上面的例子中有什么共同的特點(diǎn)？后放進(jìn)去的，先拿出來(lái)。后放進(jìn)去的，先拿出來(lái)。第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)棧的概念和特點(diǎn)棧的概念和特點(diǎn) 什么是棧？什么是棧？ 棧是一種特殊的線性表，它只在線性表的一端棧是一種特殊的線性表，它只在線性表的一端進(jìn)展插入和刪除操作。

4、進(jìn)展插入和刪除操作。 棧中允許插入、刪除的這一端稱為棧頂，另一棧中允許插入、刪除的這一端稱為棧頂，另一個(gè)固定端稱為棧底。個(gè)固定端稱為棧底。 當(dāng)表中沒有元素時(shí)稱為空棧。當(dāng)表中沒有元素時(shí)稱為空棧。 棧的特點(diǎn)棧的特點(diǎn) “先進(jìn)后出先進(jìn)后出First In Last Out 或或“后進(jìn)先出后進(jìn)先出Last In First Out第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)棧的根本操作棧的根本操作 棧主要有建棧、入棧、出棧和銷毀棧四個(gè)根本操棧主要有建棧、入棧、出棧和銷毀棧四個(gè)根本操作。作。 建棧：新建一個(gè)空棧，向操作系統(tǒng)懇求一組存建棧：新建一個(gè)空棧，向操作系統(tǒng)

5、懇求一組存儲(chǔ)單元，用于存儲(chǔ)棧中的元素。儲(chǔ)單元，用于存儲(chǔ)棧中的元素。 入棧：將元素壓入棧內(nèi)，存儲(chǔ)在棧頂。入棧：將元素壓入棧內(nèi)，存儲(chǔ)在棧頂。 出棧：從棧中取出棧頂元素，也稱為彈出棧。出棧：從棧中取出棧頂元素，也稱為彈出棧。 銷毀棧：把存儲(chǔ)單元?dú)w還給操作系統(tǒng)。銷毀棧：把存儲(chǔ)單元?dú)w還給操作系統(tǒng)。 為了實(shí)時(shí)了解棧的情況，還需求有輸出棧這樣的為了實(shí)時(shí)了解棧的情況，還需求有輸出棧這樣的操作。操作。 輸出棧：顯示棧的內(nèi)容。輸出棧：顯示棧的內(nèi)容。第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)棧的存儲(chǔ)棧的存儲(chǔ) 回想：前面引見的線性表是采用什么方式存儲(chǔ)數(shù)據(jù)的？回想：前面引見

6、的線性表是采用什么方式存儲(chǔ)數(shù)據(jù)的？ 棧與前面引見過(guò)的線性表一樣，也可以采用順序存儲(chǔ)構(gòu)造棧與前面引見過(guò)的線性表一樣，也可以采用順序存儲(chǔ)構(gòu)造數(shù)組或者鏈?zhǔn)酱鎯?chǔ)構(gòu)造鏈表。數(shù)組或者鏈?zhǔn)酱鎯?chǔ)構(gòu)造鏈表。順序棧順序棧鏈棧單鏈表鏈棧單鏈表 棧的表示棧的表示 可以用一個(gè)棧頂指針可以用一個(gè)棧頂指針toptop來(lái)指示棧頂元素存放的位置，來(lái)指示棧頂元素存放的位置，用一個(gè)棧底指針用一個(gè)棧底指針bottombottom來(lái)指示棧底元素的存放位置。由來(lái)指示棧底元素的存放位置。由于棧底位置相對(duì)不變，通常不用于棧底位置相對(duì)不變，通常不用bottombottom。第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操

7、作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)順序棧的表示圖順序棧的表示圖第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)鏈棧的表示圖鏈棧的表示圖(1) 初始： top=NULL (2) a1入棧后： (3) a2、a3入棧后： (4) 一個(gè)元素出棧： top a1 top a3 a2 a1 top a2 a1 第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)【例】先建棧，然后輸入一個(gè)整型元素后入棧，顯示棧的內(nèi)【例】先建棧，然后輸入一個(gè)整型元素后入棧，顯示棧的內(nèi)容。接下來(lái)進(jìn)展出棧操作，再顯示棧的內(nèi)容。最后銷毀棧。容。接

8、下來(lái)進(jìn)展出棧操作，再顯示棧的內(nèi)容。最后銷毀棧。 數(shù)據(jù)構(gòu)造描畫數(shù)據(jù)構(gòu)造描畫順序棧的類型描畫如下：順序棧的類型描畫如下：#define MAXSIZE 200 #define MAXSIZE 200 struct seqstackstruct seqstack Elemtype dataMAXSIZE; Elemtype dataMAXSIZE; int top; int top;定義一個(gè)指向順序棧的指針：定義一個(gè)指向順序棧的指針：struct seqstack struct seqstack * *s;s; 源程序源程序運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次

9、課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)建棧建棧 分析分析 首先懇求棧空間，然后初始化棧頂指針。首先懇求棧空間，然后初始化棧頂指針。 流程圖流程圖 源程序源程序運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)入棧入棧 流程圖流程圖 源程序源程序int push_seqstack (struct seqstack int push_seqstack (struct seqstack * *s, Elemtype x)s, Elemtype x) s-datas-top=x;

10、 s-datas-top=x; s-top+; s-top+; return 1; return 1; 思索：假設(shè)不斷入棧，思索：假設(shè)不斷入棧，會(huì)出現(xiàn)什么情況？會(huì)出現(xiàn)什么情況？(10_2)(10_2)上溢出上溢出第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)檢查棧能否滿的子函數(shù)檢查棧能否滿的子函數(shù) 源程序源程序/*/* 函函 數(shù)數(shù) 名：名：full_seqstack */* 函數(shù)功能：檢查棧能否滿函數(shù)功能：檢查棧能否滿 */* 入口參數(shù)：入口參數(shù)：s棧棧 */* 返返 回回 值：棧滿前往值：棧滿前往1，否那么前往，否那么前往0 */*/int full

11、_seqstack(struct seqstack *s) if (s-top = MAXSIZE) return 1; else return 0;第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)改良后的入棧改良后的入棧 分析分析 為了防止上溢發(fā)生，在入棧前先檢查棧能否滿。假設(shè)未為了防止上溢發(fā)生，在入棧前先檢查棧能否滿。假設(shè)未滿，那么進(jìn)展入棧操作，否那么進(jìn)展溢棧處置或溢棧報(bào)告。滿，那么進(jìn)展入棧操作，否那么進(jìn)展溢棧處置或溢棧報(bào)告。 流程圖流程圖 源程序源程序運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次課次課-棧的性質(zhì)、棧的

12、基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)出棧出棧 流程圖流程圖 源程序源程序int pop_seqstack (struct seqstack int pop_seqstack (struct seqstack * *s, Elemtype s, Elemtype * *x)x) s-top-; s-top-; * *x=s-datas-top;x=s-datas-top; return 1; return 1; 思索：假設(shè)不斷出棧，思索：假設(shè)不斷出棧，會(huì)出現(xiàn)什么情況？會(huì)出現(xiàn)什么情況？(10_2)(10_2)下溢出下溢出第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本

13、操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)檢查棧能否為空的子函數(shù)檢查棧能否為空的子函數(shù) 源程序源程序 /*/ /* 函函 數(shù)數(shù) 名：名：empty_seqstack */ /* 函數(shù)功能：檢查棧能否為空函數(shù)功能：檢查棧能否為空 */ /* 入口參數(shù)：入口參數(shù)：s棧棧 */ /* 返返 回回 值：棧空前往值：棧空前往1，否那么前往，否那么前往0 */ /*/ int empty_seqstack(struct seqstack *s) if (s-top = 0) return 1; else return 0; 第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)改良后的出棧改良

14、后的出棧 分析分析 為了防止下溢發(fā)生，在出棧前先檢查棧能否為空。假設(shè)為了防止下溢發(fā)生，在出棧前先檢查棧能否為空。假設(shè)不空，那么進(jìn)展出棧操作，否那么進(jìn)展溢棧處置或溢棧報(bào)告。不空，那么進(jìn)展出棧操作，否那么進(jìn)展溢棧處置或溢棧報(bào)告。 流程圖流程圖 源程序源程序運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)程序程序(10_1)看源看源程序程序(10_1)第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)顯示棧顯示棧 源程序源程序 void display_seqstack(struct seqstack *s) int i; if (empty_seqstack(s) printf(目前棧為空目前棧為空

15、!n); return; printf(目前棧的內(nèi)容為：目前棧的內(nèi)容為：); for (i=0; itop-1;i+) printf(%d ,s-datai); printf(n); 第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)銷毀棧銷毀棧 分析分析 只需釋放建棧時(shí)所懇求的空間即可。只需釋放建棧時(shí)所懇求的空間即可。 源程序源程序 /*/ /* 函函 數(shù)數(shù) 名：名：destroy_seqstack */ /* 函數(shù)功能：銷毀棧函數(shù)功能：銷毀棧 */ /* 入口參數(shù)：入口參數(shù)：s棧棧 */ /* 返返 回回 值：無(wú)值：無(wú) */ /*/ void dest

16、roy_seqstack(struct seqstack *s) free(s); 第第8章章第第10次課次課-棧的性質(zhì)、棧的基本操作棧的性質(zhì)、棧的基本操作C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)去除棧去除棧 有的情況下只需求去除棧，而不銷毀棧。有的情況下只需求去除棧，而不銷毀棧。 去除棧：只是將棧內(nèi)元素清空，棧的存儲(chǔ)空間仍保管。去除棧：只是將棧內(nèi)元素清空，棧的存儲(chǔ)空間仍保管。 去除棧的源程序去除棧的源程序 /*/ /* 函函 數(shù)數(shù) 名：名：clear_seqstack */ /* 函數(shù)功能：去除棧函數(shù)功能：去除棧 */ /* 入口參數(shù)：入口參數(shù)：s棧棧 */ /* 返返 回回 值：無(wú)值：無(wú) */ /*/ void clear_seqstack(struct seqstack *s) s-top=0; 運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)程序程序(10_