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

一,、課程基本情況

開課單位：計(jì)算機(jī)與信息工程系 課程編碼：Z060106

適用專業(yè)：高職高專計(jì)算機(jī)類各專業(yè) 修課方式：必修

總 學(xué) 時(shí)： 64～76學(xué)時(shí) 考核方式：考試

教 材：陳雁.《數(shù)據(jù)結(jié)構(gòu)》. 高等教育出版社. 2002年

教學(xué)參考書：嚴(yán)尉敏 .《數(shù)據(jù)結(jié)構(gòu)》. 清華大學(xué)出版社. 2003年

蘇德富 .《數(shù)據(jù)結(jié)構(gòu)》. 重慶大學(xué)出版社. 2002年

二、課程的性質(zhì),、任務(wù)和目的

《數(shù)據(jù)結(jié)構(gòu)》是介于數(shù)學(xué),、硬件及軟件三者之間的一門核心課程,，它不僅是一般程序設(shè)計(jì)，尤其是非數(shù)值性程序設(shè)計(jì)的基礎(chǔ),，而且是設(shè)計(jì)實(shí)現(xiàn)編譯程序,、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng),、大型應(yīng)用程序及其它系統(tǒng)程序的重要基礎(chǔ),。所以《數(shù)據(jù)結(jié)構(gòu)》從課程性質(zhì)上講是一門專業(yè)基礎(chǔ)課。

本課程的目的和任務(wù)就是訓(xùn)練學(xué)生對(duì)計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象進(jìn)行分析的能力,，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu),、存貯結(jié)構(gòu)及相應(yīng)算法的能力，并且能夠創(chuàng)造性地進(jìn)行算法設(shè)計(jì)和程序設(shè)計(jì),，使所設(shè)計(jì)的程序結(jié)構(gòu)清楚,，正確易讀，并上機(jī)調(diào)試通過,。

三,、課程的主要內(nèi)容與學(xué)時(shí)分配

(一) 主要內(nèi)容

1．?dāng)?shù)據(jù)結(jié)構(gòu)概述 2學(xué)時(shí)

1.1 數(shù)據(jù)結(jié)構(gòu)研究的對(duì)象----數(shù)據(jù)、數(shù)據(jù)之間的關(guān)系

1.2 實(shí)際問題抽象成數(shù)學(xué)模型----線性結(jié)構(gòu),、層次結(jié)構(gòu),、網(wǎng)狀結(jié)構(gòu)

1.3 數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語----數(shù)據(jù)、數(shù)據(jù)元素,、數(shù)據(jù)項(xiàng),、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu),、存儲(chǔ)結(jié)構(gòu)

1.4 數(shù)據(jù)結(jié)構(gòu)的發(fā)展及它的地位----為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.5 算法描述的語言及對(duì)算法分析的方法----算法,、算法特征、時(shí)間復(fù)雜度,，空間復(fù)雜度的分析

2．線性表 12 學(xué)時(shí)（6+2+4 ）

2.1 順序表的定義----存儲(chǔ)原理,、運(yùn)算（查找、插入,、刪除）

2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),、運(yùn)算----存儲(chǔ)原理、運(yùn)算（查找,、插入,、刪除）

2.3 循環(huán)鏈、雙向鏈

3．棧和隊(duì)列 8學(xué)時(shí)（6+2）

3.1 棧的邏輯結(jié)構(gòu),、棧的基本運(yùn)算

3.2 隊(duì)列的基本運(yùn)算,、循環(huán)隊(duì)列

3.3 棧與隊(duì)的應(yīng)用

4．?dāng)?shù)組 6學(xué)時(shí)(4+*2)

4.1 數(shù)組的概念

4.2 特殊矩陣、稀疏矩陣的存儲(chǔ)方法

5．串 2學(xué)時(shí)

5.l 串的定義及基本運(yùn)算

5.2 串的存貯結(jié)構(gòu)

5.3 串的基本運(yùn)算的實(shí)現(xiàn)——模式匹配（KMP）

6．樹 12學(xué)時(shí)（6+2+4）

6.1 樹的概念

6.2 二叉樹的概念

6.3 二叉樹的存儲(chǔ)結(jié)構(gòu)

6.4 樹的遍歷

6.5 線索樹——

6.6 樹的存儲(chǔ)結(jié)構(gòu)

6.7 樹,、二叉樹和森林之間的轉(zhuǎn)換

6.8 哈夫曼樹（Huffman）算法及其應(yīng)用（哈夫曼編碼）

7．圖 12學(xué)時(shí)（8+2+2）

7.1 圖的定義,，術(shù)語

7.2 圖的存貯結(jié)構(gòu)——順序鏈?zhǔn)酱鎯?chǔ)

7.3 圖的遍歷

7.4 最小生成樹

7.5 拓?fù)渑判?

7.6 最短路徑

7.7 關(guān)鍵路徑

8．檢索 10學(xué)時(shí)（6+2+2）

8.1 順序檢索,、有序檢索、分塊檢索,、散列表的檢索

8.2 二叉排序樹

8.3 平衡二叉排序樹

* 8.4 B_樹

9．排序 8學(xué)時(shí)（6+2+2）

9.1 插入排序

9.2 快速排序

9.3 選擇排序

9.4 堆排序

9.5 歸并排序

9.6 基數(shù)排序

9.7 內(nèi)部排序方法的比較

9.8 外部排序簡(jiǎn)介

*10．文件 2學(xué)時(shí)

10.l 順序文件

10.2 索引文件

10.3 直接存取文件

10.4 多關(guān)鍵字文件

(二) 學(xué)時(shí)分配

四、課程教學(xué)基本要求及重點(diǎn)

1．?dāng)?shù)據(jù)結(jié)構(gòu)概述：了解數(shù)據(jù)結(jié)構(gòu)研究的對(duì)象,、數(shù)據(jù)結(jié)構(gòu)的發(fā)展及地位,，掌握實(shí)際問題抽象成數(shù)學(xué)模型的概念、數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語和算法描述的語言及算法分析的方法,。具體為：

學(xué)會(huì)分析數(shù)據(jù)結(jié)構(gòu)研究的對(duì)象 ----數(shù)據(jù),、數(shù)據(jù)之間的關(guān)系；

會(huì)將實(shí)際問題抽象成數(shù)學(xué)模型 ----線性結(jié)構(gòu),、層次結(jié)構(gòu),、網(wǎng)狀結(jié)構(gòu)；

掌握數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語 ----數(shù)據(jù),、數(shù)據(jù)元素,、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象,、數(shù)據(jù)結(jié)構(gòu),、存儲(chǔ)結(jié)構(gòu)；

了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展及它的地位 ----為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),；

掌握算法描述的語言及對(duì)算法分析的方法 ----算法,、算法特征、時(shí)間復(fù)雜度,，空間復(fù)雜度的分析,。

重點(diǎn)：概念、算法分析的方法,。

難點(diǎn)：算法分析的方法,。

2．線性結(jié)構(gòu)

熟練掌握順序表的定義、向量 (或一維數(shù)組)的存儲(chǔ),、插入,、刪除元素等運(yùn)算。

掌握鏈?zhǔn)奖淼慕?、插入,、刪除元素等運(yùn)算。

熟悉鏈表的連接,，多項(xiàng)式的加,、減運(yùn)算等操作。

熟悉循環(huán)鏈、雙向鏈的操作,。

重點(diǎn)：概念、基本運(yùn)算實(shí)現(xiàn)方法,。

難點(diǎn)：應(yīng)用,。

3．棧、隊(duì)列

掌握棧的定義,，順序棧存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)綏４鎯?chǔ)結(jié)構(gòu)的建立,、基本操作（運(yùn)算）。

熟悉棧在計(jì)算表達(dá)式中的應(yīng)用,、棧與遞歸過程,。

掌握循環(huán)隊(duì)列的操作和實(shí)現(xiàn)，應(yīng)用,。

熟悉隊(duì)列的定義,，順序隊(duì)列（循環(huán)隊(duì)列）存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)疥?duì)列存儲(chǔ)結(jié)構(gòu)的建立、基本操作（運(yùn)算）,。

熟悉隊(duì)列的應(yīng)用,。

重點(diǎn)：概念、棧和隊(duì)列基本運(yùn)算實(shí)現(xiàn)方法,。

難點(diǎn)：棧和隊(duì)列的應(yīng)用,。

4．?dāng)?shù)組

掌握數(shù)組的定義、數(shù)組的順序表示和實(shí)現(xiàn),；

掌握特殊矩陣： 三角矩陣,、對(duì)稱矩陣及稀疏矩陣的定義、存儲(chǔ)方法,，地址計(jì)算式,；

熟悉稀疏矩陣的十字鏈表存儲(chǔ)方法；

熟悉特殊矩陣的一些算法,。

重點(diǎn)：概念,、存儲(chǔ)方法，地址計(jì)算式,；

難點(diǎn)：應(yīng)用,。

5．串

掌握串的定義及基本運(yùn)算；

掌握串的存貯結(jié)構(gòu),；

掌握串基本運(yùn)算的實(shí)現(xiàn),；

熟悉串的基本運(yùn)算的實(shí)現(xiàn) ----模式匹配（KMP）。

重點(diǎn)：串的定義及基本運(yùn)算,。

6．樹

熟練掌握樹的概念,、二叉樹的概念、二叉樹的性質(zhì)、完全二叉樹,、滿二叉樹的概念和特點(diǎn),；

掌握二叉樹的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)）；

掌握二叉樹的遍歷算法（使用棧的遍歷）前序,、中序和后序,；

掌握線索樹的概念，線索方法,；

掌握樹的存儲(chǔ)結(jié)構(gòu),、樹、二叉樹和森林之間的轉(zhuǎn)換,、哈夫曼樹（ Huffman）算法及其應(yīng)用（哈夫曼編碼）,。

重點(diǎn)：二叉樹的概念、二叉樹的性質(zhì),、完全二叉樹,、滿二叉樹的概念和特點(diǎn)；二叉樹的遍歷,。

難點(diǎn)：遍歷過程,、線索樹的線索方法。

7．圖

熟練掌握?qǐng)D的定義,，術(shù)語,、圖的存貯結(jié)構(gòu)、圖的兩種遍歷方法,；

掌握最小生成樹的 Kruskal和Prim兩種生成過程,，掌握Prim算法。

掌握拓?fù)渑判?、最短路徑,、關(guān)鍵路徑的算法思想。

重點(diǎn)：圖的定義,，術(shù)語,、圖的存貯結(jié)構(gòu)、圖的兩種遍歷方法,；

難點(diǎn)：拓?fù)渑判?、最短路徑、關(guān)鍵路徑的算法思想,。

8．排序

熟練掌握插入排序,、快速排序、選擇排序,、堆排序,、歸并排序和基數(shù)排序的思想,、算法、時(shí)間和空間復(fù)雜度,；

會(huì)對(duì)各種內(nèi)部排序方法進(jìn)行時(shí)間和空間復(fù)雜度的比較,；

熟悉外部排序方法。

重點(diǎn)：插入排序,、快速排序,、選擇排序、堆排序,、歸并排序和基數(shù)排序的思想、算法,、時(shí)間和空間復(fù)雜度分析,。

難點(diǎn)：各排序方法的使用情況和比較。

9．檢索

熟練掌握順序檢索,、二分檢索,、分塊檢索、散列表的檢索的方法,；掌握順序檢索中監(jiān)視哨的作用,。

掌握散列的基本思想、處理沖突常用的方法,；掌握用除余法構(gòu)造散列函數(shù)的方法,、掌握用開放地址法（重點(diǎn)：線性探測(cè)再散列）和拉鏈處理沖突的方法；

掌握二叉排序樹,、平衡二叉排序樹的概念,；掌握二叉排序樹、熟悉平衡二叉排序樹構(gòu)造方法,。

熟悉 B_樹的概念,。

重點(diǎn)：各種檢索的思想、算法,、時(shí)間和空間復(fù)雜度分析,。

難點(diǎn)：二叉排序樹構(gòu)造機(jī)刪除方法、平衡二叉排序樹構(gòu)造方法,。

10．文件

熟悉順序文件,、索引文件、直接存取文件和多關(guān)鍵字文件的概念,。

五,、實(shí)驗(yàn)課時(shí)分配表

主要儀器設(shè)備附表

六、大綱說明及教學(xué)方法建議

1．在教學(xué)內(nèi)容的組織上應(yīng)從靜態(tài),，半靜態(tài)到動(dòng)態(tài)等,，體現(xiàn)出由易到難，循序漸近的教學(xué)原則，使學(xué)生入門容易,，并用實(shí)驗(yàn)加深和鞏固學(xué)生所學(xué)的知識(shí),。

2．在講解中，需要把數(shù)據(jù)結(jié)構(gòu)的說明與某種現(xiàn)有程序設(shè)計(jì)語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)加以區(qū)別,，并且應(yīng)該集中描述數(shù)據(jù)結(jié)構(gòu)的功能,。

3．除了對(duì)每種結(jié)構(gòu)應(yīng)用算法的講解外，還應(yīng)討論資源即時(shí)間和空間的利用,，應(yīng)使學(xué)生能對(duì)這些因素進(jìn)行分析,。

4．注重培養(yǎng)學(xué)生使用數(shù)據(jù)結(jié)構(gòu)編寫實(shí)際應(yīng)用中的問題，提高學(xué)生綜合素質(zhì),。

5．對(duì)帶有“*”的章節(jié)可根據(jù)實(shí)際情況處理,。