【文章內(nèi)容簡介】 （三）實驗教學(xué)基本要求通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實驗后學(xué)生提交實驗報告。（四）實驗設(shè)備和材料 計算機(jī)。（五）實驗學(xué)時 2學(xué)時實驗三最小生成樹問題（一）實驗內(nèi)容利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權(quán)值。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實驗后學(xué)生提交實驗報告。（四）實驗設(shè)備和材料 計算機(jī)。（五）實驗學(xué)時 2學(xué)時實驗四哈希表設(shè)計（一）實驗內(nèi)容假設(shè)人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測再散列法處理沖突。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求 掌握索引技術(shù)的使用。（四）實驗設(shè)備和材料 計算機(jī)（五）實驗學(xué)時 4學(xué)時五、課程教學(xué)的基本要求和主要環(huán)節(jié)本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué)。條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué)。每章布置3~6道習(xí)題以鞏固教學(xué)。在課程后半程，安排3~4個上機(jī)實驗，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計幾個較大的軟件，使理論與實際相結(jié)合?？荚嚥捎瞄]卷方式?？偝煽冇善綍r成績和考試成績組成。平時成績占30%，考試成績占70%。六、本課程與其它課程的聯(lián)系與分工先修課包括：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）；后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。七、建議教材與參考教材《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏等清華大學(xué)出版社1997 《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏等清華大學(xué)出版社1999《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》李春葆清華大學(xué)出版社2004八、負(fù)責(zé)人撰稿人：劉景匯、李玉香審稿人：系（院）領(lǐng)導(dǎo)：第四篇：《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱Data Structure 執(zhí)筆人：編寫日期：一、課程基本信息：： 必修課 / 專業(yè)主干課： 48 學(xué)時（另實驗16學(xué)時）/ 4 學(xué)分：計算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息管理與信息系統(tǒng)等專業(yè)二、課程教學(xué)目標(biāo)及學(xué)生應(yīng)達(dá)到的能力數(shù)據(jù)結(jié)構(gòu)課程是計算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計算機(jī)解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲表示、運(yùn)算方法以及在計算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實踐基礎(chǔ)。三、課程教學(xué)內(nèi)容與基本要求（一）緒論（3 學(xué)時）1．主要內(nèi)容：（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；（3）抽象數(shù)據(jù)類型的表示與實現(xiàn)；（4）算法和算法分析: 算法的概念、算法設(shè)計的要求以及算法效率的度量。2．基本要求（1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)方法；（4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。3．自學(xué)內(nèi)容：類C語言的書寫規(guī)范。（二）線性表（6 學(xué)時）1．主要內(nèi)容：（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯Ρ硎竞突静僮鞯膶崿F(xiàn)；（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。2．基本要求（1）掌握線性表的定義和特點(diǎn)；（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現(xiàn)算法；（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實現(xiàn)算法。3．自學(xué)內(nèi)容：靜態(tài)鏈表。（三）棧和隊列（5 學(xué)時）1．主要內(nèi)容：（1）棧和隊列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實現(xiàn)；（3）棧和隊列的鏈?zhǔn)酱鎯Ρ硎竞蛯崿F(xiàn)；（4）棧和隊列在程序設(shè)計中的應(yīng)用。2．基本要求（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點(diǎn)；（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿?？盏臈l件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關(guān)系。3．自學(xué)內(nèi)容：鏈棧，離散事件模擬（四）串（3 學(xué)時）1．主要內(nèi)容：（1）串的抽象數(shù)據(jù)類型定義；（2）串的表示和實現(xiàn): 定長順序存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；（3）串的各種基本操作的實現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。2．基本要求（1）熟悉串的一些基本操作的定義，并能利用基本操作實現(xiàn)串的其它操作；（2）掌握串的定長順序存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（3）掌握串的堆分配存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（4）掌握串的簡單模式匹配算法，理解KMP算法。3．自學(xué)內(nèi)容：串操作的應(yīng)用實例。（五）數(shù)組和廣義表（4 學(xué)時）1．主要內(nèi)容：（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu)。2．基本要求（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；（2）掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式；（3）熟悉稀疏矩陣的三元組順序表存儲結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲結(jié)構(gòu)；（4）掌握廣義表的結(jié)構(gòu)特點(diǎn)、取表頭表尾操作，及其存儲表示方法。3．自學(xué)內(nèi)容：采用十字鏈表存儲結(jié)構(gòu)創(chuàng)建稀疏矩陣。（六）樹和二叉樹（10 學(xué)時）1．主要內(nèi)容：（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲結(jié)構(gòu)；（3）二叉樹的遍歷；（4）線索二叉樹的定義、遍歷及線索化二叉樹；（5）樹的存儲結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。2．基本要求（1）掌握樹型結(jié)構(gòu)的特點(diǎn)和基本術(shù)語；（2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；（3）了解二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，熟練掌握二叉鏈表存儲結(jié)構(gòu)；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運(yùn)用遍歷算法實現(xiàn)二叉樹的其他操作；（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點(diǎn)的前驅(qū)與后繼的方法；（6）熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學(xué)內(nèi)容：先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。（七）圖（9 學(xué)時）1．主要內(nèi)容：（1）圖的定義和術(shù)語；（2）圖的四種存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；（5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。2．基本要求（1）熟悉圖的定義和術(shù)語；（2）了解圖的存儲結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法；（6）熟悉兩種最短路徑問題求解算法。3．自學(xué)內(nèi)容：樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。（八）查找（4 學(xué)時）1．主要內(nèi)容：（1）查找的基本概念和相關(guān)術(shù)語；（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(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é)時）1．主要內(nèi)容：（1）排序的基本概念和相關(guān)術(shù)語；（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較