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

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

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

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

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

5、.4.4 算法的存儲(chǔ)空間需求第二章 線性表教學(xué)目的：線性表的類型定義，線性表的順序表示和實(shí)現(xiàn)，線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。基本要求：1.了解線性表的邏輯結(jié)構(gòu)特性，了解線性表的ADT定義。2. 掌握線性表的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3. 順序表：掌握C描述方法，熟練掌握查找、插入、刪除算法；掌握構(gòu)造一個(gè)空的順序線性表的算法，并掌握在此空表的基礎(chǔ)上進(jìn)行其他基本操作（取元素、求前驅(qū)元素、求后繼元素等）算法的實(shí)現(xiàn)。4. 單鏈表：掌握C描述方法，熟練掌握查找、插入、刪除算法；掌握順序、逆序建立單鏈表的算法；學(xué)會(huì)如何建立一張空表的算法，并掌握在此表基礎(chǔ)上進(jìn)行其他基本操作（求表長(zhǎng)、取元素、清空和

6、銷毀等）算法的實(shí)現(xiàn)。5、 熟練掌握循環(huán)鏈表、雙向循環(huán)鏈表的C描述方法，了解其遍歷、插入、刪除算法思想。7. 掌握算法的時(shí)間復(fù)雜度的概念，掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法。了解算法的空間復(fù)雜度的概念，了解計(jì)算算法的空間復(fù)雜度的方法能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。重點(diǎn)與難點(diǎn)：順序表和單鏈表的插入、刪除算法；順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的性能分析教學(xué)時(shí)數(shù)：8學(xué)時(shí)教學(xué)內(nèi)容：2. 線性表2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1 線性鏈表2.3.2 循環(huán)鏈表2.3.3 雙向鏈表第三章 棧和隊(duì)列教學(xué)目的：棧和

7、隊(duì)列的定義、存儲(chǔ)結(jié)構(gòu)、基本操作和實(shí)現(xiàn)算法?；疽螅?掌握棧的有關(guān)概念和特點(diǎn)。2. 熟練掌握棧類型的兩種實(shí)現(xiàn)方法（順序棧和鏈棧），特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。3.熟練掌握初始化棧、進(jìn)棧和出棧操作的實(shí)現(xiàn)算法。3. 掌握隊(duì)列的有關(guān)概念和特點(diǎn)。5. 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作（隊(duì)列初始化、入隊(duì)列和出隊(duì)列）實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。6. 會(huì)在相應(yīng)的應(yīng)用問題中正確選用棧和隊(duì)列，注意理解操作受限的含義。重點(diǎn)與難點(diǎn)：棧和隊(duì)列的操作特點(diǎn)、循環(huán)隊(duì)列的運(yùn)算特點(diǎn)。教學(xué)時(shí)數(shù)：8學(xué)時(shí)教學(xué)內(nèi)容：3. 棧和隊(duì)列3.1 棧3.1.1 抽象數(shù)據(jù)類型棧的定義3.1.2 棧的表示和實(shí)現(xiàn)3.2

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

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

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

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

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

13、路徑的遍歷。要掌握遍歷的邏輯定義，深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。4. 掌握?qǐng)D的算法，學(xué)會(huì)手工計(jì)算：求無向圖的連通分量的方法；求最小生成樹的普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法；求有向圖的拓?fù)渑判蛐蛄兴惴?；求AOE網(wǎng)的關(guān)鍵路徑的算法；求最短路徑的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。重點(diǎn)與難點(diǎn)：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法教學(xué)時(shí)數(shù)：10學(xué)時(shí)教學(xué)內(nèi)容：7. 圖7.1 圖的定義和術(shù)語7.2 圖的存儲(chǔ)結(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.2 廣度優(yōu)先搜索

14、7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹7.4.3 最小生成樹7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判?.5.2 關(guān)鍵路徑7.6 最短路徑7.6.1 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑7.6.2 每一對(duì)頂點(diǎn)之間的最短路徑第九章 查找教學(xué)目的：基本要求：1. 熟練掌握靜態(tài)查找表：順序表（順序查找）和有序表（二分查找）的查找算法，理解平均查找長(zhǎng)度的計(jì)算方法。2. 熟練掌握動(dòng)態(tài)查找表：二叉排序樹（包括平衡二叉樹）的構(gòu)造和查找方法，掌握在二叉排序樹中插入和刪除結(jié)點(diǎn)的方法，注意當(dāng)二叉平衡樹失去平衡時(shí)要學(xué)會(huì)如何做相應(yīng)的調(diào)整。3. 了解B-樹、B+樹的特點(diǎn)以及它們的建樹和查找的過程。4

15、. 熟練掌握哈希表的構(gòu)造方法，學(xué)會(huì)如何去尋找哈希函數(shù)及處理沖突的方法。深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。5. 掌握按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。重點(diǎn)與難點(diǎn)：二叉排序樹（包括平衡二叉樹）的構(gòu)造、查找和插入、刪除的方法；哈希表的構(gòu)造方法教學(xué)時(shí)數(shù)：10學(xué)時(shí)教學(xué)內(nèi)容：9. 查找9.1 靜態(tài)查找表9.1.1 順序表的查找9.1.2 有序表的查找9.1.4 索引順序表的查找9.2 動(dòng)態(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.4 哈希表的查

16、找及其分析第十章 內(nèi)部排序教學(xué)目的：基本要求：1. 了解排序的定義和各種排序方法的特點(diǎn)。熟悉各種方法的排序過程及其依據(jù)的原則，對(duì)給定關(guān)鍵字的序列能夠熟練寫出各種排序算法的排序過程。2. 掌握各種排序方法的時(shí)間復(fù)雜度。了解各種排序算法的平均情況和最壞情況的時(shí)間性能。3. 理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。4. 掌握各種內(nèi)部排序方法的比較以及得出的結(jié)論。重點(diǎn)與難點(diǎn)：各種排序算法的排序過程和算法；各種排序算法的平均情況和最壞情況的時(shí)間性能及比較教學(xué)時(shí)數(shù)：10學(xué)時(shí)教學(xué)內(nèi)容：10. 內(nèi)部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.3 希爾排序10.3 快速排序10.4 選擇排序10.4.1 簡(jiǎn)單選擇排序10.4.2 樹形選擇排序10.4.3 堆排序10.5 歸并排序10.6 基數(shù)排序10.6.1 多關(guān)鍵字的排序10.6.2 鏈?zhǔn)交鶖?shù)排序10.7 各種內(nèi)部排序方法的比較討論考核方式及要求：閉卷考試三、參考教材及資料：序號(hào)名 稱類別作者出版社或刊物