1、數據結構課程教學大綱Data Strueture執筆人:編寫日期:一、課程基本信息1. 課程編號：2. 課程性質/類別：必修課/專業主干課3. 學時/學分：48學時（另實驗16學時）/ 4學分4. 適用專業：計算機科學與技術、軟件工程、網絡工程、信息管理與信息系統等專業二、課程教學目標及學生應達到的能力數據結構課程是計算機相關專業的專業基礎課、必修課程，主要介紹用計算機解決一 系列問題特別是非數值信息處理問題時所用的各種組織數據的方法、存儲數據結構的方法以 及在各種結構上執行操作的算法。通過本課程的學習，要求學生掌握各種數據結構的特點、 存儲表示、運算方法以及在計算機科學中最基本的應用，培養、

2、訓練學生選用合適的數據結 構和編寫質量高、風格好的應用程序的能力，培養學生分析問題、解決問題的能力，并為后 續課程的學習打下良好的理論基礎和實踐基礎。三、課程教學容與基本要求（一）緒論（3學時）1. 主要容：（1）介紹什么是數據結構；（2）基本概念和術語：數據、數據元素、數據對象，以及數據結構的定義、邏輯結構、 物理結構（理解）數據類型、抽象數據類型；（3）抽象數據類型的表示與實現；（4）算法和算法分析：算法的概念、算法設計的要求以及算法效率的度量。2. 基本要求（1）了解學習數據結構的重要性；（2）掌握數據結構的定義及相關概念和術語；（3）了解抽象數據類型的定義、表示與實現方法；（4）理解算

3、法的概念、特點并掌握度量其效率的基本方法。3. 自學容：類C語言的書寫規。（二）線性表（6學時）1. 主要容：（1）線性表的抽象數據類型定義和相關概念：數據項、記錄、文件等;（2）線性表順序存儲表示和基本操作的實現；（3）線性表的鏈式存儲表示和基本操作的實現；（4）稀疏多項式的抽象數據類型定義、表示和加法的實現。2. 基本要求（1）掌握線性表的定義和特點；（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現算法；（3）熟練掌握單鏈表、循環鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插 入、刪除、創建等實現算法。3. 自學容：靜態鏈表。（三）找和隊列（5學時）1. 主要容：（1）棧和隊

4、列的結構待性和抽象數據類型定義；（2）棧和隊列的順序存儲表示和實現；（3）棧和隊列的鏈式存儲表示和實現；（4）棧和隊列在程序設計中的應用。2. 基本要求（1）掌握棧和隊列兩種抽象數據類型的特點；（2）學握棧的兩種存儲表示和實現，特別注意棧滿棧空的條件；（3）學握隊列的兩種存儲表示和實現，待別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關系。3自學容：錢棧，離散事件模擬（四）串（3學時）1. 主要容：（1）串的抽象數據類型定義；（2）串的表示和實現：定長順序存儲結構和堆分配存儲結構；（3）串的各種基本操作的實現及其應用；（4）串的模式匹配操作。2. 基本要求（1）熟悉串的一些基本操作的定義，并能

5、利用基本操作實現串的其它操作；（2）學握串的定長順序存儲結構以及基本操作的實現；（3）掌握串的堆分配存儲結構以及基本操作的實現；（4）掌握串的簡單模式匹配算法，理解KIP算法。3自學容：串操作的應用實例。（五）數組和廣義表（4學時）1. 主要容：（1）數組的抽象數據類型定義及其順序表示和實現；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數據類型定義和存儲結構。2. 基本要求（1）了解數組的兩種存儲表示方法，并掌握數組在以行為主的存儲結構中的地址計算 方法；（2）掌握對特殊矩陣進行壓縮存儲時的下標變換公式；（3）熟悉稀疏矩陣的三元組順序表存儲結構下的一般轉置和快速轉置算法；了解十字 鏈

6、表等存儲結構；（4）掌握廣義表的結構特點、取表頭表尾操作，及其存儲表示方法。3自學容：采用十字鏈表存儲結構創建稀疏矩陣。（六）樹和二叉樹（10學時）1主要容：（1）樹的抽象數據類型定義和基本術語；（2）二叉樹的抽象數據類型定義、性質和存儲結構；（3）二叉樹的遍歷；（4）線索二叉樹的定義、遍歷及線索化二叉樹；（5）樹的存儲結構、樹和森林的遍歷以及與二叉樹的轉換；（6）Huffman樹及其應用。2. 基本要求（1）掌握樹型結構的特點和基本術語；（2）熟練掌握二叉樹的性質，了解相應的證明方法；（3）了解二叉樹的順序存儲結構和鏈式存儲結構，熟練掌握二叉鏈表存儲結構；（4）熟練掌握二叉樹三種遍歷的遞歸算

7、法和中序遍歷非遞歸算法，能靈活運用遍歷算 法實現二叉樹的其他操作；（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結點的前驅與后繼的 方法；（6）熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3自學容：先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。（七）圖（9學時）1. 主要容：（1）圖的定義和術語；（2）圖的四種存儲結構：數組表示法（鄰接矩陣）、鄰接表、十字準表和鄰接多重表；（3）圖的兩種遍歷策略：深度優先遍歷和廣度優先遍歷；（4）圖的連通性和最小生成樹；（5）有向無環圖及其

8、應用：拓撲排序和關鍵路徑；（6）最短路徑問題。2. 基本要求（1）熟悉圖的定義和術語；（2）了解圖的存儲結構，熟練掌握數組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優先遍歷和廣度優先遍歷算法；（4）學握無向連通帶權圖的最小生成樹求解算法；（5）了解有向無環圖、AOV網、A0E網及其在實際中的應用，熟悉拓撲排序算法和關鍵 路徑算法；（6）熟悉兩種最短路徑問題求解算法。3自學容：樹的先根遍歷算法與圖的深度優先遍歷算法比較； 樹的層次遍歷算法與圖的廣度優先遍歷算法比較。（A）查找（4學時）1. 主要容：（1）查找的基本概念和相關術語；（2）靜態查找表：順序查找、折半查找和索引順序表查

9、找；（3）動態查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2. 基本要求（1）了解查找的作用，熟悉相關術語；（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構造和查找方法；（4）熟練掌握哈希表的構造方法，特別是咯希函數和處理沖突方法的選??；（5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3自學容：平衡二叉樹。（九）部排序（4學時）1. 主要容：（1）排序的基本概念和相關術語；（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基

10、數排序：鏈式基數排序；（7）各種部排序方法的比較討論。2. 基本要求（1）了解排序作用，熟悉相關術語；（2）掌握多種排序的基本思想、算法特點和排序過程，分析它們的時間復雜度、空間 復雜度和穩定性。3自學容：二路插入排序、表插入排序和樹形選擇排序。四、教學安排建議1. 作業練習完成每章的教學后進行布置習題，使用教材配套的數據結構題集（C語言版）。盡量 選擇基礎的并且加注了標記的題，應注重于精，而不要求多。要求積極獨立完成所布置的習 題，建議安排至少六次。2. 案例分析可參考選擇以下一些案例：（1）學生通訊錄管理系統，（2）表達式求值問題（3）交通 咨詢系統，等。3. 專題研討可參考選擇以下一些：

11、（1）最小生成樹問題（2）航班信息查詢與檢索系統，（3）部排 序算法比較，等。4. 實驗安排為了達到理論與實際應用的結合，讓學生能將所學知識應用于實際問題的求解中，培養 學生的實際動手能力，從而加深對概念及所學知識的理解，靈活、牢固掌握教材容，提高程 序設計及解決實際問題的能力，實驗環節的安排非常重要。建議實驗安排為八次，共16學時，分別如下：實驗1線性表的順序存儲結構的實現（2學時）實驗2線性表的鏈式存儲結構的實現（2學時）實驗3棧的算法實現（2學時）實驗4隊列的算法實現（2學時）實驗5串類型及操作（2學時）實驗6二叉樹的建立與遍歷（2學時）實驗7圖的建立與遍歷（2學時）實驗8查找與排序（2

12、學時）注：教師可根據教學實際情況（如：學生情況及學時情況等），適當調整實踐教學容及 學時分配。五、課程考核1. 考核形式及成績評走辦法本課程考核形式為：平時成績占40%,期末考試成績占60%。其中平時成績的結構分包 括：課堂表現10%、平時作業10%和實驗20%,期末考試為閉卷筆試考試：120分鐘，卷面分 滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。2. 本課程考核的基本要求課堂表現10%：包括課堂考勤和課堂提問，如果缺課課時達到本課程教學時數的1/3, 則取消考試資格。平時作業10%：根據上交次數及完成情況進行評定。實驗20%：根據各次實驗完成情況及實驗報告成績進行評定。

13、期末考試60%：本課程的期末考試考核容主要包括線性表、棧與隊列、串、數組與廣義 表、樹與二叉樹、圖、查找和部排序。其中，線性表、二叉樹、圖、查找和部排序容為考核 的重點。六、本課程與其它課程的先行后續關系先行課程：高級程序設計語言、離散數學后續課程：操作系統、編譯原理、數據庫理論、算法分析與設計等七、建議教材及教學參考書1.教材：嚴蔚敏，吳偉民編著，數據結構（C語言版），清華大學出版，2012.5嚴蔚敏，吳偉民編著，數據結構題集（C語言版），清華大學出版，2012.52.參考書：1 許卓群，乃孝，冬青，唐世渭，數據結構，高等教育，2004.2 徐孝凱，數據結構簡明教程，清華大學，19953 文博，朱青，數據結構與算法，機核工業，19964 云清，慶紅，揭安全編著，數據結構（C語言版），人民郵電，2007.5 秀金主編，數據結構，電子科技大學，2002.6 廉治，文清，郭福順，數據結構，理工大學，19897 Aho A V, Hopcroft J E, Ullman J D. Data Structures and Algorithms. Addison-Wesley Publishing Company,Inc. ,19838 Baron R J