數(shù)據(jù)結構課程教學大綱一、課程基本情況開課單位：計算機與信息工程系 課程編碼：Z060106適用專業(yè)：高職高專計算機類各專業(yè) 修課方式：必修總 學 時： 6476學時 考核方式：考試教 材：陳雁.數(shù)據(jù)結構. 高等教育出版社. 2002年教學參考書：嚴尉敏 .數(shù)據(jù)結構. 清華大學出版社. 2003年蘇德富 .數(shù)據(jù)結構. 重慶大學出版社. 2002年二、課程的性質、任務和目的數(shù)據(jù)結構是介于數(shù)學、硬件及軟件三者之間的一門核心課程，它不僅是一般程序設計，尤其是非數(shù)值性程序設計的基礎，而且是設計實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、大型應用程序及其它系統(tǒng)程序的重要基礎。所以數(shù)據(jù)結構從課程性質上講是一門專業(yè)基礎課。本課程的目的和任務就是訓練學生對計算機加工的數(shù)據(jù)對象進行分析的能力，選擇適當?shù)臄?shù)據(jù)結構、存貯結構及相應算法的能力，并且能夠創(chuàng)造性地進行算法設計和程序設計，使所設計的程序結構清楚，正確易讀，并上機調試通過。三、課程的主要內容與學時分配(一) 主要內容1數(shù)據(jù)結構概述 2學時1.1 數(shù)據(jù)結構研究的對象-數(shù)據(jù)、數(shù)據(jù)之間的關系1.2 實際問題抽象成數(shù)學模型-線性結構、層次結構、網狀結構1.3 數(shù)據(jù)結構中使用的基本術語-數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構1.4 數(shù)據(jù)結構的發(fā)展及它的地位-為什么要學習數(shù)據(jù)結構1.5 算法描述的語言及對算法分析的方法-算法、算法特征、時間復雜度，空間復雜度的分析2線性表 12 學時（6+2+4 ）2.1 順序表的定義-存儲原理、運算（查找、插入、刪除）2.2 鏈式存儲結構、運算-存儲原理、運算（查找、插入、刪除）2.3 循環(huán)鏈、雙向鏈3棧和隊列 8學時（6+2）3.1 棧的邏輯結構、棧的基本運算3.2 隊列的基本運算、循環(huán)隊列3.3 棧與隊的應用4數(shù)組 6學時(4+*2)4.1 數(shù)組的概念4.2 特殊矩陣、稀疏矩陣的存儲方法5串 2學時5.l 串的定義及基本運算5.2 串的存貯結構5.3 串的基本運算的實現(xiàn)模式匹配（KMP）6樹 12學時（6+2+4）6.1 樹的概念6.2 二叉樹的概念6.3 二叉樹的存儲結構6.4 樹的遍歷6.5 線索樹6.6 樹的存儲結構6.7 樹、二叉樹和森林之間的轉換6.8 哈夫曼樹（Huffman）算法及其應用（哈夫曼編碼）7圖 12學時（8+2+2）7.1 圖的定義，術語7.2 圖的存貯結構順序鏈式存儲7.3 圖的遍歷7.4 最小生成樹7.5 拓撲排序7.6 最短路徑7.7 關鍵路徑8檢索 10學時（6+2+2）8.1 順序檢索、有序檢索、分塊檢索、散列表的檢索8.2 二叉排序樹8.3 平衡二叉排序樹* 8.4 B_樹9排序 8學時（6+2+2）9.1 插入排序9.2 快速排序9.3 選擇排序9.4 堆排序9.5 歸并排序9.6 基數(shù)排序9.7 內部排序方法的比較9.8 外部排序簡介*10文件 2學時10.l 順序文件10.2 索引文件10.3 直接存取文件10.4 多關鍵字文件(二) 學時分配序號章 節(jié)課 時 分 配理論課習題課實驗課其它共計1數(shù)據(jù)結構概述2dd22線性結構表624123棧、隊列6d284數(shù)組4d*265串2dd26樹6*22+*2127圖8*22128查找6*22109排序6*221010文件2dd2合 計481018d76四、課程教學基本要求及重點1數(shù)據(jù)結構概述：了解數(shù)據(jù)結構研究的對象、數(shù)據(jù)結構的發(fā)展及地位，掌握實際問題抽象成數(shù)學模型的概念、數(shù)據(jù)結構中使用的基本術語和算法描述的語言及算法分析的方法。具體為：學會分析數(shù)據(jù)結構研究的對象 -數(shù)據(jù)、數(shù)據(jù)之間的關系；會將實際問題抽象成數(shù)學模型 -線性結構、層次結構、網狀結構；掌握數(shù)據(jù)結構中使用的基本術語 -數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構；了解數(shù)據(jù)結構的發(fā)展及它的地位 -為什么要學習數(shù)據(jù)結構；掌握算法描述的語言及對算法分析的方法 -算法、算法特征、時間復雜度，空間復雜度的分析。重點：概念、算法分析的方法。難點：算法分析的方法。2線性結構熟練掌握順序表的定義、向量 (或一維數(shù)組)的存儲、插入、刪除元素等運算。掌握鏈式表的建立、插入、刪除元素等運算。熟悉鏈表的連接，多項式的加、減運算等操作。熟悉循環(huán)鏈、雙向鏈的操作。重點：概念、基本運算實現(xiàn)方法。難點：應用。3棧、隊列掌握棧的定義，順序棧存儲結構和鏈式棧存儲結構的建立、基本操作（運算）。熟悉棧在計算表達式中的應用、棧與遞歸過程。掌握循環(huán)隊列的操作和實現(xiàn)，應用。熟悉隊列的定義，順序隊列（循環(huán)隊列）存儲結構和鏈式隊列存儲結構的建立、基本操作（運算）。熟悉隊列的應用。重點：概念、棧和隊列基本運算實現(xiàn)方法。難點：棧和隊列的應用。4數(shù)組掌握數(shù)組的定義、數(shù)組的順序表示和實現(xiàn)；掌握特殊矩陣： 三角矩陣、對稱矩陣及稀疏矩陣的定義、存儲方法，地址計算式；熟悉稀疏矩陣的十字鏈表存儲方法；熟悉特殊矩陣的一些算法。重點：概念、存儲方法，地址計算式；難點：應用。5串掌握串的定義及基本運算；掌握串的存貯結構；掌握串基本運算的實現(xiàn)；熟悉串的基本運算的實現(xiàn) -模式匹配（KMP）。重點：串的定義及基本運算。6樹熟練掌握樹的概念、二叉樹的概念、二叉樹的性質、完全二叉樹、滿二叉樹的概念和特點；掌握二叉樹的存儲結構（順序存儲和鏈式存儲）；掌握二叉樹的遍歷算法（使用棧的遍歷）前序、中序和后序；掌握線索樹的概念，線索方法；掌握樹的存儲結構、樹、二叉樹和森林之間的轉換、哈夫曼樹（ Huffman）算法及其應用（哈夫曼編碼）。重點：二叉樹的概念、二叉樹的性質、完全二叉樹、滿二叉樹的概念和特點；二叉樹的遍歷。難點：遍歷過程、線索樹的線索方法。7圖熟練掌握圖的定義，術語、圖的存貯結構、圖的兩種遍歷方法；掌握最小生成樹的 Kruskal和Prim兩種生成過程，掌握Prim算法。掌握拓撲排序、最短路徑、關鍵路徑的算法思想。重點：圖的定義，術語、圖的存貯結構、圖的兩種遍歷方法；難點：拓撲排序、最短路徑、關鍵路徑的算法思想。8排序熟練掌握插入排序、快速排序、選擇排序、堆排序、歸并排序和基數(shù)排序的思想、算法、時間和空間復雜度；會對各種內部排序方法進行時間和空間復雜度的比較；熟悉外部排序方法。重點：插入排序、快速排序、選擇排序、堆排序、歸并排序和基數(shù)排序的思想、算法、時間和空間復雜度分析。難點：各排序方法的使用情況和比較。9檢索熟練掌握順序檢索、二分檢索、分塊檢索、散列表的檢索的方法；掌握順序檢索中監(jiān)視哨的作用。掌握散列的基本思想、處理沖突常用的方法；掌握用除余法構造散列函數(shù)的方法、掌握用開放地址法（重點：線性探測再散列）和拉鏈處理沖突的方法；掌握二叉排序樹、平衡二叉排序樹的概念；掌握二叉排序樹、熟悉平衡二叉排序樹構造方法。熟悉 B_樹的概念。重點：各種檢索的思想、算法、時間和空間復雜度分析。難點：二叉排序樹構造機刪除方法、平衡二叉排序樹構造方法。10文件熟悉順序文件、索引文件、直接存取文件和多關鍵