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

PAGE安慶師范學(xué)院教案（課時計劃）課程名稱：數(shù)據(jù)結(jié)構(gòu)授課班級：授課地點(diǎn)：主講教師：程玉勝20152016學(xué)年第2學(xué)期

目錄01、數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語02、抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法和算法分析03、線性表的類型定義、線性表的順序表示和實現(xiàn)04、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表）05、循環(huán)鏈表、雙向鏈表、一元多項式的表示及相加06、棧、棧應(yīng)用舉例（數(shù)制轉(zhuǎn)換、括號匹配、行編輯）07、迷宮求解、表達(dá)式求值、棧與遞歸的實現(xiàn)08、隊列09、機(jī)動10、習(xí)題課11、串類型的定義、串的表示和實現(xiàn)12、串的模式匹配算法、串操作應(yīng)用舉例13、數(shù)組的定義、順序表示和實現(xiàn)、矩陣的壓縮存儲14、稀疏矩陣的存儲結(jié)構(gòu)、廣義表15、樹的定義和基本術(shù)語、二叉樹的定義16、二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)17、遍歷二叉樹和線索二叉樹18、樹和森林19、赫夫曼樹及其應(yīng)用20、習(xí)題課21、圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)22、十字鏈表、鄰接多重表、圖的遍歷23、圖的連通性問題24、有向無環(huán)圖及其應(yīng)用25、最短路徑26、靜態(tài)查找表27、二叉排序樹和平衡二叉樹28、B-樹和B+樹29、哈希表30、排序概述、插入排序31、快速排序、選擇排序32、歸并排序、基數(shù)排序33、外部排序、各種排序方法的比較34、文件編號1周次1日期課時安排2課題數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)(3)抽象數(shù)據(jù)類型的概念教學(xué)目標(biāo)掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象的概念熟練掌握數(shù)據(jù)結(jié)構(gòu)的概念及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類掌握抽象數(shù)據(jù)類型的定義方法教學(xué)方法和教學(xué)手段講授法多媒體教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第一章 緒論1．1什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值計算問題舉例《數(shù)據(jù)結(jié)構(gòu)》產(chǎn)生的背景《數(shù)據(jù)結(jié)構(gòu)》在計算機(jī)科學(xué)中的地位和作用教學(xué)過程1．2基本概念和術(shù)語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義Data-Structure=(D,S)數(shù)據(jù)的邏輯結(jié)構(gòu)及分類：集合、線性、樹形、圖形結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)：順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的形式定義ADT=(D,S,P)抽象數(shù)據(jù)類型定義舉例—Triplet師生雙邊活動：提問：什么是數(shù)據(jù)類型舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記教材：[1]嚴(yán)蔚敏吳偉民編著：數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，1997年參考書目：[1]WirthN：Algorithms+DataStructures=Programs，Prentice-HallInc.，1976[2][美]S巴斯：計算機(jī)算法：設(shè)計和分析引論，復(fù)旦大學(xué)出版社，1985編號2周次1日期課時安排2課題抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法和算法分析教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)算法復(fù)雜度的分析方法難點(diǎn)：(1)算法復(fù)雜度的分析方法教學(xué)目標(biāo)(1)理解數(shù)據(jù)抽象的意義(2)熟悉類C語言(3)掌握抽象數(shù)據(jù)類型的表示和實現(xiàn)方法(4)掌握算法描述和算法分析的方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安與排板書設(shè)計：1．3抽象數(shù)據(jù)類型的表示和實現(xiàn)數(shù)據(jù)抽象的意義類C語言抽象數(shù)據(jù)類型的表示和實現(xiàn)舉例教學(xué)過程1．4算法和算法分析算法算法的定義算法的特性：有窮性、確定性、可行性、輸入、輸出算法設(shè)計的要求正確性、可讀性、健壯性、效率與低存儲量需求算法效率的度量時間度量的方法分析時間復(fù)雜度T(n)=O(f(n))時間復(fù)雜度的計算算法的存儲空間需求S(n)=O(f(n))師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號3周次2日期課時安排2課題線性表的類型定義、線性表的順序表示和實現(xiàn)教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)順序表的基本運(yùn)算(2)順序表上實現(xiàn)的各種算法的時間性能分析教學(xué)目標(biāo)(1)理解線性表的邏輯結(jié)構(gòu)特征(2)熟練掌握順序表的描述方法、特點(diǎn)及有關(guān)概念(3)熟練掌握順序表的基本運(yùn)算教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第二章 線性表線性結(jié)構(gòu)的特點(diǎn)2．1線性表的類型定義線性表的定義及其表示線性表的類型定義線性表操作舉例：用線性表表示集合、線性表的合并教學(xué)過程2．2線性表的順序表示和實現(xiàn)線索性表的順序表示線性表的順序存儲結(jié)構(gòu)的定義及其特征順序表的基本運(yùn)算順序表的初始化順序表的插入操作順序表的刪除操作順序表的合并順序表基本操作的時間復(fù)雜度計算師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號4周次2日期課時安排2課題線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表）教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)鏈表的基本運(yùn)算(2)鏈表上實現(xiàn)的各種算法的時間性能分析教學(xué)目標(biāo)(1)熟練掌握鏈表的描述方法、特點(diǎn)及有關(guān)概念(2)掌握鏈表的基本運(yùn)算(3)掌握靜態(tài)鏈表的構(gòu)造方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：2．3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2．3．1線性鏈表單鏈表的定義單鏈表的存儲結(jié)構(gòu)特征單鏈表的基本操作：插入教學(xué)過程刪除有序鏈表的合并靜態(tài)鏈表靜態(tài)鏈表的定義靜態(tài)鏈表的操作舉例師生雙邊活動：提問：malloc()free()舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號5周次3日期課時安排2課題循環(huán)鏈表、雙向鏈表、一元多項式的表示及相加教材的重點(diǎn)、難點(diǎn)分析難點(diǎn)：(1)循環(huán)鏈表教學(xué)目標(biāo)(1)掌握循環(huán)鏈表的特點(diǎn)(2)掌握雙向鏈表的特點(diǎn)(3)從時空角度綜合比較順序表和鏈表的不同特點(diǎn)及使用場合(4)能應(yīng)用線性表解決一些實際問題教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：2．3．2循環(huán)鏈表循環(huán)鏈表的定義循環(huán)鏈表的操作教學(xué)過程2．3．3雙向鏈表雙向鏈表的定義雙向鏈表的操作特點(diǎn)線性鏈表的類型定義2．4一元多項式的表示及相加一元多項式的表示一元多項式的相加一元多項式的類型定義多項式的相加算法師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號6周次3日期課時安排2課題棧、棧應(yīng)用舉例（數(shù)制轉(zhuǎn)換、括號匹配、行編輯）教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)棧在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運(yùn)算。難點(diǎn)：棧滿?？盏臈l件及它們的描述教學(xué)目標(biāo)(1)掌握棧這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)(2)熟悉棧與線性表的關(guān)系(3)重點(diǎn)掌握順序棧和鏈?zhǔn)綏５奈宸N基本運(yùn)算(4)掌握棧的應(yīng)用方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第三章 棧與隊列3．1棧3．1．1抽象數(shù)據(jù)類型棧的定義棧及其與線性表的關(guān)系棧的類型定義教學(xué)過程3．1．2棧的表示和實現(xiàn)順序棧的定義鏈棧的定義3．2棧的應(yīng)用舉例3．2．1數(shù)制轉(zhuǎn)換3．2．2括號匹配的檢驗3．2．3行編輯程序師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號7周次4日期課時安排2課題迷宮求解、表達(dá)式求值、棧與遞歸的實現(xiàn)教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)(1)能應(yīng)用棧解決一些實際問題(2)了解遞歸算法執(zhí)行過程中棧的變化過程教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：3．2．4迷宮求解3．2．5表達(dá)式求值3．3棧與遞歸的實現(xiàn)教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號8周次4日期課時安排2課題隊列教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運(yùn)算。難點(diǎn)：(1)循環(huán)隊列（注意隊滿隊空的條件及它們的描述）教學(xué)目標(biāo)(1)掌握隊列這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)(2)熟悉隊列與線性表的關(guān)系(3)掌握循環(huán)隊列和鏈?zhǔn)疥犃械奈宸N基本運(yùn)算(4)能應(yīng)用隊列解決一些實際問題教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：3．4隊列3．4．1抽象數(shù)據(jù)類型隊列的定義隊列的定義(FIFO)隊列的類型定義教學(xué)過程3．4．2鏈隊列—隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)單鏈隊列的定義單鏈隊列的操作3．4．3循環(huán)隊列—隊列的順序表示和實現(xiàn)隊列的順序存儲結(jié)構(gòu)循環(huán)隊列的基本操作師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號9周次5日期課時安排2課題機(jī)動教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號10周次5日期課時安排2課題習(xí)題課教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)教學(xué)方法和教學(xué)手段講授法教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號11周次6日期課時安排2課題串類型的定義、串的表示和實現(xiàn)教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)串的基本運(yùn)算難點(diǎn)：(1)串的動態(tài)存儲結(jié)構(gòu)教學(xué)目標(biāo)(1)熟悉串的有關(guān)概念，串與線性表的關(guān)系(2)掌握串的靜態(tài)存儲結(jié)構(gòu)與動態(tài)存儲結(jié)構(gòu)和它們的優(yōu)缺點(diǎn)(3)熟練掌握串的基本運(yùn)算教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第四章 串4．1串類型的定義串的概念串類型的定義教學(xué)過程4．2串的表示和實現(xiàn)4．2．1定長順序存儲表示串的定長順序存儲表示串聯(lián)接求子串4．2．2堆分配存儲表示串的堆分配存儲表示堆的基本操作4．2．3串的塊鏈存儲表示師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號12周次6日期課時安排2課題串的模式匹配算法、串操作應(yīng)用舉例教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)(1)理解串的模式匹配算法(2)了解串的應(yīng)用教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：4．3串的模式匹配算法4．3．1求子串位置的定位函數(shù)4．3．2模式匹配的一種改進(jìn)算法KMP算法教學(xué)過程4．4串操作應(yīng)用舉例4．4．1文本編輯師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號13周次7日期課時安排2課題數(shù)組的定義、順序表示和實現(xiàn)、矩陣的壓縮存儲教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)多維數(shù)組的存儲方式(2)矩陣的壓縮存儲方式難點(diǎn)：(1)稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法教學(xué)目標(biāo)(1)熟悉數(shù)組的按行（列）優(yōu)先順序的存儲結(jié)構(gòu)中的地址計算方法(2)熟悉特殊矩陣在壓縮存儲時的下標(biāo)變換(3)理解稀疏矩陣的三元組和十字鏈表兩種壓縮存儲表示教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第五章 數(shù)組和廣義表5．1數(shù)組的定義數(shù)組的類型定義二維數(shù)組教學(xué)過程5．2數(shù)組的順序表示和實現(xiàn)二維數(shù)組的存儲方式數(shù)組的順序存儲表示和實現(xiàn)5．3矩陣的壓縮存儲5．3．1特殊矩陣對稱矩陣對角矩陣5．3．2稀疏矩陣稀疏矩陣的類型定義1、三元組順序表師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號14周次7日期課時安排2課題稀疏矩陣的存儲結(jié)構(gòu)、廣義表的定義和存儲結(jié)構(gòu)教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)廣義表的定義及其運(yùn)算教學(xué)目標(biāo)(1)掌握稀疏矩陣的存儲結(jié)構(gòu)(2)熟悉廣義表的有關(guān)概念和運(yùn)算(3)掌握廣義表的兩種存儲結(jié)構(gòu)教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：2、行邏輯鏈接的順序表3、十字鏈表5．4廣義表的定義教學(xué)過程廣義表的類型定義廣義表舉例廣義表的特點(diǎn)5．5廣義表的存儲結(jié)構(gòu)討論：M元多項式的表示廣義表的遞歸算法師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號15周次8日期課時安排2課題樹的定義和基本術(shù)語、二叉樹的定義教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)樹的基本術(shù)語(2)二叉樹的定義教學(xué)目標(biāo)(1)掌握樹的定義和有關(guān)術(shù)語(2)熟悉二叉樹的遞歸定義，有關(guān)術(shù)語及基本概念教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第六章 樹和二叉樹6．1樹的定義和基本術(shù)語樹的類型定義基本術(shù)語教學(xué)過程6．2二叉樹6．2．1二叉樹的定義二叉樹的類型定義二叉樹的基本形態(tài)師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號16周次8日期課時安排2課題二叉樹的性質(zhì)和和存儲結(jié)構(gòu)教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)二叉樹的存儲結(jié)構(gòu)難點(diǎn)：(1)二叉樹的性質(zhì)教學(xué)目標(biāo)(1)熟練掌握二叉樹的性質(zhì)及證明方法(2)熟練掌握二叉樹的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)及特點(diǎn)教學(xué)方法和教學(xué)手段講授法教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：6．2．2二叉樹的性質(zhì)性質(zhì)1性質(zhì)2性質(zhì)3性質(zhì)4性質(zhì)5教學(xué)過程6．2．3二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號17周次9日期課時安排2課題遍歷二叉樹和線索二叉樹教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)二叉樹的遍歷算法及其相關(guān)應(yīng)用難點(diǎn)：(1)二叉樹的非遞歸遍歷算法教學(xué)目標(biāo)(1)熟練掌握二叉樹的各種遍歷(2)能靈活運(yùn)用遍歷算法實現(xiàn)二叉樹的基本運(yùn)算(3)掌握二叉樹的線索化及相應(yīng)算法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：6．3遍歷二叉樹和線索二叉樹6．3．1遍歷二叉樹遍歷二叉樹的遞歸算法先序遍歷中序遍歷后序遍歷教學(xué)過程遍歷二叉樹的非遞歸算法遍歷二叉樹的其他算法二叉樹的其他操作6．3．2線索二叉樹線索二叉樹及其存儲結(jié)構(gòu)二叉樹的線索化師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),,教學(xué)后記編號18周次9日期課時安排2課題樹和森林教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)樹的存儲結(jié)構(gòu)難點(diǎn)：(1)森林、樹與二叉樹之間的轉(zhuǎn)換教學(xué)目標(biāo)(1)掌握樹的存儲結(jié)構(gòu)及其特點(diǎn)(2)熟練掌握森林、樹與二叉樹之間的轉(zhuǎn)換方法(3)掌握森林和樹的遍歷教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：6．4樹和森林6．4．1樹的存儲結(jié)構(gòu)雙親表示法孩子表示法孩子兄弟表示法教學(xué)過程6．4．2森林與二叉樹的轉(zhuǎn)換森林與二叉樹的對應(yīng)關(guān)系二叉樹與森林的對應(yīng)關(guān)系6．4．3樹和森林的遍歷先序遍歷森林中序遍歷森林師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號19周次10日期課時安排2課題赫夫曼樹及其應(yīng)用教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)赫夫曼編碼難點(diǎn)：(1)赫夫曼編碼教學(xué)目標(biāo)(1)掌握最優(yōu)化二叉樹的特性、熟練掌握建立最優(yōu)二叉樹的方法(2)熟練掌握哈夫曼編碼的方法教學(xué)方法和教學(xué)手段講授法教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：6．6赫夫曼樹6．6．1最優(yōu)二叉樹最優(yōu)二叉樹的概念構(gòu)造赫夫曼樹最優(yōu)判定算法6．6．2赫夫曼編碼教學(xué)過程求赫夫曼編碼師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號20周次10日期課時安排2課題習(xí)題課教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)教學(xué)方法和教學(xué)手段講授法教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號21周次11日期課時安排2課題圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)圖的存儲教學(xué)目標(biāo)(1)熟悉圖的有關(guān)術(shù)語和概念(2)熟練掌握圖的四種存儲結(jié)構(gòu)和建立算法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第七章 圖7．1圖的定義和術(shù)語圖的類型定義圖的分類連通圖、連通分量、生成樹教學(xué)過程7．2圖的存儲結(jié)構(gòu)7．2．1數(shù)組表示法圖的鄰接矩陣網(wǎng)及其鄰接矩陣7．2．2鄰接表圖的鄰接表存儲表示鄰接表和逆鄰接表師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號22周次11日期課時安排2課題十字鏈表、鄰接多重表、圖的遍歷教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)圖的遍歷難點(diǎn)：(1)圖的遍歷非遞歸算法教學(xué)目標(biāo)(1)熟練掌握圖的四種存儲結(jié)構(gòu)和建立算法(2)熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：7．2．3十字鏈表有向圖的十字鏈表存儲表示構(gòu)造有向圖7．2．4鄰接多重表無向圖的鄰接多重表教學(xué)過程7．3圖的遍歷7．3．1深度優(yōu)先搜索7．3．2廣度優(yōu)先搜索師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè),教學(xué)后記編號23周次12日期課時安排2課題圖的連通性問題教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)最小生成樹的構(gòu)造教學(xué)目標(biāo)掌握最小生成樹的兩種構(gòu)造方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：7．4圖的連通性問題7．4．1無向圖的連通分量和生成樹7．4．2有向圖的強(qiáng)連通分量教學(xué)過程7．4．3最小生成樹Prim算法Kruskal算法7．4．3關(guān)節(jié)點(diǎn)和重連通分量師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號24周次12日期課時安排2課題有向無環(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é)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：7．5有向無環(huán)圖及其應(yīng)用DAG7．5．1拓?fù)渑判?．5．2關(guān)鍵路徑AOE網(wǎng)關(guān)鍵路徑教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號25周次13日期課時安排2課題最短路徑教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)求最短路徑難點(diǎn)：(1)求每一對頂點(diǎn)之間的最短路徑教學(xué)目標(biāo)熟練掌握從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑的求法掌握求每一對頂點(diǎn)之間的最短路徑的求法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：7．6最短路徑7．6．1從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑Dijkstra算法7．6．2每一對頂點(diǎn)之間的最短路徑教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號26周次13日期課時安排2課題靜態(tài)查找表教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)順序查找(2)折半查找教學(xué)目標(biāo)(1)熟練掌握靜態(tài)查找的各種方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第八章 查找查找表與靜態(tài)查找表和動態(tài)查找表關(guān)鍵字與主關(guān)鍵字和次關(guān)鍵字查找與成功和不成功教學(xué)過程8．1靜態(tài)查找表靜態(tài)查找表的類型定義8．1．1順序表的查找順序查找平均查找長度8．1．2有序表的查找折半查找折半查找的性能分析8．1．3靜態(tài)樹表的查找8．1．4索引順序表的查找表其索引表分塊查找?guī)熒p邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號27周次14日期課時安排2課題二叉排序樹和平衡二叉樹教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)動態(tài)查找表及查找算法(2)二叉排序樹難點(diǎn)：(1)二叉排序樹教學(xué)目標(biāo)(1)熟練掌握二叉排序樹的構(gòu)造方法及查找過程(2)掌握AVL樹的構(gòu)造教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：8．2動態(tài)查找表動態(tài)查找表的類型定義8．2．1二叉排序樹和平衡二叉樹1、二叉排序樹及其查找過程二叉排序樹教學(xué)過程2、二叉排序樹的插入和刪除二叉排序樹的構(gòu)造二叉排序樹的刪除3、二叉排序樹的查找分析4、平衡二叉樹平衡二叉樹與不平衡的二叉樹平衡樹的生成過程二叉排序樹的平衡旋轉(zhuǎn)二叉排序樹的類型定義5、平衡樹查找的分析師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號28周次14日期課時安排2課題B-樹和B+樹教材的重點(diǎn)、難點(diǎn)分析教學(xué)目標(biāo)(1)掌握B-樹和B+樹的構(gòu)造和查找(2)了解鍵樹的構(gòu)造方法教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：8．2．2B-樹和B+樹1、B-樹及其查找2、B-樹查找分析教學(xué)過程3、B-樹的插入和刪除4、B+樹8．2．3鍵樹師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號29周次15日期課時安排2課題哈希表教材的重點(diǎn)、難點(diǎn)分析難點(diǎn)：(1)哈希表及查找算法教學(xué)目標(biāo)(1)熟練掌握哈希表的建表方法、沖突的處理及查找過程(2)理解哈希表與其它存儲結(jié)構(gòu)的表的本質(zhì)區(qū)別(3)熟練掌握哈希表的平均查找長度的計算（等概率）教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：8．3哈希表8．3．1什么是哈希表哈希函數(shù)沖突散列教學(xué)過程8．3．2哈希函數(shù)的構(gòu)造方法1、直接定址法2、數(shù)字分析法3、平方取中法4、折疊法5、除留余數(shù)法6、隨機(jī)數(shù)法8．3．3處理沖突的方法1、開放定址法2、再哈希法3、鏈地址法4、建立一個公共溢出區(qū)8．3．4哈希表的查找及其分析師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號30周次15日期課時安排2課題排序概述、插入排序教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)希爾排序教學(xué)目標(biāo)(1)深刻理解插入排序的基本思想及其特點(diǎn)(2)熟練掌握插入排序方法的排序過程(3)掌握插入排序算法時間復(fù)雜度的分析方法并熟記其分析結(jié)論教學(xué)方法和教學(xué)手段教學(xué)過程教學(xué)內(nèi)容安排與板書設(shè)計：第九章 排序9．1排序概述排序排序方法的穩(wěn)定性內(nèi)部排序與外部排序教學(xué)過程9．2插入排序9．2．1直接插入排序9．2．2其他插入排序1、折半插入排序2、2-路插入排序3、表插入排序9．2．3希爾排序師生雙邊活動：提問：舉例：演示實驗：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號31周次16日期課時安排2課題快速排序、選擇排序教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)快速排序(2)堆排序難點(diǎn)：(1)快速排序(2)堆排序教學(xué)目標(biāo)(1)深刻理解快速排序的基本思想及其特點(diǎn)(2)熟練掌握快速排序方法的排序過程(3)掌握快速排序算法時間復(fù)雜度的分析方法并熟記其分