《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱

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

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

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

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

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

6、表長、取元素、清空和銷毀等）算法的實現(xiàn)。5、熟練掌握循環(huán)鏈表、雙向循環(huán)鏈表的C描述方法，了解其遍歷、插入、刪除算法思想。7. 掌握算法的時間復(fù)雜度的概念，掌握計算語句頻度和估算算法時間復(fù)雜度的方法。了解算法的空間復(fù)雜度的概念，了解計算算法的空間復(fù)雜度的方法能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。重點與難點：順序表和單鏈表的插入、刪除算法；順序存儲和鏈式存儲的性能分析教學(xué)時數(shù)：8學(xué)時教學(xué)內(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、列教學(xué)目的：棧和隊列的定義、存儲結(jié)構(gòu)、基本操作和實現(xiàn)算法。基本要求：1. 掌握棧的有關(guān)概念和特點。2. 熟練掌握棧類型的兩種實現(xiàn)方法（順序棧和鏈棧），特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。3. 熟練掌握初始化棧、進棧和出棧操作的實現(xiàn)算法。9. 掌握隊列的有關(guān)概念和特點。5. 熟練掌握循環(huán)隊列和鏈隊列的基本操作（隊列初始化、入隊列和出隊列）實現(xiàn)算法，特別注意隊滿和隊空的描述方法。6. 會在相應(yīng)的應(yīng)用問題中正確選用棧和隊列，注意理解操作受限的含義。重點與難點：棧和隊列的操作特點、循環(huán)隊列的運算特點。教學(xué)時數(shù)：8學(xué)時教學(xué)內(nèi)容：3. 棧和隊列3.1 棧3.1.1 抽象數(shù)據(jù)類型棧的定義3.1.2

8、 棧的表示和實現(xiàn)3.2 棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換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)第四章串教學(xué)目的：串及串的一些相關(guān)概念，串的存儲方法，串的基本運算及實現(xiàn)算法?；疽螅? 、掌握串的概念。2 、掌握空串、空格串、子串、主串、位置、兩串相等的概念。3、掌握串有哪些基本操作。4 、掌握定長順序存儲結(jié)構(gòu)的表示。5 、掌握基本操作在定長順序存儲結(jié)構(gòu)上的實現(xiàn)。6 、掌握定長順序存儲結(jié)構(gòu)串操作的特點。重點與難點：串的表示實現(xiàn)教學(xué)時數(shù)：6學(xué)時教學(xué)內(nèi)容:4. 串

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

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

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

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

13、練掌握圖的兩種搜索路徑的遍歷。要掌握遍歷的邏輯定義，深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。4. 掌握圖的算法，學(xué)會手工計算：求無向圖的連通分量的方法；求最小生成樹的普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法；求有向圖的拓撲排序序列算法；求AOE網(wǎng)的關(guān)鍵路徑的算法；求最短路徑的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。重點與難點：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法教學(xué)時數(shù)：10學(xué)時教學(xué)內(nèi)容：7. 圖7.1 圖的定義和術(shù)語7.2 圖的存儲結(jié)構(gòu)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)圖及其應(yīng)用7.5.1 拓撲排序7.5.2 關(guān)鍵路徑7.6 最短路徑7.6.1 從某個源點到其余各頂點的最短路徑7.6.2 每一對頂點之間的最短路徑第九章查找教學(xué)目的：基本要求：1. 熟練掌握靜態(tài)查找表：順序表（順序查找）和有序表（二分查找）的查找算法，理解平均查找長度的計算方法。2. 熟練掌握動態(tài)查找表：二叉排序樹（包括平衡二叉樹）的構(gòu)造和查找方法，掌握在二叉排序樹中插入和刪除結(jié)點的方法，注意當(dāng)二叉平衡樹失去平衡時要學(xué)會如何做相應(yīng)的調(diào)整。3. 了解B-樹

15、、B+樹的特點以及它們的建樹和查找的過程。4. 熟練掌握哈希表的構(gòu)造方法，學(xué)會如何去尋找哈希函數(shù)及處理沖突的方法。深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別。5. 掌握按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。重點與難點：二叉排序樹（包括平衡二叉樹）的構(gòu)造、查找和插入、刪除的方法；哈希表的構(gòu)造方法教學(xué)時數(shù)：10學(xué)時教學(xué)內(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ù)的構(gòu)造方法9.3.3 處理沖突的方法9.3

16、.4 哈希表的查找及其分析第十章內(nèi)部排序教學(xué)目的：基本要求：1. 了解排序的定義和各種排序方法的特點。熟悉各種方法的排序過程及其依據(jù)的原則，對給定關(guān)鍵字的序列能夠熟練寫出各種排序算法的排序過程。2. 掌握各種排序方法的時間復(fù)雜度。了解各種排序算法的平均情況和最壞情況的時間性能。3. 理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。4. 掌握各種內(nèi)部排序方法的比較以及得出的結(jié)論。重點與難點：各種排序算法的排序過程和算法；各種排序算法的平均情況和最壞情況的時間性能及比較教學(xué)時數(shù)：10學(xué)時教學(xué)內(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 多關(guān)鍵字的排序10.6.2 鏈式基數(shù)排序10.7 各種內(nèi)部排序方法的比較討論考核方式及要求：閉卷考試三、參考教材及資料:序號名稱類別作者出版社或刊物名稱出版或刊發(fā)時間貞他1數(shù)據(jù)結(jié)構(gòu)（C語言版）教材嚴蔚敏吳偉民清華大學(xué)出版社19971-3342數(shù)據(jù)結(jié)構(gòu)（C語言描述）教材徐孝凱賀桂英清華大學(xué)出版社20041-2753數(shù)據(jù)結(jié)構(gòu)（C語言版）教材姚菁機械工業(yè)出版社20011-2194數(shù)據(jù)結(jié)構(gòu)（C語百）教材曲建民清華大學(xué)出版社20051-2125數(shù)據(jù)結(jié)構(gòu)與算法分析C語百描述著作（美）MarkAllenWeiss著馮舜璽譯機械工業(yè)出版社20041-252執(zhí)筆人：莊波教研室主任：莊波系主任：譚業(yè)武計算機科學(xué)技術(shù)系（部）軟件教研室2006年3月23日不得用于商業(yè)用途僅供個人用于學(xué)習(xí)、研究；不得用于商業(yè)用途。Forpersonaluseonlyinstudyandresearch;notforcom