《數(shù)據(jù)結(jié)構(gòu)》教案

1、安慶師范學(xué)院教案（課時(shí)計(jì)劃）課程名稱：數(shù)據(jù)結(jié)構(gòu) 授課班級(jí)： 授課地點(diǎn)： 主講教師：程玉勝20152016 學(xué)年第 2學(xué)期7201 、數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語(yǔ)02、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法和算法分析03、線性表的類型定義、線性表的順序表示和實(shí)現(xiàn)04、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（線性鏈表）05、循環(huán)鏈表、雙向鏈表、一元多項(xiàng)式的表示及相加06、棧、棧應(yīng)用舉例（數(shù)制轉(zhuǎn)換、括號(hào)匹配、行編輯）07、迷宮求解、表達(dá)式求值、棧與遞歸的實(shí)現(xiàn)08、隊(duì)列09、機(jī)動(dòng)10、習(xí)題課11 、串類型的定義、串的表示和實(shí)現(xiàn)12、串的模式匹配算法、串操作應(yīng)用舉例13、數(shù)組的定義、順序表示和實(shí)現(xiàn)、矩陣的壓縮存儲(chǔ)14、稀疏矩陣的存

2、儲(chǔ)結(jié)構(gòu)、廣義表15、樹的定義和基本術(shù)語(yǔ)、二叉樹的定義16、二叉樹的性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)17、遍歷二叉樹和線索二叉樹18、樹和森林19、赫夫曼樹及其應(yīng)用20、習(xí)題課21 、圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)22、十字鏈表、鄰接多重表、圖的遍歷23、圖的連通性問(wèn)題24、有向無(wú)環(huán)圖及其應(yīng)用25、最短路徑26、靜態(tài)查找表27、二叉排序樹和平衡二叉樹28、 B-樹和B+樹29、哈希表30、排序概述、插入排序31 、快速排序、選擇排序32、歸并排序、基數(shù)排序33、外部排序、各種排序方法的比較34、文件編號(hào)1周次1日期9.3課時(shí)安排2課題數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語(yǔ)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)數(shù)據(jù)結(jié)構(gòu)的

3、邏輯結(jié)構(gòu)(2)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)(3)抽象數(shù)據(jù)類型的概念教 學(xué) 目 標(biāo)掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象的概念熟練掌握數(shù)據(jù)結(jié)構(gòu)的概念及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類掌握抽象數(shù)據(jù)類型的定義方法教學(xué)方法和 教學(xué) 手段講授法多媒體教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第一章緒論1 1 什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值計(jì)算問(wèn)題舉例數(shù)據(jù)結(jié)構(gòu)產(chǎn)生的背景數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的地位和作用1 2 基本概念和術(shù)語(yǔ)數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象數(shù)據(jù)結(jié)構(gòu)教數(shù)據(jù)結(jié)構(gòu)的形式定義Data-Structure = (D, S)數(shù)據(jù)的邏輯結(jié)構(gòu)及分類：集合、線性、樹形、圖形結(jié)構(gòu)學(xué)數(shù)據(jù)的物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)類型過(guò)抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的形

4、式定義ADT =(D, S, P)程抽象數(shù)據(jù)類型定義舉例Triplet師生雙邊活動(dòng)：提問(wèn)：什么是數(shù)據(jù)類型？舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后1.2,1.19作業(yè)教材：1 嚴(yán)蔚敏吳偉民編著：數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版)，清華大學(xué)出版社，1997 年教學(xué) 后記參考書目：1Wirth N ： Algorithms+Data Structures=Programs ， Prentice-Hall Inc.， 19762 美 S 巴斯：計(jì)算機(jī)算法：設(shè)計(jì)和分析引論，復(fù)旦大學(xué)出版社，1985編號(hào)2周次1日期9.6課時(shí)安排2課題抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法和算法分析教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)算法復(fù)雜度的

5、分析方法難點(diǎn)：(1)算法復(fù)雜度的分析方法教 學(xué) 目 標(biāo)(1)理解數(shù)據(jù)抽象的意義(2)熟悉類C 語(yǔ)言(3)掌握抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)方法(4)掌握算法描述和算法分析的方法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安與排板書設(shè)計(jì)：1 3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)數(shù)據(jù)抽象的意義類 C 語(yǔ)言抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)舉例1 4 算法和算法分析算法算法的定義算法的特性：有窮性、確定性、可行性、輸入、輸出算法設(shè)計(jì)的要求教正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求算法效率的度量學(xué)時(shí)間度量的方法分析時(shí)間復(fù)雜度過(guò)T(n) = O(f(n)時(shí)間復(fù)雜度的計(jì)算程算法的存儲(chǔ)空間需求S(n) = O(f(n)師生雙邊活

6、動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后1.4,1.20作業(yè)教學(xué)后記編號(hào)3周次2日期9.10課時(shí)安排2課題線性表的類型定義、線性表的順序表示和實(shí)現(xiàn)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)順序表的基本運(yùn)算(2)順序表上實(shí)現(xiàn)的各種算法的時(shí)間性能分析教 學(xué) 目 標(biāo)(1)理解線性表的邏輯結(jié)構(gòu)特征(2)熟練掌握順序表的描述方法、特點(diǎn)及有關(guān)概念(3)熟練掌握順序表的基本運(yùn)算教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第二章線性表線性結(jié)構(gòu)的特點(diǎn)21 線性表的類型定義線性表的定義及其表示線性表的類型定義線性表操作舉例：用線性表表示集合、線性表的合并教學(xué)過(guò)程2 2 線性表的順序表示和實(shí)現(xiàn)線索性表

7、的順序表示線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及其特征順序表的基本運(yùn)算順序表的初始化順序表的插入操作順序表的刪除操作順序表的合并順序表基本操作的時(shí)間復(fù)雜度計(jì)算師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后 作業(yè)2.12教學(xué) 后記編號(hào)4周次2日期9.13課時(shí)安排2課題線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)(線性鏈表)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)鏈表的基本運(yùn)算(2)鏈表上實(shí)現(xiàn)的各種算法的時(shí)間性能分析教 學(xué) 目 標(biāo)(1)熟練掌握鏈表的描述方法、特點(diǎn)及有關(guān)概念(2)掌握鏈表的基本運(yùn)算(3)掌握靜態(tài)鏈表的構(gòu)造方法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：2 3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2 3 1

8、線性鏈表單鏈表的定義單鏈表的存儲(chǔ)結(jié)構(gòu)特征單鏈表的基本操作：插入刪除有序鏈表的合并靜態(tài)鏈表靜態(tài)鏈表的定義靜態(tài)鏈表的操作舉例教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：malloc() free()舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后2.17,2.25作業(yè)教學(xué)后記編號(hào)5周次3日期9.17課時(shí)安排2課題循環(huán)鏈表、雙向鏈表、一元多項(xiàng)式的表示及相加教材 的重 點(diǎn)、 難點(diǎn) 分析難點(diǎn)：(1)循環(huán)鏈表教 學(xué) 目 標(biāo)(1)掌握循環(huán)鏈表的特點(diǎn)(2)掌握雙向鏈表的特點(diǎn)(3)從時(shí)空角度綜合比較順序表和鏈表的不同特點(diǎn)及使用場(chǎng)合(4)能應(yīng)用線性表解決一些實(shí)際問(wèn)題教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：2 3 2 循環(huán)鏈表循

9、環(huán)鏈表的定義循環(huán)鏈表的操作2 3 3 雙向鏈表雙向鏈表的定義雙向鏈表的操作特點(diǎn)線性鏈表的類型定義2 4 一元多項(xiàng)式的表示及相加教一元多項(xiàng)式的表示一元多項(xiàng)式的相加學(xué)一元多項(xiàng)式的類型定義多項(xiàng)式的相加算法過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后2.32作業(yè)教學(xué)后記編號(hào)6周次3日期9.20課時(shí)安排2課題棧、棧應(yīng)用舉例(數(shù)制轉(zhuǎn)換、括號(hào)匹配、行編輯)教材重點(diǎn)：(1)棧在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。的重難點(diǎn)分析難點(diǎn)：棧滿棧空的條件及它們的描述(1)掌握棧這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)教 學(xué)(2)熟悉棧與線性表的關(guān)系(3)重點(diǎn)掌握順序棧和鏈?zhǔn)綏５奈宸N基本運(yùn)算目 標(biāo)(4)掌握棧的應(yīng)用方法教學(xué)方法和 教學(xué)手段

10、教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第三章棧與隊(duì)列教3 1 棧學(xué) 過(guò) 程3 1 1抽象數(shù)據(jù)類型棧的定義棧及其與線性表的關(guān)系棧的類型定義3 1 2 棧的表示和實(shí)現(xiàn)順序棧的定義鏈棧的定義3 2 棧的應(yīng)用舉例教3 2 1 數(shù)制轉(zhuǎn)換3 2 2 括號(hào)匹配的檢驗(yàn)學(xué)3 2 3 行編輯程序過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后3.15作業(yè)教學(xué)后記編號(hào)7周次4日期9.24課時(shí)安排2課題迷宮求解、表達(dá)式求值、棧與遞歸的實(shí)現(xiàn)教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)(1)能應(yīng)用棧解決一些實(shí)際問(wèn)題(2)了解遞歸算法執(zhí)行過(guò)程中棧的變化過(guò)程教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：3 2 4 迷宮求

11、解3 2 5 表達(dá)式求值3 3 棧與遞歸的實(shí)現(xiàn)程課后師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：3.19,3.25作業(yè)教學(xué) 后記編號(hào)8周次4日期9.27課時(shí)安排2課題隊(duì)列教材重點(diǎn)：(1)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。的重難點(diǎn)分析難點(diǎn)：(1)循環(huán)隊(duì)列(注意隊(duì)滿隊(duì)空的條件及它們的描述)(1) 掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)教 學(xué)(2)熟悉隊(duì)列與線性表的關(guān)系(3)掌握循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的五種基本運(yùn)算目 標(biāo)(4)能應(yīng)用隊(duì)列解決一些實(shí)際問(wèn)題教學(xué)方法和 教學(xué)手段教學(xué)內(nèi)容安排與板書設(shè)計(jì)：3 4 隊(duì)列教3 4 1抽象數(shù)據(jù)類型隊(duì)列的定義學(xué) 過(guò) 程隊(duì)列的定義(FIFO)隊(duì)列的類型定義3 4 2 鏈隊(duì)列隊(duì)列的鏈

12、式表示和實(shí)現(xiàn)單鏈隊(duì)列的定義單鏈隊(duì)列的操作3 4 3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)教循環(huán)隊(duì)列的基本操作學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后3.29作業(yè)教學(xué)后記編號(hào)9周次5日期10.1課時(shí)安排2課題機(jī)動(dòng)教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：程師生雙邊活動(dòng)： 提問(wèn)： 舉例： 演示實(shí)驗(yàn)： 教具準(zhǔn)備：課后 作業(yè)教學(xué) 后記編號(hào)10周次5日期10.4課時(shí)安排2課題習(xí)題課教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)教學(xué)方法和 教學(xué) 手段講授法教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：程師生雙邊活動(dòng)： 提問(wèn)： 舉例：

13、 演示實(shí)驗(yàn)： 教具準(zhǔn)備：課后 作業(yè)教學(xué) 后記編號(hào)11周次6日期10.8課時(shí)安排2課題串類型的定義、串的表示和實(shí)現(xiàn)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)串的基本運(yùn)算難點(diǎn)：(1)串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)教 學(xué) 目 標(biāo)(1)熟悉串的有關(guān)概念，串與線性表的關(guān)系(2)掌握串的靜態(tài)存儲(chǔ)結(jié)構(gòu)與動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)和它們的優(yōu)缺點(diǎn)(3)熟練掌握串的基本運(yùn)算教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第四章串41 串類型的定義串的概念串類型的定義4 2 串的表示和實(shí)現(xiàn)4 2 1 定長(zhǎng)順序存儲(chǔ)表示串的定長(zhǎng)順序存儲(chǔ)表示串聯(lián)接求子串教4 2 2 堆分配存儲(chǔ)表示串的堆分配存儲(chǔ)表示學(xué)堆的基本操作4 2 3 串的塊鏈存儲(chǔ)表

14、示過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后4.17,4.22/4.24作業(yè)教學(xué)后記編號(hào)12周次6日期10.11課時(shí)安排2課題串的模式匹配算法、串操作應(yīng)用舉例教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)(1)理解串的模式匹配算法(2)了解串的應(yīng)用教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：4 3 串的模式匹配算法4 3 1 求子串位置的定位函數(shù)4 3 2 模式匹配的一種改進(jìn)算法KMP 算法4 4 串操作應(yīng)用舉例4 4 1 文本編輯教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后4.8作業(yè)教學(xué)后記編號(hào)13周次7日期10.15課時(shí)安排2課題數(shù)組的定義、順序表示和

15、實(shí)現(xiàn)、矩陣的壓縮存儲(chǔ)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)多維數(shù)組的存儲(chǔ)方式(2)矩陣的壓縮存儲(chǔ)方式難點(diǎn)：(1)稀疏矩陣的壓縮存儲(chǔ)表示下實(shí)現(xiàn)的算法教 學(xué) 目 標(biāo)(1)熟悉數(shù)組的按行(列)優(yōu)先順序的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法(2)熟悉特殊矩陣在壓縮存儲(chǔ)時(shí)的下標(biāo)變換(3)理解稀疏矩陣的三元組和十字鏈表兩種壓縮存儲(chǔ)表示教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第五章數(shù)組和廣義表5 1 數(shù)組的定義數(shù)組的類型定義二維數(shù)組5 2 數(shù)組的順序表示和實(shí)現(xiàn)二維數(shù)組的存儲(chǔ)方式數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)5 3 矩陣的壓縮存儲(chǔ)教5 3 1 特殊矩陣對(duì)稱矩陣學(xué)對(duì)角矩陣5 3 2 稀疏矩陣過(guò)稀疏矩陣的類型

16、定義1、三元組順序表程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后5.21作業(yè)教學(xué)后記編號(hào)14周次7日期10.18課時(shí)安排2課題稀疏矩陣的存儲(chǔ)結(jié)構(gòu)、廣義表的定義和存儲(chǔ)結(jié)構(gòu)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)廣義表的定義及其運(yùn)算教 學(xué) 目 標(biāo)(1)掌握稀疏矩陣的存儲(chǔ)結(jié)構(gòu)(2)熟悉廣義表的有關(guān)概念和運(yùn)算(3)掌握廣義表的兩種存儲(chǔ)結(jié)構(gòu)教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：2、行邏輯鏈接的順序表3、十字鏈表5 4 廣義表的定義廣義表的類型定義廣義表舉例廣義表的特點(diǎn)5 5 廣義表的存儲(chǔ)結(jié)構(gòu)教學(xué)討論：M 元多項(xiàng)式的表示過(guò)廣義表的遞歸算法程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：

17、教具準(zhǔn)備：課后5.26,5.12作業(yè)教學(xué)后記編號(hào)15周次8日期10.22課時(shí)安排2課題樹的定義和基本術(shù)語(yǔ)、二叉樹的定義教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)樹的基本術(shù)語(yǔ)(2)二叉樹的定義教 學(xué) 目 標(biāo)(1)掌握樹的定義和有關(guān)術(shù)語(yǔ)(2)熟悉二叉樹的遞歸定義，有關(guān)術(shù)語(yǔ)及基本概念教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第六章樹和二叉樹61 樹的定義和基本術(shù)語(yǔ)樹的類型定義基本術(shù)語(yǔ)6 2 二叉樹6 2 1 二叉樹的定義二叉樹的類型定義二叉樹的基本形態(tài)教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后6.2作業(yè)教學(xué)后記編號(hào)16周次8日期10.25課時(shí)安排2課題二叉樹的性質(zhì)和和

18、存儲(chǔ)結(jié)構(gòu)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)二叉樹的存儲(chǔ)結(jié)構(gòu)難點(diǎn)：(1)二叉樹的性質(zhì)教 學(xué) 目 標(biāo)(1)熟練掌握二叉樹的性質(zhì)及證明方法(2)熟練掌握二叉樹的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及特點(diǎn)教學(xué)方法和 教學(xué) 手段講授法教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：6 2 2 二叉樹的性質(zhì)性質(zhì)1性質(zhì)2性質(zhì)3性質(zhì)4性質(zhì)56 2 3 二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后6.6,6.11作業(yè)教學(xué)后記編號(hào)17周次9日期10.29課時(shí)安排2課題遍歷二叉樹和線索二叉樹教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)二叉樹的遍歷算法及其相關(guān)應(yīng)用難點(diǎn)：(1)二叉樹的非遞歸

19、遍歷算法教 學(xué) 目 標(biāo)(1)熟練掌握二叉樹的各種遍歷(2)能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的基本運(yùn)算(3)掌握二叉樹的線索化及相應(yīng)算法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：6 3 遍歷二叉樹和線索二叉樹6 3 1 遍歷二叉樹遍歷二叉樹的遞歸算法先序遍歷中序遍歷后序遍歷遍歷二叉樹的非遞歸算法遍歷二叉樹的其他算法二叉樹的其他操作6 3 2 線索二叉樹線索二叉樹及其存儲(chǔ)結(jié)構(gòu)教二叉樹的線索化學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后6.43,6.47,6.56作業(yè)教學(xué)后記編號(hào)18周次9日期11.1課時(shí)安排2課題樹和森林教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)樹的存儲(chǔ)結(jié)構(gòu)

20、難點(diǎn)：(1) 森林、樹與二叉樹之間的轉(zhuǎn)換教 學(xué) 目 標(biāo)(1)掌握樹的存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)(2)熟練掌握森林、樹與二叉樹之間的轉(zhuǎn)換方法(3)掌握森林和樹的遍歷教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：6 4 樹和森林6 4 1 樹的存儲(chǔ)結(jié)構(gòu)雙親表示法孩子表示法孩子兄弟表示法6 4 2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的對(duì)應(yīng)關(guān)系二叉樹與森林的對(duì)應(yīng)關(guān)系6 4 3 樹和森林的遍歷先序遍歷森林教中序遍歷森林學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后6.60,6.66作業(yè)教學(xué)后記編號(hào)19周次10日期11.5課時(shí)安排2課題赫夫曼樹及其應(yīng)用教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)赫夫

21、曼編碼難點(diǎn)：(1)赫夫曼編碼教 學(xué) 目 標(biāo)(1)掌握最優(yōu)化二叉樹的特性、熟練掌握建立最優(yōu)二叉樹的方法(2)熟練掌握哈夫曼編碼的方法教學(xué)方法和 教學(xué) 手段講授法教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：6 6 赫夫曼樹6 6 1 最優(yōu)二叉樹最優(yōu)二叉樹的概念構(gòu)造赫夫曼樹最優(yōu)判定算法6 6 2 赫夫曼編碼求赫夫曼編碼程課后師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：6.26作業(yè)教學(xué) 后記編號(hào)20周次10日期11.8課時(shí)安排2課題習(xí)題課教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)教學(xué)方法和 教學(xué) 手段講授法教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：程師生雙邊活動(dòng)： 提問(wèn)： 舉例： 演示實(shí)驗(yàn)： 教具準(zhǔn)備：課后

22、作業(yè)教學(xué) 后記編號(hào)21周次11日期11.12課時(shí)安排2課題圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)圖的存儲(chǔ)教 學(xué) 目 標(biāo)(1)熟悉圖的有關(guān)術(shù)語(yǔ)和概念(2)熟練掌握?qǐng)D的四種存儲(chǔ)結(jié)構(gòu)和建立算法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第七章圖7 1 圖的定義和術(shù)語(yǔ)圖的類型定義圖的分類連通圖、連通分量、生成樹7 2 圖的存儲(chǔ)結(jié)構(gòu)7 2 1 數(shù)組表示法圖的鄰接矩陣網(wǎng)及其鄰接矩陣7 2 2 鄰接表教圖的鄰接表存儲(chǔ)表示鄰接表和逆鄰接表學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后7.14,7.15作業(yè)教學(xué)后記編號(hào)22周次11日期11.15課時(shí)安排2課

23、題十字鏈表、鄰接多重表、圖的遍歷教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)圖的遍歷難點(diǎn)：(1)圖的遍歷非遞歸算法教 學(xué) 目 標(biāo)(1)熟練掌握?qǐng)D的四種存儲(chǔ)結(jié)構(gòu)和建立算法(2)熟練掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：7 2 3 十字鏈表有向圖的十字鏈表存儲(chǔ)表示構(gòu)造有向圖7 2 4 鄰接多重表無(wú)向圖的鄰接多重表7 3 圖的遍歷7 3 1 深度優(yōu)先搜索7 3 2 廣度優(yōu)先搜索教學(xué)學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后7.22,7.28作業(yè)教學(xué) 后記編號(hào)23周次12日期11.19課時(shí)安排2課題圖的連通性問(wèn)題教材 的重 點(diǎn)、 難點(diǎn)

24、分析重點(diǎn)：(1)最小生成樹的構(gòu)造教 學(xué) 目 標(biāo)掌握最小生成樹的兩種構(gòu)造方法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：7 4 圖的連通性問(wèn)題7 4 1 無(wú)向圖的連通分量和生成樹7 4 2 有向圖的強(qiáng)連通分量7 4 3 最小生成樹Prim 算法Kruskal 算法7 4 3 關(guān)節(jié)點(diǎn)和重連通分量教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后7.32作業(yè)教學(xué)后記編號(hào)24周次12日期11.22課時(shí)安排2課題有向無(wú)環(huán)圖及其應(yīng)用教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)拓?fù)渑判?2)求關(guān)鍵路徑難點(diǎn)：(1)求關(guān)鍵路徑教 學(xué) 目 標(biāo)(1)掌握拓?fù)渑判虻姆椒?2)掌握關(guān)鍵路徑的求法教學(xué)

25、方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：7 5 有向無(wú)環(huán)圖及其應(yīng)用DAG7 5 1 拓?fù)渑判? 5 2 關(guān)鍵路徑AOE 網(wǎng)關(guān)鍵路徑過(guò)程師生雙邊活動(dòng)： 提問(wèn)： 舉例： 演示實(shí)驗(yàn)： 教具準(zhǔn)備：課后7.36作業(yè)教學(xué) 后記編號(hào)25周次13日期11.26課時(shí)安排2課題最短路徑教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)求最短路徑難點(diǎn)：(1)求每一對(duì)頂點(diǎn)之間的最短路徑教 學(xué) 目 標(biāo)熟練掌握從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑的求法掌握求每一對(duì)頂點(diǎn)之間的最短路徑的求法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：7 6 最短路徑7 6 1 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑Dijkstr

26、a 算法7 6 2 每一對(duì)頂點(diǎn)之間的最短路徑教學(xué)學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后7.42作業(yè)教學(xué)后記編號(hào)26周次13日期11.29課時(shí)安排2課題靜態(tài)查找表教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)順序查找(2)折半查找教 學(xué) 目 標(biāo)(1)熟練掌握靜態(tài)查找的各種方法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第八章查找查找表與靜態(tài)查找表和動(dòng)態(tài)查找表關(guān)鍵字與主關(guān)鍵字和次關(guān)鍵字查找與成功和不成功8 1 靜態(tài)查找表靜態(tài)查找表的類型定義8 1 1 順序表的查找順序查找平均查找長(zhǎng)度教8 1 2 有序表的查找折半查找學(xué)折半查找的性能分析8 1 3 靜態(tài)樹表的查找過(guò)8 1

27、 4 索引順序表的查找表其索引表程分塊查找?guī)熒p邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后9.29作業(yè)教學(xué)后記編號(hào)27周次14日期12.3課時(shí)安排2課題二叉排序樹和平衡二叉樹教材重點(diǎn)：(1)動(dòng)態(tài)查找表及查找算法的重(2)二叉排序樹難點(diǎn)分析難點(diǎn)：(1)二叉排序樹(1)熟練掌握二叉排序樹的構(gòu)造方法及查找過(guò)程教 學(xué)(2)掌握AVL 樹的構(gòu)造目 標(biāo)教學(xué)方法和 教學(xué)手段教學(xué)內(nèi)容安排與板書設(shè)計(jì)：8 2 動(dòng)態(tài)查找表教動(dòng)態(tài)查找表的類型定義學(xué) 過(guò) 程8 2 1二叉排序樹和平衡二叉樹1、二叉排序樹及其查找過(guò)程二叉排序樹2、二叉排序樹的插入和刪除二叉排序樹的構(gòu)造二叉排序樹的刪除3、二叉排序樹的查找分析教4、平衡二

28、叉樹平衡二叉樹與不平衡的二叉樹學(xué)平衡樹的生成過(guò)程二叉排序樹的平衡旋轉(zhuǎn)過(guò)二叉排序樹的類型定義5、平衡樹查找的分析程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后9.33作業(yè)教學(xué)后記編號(hào)28周次14日期12.6課時(shí)安排2課題B-樹和B+樹教材 的重 點(diǎn)、 難點(diǎn) 分析教 學(xué) 目 標(biāo)(1)掌握B-樹和B+樹的構(gòu)造和查找(2)了解鍵樹的構(gòu)造方法教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：8 2 2 B-樹和B+樹1、 B-樹及其查找2、B-樹查找分析3、B-樹的插入和刪除4、 B+樹8 2 3 鍵樹教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號(hào)29周次15

29、日期12.10課時(shí)安排2課題哈希表教材 的重 點(diǎn)、 難點(diǎn) 分析難點(diǎn)：(1)哈希表及查找算法教 學(xué) 目 標(biāo)(1)熟練掌握哈希表的建表方法、沖突的處理及查找過(guò)程(2)理解哈希表與其它存儲(chǔ)結(jié)構(gòu)的表的本質(zhì)區(qū)別(3)熟練掌握哈希表的平均查找長(zhǎng)度的計(jì)算(等概率)教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：8 3 哈希表8 3 1 什么是哈希表哈希函數(shù)沖突散列教學(xué)過(guò)程8 3 2 哈希函數(shù)的構(gòu)造方法1、直接定址法2、數(shù)字分析法3、平方取中法4、折疊法5、除留余數(shù)法6、隨機(jī)數(shù)法8 3 3 處理沖突的方法1、開(kāi)放定址法2、再哈希法3、鏈地址法4、建立一個(gè)公共溢出區(qū)8 3 4 哈希表的查找及其分析師

30、生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后 作業(yè)9.46教學(xué) 后記編號(hào)30周次15日期12.13課時(shí)安排2課題排序概述、插入排序教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)希爾排序教 學(xué) 目 標(biāo)(1)深刻理解插入排序的基本思想及其特點(diǎn)(2)熟練掌握插入排序方法的排序過(guò)程(3)掌握插入排序算法時(shí)間復(fù)雜度的分析方法并熟記其分析結(jié)論教學(xué)方法和 教學(xué) 手段教 學(xué) 過(guò) 程教學(xué)內(nèi)容安排與板書設(shè)計(jì)：第九章排序9 1 排序概述排序排序方法的穩(wěn)定性內(nèi)部排序與外部排序9 2 插入排序9 2 1 直接插入排序9 2 2 其他插入排序1、折半插入排序教2、2-路插入排序3、表插入排序?qū)W9 2 3 希爾排序過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后10.25作業(yè)教學(xué)后記編號(hào)31周次16日期12.17課時(shí)安排2課題快速排序、選擇排序教材 的重 點(diǎn)、 難點(diǎn) 分析重點(diǎn)：(1)快速排序(2)堆排序難點(diǎn)：(1)快速排序(2)堆排序教 學(xué) 目 標(biāo)(1)深刻理解快速排序的基本思想及其特點(diǎn)(2)熟練掌握快速排序方法的排序過(guò)程(3)掌握快速排序算法時(shí)間復(fù)雜度的分析方法并熟記其分析結(jié)論(4)深刻理解選擇排序的基本思想及其特