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

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

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

4、, S, P) 抽象數據類型定義舉例Triplet師生雙邊活動：提問：什么是數據類型？舉例：演示實驗：教具準備：課后作業1.2,1.19教學后記教材：1嚴蔚敏 吳偉民編著：數據結構（C語言版），清華大學出版社，1997年參考書目：1Wirth N：Algorithms+Data Structures=Programs，Prentice-Hall Inc.，19762美S 巴斯：計算機算法：設計和分析引論，復旦大學出版社，1985編號2周次1日期9.6課時安排2課題抽象數據類型的表示與實現、算法和算法分析教材的重點 、難點分析重點：(1)算法復雜度的分析方法難點：(1)算法復雜度的分析方法教學目

5、標(1)理解數據抽象的意義(2)熟悉類C語言(3)掌握抽象數據類型的表示和實現方法(4)掌握算法描述和算法分析的方法教學方法和 教學手段教學過程教學內容安與排板書設計：13 抽象數據類型的表示和實現數據抽象的意義類C語言抽象數據類型的表示和實現舉例教學過程14 算法和算法分析算法 算法的定義算法的特性：有窮性、確定性、可行性、輸入、輸出算法設計的要求 正確性、可讀性、健壯性、效率與低存儲量需求算法效率的度量 時間度量的方法分析 時間復雜度 T(n) = O(f(n) 時間復雜度的計算算法的存儲空間需求 S(n) = O(f(n)師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業1.4,1.

6、20教學后記編號3周次2日期9.10課時安排2課題線性表的類型定義、線性表的順序表示和實現教材的重點 、難點分析重點：(1)順序表的基本運算(2)順序表上實現的各種算法的時間性能分析教學目標(1)理解線性表的邏輯結構特征(2)熟練掌握順序表的描述方法、特點及有關概念(3)熟練掌握順序表的基本運算教學方法和 教學手段教學過程教學內容安排與板書設計：第二章線性表線性結構的特點21 線性表的類型定義線性表的定義及其表示線性表的類型定義線性表操作舉例：用線性表表示集合、線性表的合并教學過程22 線性表的順序表示和實現線索性表的順序表示線性表的順序存儲結構的定義及其特征順序表的基本運算 順序表的初始化

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

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

9、的表示及相加一元多項式的表示一元多項式的相加一元多項式的類型定義多項式的相加算法師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業2.32教學后記編號6周次3日期9.20課時安排2課題棧、棧應用舉例（數制轉換、括號匹配、行編輯）教材的重點 、難點分析重點：(1)棧在兩種存儲結構上實現的基本運算。難點：棧滿棧空的條件及它們的描述教學目標(1)掌握棧這種數據結構的特點(2)熟悉棧與線性表的關系(3)重點掌握順序棧和鏈式棧的五種基本運算(4)掌握棧的應用方法教學方法和 教學手段教學過程教學內容安排與板書設計：第三章棧與隊列31 棧311 抽象數據類型棧的定義棧及其與線性表的關系棧的類型定義教學過

10、程312 棧的表示和實現順序棧的定義鏈棧的定義32 棧的應用舉例321 數制轉換322 括號匹配的檢驗323 行編輯程序師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業3.15教學后記編號7周次4日期9.24課時安排2課題迷宮求解、表達式求值、棧與遞歸的實現教材的重點 、難點分析教學目標(1)能應用棧解決一些實際問題(2)了解遞歸算法執行過程中棧的變化過程教學方法和 教學手段教學過程教學內容安排與板書設計：324 迷宮求解325 表達式求值33 棧與遞歸的實現教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業3.19,3.25教學后記編號8周次4日期9.27課時安排2課題隊列

11、教材的重點 、難點分析重點：(1)隊列在兩種存儲結構上實現的基本運算。難點：(1)循環隊列（注意隊滿隊空的條件及它們的描述）教學目標(1) 掌握隊列這種數據結構的特點(2)熟悉隊列與線性表的關系(3)掌握循環隊列和鏈式隊列的五種基本運算(4)能應用隊列解決一些實際問題教學方法和 教學手段教學過程教學內容安排與板書設計：34 隊列341 抽象數據類型隊列的定義隊列的定義(FIFO)隊列的類型定義教學過程342 鏈隊列隊列的鏈式表示和實現單鏈隊列的定義單鏈隊列的操作343 循環隊列隊列的順序表示和實現隊列的順序存儲結構循環隊列的基本操作師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業3.29

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

13、)掌握串的靜態存儲結構與動態存儲結構和它們的優缺點(3)熟練掌握串的基本運算教學方法和 教學手段教學過程教學內容安排與板書設計：第四章串41 串類型的定義串的概念串類型的定義教學過程42 串的表示和實現421 定長順序存儲表示串的定長順序存儲表示串聯接求子串422 堆分配存儲表示串的堆分配存儲表示堆的基本操作423 串的塊鏈存儲表示師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業4.17,4.22/4.24教學后記編號12周次6日期10.11課時安排2課題串的模式匹配算法、串操作應用舉例教材的重點 、難點分析教學目標(1)理解串的模式匹配算法(2)了解串的應用教學方法和 教學手段教學過程

14、教學內容安排與板書設計：43 串的模式匹配算法431 求子串位置的定位函數432 模式匹配的一種改進算法KMP算法教學過程44 串操作應用舉例441 文本編輯師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業4.8教學后記編號13周次7日期10.15課時安排2課題數組的定義、順序表示和實現、矩陣的壓縮存儲教材的重點 、難點分析重點：(1)多維數組的存儲方式(2)矩陣的壓縮存儲方式難點：(1)稀疏矩陣的壓縮存儲表示下實現的算法教學目標(1)熟悉數組的按行（列）優先順序的存儲結構中的地址計算方法(2)熟悉特殊矩陣在壓縮存儲時的下標變換(3)理解稀疏矩陣的三元組和十字鏈表兩種壓縮存儲表示教學方法

15、和 教學手段教學過程教學內容安排與板書設計：第五章數組和廣義表51 數組的定義數組的類型定義二維數組教學過程52 數組的順序表示和實現二維數組的存儲方式數組的順序存儲表示和實現53 矩陣的壓縮存儲531 特殊矩陣對稱矩陣對角矩陣532 稀疏矩陣稀疏矩陣的類型定義1、三元組順序表師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業5.21教學后記編號14周次7日期10.18課時安排2課題稀疏矩陣的存儲結構、廣義表的定義和存儲結構教材的重點 、難點分析重點：(1)廣義表的定義及其運算教學目標(1)掌握稀疏矩陣的存儲結構(2)熟悉廣義表的有關概念和運算(3)掌握廣義表的兩種存儲結構教學方法和 教學

16、手段教學過程教學內容安排與板書設計：2、行邏輯鏈接的順序表3、十字鏈表54 廣義表的定義教學過程廣義表的類型定義廣義表舉例廣義表的特點55 廣義表的存儲結構討論：M元多項式的表示廣義表的遞歸算法師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業5.26,5.12教學后記編號15周次8日期10.22課時安排2課題樹的定義和基本術語、二叉樹的定義教材的重點 、難點分析重點：(1)樹的基本術語 (2)二叉樹的定義教學目標(1)掌握樹的定義和有關術語 (2)熟悉二叉樹的遞歸定義，有關術語及基本概念教學方法和 教學手段教學過程教學內容安排與板書設計：第六章樹和二叉樹61 樹的定義和基本術語樹的類型定

17、義基本術語教學過程62 二叉樹621 二叉樹的定義二叉樹的類型定義二叉樹的基本形態師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業6.2教學后記編號16周次8日期10.25課時安排2課題二叉樹的性質和和存儲結構教材的重點 、難點分析重點：(1)二叉樹的存儲結構難點：(1)二叉樹的性質教學目標(1)熟練掌握二叉樹的性質及證明方法(2)熟練掌握二叉樹的順序和鏈式存儲結構及特點教學方法和 教學手段講授法教學過程教學內容安排與板書設計：622 二叉樹的性質性質1性質2性質3性質4性質5教學過程623 二叉樹的存儲結構順序存儲結構鏈式存儲結構師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業6

18、.6,6.11教學后記編號17周次9日期10.29課時安排2課題遍歷二叉樹和線索二叉樹教材的重點 、難點分析重點：(1)二叉樹的遍歷算法及其相關應用難點：(1)二叉樹的非遞歸遍歷算法教學目標(1)熟練掌握二叉樹的各種遍歷(2)能靈活運用遍歷算法實現二叉樹的基本運算(3)掌握二叉樹的線索化及相應算法教學方法和 教學手段教學過程教學內容安排與板書設計：63 遍歷二叉樹和線索二叉樹631 遍歷二叉樹遍歷二叉樹的遞歸算法先序遍歷中序遍歷后序遍歷教學過程遍歷二叉樹的非遞歸算法遍歷二叉樹的其他算法二叉樹的其他操作632 線索二叉樹線索二叉樹及其存儲結構二叉樹的線索化師生雙邊活動：提問：舉例：演示實驗：教具

19、準備：課后作業6.43,6.47,6.56教學后記編號18周次9日期11.1課時安排2課題樹和森林教材的重點 、難點分析重點：(1)樹的存儲結構難點：(1) 森林、樹與二叉樹之間的轉換教學目標(1)掌握樹的存儲結構及其特點(2)熟練掌握森林、樹與二叉樹之間的轉換方法(3)掌握森林和樹的遍歷教學方法和 教學手段教學過程教學內容安排與板書設計：64 樹和森林641 樹的存儲結構雙親表示法孩子表示法孩子兄弟表示法教學過程642 森林與二叉樹的轉換森林與二叉樹的對應關系二叉樹與森林的對應關系643 樹和森林的遍歷先序遍歷森林中序遍歷森林師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業6.60,6

20、.66教學后記編號19周次10日期11.5課時安排2課題赫夫曼樹及其應用教材的重點 、難點分析重點：(1)赫夫曼編碼難點：(1)赫夫曼編碼教學目標(1)掌握最優化二叉樹的特性、熟練掌握建立最優二叉樹的方法(2)熟練掌握哈夫曼編碼的方法教學方法和 教學手段講授法教學過程教學內容安排與板書設計：66 赫夫曼樹661 最優二叉樹最優二叉樹的概念構造赫夫曼樹最優判定算法662 赫夫曼編碼教學過程求赫夫曼編碼師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業6.26教學后記編號20周次10日期11.8課時安排2課題習題課教材的重點 、難點分析教學目標教學方法和 教學手段講授法教學過程教學內容安排與板

21、書設計：教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業教學后記編號21周次11日期11.12課時安排2課題圖的定義和術語、圖的存儲結構教材的重點 、難點分析重點：(1)圖的存儲教學目標(1)熟悉圖的有關術語和概念(2)熟練掌握圖的四種存儲結構和建立算法教學方法和 教學手段教學過程教學內容安排與板書設計：第七章圖71 圖的定義和術語圖的類型定義圖的分類連通圖、連通分量、生成樹教學過程72 圖的存儲結構721 數組表示法圖的鄰接矩陣網及其鄰接矩陣722 鄰接表圖的鄰接表存儲表示鄰接表和逆鄰接表師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業7.14,7.15教學后記編號22周

22、次11日期11.15課時安排2課題十字鏈表、鄰接多重表、圖的遍歷教材的重點 、難點分析重點：(1)圖的遍歷難點：(1)圖的遍歷非遞歸算法教學目標(1)熟練掌握圖的四種存儲結構和建立算法(2)熟練掌握圖的深度優先遍歷和廣度優先遍歷教學方法和 教學手段教學過程教學內容安排與板書設計：723 十字鏈表有向圖的十字鏈表存儲表示構造有向圖724 鄰接多重表無向圖的鄰接多重表教學過程73 圖的遍歷731 深度優先搜索732 廣度優先搜索師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業7.22,7.28教學后記編號23周次12日期11.19課時安排2課題圖的連通性問題教材的重點 、難點分析重點：(1)

23、最小生成樹的構造 教學目標掌握最小生成樹的兩種構造方法教學方法和 教學手段教學過程教學內容安排與板書設計：74 圖的連通性問題741 無向圖的連通分量和生成樹742 有向圖的強連通分量教學過程743 最小生成樹Prim算法Kruskal算法743 關節點和重連通分量師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業7.32教學后記編號24周次12日期11.22課時安排2課題有向無環圖及其應用教材的重點 、難點分析重點：(1)拓撲排序(2)求關鍵路徑難點：(1)求關鍵路徑 教學目標(1)掌握拓撲排序的方法(2)掌握關鍵路徑的求法教學方法和 教學手段教學過程教學內容安排與板書設計：75 有向無

24、環圖及其應用DAG751 拓撲排序752 關鍵路徑AOE網關鍵路徑教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業7.36教學后記編號25周次13日期11.26課時安排2課題最短路徑教材的重點 、難點分析重點：(1)求最短路徑難點：(1)求每一對頂點之間的最短路徑教學目標熟練掌握從某個源點到其余各頂點的最短路徑的求法掌握求每一對頂點之間的最短路徑的求法教學方法和 教學手段教學過程教學內容安排與板書設計：76 最短路徑761 從某個源點到其余各頂點的最短路徑Dijkstra算法762 每一對頂點之間的最短路徑教學過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業7.42教學

25、后記編號26周次13日期11.29課時安排2課題靜態查找表教材的重點 、難點分析重點：(1)順序查找(2)折半查找教學目標(1)熟練掌握靜態查找的各種方法教學方法和 教學手段教學過程教學內容安排與板書設計：第八章查找查找表與靜態查找表和動態查找表關鍵字與主關鍵字和次關鍵字查找與成功和不成功教學過程81 靜態查找表靜態查找表的類型定義811 順序表的查找 順序查找平均查找長度812 有序表的查找折半查找折半查找的性能分析813 靜態樹表的查找814 索引順序表的查找表其索引表分塊查找師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業9.29教學后記編號27周次14日期12.3課時安排2課題二

26、叉排序樹和平衡二叉樹教材的重點 、難點分析重點：(1)動態查找表及查找算法(2)二叉排序樹難點：(1)二叉排序樹教學目標(1)熟練掌握二叉排序樹的構造方法及查找過程(2)掌握AVL樹的構造教學方法和 教學手段教學過程教學內容安排與板書設計：82 動態查找表動態查找表的類型定義821 二叉排序樹和平衡二叉樹1、二叉排序樹及其查找過程二叉排序樹教學過程2、二叉排序樹的插入和刪除二叉排序樹的構造二叉排序樹的刪除3、二叉排序樹的查找分析4、平衡二叉樹平衡二叉樹與不平衡的二叉樹平衡樹的生成過程二叉排序樹的平衡旋轉二叉排序樹的類型定義5、平衡樹查找的分析師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作

27、業9.33教學后記編號28周次14日期12.6課時安排2課題B-樹和B+樹教材的重點 、難點分析教學目標(1)掌握B-樹和B+樹的構造和查找(2)了解鍵樹的構造方法教學方法和 教學手段教學過程教學內容安排與板書設計：822 B-樹和B+樹1、B-樹及其查找2、B-樹查找分析教學過程3、B-樹的插入和刪除4、B+樹823 鍵樹師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業教學后記編號29周次15日期12.10課時安排2課題哈希表教材的重點 、難點分析難點：(1)哈希表及查找算法教學目標(1)熟練掌握哈希表的建表方法、沖突的處理及查找過程(2)理解哈希表與其它存儲結構的表的本質區別(3)熟

28、練掌握哈希表的平均查找長度的計算（等概率）教學方法和 教學手段教學過程教學內容安排與板書設計：83 哈希表831 什么是哈希表哈希函數沖突散列教學過程832 哈希函數的構造方法1、直接定址法2、數字分析法3、平方取中法4、折疊法5、除留余數法6、隨機數法833 處理沖突的方法1、開放定址法2、再哈希法3、鏈地址法4、建立一個公共溢出區834 哈希表的查找及其分析師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業9.46教學后記編號30周次15日期12.13課時安排2課題排序概述、插入排序教材的重點 、難點分析重點：(1)希爾排序教學目標(1)深刻理解插入排序的基本思想及其特點(2)熟練掌握

29、插入排序方法的排序過程(3)掌握插入排序算法時間復雜度的分析方法并熟記其分析結論教學方法和 教學手段教學過程教學內容安排與板書設計：第九章排序91 排序概述排序排序方法的穩定性內部排序與外部排序教學過程92 插入排序921 直接插入排序922 其他插入排序1、折半插入排序2、2-路插入排序3、表插入排序923 希爾排序師生雙邊活動：提問：舉例：演示實驗：教具準備：課后作業10.25教學后記編號31周次16日期12.17課時安排2課題快速排序、選擇排序教材的重點 、難點分析重點：(1)快速排序(2)堆排序難點：(1)快速排序 (2)堆排序教學目標(1)深刻理解快速排序的基本思想及其特點(2)熟練掌握快速排序方法的排序過程(3)掌握快速排序算法時間復雜度的分析方法并熟記其分析結論(4)深刻理解選擇排