《數(shù)據(jù)結構》教案

1、 安慶師范學院教案（課時計劃）課程名稱：數(shù)據(jù)結構授課班級：授課地點：主講教師：20152016學年第2學期01、數(shù)據(jù)結構的概念及相關術語02、抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法和算法分析03、線性表的類型定義、線性表的順序表示和實現(xiàn)04、線性表的鏈式表示和實現(xiàn)（線性鏈表）05、循環(huán)鏈表、雙向鏈表、一元多項式的表示及相加06、棧、棧應用舉例（數(shù)制轉換、括號匹配、行編輯）07、迷宮求解、表達式求值、棧與遞歸的實現(xiàn)08、隊列09、機動10、習題課11、串類型的定義、串的表示和實現(xiàn)12、串的模式匹配算法、串操作應用舉例13、數(shù)組的定義、順序表示和實現(xiàn)、矩陣的壓縮存儲14、稀疏矩陣的存儲結構、廣義表15、樹

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

3、)抽象數(shù)據(jù)類型的概念教學目標掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象的概念熟練掌握數(shù)據(jù)結構的概念及其邏輯結構和物理結構的分類掌握抽象數(shù)據(jù)類型的定義方法教學方法和教學手段講授法多媒體教學過程教學內容安排與板書設計：第一章緒論1.1什么是數(shù)據(jù)結構非數(shù)值計算問題舉例數(shù)據(jù)結構產(chǎn)生的背景數(shù)據(jù)結構在計算機科學中的地位和作用1.2基本概念和術語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)結構教數(shù)據(jù)結構的形式定義Data-Structure=(D,S)數(shù)據(jù)的邏輯結構及分類：集合、線性、樹形、圖形結構學數(shù)據(jù)的物理結構：順序存儲結構與鏈式存儲結構數(shù)據(jù)類型過抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的形式定義ADT=(D,S,P)程抽象數(shù)據(jù)類型定義舉例-Tripl

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

5、數(shù)據(jù)類型的表示和實現(xiàn)方法(4)掌握算法描述和算法分析的方法教學方法和教學手段教學過程教學內容安與排板書設計：1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)數(shù)據(jù)抽象的意義類C語言抽象數(shù)據(jù)類型的表示和實現(xiàn)舉例1.4算法和算法分析算法算法的定義算法的特性：有窮性、確定性、可行性、輸入、輸出算法設計的要求教正確性、可讀性、健壯性、效率與低存儲量需求算法效率的度量學時間度量的方法分析時間復雜度過T(n)=O(f(n)時間復雜度的計算程算法的存儲空間需求S(n)=O(f(n)師生雙邊活動：提問：舉例：演示實驗：教具準備：課后1.4,1.20作業(yè)教學后記編號3周次2日期9.10課時安排2課題線性表的類型定義、線性表的順序表

6、示和實現(xiàn)教材的重點、難點分析重點：(1)順序表的基本運算(2)順序表上實現(xiàn)的各種算法的時間性能分析教學目標(1)理解線性表的邏輯結構特征(2)熟練掌握順序表的描述方法、特點及有關概念(3)熟練掌握順序表的基本運算教學方法和教學手段教學過程教學內容安排與板書設計：第二章線性表線性結構的特點2.1線性表的類型定義線性表的定義及其表示線性表的類型定義線性表操作舉例：用線性表表示集合、線性表的合并2.2線性表的順序表示和實現(xiàn)線索性表的順序表示線性表的順序存儲結構的定義及其特征順序表的基本運算順序表的初始化教順序表的插入操作順序表的刪除操作學順序表的合并順序表基本操作的時間復雜度計算過程師生雙邊活動：提

7、問：舉例：演示實驗：教具準備：課后2.12作業(yè)教學后記編號4周次2日期9.13課時安排2課題線性表的鏈式表示和實現(xiàn)(線性鏈表)教材的重點、難點分析重點：(1)鏈表的基本運算(2)鏈表上實現(xiàn)的各種算法的時間性能分析教學目標(1)熟練掌握鏈表的描述方法、特點及有關概念(2)掌握鏈表的基本運算(3)掌握靜態(tài)鏈表的構造方法教學方法和教學手段教學過程教學內容安排與板書設計：2.3線性表的鏈式表示和實現(xiàn)2.3.1線性鏈表單鏈表的定義單鏈表的存儲結構特征單鏈表的基本操作：插入刪除有序鏈表的合并靜態(tài)鏈表靜態(tài)鏈表的定義靜態(tài)鏈表的操作舉例教學過程師生雙邊活動：提問：malloc()free()舉例：演示實驗：教具

8、準備：課后2.17,2.25作業(yè)教學后記編號5周次3日期9.17課時安排2課題循環(huán)鏈表、雙向鏈表、一元多項式的表示及相加教材的重點、難點分析難點：(1)循環(huán)鏈表教學目標(1)掌握循環(huán)鏈表的特點(2)掌握雙向鏈表的特點(3)從時空角度綜合比較順序表和鏈表的不同特點及使用場合(4)能應用線性表解決一些實際問題教學方法和教學手段教學過程教學內容安排與板書設計：2.3.2循環(huán)鏈表循環(huán)鏈表的定義循環(huán)鏈表的操作2.3.3雙向鏈表雙向鏈表的定義雙向鏈表的操作特點線性鏈表的類型定義2.4一元多項式的表示及相加教一元多項式的表示一元多項式的相加學一兀多項式的類型定義多項式的相加算法過程師生雙邊活動：提問：舉例：

9、演示實驗：教具準備：課后2.32作業(yè)教學后記編號6周次3日期9.20課時安排2課題棧、棧應用舉例(數(shù)制轉換、括號匹配、行編輯)教材的重點、難點分析重點：(1)棧在兩種存儲結構上實現(xiàn)的基本運算。難點：棧滿棧空的條件及它們的描述教學目標(1)掌握棧這種數(shù)據(jù)結構的特點(2)熟悉棧與線性表的關系(3)重點掌握順序棧和鏈式棧的五種基本運算(4)掌握棧的應用方法教學方法和教學手段教學過程教學內容安排與板書設計：第三章棧與隊列3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義棧及其與線性表的關系棧的類型定義3.1.2棧的表示和實現(xiàn)順序棧的定義鏈棧的定義3.2棧的應用舉例教3.2.1數(shù)制轉換3.2.2括號匹配的檢驗學3.

10、2.3行編輯程序過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后3.15作業(yè)教學后記編號7周次4日期9.24課時安排2課題迷宮求解、表達式求值、棧與遞歸的實現(xiàn)教材的重點、難點分析教學目標(1)能應用棧解決一些實際問題(2)了解遞歸算法執(zhí)行過程中棧的變化過程教學方法和教學手段教學過程教學內容安排與板書設計：3.2.4迷宮求解3.2.5表達式求值3.3棧與遞歸的實現(xiàn)教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業(yè)3.19,3.25教學后記編號8周次4日期9.27課時安排2課題隊列教材的重點、難點分析重點：(1)隊列在兩種存儲結構上實現(xiàn)的基本運算。難點：(1)循環(huán)隊列(注意隊滿隊

11、空的條件及它們的描述)教學目標(1)掌握隊列這種數(shù)據(jù)結構的特點(2)熟悉隊列與線性表的關系(3)掌握循環(huán)隊列和鏈式隊列的五種基本運算(4)能應用隊列解決一些實際問題教學方法和教學手段教學過程教學內容安排與板書設計：3.4隊列3.4.1抽象數(shù)據(jù)類型隊列的定義隊列的定義(FIFO)隊列的類型定義3.4.2鏈隊列一隊列的鏈式表示和實現(xiàn)單鏈隊列的定義單鏈隊列的操作3.4.3循環(huán)隊列一隊列的順序表示和實現(xiàn)隊列的順序存儲結構教循環(huán)隊列的基本操作學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后3.29作業(yè)教學后記編號9周次5日期10.1課時安排2課題機動教材的重點、難點分析教學目教學方法和教學手段教

12、學過程教學內容安排與板書設計：教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業(yè)教學后記編號10周次5日期10.4課時安排2課題習題課教材的重點、難點分析教學目教學方法和教學手段講授法教學過程教學內容安排與板書設計：教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業(yè)教學后記編號11周次6日期10.8課時安排2課題串類型的定義、串的表示和實現(xiàn)教材的重點、難點分析重點：(1)串的基本運算難點：(1)串的動態(tài)存儲結構教學目標(1)熟悉串的有關概念，串與線性表的關系(2)掌握串的靜態(tài)存儲結構與動態(tài)存儲結構和它們的優(yōu)缺點(3)熟練掌握串的基本運算教學方法和教學手段教學過程教學內容

13、安排與板書設計：第四章串4.1串類型的定義串的概念串類型的定義4.2串的表示和實現(xiàn)4.2.1定長順序存儲表示串的定長順序存儲表示串聯(lián)接求子串教4.2.2堆分配存儲表示串的堆分配存儲表示學堆的基本操作4.2.3串的塊鏈存儲表示過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后4.17,4.22/4.24作業(yè)教學后記編號12周次6日期10.11課時安排2課題串的模式匹配算法、串操作應用舉例教材的重點、難點分析教學目標(1)理解串的模式匹配算法(2)了解串的應用教學方法和教學手段教學過程教學內容安排與板書設計：4.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)4.3.2模式匹配的一種改進算法KMP算法4.4串操作應用舉例4.4.1文本編輯教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后4.8作業(yè)教學后記編號13周次7日期10.15課時安排2課題數(shù)組的定義