實(shí)用文檔教案課程名稱：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 授課班級(jí)：技校二年級(jí)學(xué)生 授課學(xué)時(shí)：1學(xué)時(shí) 授課章節(jié)：第三章棧和隊(duì)列課型：理論課 任課教師：*** §3.1棧教材分析名稱《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》編者：嚴(yán)蔚敏吳偉民等出版社：清華大學(xué)出版社特點(diǎn)“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。它的教學(xué)要求是：學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)結(jié)構(gòu)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法。地位“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。本書是為“數(shù)據(jù)結(jié)構(gòu)”課程編寫的教材，其內(nèi)容選取符合教學(xué)大綱要求。學(xué)情分析知識(shí)基礎(chǔ)技本學(xué)生普遍基礎(chǔ)薄弱，除了少數(shù)幾個(gè)同學(xué)之外，普遍學(xué)習(xí)起點(diǎn)能力低于普通高中生源的學(xué)生。在教學(xué)中學(xué)生可能會(huì)遇到的最大問題是對(duì)符號(hào)化的東西沒有感覺。因此，在授課過程中應(yīng)注意放慢速度，通過理論聯(lián)系實(shí)際，從生活中尋找科學(xué)原型，培養(yǎng)學(xué)生對(duì)符號(hào)化和圖形的認(rèn)知能力。學(xué)習(xí)態(tài)度由于技校學(xué)生沒有升學(xué)壓力,競(jìng)爭(zhēng)意識(shí)薄弱,導(dǎo)致他們的學(xué)習(xí)態(tài)度不端正,不思進(jìn)取、得過且過、目標(biāo)不明確、缺乏學(xué)習(xí)興趣。再加上現(xiàn)在很多職業(yè)技校仍在走傳統(tǒng)教育的老路子,教學(xué)課程枯燥乏味,使得學(xué)生逐漸產(chǎn)生厭倦、逃避、無聊的心理。因此，在授課過程中應(yīng)注意培養(yǎng)學(xué)生的學(xué)習(xí)習(xí)慣和學(xué)習(xí)方法，與學(xué)習(xí)的自制力。思維狀態(tài)觀察力和動(dòng)手能力強(qiáng)，形象思維發(fā)展的很好，但抽象思維和歸納概括能力較差。因此，要注意培養(yǎng)學(xué)生的抽象思維能力，讓學(xué)生學(xué)會(huì)聯(lián)系學(xué)習(xí)法、歸納學(xué)習(xí)法、合作學(xué)習(xí)法和反思學(xué)習(xí)法等。教學(xué)目標(biāo)知識(shí)理解棧的特點(diǎn)。掌握棧的使用方法，能夠?qū)＿M(jìn)行入棧、出棧。能夠根據(jù)棧的出棧順序還原入棧順序。技能能應(yīng)用棧的知識(shí)解決實(shí)際問題。學(xué)會(huì)多種學(xué)習(xí)方法，提高抽象思維和舉一反三能力。情感提高對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)興趣，認(rèn)識(shí)到棧在顯示問題進(jìn)行抽象中的重要作用。培養(yǎng)理論聯(lián)系實(shí)際、積極思考和自主訓(xùn)練的精神。培養(yǎng)主動(dòng)從生活中尋找科學(xué)原型的習(xí)慣。重點(diǎn)與難點(diǎn)重點(diǎn)：棧的特點(diǎn)，棧的基本操作的實(shí)現(xiàn)算法。依據(jù)：課程大綱。處理：通過簡(jiǎn)單有趣的漢諾塔游戲來說明棧的特點(diǎn)。以課堂講授為主，采用多媒體教學(xué)方式以增大信息量，對(duì)重點(diǎn)部分通過動(dòng)畫演示和板書進(jìn)行深入分析，通過提問啟發(fā)學(xué)生思考。難點(diǎn)：解決棧的應(yīng)用問題依據(jù)：多次給同學(xué)們講課經(jīng)驗(yàn)，總結(jié)出來同學(xué)們對(duì)解決應(yīng)用上有點(diǎn)吃力處理：授人以魚不如授人以漁，更要授人以欲。課堂上留幾分鐘時(shí)間讓學(xué)生思考。首先，啟發(fā)學(xué)生對(duì)棧的特點(diǎn)進(jìn)行分析；然后，能根據(jù)給出的一串出棧順序推導(dǎo)出入棧順序，根據(jù)對(duì)棧的特點(diǎn)的理解，分析在實(shí)際生活中的應(yīng)用。方法手段理論指導(dǎo)：以內(nèi)容為主線，以教師為主導(dǎo)，學(xué)生為主體，職業(yè)能力為目標(biāo)，社會(huì)需求為背景。教法：講授法，演示法，探究法，講練結(jié)合法學(xué)法：項(xiàng)目教學(xué)法，情景模擬教學(xué)法教學(xué)手段：板書、動(dòng)態(tài)多媒體課件教學(xué)過程環(huán)節(jié)主要內(nèi)容設(shè)計(jì)意圖回顧與導(dǎo)入（6分鐘）今天我們一起學(xué)習(xí)的內(nèi)容是3.1棧，可以說棧是《棧和隊(duì)列》這一章節(jié)的基礎(chǔ)，也是《數(shù)據(jù)結(jié)構(gòu)》這門課的核心思想之一。掌握這個(gè)思想對(duì)與整門課程的學(xué)習(xí)都有重要影響。前面我們已經(jīng)學(xué)過線性表，請(qǐng)大家回顧一下，棧和隊(duì)列與線性表有哪些相同點(diǎn)呢？棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列也是線性表，其特殊性在于棧和隊(duì)列的基本操作是線性表操作的子集，它們是操作受限的線性表，因此可稱為限定性的數(shù)據(jù)結(jié)構(gòu)。那它們的主要區(qū)別又是什么呢？但從數(shù)據(jù)類型角度看，它們是和線性表大不相同的兩類重要的抽象數(shù)據(jù)類型。由于它們廣泛應(yīng)用在各種軟件系統(tǒng)中，因此，在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，它們是多型數(shù)據(jù)類型。那大家有沒有想過，在現(xiàn)實(shí)中我們并沒有聽說過棧，為什么《數(shù)據(jù)結(jié)構(gòu)》中卻有棧呢？在我們?nèi)粘Ｉ钪新牭阶疃嗟木褪桥抨?duì)列，就像我們?nèi)ボ囌举I票，先排隊(duì)的人先買上票先出隊(duì)列，但我們忽略還有另外一種線性結(jié)構(gòu)——棧。那么棧是如何表示和實(shí)現(xiàn)的呢？激發(fā)學(xué)生學(xué)習(xí)動(dòng)機(jī)，培養(yǎng)其學(xué)會(huì)目標(biāo)學(xué)習(xí)法?；仡櫯f知識(shí)引導(dǎo)學(xué)生一起回答設(shè)疑啟發(fā)激發(fā)學(xué)生的好奇心和學(xué)習(xí)興趣，培養(yǎng)其學(xué)會(huì)聯(lián)系學(xué)習(xí)法。提出問題（3分鐘）提出問題（3分鐘）一個(gè)現(xiàn)實(shí)當(dāng)中的問題：地鐵到達(dá)終點(diǎn)站時(shí)的入站出站問題。如圖1所示，假設(shè)這張圖表示地鐵到站后再出站的圖示。大家想一下，地鐵到終點(diǎn)站后想要再原路返回，向另一個(gè)方向出發(fā)，地鐵是怎樣調(diào)整方向的呢？大家可以先在心里想一下，看是否與我們這節(jié)課所介紹的方法一致。圖1地鐵站入站出站圖1地鐵站入站出站再比如我們餐廳中一疊一疊的盤子，如果它們是按1,2,3，……，n的次序往上疊的話，那么使用的次序應(yīng)該是什么樣的？必然是依從上往下的次序，，即n，，3,2,1。它們遵循的是規(guī)律正是本節(jié)課要討論的“?！钡慕Y(jié)構(gòu)特點(diǎn)。對(duì)圖1進(jìn)行抽象，用地鐵的每節(jié)車廂表示棧中每個(gè)元素這樣就得到一個(gè)棧的示意圖，如圖2所示圖2棧的示意圖圖2棧的示意圖從圖2中可以看出第一個(gè)進(jìn)棧的a1為棧底元素，最后一個(gè)進(jìn)棧的an為棧頂元素，進(jìn)棧和出棧也是同一個(gè)方向。這也是最基本的棧的示意圖。需要同學(xué)們熟知。其實(shí)，要解決這個(gè)出站問題就離不開我們今天將要學(xué)習(xí)的進(jìn)棧、出棧技術(shù)，這節(jié)課我們將從如下三個(gè)方面來掌握它：棧的定義、棧的表示和實(shí)現(xiàn)、棧的應(yīng)用與練習(xí)。其中棧的表示與實(shí)現(xiàn)是本節(jié)的重點(diǎn)。任務(wù)驅(qū)動(dòng)提出問題培養(yǎng)學(xué)生學(xué)會(huì)問題學(xué)習(xí)法。抽象思維激發(fā)學(xué)生的學(xué)習(xí)興趣講授新課（30分鐘）講授新課（30分鐘）講授新課（30分鐘）講授新課（30分鐘）講授新課（30分鐘抽象數(shù)據(jù)類型棧的定義（6分鐘）定義：棧（stack）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對(duì)棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭端稱為棧底（bottom）。不含元素的空表稱為空棧。引出特點(diǎn)：假設(shè)棧S=（a1,a2,?????,an）,則稱a1為棧底元素，an為棧頂元素。棧中元素按a1,a2,?????,an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說，棧的修改是按照后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出的線性表。目的：根據(jù)入棧順序得到出棧序列，以及能夠在實(shí)際生活中運(yùn)用棧，為棧的操作打基礎(chǔ)。我們回到定義：出棧序列如何確定呢？根據(jù)給出的幾組出棧序列如何判斷哪些可以由入棧序列得到，哪些序列由入棧序列得不到。這就是入棧方法的問題。下面我們來做一個(gè)簡(jiǎn)單的小實(shí)驗(yàn)更深入的了解站的特點(diǎn)。介紹棧的定義類型（8分鐘）ADTStack{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底?；静僮鳎篒nitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。StackTraverse(S,visit())初始條件：棧S已存在且非空。

操作結(jié)果：從棧底到棧頂依次對(duì)S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失效。}ADTStrack練習(xí)與拓展（16分鐘）練習(xí)（解決問題）回到地鐵到達(dá)終點(diǎn)站時(shí)的入站出站問題。請(qǐng)同學(xué)們對(duì)右圖棧的示意圖中進(jìn)棧序列依次為{a1,a2,a3,a4,a5,a6}，進(jìn)行出棧序列排序。根據(jù)前面提出的棧的特點(diǎn)是不是可以很容易的得出這個(gè)序列的出棧序列呀。出棧序列為：a6,a5,a4,a3,a2,a1大家可以看看現(xiàn)在的解決方案與提出規(guī)劃的方法是否一致。由此也可以看出該技術(shù)的重要。同學(xué)有沒有覺得出棧序列還是很容易得到的，有沒有感覺棧的知識(shí)也沒有很難呀？根據(jù)以上對(duì)棧的理解，現(xiàn)在提出一個(gè)進(jìn)棧出棧更寬泛的規(guī)則，讓同學(xué)們感受到棧的知識(shí)的有趣性和多變性。注：進(jìn)棧時(shí)除了一次性全部進(jìn)棧之后再出棧的規(guī)則之外，其實(shí)還可以進(jìn)棧元素進(jìn)去一個(gè)或兩個(gè)之后直接出棧，出?？梢圆槐囟汲鐾辏又M(jìn)棧隨時(shí)可以出棧。比如上述題中出棧序列也可以為如下序列：序列1：a1,a2,a3,a4,a5,a6序列2：a2,a1,a4,a3,a5,a6序列3：a4,a5,a3,a6,a2,a1??????同學(xué)們有沒有感覺根據(jù)棧的入棧方式不同可以產(chǎn)生不同的出棧序列，是不是棧的出棧序列很靈活，就像我們生活中的趣事一般。同學(xué)們發(fā)現(xiàn)棧和線性表的相似了沒有呢？下面我畫一個(gè)順序存儲(chǔ)結(jié)構(gòu)的線性表線性表，同學(xué)們觀察一下它們是不是很相似呢？拓展（1）設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，b請(qǐng)同學(xué)們想一下上面的序列哪些可以根據(jù)進(jìn)棧順序得到，哪些得不到呢？解：A、D可以（B、C不行）同學(xué)們對(duì)一下看看給出的答案跟你們心中的答案是否一致呢？有不理解的同學(xué)可以舉手提問哦。下面再來解答一個(gè)題，鞏固鞏固今天所學(xué)過的知識(shí)。數(shù)制轉(zhuǎn)換算法基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，

其運(yùn)算過程如下：同學(xué)們想到答案了嗎？思考棧往往用單鏈表實(shí)現(xiàn)。可以用雙鏈表嗎？哪個(gè)更好？這個(gè)問題同學(xué)們課后思考一下，下節(jié)課我們來解答。暗示啟發(fā)多種字體提示學(xué)生主動(dòng)思考，培養(yǎng)其速記學(xué)習(xí)的能力。設(shè)疑啟發(fā)提出疑問，引起學(xué)生對(duì)接下來的內(nèi)容產(chǎn)生好奇心，對(duì)接下來要講的內(nèi)容產(chǎn)生濃厚的興趣。聯(lián)系實(shí)際根據(jù)定義給出在編程中對(duì)棧進(jìn)行操作是可以實(shí)現(xiàn)哪些功能。講授操作講解棧的基本操作中插入圖示，可以更直觀的看出棧的每個(gè)操作實(shí)現(xiàn)的最終結(jié)果。任務(wù)驅(qū)動(dòng)解決問題練習(xí)法學(xué)以致用，當(dāng)堂鞏固。知識(shí)補(bǔ)充根據(jù)前面提出的問題進(jìn)行解答。最后對(duì)棧的知識(shí)沒有講解到的加以補(bǔ)充。使同學(xué)們更深入的理解棧。設(shè)疑啟發(fā)提示同學(xué)們觀察棧和線性表的相似點(diǎn)與不同點(diǎn)。有助于提高學(xué)習(xí)效率和質(zhì)量。最終使同學(xué)們喜歡上這門課。反思學(xué)習(xí)法學(xué)以致用從本節(jié)課的難點(diǎn)出發(fā)設(shè)置兩個(gè)例題，讓同學(xué)們思考一下，學(xué)以致用，會(huì)使用所學(xué)的知識(shí)解決實(shí)際生活中的問題。小結(jié)（3分鐘）理解棧和線性表的異同點(diǎn)。掌握棧的特點(diǎn)，根據(jù)特點(diǎn)能夠解決入棧出棧順序，以及可以根據(jù)入棧得到多種入棧序列。能夠利用棧知識(shí)解決實(shí)際生活中的問題。大家要掌握棧的特點(diǎn)，這是棧的重點(diǎn)。大家只要多練習(xí)、多思考、多歸納、多總結(jié)，就一定能熟練掌握。我們學(xué)過的知識(shí)。同學(xué)們加油哦！知識(shí)總結(jié)課堂總結(jié)可以把學(xué)過的知識(shí)整理成一個(gè)系統(tǒng)的體系，有助于提高學(xué)習(xí)效率和質(zhì)量。布置作業(yè)（3分鐘）書面作業(yè)：設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4,

s6

,

s5,s1,則棧的容量至少應(yīng)該是（）A.2

B.

3

C.

5

D.6思考：hanoi塔問題傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫Brahma的寺廟里，有三個(gè)柱子，其中一柱上有64個(gè)盤