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

1、 安慶師范學(xué)院教案（課時(shí)計(jì)劃）課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)授課班級(jí)：授課地點(diǎn)：主講教師：20152016學(xué)年第2學(xué)期01、數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語(yǔ)02、抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)、算法和算法分析03、線性表的類(lèi)型定義、線性表的順序表示和實(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、串類(lèi)型的定義、串的表示和實(shí)現(xiàn)12、串的模式匹配算法、串操作應(yīng)用舉例13、數(shù)組的定義、順序表示和實(shí)現(xiàn)、矩陣的壓縮存儲(chǔ)14、稀疏矩陣的存儲(chǔ)結(jié)構(gòu)、廣義表15、樹(shù)

2、的定義和基本術(shù)語(yǔ)、二叉樹(shù)的定義16、二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)17、遍歷二叉樹(shù)和線索二叉樹(shù)18、樹(shù)和森林19、赫夫曼樹(shù)及其應(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、二叉排序樹(shù)和平衡二叉樹(shù)28、B-樹(shù)和B+樹(shù)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)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)(3

3、)抽象數(shù)據(jù)類(lèi)型的概念教學(xué)目標(biāo)掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象的概念熟練掌握數(shù)據(jù)結(jié)構(gòu)的概念及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類(lèi)掌握抽象數(shù)據(jù)類(lèi)型的定義方法教學(xué)方法和教學(xué)手段講授法多媒體教學(xué)過(guò)程教學(xué)內(nèi)容安排與板書(shū)設(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)及分類(lèi)：集合、線性、樹(shù)形、圖形結(jié)構(gòu)學(xué)數(shù)據(jù)的物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)類(lèi)型過(guò)抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型的形式定義ADT=(D,S,P)程抽象數(shù)據(jù)類(lèi)型定義舉例-Tripl

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

5、數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)方法(4)掌握算法描述和算法分析的方法教學(xué)方法和教學(xué)手段教學(xué)過(guò)程教學(xué)內(nèi)容安與排板書(shū)設(shè)計(jì)：1.3抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)數(shù)據(jù)抽象的意義類(lèi)C語(yǔ)言抽象數(shù)據(jù)類(lèi)型的表示和實(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)師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后1.4,1.20作業(yè)教學(xué)后記編號(hào)3周次2日期9.10課時(shí)安排2課題線性表的類(lèi)型定義、線性表的順序表

6、示和實(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ū)設(shè)計(jì)：第二章線性表線性結(jié)構(gòu)的特點(diǎn)2.1線性表的類(lèi)型定義線性表的定義及其表示線性表的類(lèi)型定義線性表操作舉例：用線性表表示集合、線性表的合并2.2線性表的順序表示和實(shí)現(xiàn)線索性表的順序表示線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及其特征順序表的基本運(yùn)算順序表的初始化教順序表的插入操作順序表的刪除操作學(xué)順序表的合并順序表基本操作的時(shí)間復(fù)雜度計(jì)算過(guò)程師生雙邊活動(dòng)：提

7、問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后2.12作業(yè)教學(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ū)設(shè)計(jì)：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性鏈表單鏈表的定義單鏈表的存儲(chǔ)結(jié)構(gòu)特征單鏈表的基本操作：插入刪除有序鏈表的合并靜態(tài)鏈表靜態(tài)鏈表的定義靜態(tài)鏈表的操作舉例教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：malloc()free()舉例：演示實(shí)驗(yàn)：教具

8、準(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ū)設(shè)計(jì)：2.3.2循環(huán)鏈表循環(huán)鏈表的定義循環(huán)鏈表的操作2.3.3雙向鏈表雙向鏈表的定義雙向鏈表的操作特點(diǎn)線性鏈表的類(lèi)型定義2.4一元多項(xiàng)式的表示及相加教一元多項(xiàng)式的表示一元多項(xiàng)式的相加學(xué)一兀多項(xiàng)式的類(lèi)型定義多項(xiàng)式的相加算法過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：

9、演示實(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)、難點(diǎn)分析重點(diǎn)：(1)棧在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。難點(diǎn)：棧滿(mǎn)棧空的條件及它們的描述教學(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é)過(guò)程教學(xué)內(nèi)容安排與板書(shū)設(shè)計(jì)：第三章棧與隊(duì)列3.1棧3.1.1抽象數(shù)據(jù)類(lèi)型棧的定義棧及其與線性表的關(guān)系棧的類(lèi)型定義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.

10、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ū)設(shè)計(jì)：3.2.4迷宮求解3.2.5表達(dá)式求值3.3棧與遞歸的實(shí)現(xiàn)教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后作業(yè)3.19,3.25教學(xué)后記編號(hào)8周次4日期9.27課時(shí)安排2課題隊(duì)列教材的重點(diǎn)、難點(diǎn)分析重點(diǎn)：(1)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。難點(diǎn)：(1)循環(huán)隊(duì)列(注意隊(duì)滿(mǎn)隊(duì)

11、空的條件及它們的描述)教學(xué)目標(biāo)(1)掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)(2)熟悉隊(duì)列與線性表的關(guān)系(3)掌握循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的五種基本運(yùn)算(4)能應(yīng)用隊(duì)列解決一些實(shí)際問(wèn)題教學(xué)方法和教學(xué)手段教學(xué)過(guò)程教學(xué)內(nèi)容安排與板書(shū)設(shè)計(jì)：3.4隊(duì)列3.4.1抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義隊(duì)列的定義(FIFO)隊(duì)列的類(lèi)型定義3.4.2鏈隊(duì)列一隊(duì)列的鏈?zhǔn)奖硎竞蛯?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é)目教學(xué)方法和教學(xué)手段教

12、學(xué)過(guò)程教學(xué)內(nèi)容安排與板書(shū)設(shè)計(jì)：教學(xué)過(guò)程師生雙邊活動(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é)目教學(xué)方法和教學(xué)手段講授法教學(xué)過(guò)程教學(xué)內(nèi)容安排與板書(shū)設(shè)計(jì)：教學(xué)過(guò)程師生雙邊活動(dòng)：提問(wèn)：舉例：演示實(shí)驗(yàn)：教具準(zhǔn)備：課后作業(yè)教學(xué)后記編號(hào)11周次6日期10.8課時(shí)安排2課題串類(lèi)型的定義、串的表示和實(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)容

13、安排與板書(shū)設(shè)計(jì)：第四章串4.1串類(lèi)型的定義串的概念串類(lèi)型的定義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ǔ)表示過(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ū)設(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ù)組的定義