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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱Data Structure執(zhí)筆人：編寫日期：一、課程基本信息1. 課程編號(hào)：2. 課程性質(zhì) / 類別： 必修課 / 專業(yè)主干課3. 學(xué)時(shí) / 學(xué)分：48 學(xué)時(shí)（另實(shí)驗(yàn)16 學(xué)時(shí)）/4 學(xué)分4. 適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息管理與信息系統(tǒng)等專業(yè)二、課程教學(xué)目標(biāo)及學(xué)生應(yīng)達(dá)到的能力數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計(jì)算機(jī)解決一系列問題特別是非數(shù)值信息處理問題時(shí)所用的各種組織數(shù)據(jù)的方法、存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、 運(yùn)算方法以及在計(jì)算機(jī)科學(xué)中最基本

2、的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。三、課程教學(xué)內(nèi)容與基本要求（一）緒論（3 學(xué)時(shí)）1主要內(nèi)容：（ 1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；（ 2）基本概念和術(shù)語 : 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；（ 3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；（ 4）算法和算法分析 : 算法的概念、算法設(shè)計(jì)的要求以及算法效率的度量。2基本要求（ 1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；（ 2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（ 3）了解抽象數(shù)據(jù)類型的定義、

3、表示與實(shí)現(xiàn)方法；（ 4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。3自學(xué)內(nèi)容：類 C 語言的書寫規(guī)范。（二）線性表（ 6 學(xué)時(shí)）1主要內(nèi)容：（ 1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項(xiàng)、記錄、文件等；（ 2）線性表順序存儲(chǔ)表示和基本操作的實(shí)現(xiàn)；（ 3）線性表的鏈?zhǔn)酱鎯?chǔ)表示和基本操作的實(shí)現(xiàn)；（ 4）稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。2基本要求（ 1）掌握線性表的定義和特點(diǎn)；（ 2）熟練掌握線性表的順序存儲(chǔ)表示和插入、刪除、查找等實(shí)現(xiàn)算法；（ 3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實(shí)現(xiàn)算法。3自學(xué)內(nèi)容：靜態(tài)鏈表。（三）棧

4、和隊(duì)列（5 學(xué)時(shí)）1主要內(nèi)容：（ 1）棧和隊(duì)列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（ 2）棧和隊(duì)列的順序存儲(chǔ)表示和實(shí)現(xiàn)；（ 3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)；（ 4）棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。2基本要求（ 1）掌握棧和隊(duì)列兩種抽象數(shù)據(jù)類型的特點(diǎn)；（ 2）掌握棧的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意棧滿?？盏臈l件；（ 3）掌握隊(duì)列的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意隊(duì)滿隊(duì)空的條件；（ 4）了解遞歸算法與棧的關(guān)系。3自學(xué)內(nèi)容：鏈棧，離散事件模擬（四）串（3 學(xué)時(shí)）1主要內(nèi)容：（ 1）串的抽象數(shù)據(jù)類型定義；（ 2）串的表示和實(shí)現(xiàn) : 定長順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；（ 3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（ 4）串

5、的模式匹配操作。2基本要求（ 1）熟悉串的一些基本操作的定義，并能利用基本操作實(shí)現(xiàn)串的其它操作；（ 2）掌握串的定長順序存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（ 3）掌握串的堆分配存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（ 4）掌握串的簡單模式匹配算法，理解KMP 算法。3自學(xué)內(nèi)容：串操作的應(yīng)用實(shí)例。（五）數(shù)組和廣義表（4 學(xué)時(shí)）1主要內(nèi)容：（ 1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)；（ 2）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)；（ 3）廣義表的抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)。2基本要求（ 1）了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；（ 2）掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；

6、（ 3）熟悉稀疏矩陣的三元組順序表存儲(chǔ)結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲(chǔ)結(jié)構(gòu)；（ 4）掌握廣義表的結(jié)構(gòu)特點(diǎn)、取表頭表尾操作，及其存儲(chǔ)表示方法。3自學(xué)內(nèi)容：采用十字鏈表存儲(chǔ)結(jié)構(gòu)創(chuàng)建稀疏矩陣。（六）樹和二叉樹（10 學(xué)時(shí)）1主要內(nèi)容：（ 1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；（ 2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；（ 3）二叉樹的遍歷；（ 4）線索二叉樹的定義、遍歷及線索化二叉樹；（ 5）樹的存儲(chǔ)結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（ 6） Huffman 樹及其應(yīng)用。2基本要求（ 1）掌握樹型結(jié)構(gòu)的特點(diǎn)和基本術(shù)語；（ 2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；（

7、3）了解二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，熟練掌握二叉鏈表存儲(chǔ)結(jié)構(gòu)；（ 4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；（ 5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點(diǎn)的前驅(qū)與后繼的方法；（ 6）熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（ 7）了解 Huffman 樹的特性，掌握建立Huffman 樹和 Huffman 編碼的方法。3自學(xué)內(nèi)容：先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。（七）圖（9 學(xué)時(shí)）1主要內(nèi)容：（ 1）圖的定義和術(shù)語；（ 2）圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表

8、、十字鏈表和鄰接多重表；（ 3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（ 4）圖的連通性和最小生成樹；（ 5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（ 6）最短路徑問題。2基本要求（ 1）熟悉圖的定義和術(shù)語；（ 2）了解圖的存儲(chǔ)結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲(chǔ)表示；（ 3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（ 4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；（ 5）了解有向無環(huán)圖、 AOV 網(wǎng)、 AOE 網(wǎng)及其在實(shí)際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法；（ 6）熟悉兩種最短路徑問題求解算法。3自學(xué)內(nèi)容：樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；樹的層次遍歷

9、算法與圖的廣度優(yōu)先遍歷算法比較。（八）查找（4 學(xué)時(shí)）1主要內(nèi)容：（ 1）查找的基本概念和相關(guān)術(shù)語；（ 2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（ 3）動(dòng)態(tài)查找表：二叉排序樹的查找、插入和刪除；（ 4）哈希表。2基本要求（ 1）了解查找的作用，熟悉相關(guān)術(shù)語；（ 2）熟練掌握順序查找、折半查找和索引順序表查找；（ 3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；（ 4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選?。唬?5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3自學(xué)內(nèi)容：平衡二叉樹。（九）內(nèi)部排序（4 學(xué)時(shí)）1主要內(nèi)容：（ 1）排序的基本概念和相關(guān)術(shù)語

10、；（ 2）插入排序：直接插入排序、折半插入排序和希爾排序；（ 3）交換排序：起泡排序和快速排序；（ 4）選擇排序：簡單選擇排序和堆排序；（ 5）歸并排序：二路歸并排序；（ 6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（ 7）各種內(nèi)部排序方法的比較討論。2基本要求（ 1）了解排序作用，熟悉相關(guān)術(shù)語；（ 2）掌握多種排序的基本思想、算法特點(diǎn)和排序過程，分析它們的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。3自學(xué)內(nèi)容：二路插入排序、表插入排序和樹形選擇排序。四、教學(xué)安排建議1. 作業(yè)練習(xí)完成每章的教學(xué)后進(jìn)行布置習(xí)題，使用教材配套的數(shù)據(jù)結(jié)構(gòu)題集（C 語言版）。盡量選擇基礎(chǔ)的并且加注了標(biāo)記的題，應(yīng)注重于精， 而不要求多。 要求積極

11、獨(dú)立完成所布置的習(xí)題，建議安排至少六次。2. 案例分析可參考選擇以下一些案例： （ 1）學(xué)生通訊錄管理系統(tǒng)， （ 2）表達(dá)式求值問題（ 3）交通咨詢系統(tǒng)，等。3. 專題研討可參考選擇以下一些： （ 1）最小生成樹問題（ 2）航班信息查詢與檢索系統(tǒng)， （3）內(nèi)部排序算法比較，等。4. 實(shí)驗(yàn)安排為了達(dá)到理論與實(shí)際應(yīng)用的結(jié)合，讓學(xué)生能將所學(xué)知識(shí)應(yīng)用于實(shí)際問題的求解中，培養(yǎng)學(xué)生的實(shí)際動(dòng)手能力，從而加深對(duì)概念及所學(xué)知識(shí)的理解，靈活、牢固掌握教材內(nèi)容，提高程序設(shè)計(jì)及解決實(shí)際問題的能力，實(shí)驗(yàn)環(huán)節(jié)的安排非常重要。建議實(shí)驗(yàn)安排為八次，共16 學(xué)時(shí)，分別如下：實(shí)驗(yàn) 1線性表的順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時(shí) )實(shí)驗(yàn) 2

12、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時(shí) )實(shí)驗(yàn) 3棧的算法實(shí)現(xiàn) (2學(xué)時(shí) )實(shí)驗(yàn) 4隊(duì)列的算法實(shí)現(xiàn) (2學(xué)時(shí) )實(shí)驗(yàn) 5串類型及操作 (2學(xué)時(shí) )實(shí)驗(yàn) 6二叉樹的建立與遍歷(2學(xué)時(shí) )實(shí)驗(yàn) 7圖的建立與遍歷 (2學(xué)時(shí) )實(shí)驗(yàn) 8查找與排序 (2學(xué)時(shí) )注：教師可根據(jù)教學(xué)實(shí)際情況（如：學(xué)生情況及學(xué)時(shí)情況等），適當(dāng)調(diào)整實(shí)踐教學(xué)內(nèi)容及學(xué)時(shí)分配。五、課程考核1. 考核形式及成績評(píng)定辦法本課程考核形式為： 平時(shí)成績占 40%，期末考試成績占 60%。其中平時(shí)成績的結(jié)構(gòu)分包括：課堂表現(xiàn) 10%、平時(shí)作業(yè) 10%和實(shí)驗(yàn) 20%，期末考試為閉卷筆試考試： 120 分鐘，卷面分滿分 100 分。期末考試成績低于 5

13、0 分者，本課程成績按不及格論處。2. 本課程考核的基本要求課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時(shí)達(dá)到本課程教學(xué)時(shí)數(shù)的1/3，則取消考試資格。平時(shí)作業(yè) 10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評(píng)定。實(shí)驗(yàn) 20%：根據(jù)各次實(shí)驗(yàn)完成情況及實(shí)驗(yàn)報(bào)告成績進(jìn)行評(píng)定。期末考試 60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊(duì)列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點(diǎn)。六、本課程與其它課程的先行后續(xù)關(guān)系先行課程：高級(jí)程序設(shè)計(jì)語言 、離散數(shù)學(xué)后續(xù)課程：操作系統(tǒng)、編譯原理、數(shù)據(jù)庫理論 、算法分析與設(shè)計(jì)等七、建議教材及教學(xué)參考書1.

14、 教材：嚴(yán)蔚敏，吳偉民編著， 數(shù)據(jù)結(jié)構(gòu)（ C 語言版），清華大學(xué)出版，2012.5嚴(yán)蔚敏，吳偉民編著， 數(shù)據(jù)結(jié)構(gòu)題集（ C 語言版），清華大學(xué)出版， 2012.5 2.參考書：1 許卓群，張乃孝，楊冬青，唐世渭， 數(shù)據(jù)結(jié)構(gòu)，高等教育出版社， 2004.2 徐孝凱，數(shù)據(jù)結(jié)構(gòu)簡明教程 ，清華大學(xué)出版社， 19953 陳文博，朱青， 數(shù)據(jù)結(jié)構(gòu)與算法 ，機(jī)械工業(yè)出版社， 19964 李云清，楊慶紅，揭安全編著， 數(shù)據(jù)結(jié)構(gòu)（ C 語言版），人民郵電出版社， 2007.5 楊秀金主編，數(shù)據(jù)結(jié)構(gòu)，西安電子科技大學(xué)出版社， 2002.6 李廉治，姜文清，郭福順， 數(shù)據(jù)結(jié)構(gòu)，大連理工大學(xué)出版社， 19897 Aho A V, Hopcroft J E, Ullman J D. Data Structures and Algorithms. Addison-Wesley Publishing Company,Inc.,19838 Baron