《數(shù)據(jù)結構》教學大綱

1、僅供個人參考數(shù)據(jù)結構教學大綱（課程代碼：）一、課程說明（一）適用專業(yè)：計算機網(wǎng)絡專業(yè)（?？疲?、計算機教育（?？疲⒂嬎銠C軟件技術（?？疲ǘ┱n程類別：專業(yè)課（三）課程性質與任務：數(shù)據(jù)結構是計算機應用專業(yè)的一門專業(yè)課，主要任務是討論各種數(shù)據(jù)結構的邏輯結構，存儲結構及有關操作的算法。目的是使學生學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術。另一方面，通過對本課程算法設計和上機實踐的訓練，還應培養(yǎng)學生的數(shù)據(jù)抽象能力和程序設計的能力。（四）教學目的與要求：要求學生掌握數(shù)據(jù)結構的基本概念及其分類，數(shù)據(jù)結構

2、與數(shù)據(jù)類型、抽象數(shù)據(jù)類型的關系，數(shù)據(jù)結構與算法的關系。掌握各種基本數(shù)據(jù)結構的特點、它們的內(nèi)在邏輯關系及計算機中的表示方法和基本操作的實現(xiàn)方法，熟悉它們在計算機科學中的基本應用。進一步深入理解掌握遞歸的概念、遞歸算法的設計、遞歸算法的執(zhí)行以及遞歸算法與迭代算法之間的關系。掌握算法設計的步驟和基本的算法分析的方法。通過對不同的數(shù)據(jù)結構與算法的對比，學會根據(jù)問題的要求合理選擇數(shù)據(jù)結構、設計算法并控制求解算法的空間和時間的復雜性的能力。掌握數(shù)據(jù)結構在排序和查找等常用算法中的應用。（五）先修課程：離散數(shù)學、C語言程序設計（六）學時、學分數(shù)：6學時/周，共108學時；5學分。（七）教學方式及設施要求：課堂

3、教學與上機實驗相結合上機實驗設備要求：PC機、軟件環(huán)境：BorlandC或VC+（八）考核方式與要求：閉卷考試；要求學生能夠掌握各種數(shù)據(jù)結構的特點及實現(xiàn)方法和適用范圍；具備一定的閱讀、分析和設計算法的能力；能掌握常規(guī)設計方法和技巧。二、課程內(nèi)容、基本要求與學時分配（一）課時分配表章節(jié)次數(shù)章節(jié)名稱學時數(shù)總學時理論其他1緒論10642線性表16883棧和隊列12844串8625數(shù)組和廣義表4406樹和二叉樹161067圖141049查找1410410內(nèi)部排序14104（二）各章節(jié)基本內(nèi)容及要求第一章緒論教學目的：數(shù)據(jù)結構的基本概念和術語，抽象數(shù)據(jù)類型的表示與實現(xiàn)，算法和算法分析。基本要求：1 .理

4、解各名詞、術語的含義，掌握基本概念（結合一定的實際問題舉例說明）。2 .了解類C語言，掌握用類C語言書寫算法的格式和要求。3 .了解抽象數(shù)據(jù)類型的表示與實現(xiàn)，掌握用C語言實現(xiàn)抽象數(shù)據(jù)類型的基本思路和格4 .掌握算法的概念，理解算法的五個重要特征的確切含義，了解算法設計的要求。5 .熟練掌握算法時間復雜度的分析方法。重點與難點：數(shù)據(jù)結構的基本概念、算法的時間復雜度和空間復雜度的概念與分析教學時數(shù)：6學時教學內(nèi)容：1 .緒論1.1 什么是數(shù)據(jù)結構1.2 基本概念和術語1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4 算法和算法分析1.4.1 算法1.4.2 算法設計的要求1.4.3 算法效率的度量1.4.4

5、 算法的存儲空間需求第二章線性表教學目的：線性表的類型定義，線性表的順序表示和實現(xiàn)，線性表的鏈式表示和實現(xiàn)。不得用于商業(yè)用途僅供個人參考基本要求：1. 了解線性表的邏輯結構特性，了解線性表的ADT定義。2. 掌握線性表的兩種存儲結構：順序存儲結構和鏈式存儲結構。3. 順序表：掌握C描述方法，熟練掌握查找、插入、刪除算法；掌握構造一個空的順序線性表的算法，并掌握在此空表的基礎上進行其他基本操作（取元素、求前驅元素、求后繼元素等）算法的實現(xiàn)。4. 單鏈表：掌握C描述方法，熟練掌握查找、插入、刪除算法；掌握順序、逆序建立單鏈表的算法；學會如何建立一張空表的算法，并掌握在此表基礎上進行其他基本操作（求

6、表長、取元素、清空和銷毀等）算法的實現(xiàn)。5、熟練掌握循環(huán)鏈表、雙向循環(huán)鏈表的C描述方法，了解其遍歷、插入、刪除算法思想。7. 掌握算法的時間復雜度的概念，掌握計算語句頻度和估算算法時間復雜度的方法。了解算法的空間復雜度的概念，了解計算算法的空間復雜度的方法能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合。重點與難點：順序表和單鏈表的插入、刪除算法；順序存儲和鏈式存儲的性能分析教學時數(shù)：8學時教學內(nèi)容：8. 線性表8.1 線性表的類型定義8.2 線性表的順序表示和實現(xiàn)8.3 線性表的鏈式表示和實現(xiàn)8.3.1 線性鏈表8.3.2 循環(huán)鏈表8.3.3 雙向鏈表第三章棧和隊

7、列教學目的：棧和隊列的定義、存儲結構、基本操作和實現(xiàn)算法。基本要求：1. 掌握棧的有關概念和特點。2. 熟練掌握棧類型的兩種實現(xiàn)方法（順序棧和鏈棧），特別應注意棧滿和?？盏臈l件以及它們的描述方法。3. 熟練掌握初始化棧、進棧和出棧操作的實現(xiàn)算法。9. 掌握隊列的有關概念和特點。5. 熟練掌握循環(huán)隊列和鏈隊列的基本操作（隊列初始化、入隊列和出隊列）實現(xiàn)算法，特別注意隊滿和隊空的描述方法。6. 會在相應的應用問題中正確選用棧和隊列，注意理解操作受限的含義。重點與難點：棧和隊列的操作特點、循環(huán)隊列的運算特點。教學時數(shù)：8學時教學內(nèi)容：3. 棧和隊列3.1 棧3.1.1 抽象數(shù)據(jù)類型棧的定義3.1.2

8、 棧的表示和實現(xiàn)3.2 棧的應用舉例3.2.1 數(shù)制轉換3.2.2 括號匹配的檢驗3.2.3 行編輯程序3.4隊列3.4.1 抽象數(shù)據(jù)類型隊列的定義3.4.2 鏈隊列-隊列的鏈式表示和實現(xiàn)3.4.3 循環(huán)隊列-隊列的順序表示和實現(xiàn)第四章串教學目的：串及串的一些相關概念，串的存儲方法，串的基本運算及實現(xiàn)算法?；疽螅? 、掌握串的概念。2 、掌握空串、空格串、子串、主串、位置、兩串相等的概念。3、掌握串有哪些基本操作。4 、掌握定長順序存儲結構的表示。5 、掌握基本操作在定長順序存儲結構上的實現(xiàn)。6 、掌握定長順序存儲結構串操作的特點。重點與難點：串的表示實現(xiàn)教學時數(shù)：6學時教學內(nèi)容:4. 串

9、1 .1串類型的定義2 .2串的表示和實現(xiàn)2.1.1 定長順序存儲表示2.1.2 堆分配存儲表示2.1.3 串的塊鏈存儲表示第五章稀疏矩陣和廣義表教學目的：數(shù)組的存儲結構及特殊矩陣的壓縮存儲，廣義表的概念基本要求：3 、掌握數(shù)組的概念。4 、理解數(shù)組的順序存儲的含義，掌握順序存儲的定位公式5 、矩陣的壓縮存儲6 、掌握廣義表的概念。7 、掌握廣義表的三個重要結論。重點與難點：矩陣的壓縮存儲、廣義表的結構教學時數(shù)：4學時教學內(nèi)容：5. 數(shù)組和廣義表5.1 數(shù)組的定義5.2 數(shù)組的順序表示和實現(xiàn)5.3 矩陣的壓縮存儲5.3.1 特殊矩陣5.3.2 稀疏矩陣5.4 廣義表的定義第六章樹和二叉樹教學目

10、的：樹的定義和基本術語，二叉樹的定義、性質和存儲結構，遍歷二叉樹和線索二叉樹，樹和森林，哈夫曼樹及其應用?；疽螅?. 掌握樹和二叉樹的定義和基本術語。不得用于商業(yè)用途僅供個人參考2. 熟練掌握二叉樹的結構特性和五大性質定理，了解相應性質的證明方法。3. 熟悉二叉樹的各種存儲結構的特點及適用范圍，熟練掌握二叉鏈表存儲結構。4. 遍歷二叉樹是二叉樹各種操作的基礎。掌握采用不同的存儲結構實現(xiàn)的二叉樹遍歷算法。熟練掌握遍歷二叉樹的遞歸算法，并能夠結合二叉樹的五種基本形態(tài)靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。掌握按層次遍歷二叉樹的算法。能夠熟練寫出給定二叉樹的各種遍歷序列，也會根據(jù)給定的遍歷序列畫出

11、二叉樹。5. 理解二叉樹線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯(lián)系。了解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。能夠熟練地畫出給定二叉樹的各種線索。6. 了解樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法，了解遍歷樹和森林的方法以及與遍歷二叉樹的對比。了解實現(xiàn)樹的各種操作的算法。7. 了解最優(yōu)樹（哈夫曼樹）的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法，會計算樹的帶權路徑長度（WPL）。重點與難點：遍歷二叉樹的遞歸算法、二叉樹線索化、建立最優(yōu)樹和哈夫曼編碼的方法教學時數(shù)：10學時教學內(nèi)容：6. 樹和二叉樹6.1 樹的定義和基本術語6.2 二

12、叉樹6.2.1 二叉樹的定義6.2.2 二叉樹的性質6.2.3 二叉樹的存儲結構6.3 遍歷二叉樹和線索二叉樹6.3.1 遍歷二叉樹6.3.2 線索二叉樹6.4 樹和森林6.4.1 樹的存儲結構6.4.2 森林與二叉樹的轉換6.4.3 樹和森林的遍歷6.6.1 最優(yōu)二叉樹（赫夫曼樹）6.6.2 赫夫曼編碼第七章圖教學目的：圖的定義和術語，圖的存儲結構，圖的遍歷，圖的連通性問題（最小生成樹），有向無環(huán)圖及其應用（拓撲排序、關鍵路徑），最短路徑?；疽螅?. 掌握圖的概念和術語。2. 熟練掌握圖的各種存儲結構及其構造方法，了解各種存儲結構的特點，了解算法的效率和采用的存儲結構有密切聯(lián)系。3. 熟

13、練掌握圖的兩種搜索路徑的遍歷。要掌握遍歷的邏輯定義，深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。4. 掌握圖的算法，學會手工計算：求無向圖的連通分量的方法；求最小生成樹的普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法；求有向圖的拓撲排序序列算法；求AOE網(wǎng)的關鍵路徑的算法；求最短路徑的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。重點與難點：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法教學時數(shù)：10學時教學內(nèi)容：7. 圖7.1 圖的定義和術語7.2 圖的存儲結構7.2.1 數(shù)組表示法7.2.2 鄰接表7.2.3 十字鏈表7.2.4 鄰接多重表7.3 圖的遍歷7.3.1 深度優(yōu)先搜索7.3

14、.2 廣度優(yōu)先搜索7.4 圖的連通性問題不得用于商業(yè)用途僅供個人參考7.4.1 無向圖的連通分量和生成樹7.4.3 最小生成樹7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序7.5.2 關鍵路徑7.6 最短路徑7.6.1 從某個源點到其余各頂點的最短路徑7.6.2 每一對頂點之間的最短路徑第九章查找教學目的：基本要求：1. 熟練掌握靜態(tài)查找表：順序表（順序查找）和有序表（二分查找）的查找算法，理解平均查找長度的計算方法。2. 熟練掌握動態(tài)查找表：二叉排序樹（包括平衡二叉樹）的構造和查找方法，掌握在二叉排序樹中插入和刪除結點的方法，注意當二叉平衡樹失去平衡時要學會如何做相應的調整。3. 了解B-樹

15、、B+樹的特點以及它們的建樹和查找的過程。4. 熟練掌握哈希表的構造方法，學會如何去尋找哈希函數(shù)及處理沖突的方法。深刻理解哈希表與其它結構的表的實質性的差別。5. 掌握按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。重點與難點：二叉排序樹（包括平衡二叉樹）的構造、查找和插入、刪除的方法；哈希表的構造方法教學時數(shù)：10學時教學內(nèi)容：9. 查找9.1 靜態(tài)查找表9.1.1 順序表的查找9.1.2 有序表的查找9.2 動態(tài)查找表9.2.1 二叉排序樹和平衡二叉樹9.2.2 B-樹和B+樹9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函數(shù)的構造方法9.3.3 處理沖突的方法9.3

16、.4 哈希表的查找及其分析第十章內(nèi)部排序教學目的：基本要求：1. 了解排序的定義和各種排序方法的特點。熟悉各種方法的排序過程及其依據(jù)的原則，對給定關鍵字的序列能夠熟練寫出各種排序算法的排序過程。2. 掌握各種排序方法的時間復雜度。了解各種排序算法的平均情況和最壞情況的時間性能。3. 理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。4. 掌握各種內(nèi)部排序方法的比較以及得出的結論。重點與難點：各種排序算法的排序過程和算法；各種排序算法的平均情況和最壞情況的時間性能及比較教學時數(shù)：10學時教學內(nèi)容：10. 內(nèi)部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.

17、3 希爾排序10.3 快速排序10.4 選擇排序不得用于商業(yè)用途僅供個人參考1.1.1 1簡單選擇排序1.1.2 2樹形選擇排序1.1.3 3堆排序10.5 歸并排序10.6 基數(shù)排序10.6.1 多關鍵字的排序10.6.2 鏈式基數(shù)排序10.7 各種內(nèi)部排序方法的比較討論考核方式及要求：閉卷考試三、參考教材及資料:序號名稱類別作者出版社或刊物名稱出版或刊發(fā)時間貞他1數(shù)據(jù)結構（C語言版）教材嚴蔚敏吳偉民清華大學出版社19971-3342數(shù)據(jù)結構（C語言描述）教材徐孝凱賀桂英清華大學出版社20041-2753數(shù)據(jù)結構（C語言版）教材姚菁機械工業(yè)出版社20011-2194數(shù)據(jù)結構（C語百）教材曲建民清華大學出版社20051-2125數(shù)據(jù)結構與算法分析C語百描述著作（美）MarkAllenWeiss著馮舜璽譯機械工業(yè)出版社20041-252執(zhí)筆人：莊波教研室主任：莊波系主任：譚業(yè)武計算機科學技術系（部）軟件教研室2006年3月23日不得用于商業(yè)用途僅供個人用于學習、研究；不得用于商業(yè)用途。Forpersonaluseonlyinstudyandresearch;notforcom