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

1、 課程編號15101102數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱ata Structure 一、課程基本信息課程編號15101102適用專業(yè)教育技術(shù)學(xué)、信息工程總學(xué)時數(shù)51實驗學(xué)時18課程類別學(xué)科基礎(chǔ)課教 研 室網(wǎng)絡(luò)與計算機(jī)課程學(xué)分3上機(jī)學(xué)時課程性質(zhì)必修課編 寫 人黃海軍講授學(xué)時36課外學(xué)時8開課學(xué)期3編寫時間2006年7月周學(xué)時數(shù)3見習(xí)學(xué)時二、課程教學(xué)目標(biāo)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。目前在我國，數(shù)據(jù)結(jié)構(gòu)不僅僅是計算機(jī)專業(yè)的教學(xué)計劃中的核心課程之一，而且是其它非計算機(jī)專業(yè)的主要選修課程之一，作為教育技術(shù)學(xué)專業(yè)和和信息工程專業(yè)，也需要較強的計算機(jī)專業(yè)知識，數(shù)據(jù)結(jié)構(gòu)對于后續(xù)專業(yè)課程的學(xué)習(xí)非常重要。三

2、、教學(xué)基本要求本課程系統(tǒng)地介紹數(shù)據(jù)結(jié)構(gòu)的基本概念、操作及典型應(yīng)用例子。通過課堂教學(xué)、課外練習(xí)和上機(jī)實習(xí)，使學(xué)生了解不同數(shù)據(jù)結(jié)構(gòu)的特性，學(xué)會數(shù)據(jù)組織的方法，能根據(jù)所研究的具體問題的要求選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)的算法，并初步掌握算法的時間復(fù)雜度和空間復(fù)雜壓的基本分析方法以及良好的程序設(shè)計技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下扎實的基礎(chǔ)。 1、熟練掌握：要求學(xué)生能夠全面、深入理解和熟練掌握所學(xué)內(nèi)容，并能夠用其知識分析、設(shè)計和解答相關(guān)的應(yīng)用問題。 2、掌握：要求學(xué)生能夠較好地理解和掌握，并且能夠做簡單的分析。 3、了解：要求學(xué)生能夠一般地了解的所學(xué)內(nèi)容?？己朔椒ǎ罕菊n采用平時10%+實驗

3、20%+閉卷30%，為考核成績，百分制。四、本課程的先導(dǎo)課程本課程的先導(dǎo)課程為高級語言程序設(shè)計課程，同時為數(shù)據(jù)庫原理與應(yīng)用、面向?qū)ο蟪绦蛟O(shè)計等后續(xù)專業(yè)課程的學(xué)習(xí)打下基礎(chǔ)。五、教學(xué)方法與手段1、以課堂講授為主，適應(yīng)增加一些課堂討論。2、采用多媒體教學(xué)手段進(jìn)行教學(xué)。3、理論教學(xué)與上機(jī)教學(xué)相結(jié)合，提高學(xué)生的動手實踐能力。六、考核方式與成績評定辦法本課程成績?yōu)槠綍r、上機(jī)、期末三部分組成，其中平時占，上機(jī)占，期末占。如果上機(jī)采用抽考形式，則可作如下調(diào)整：平時占，上機(jī)占，期末占，具體評定辦法見本課程的考試大綱。七、使用教材及參考書目【使用教材】1、嚴(yán)蔚敏、吳偉民 編著，C語言版數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社 2

4、006年2、嚴(yán)蔚敏、吳偉民 編著，C語言版數(shù)據(jù)結(jié)構(gòu)題集，清華大學(xué)出版社 【參考書目】1、張乃孝 編著，C語言版算法與數(shù)據(jù)結(jié)構(gòu)，高等教育出版2、Robert .Kruse, C.L.Tondo, Bruce Leung,Data Structures & program design in C2nd Edition, 清華大學(xué)出版社影印3、李春堡等編，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析，清華大學(xué)出版社2000.1 4、蔡子經(jīng)、施伯樂等編，數(shù)據(jù)結(jié)構(gòu)教程，復(fù)旦大學(xué)出版社 1994 12八、課程結(jié)構(gòu)和學(xué)時分配章節(jié)章節(jié)名稱講授學(xué)時輔導(dǎo)學(xué)時課外學(xué)時作業(yè)(數(shù)量）備注第一章緒論24第二章線性表6224第三章棧和隊列4224第

5、四章串24第五章數(shù)組與廣義表224第六章樹和二叉樹8228第七章圖6226第八章查找22第九章排序424機(jī)動（4）共計36812九、教學(xué)內(nèi)容第一章緒論（學(xué)時）【教學(xué)目標(biāo)】、了解：什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。、了解：什么是數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算三方面的概念及相互關(guān)系。、了解：算法的定義、算法的特性、算法的時間代復(fù)雜度、算法的空間復(fù)雜度。、熟練掌握：用C語言描述算法的方法，能夠使用C語言編寫程序?！局攸c難點】 重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運算三方面的概念及相互關(guān)系。 難點是

6、算法復(fù)雜度的分析方法【教學(xué)內(nèi)容】第一節(jié)什么是數(shù)據(jù)結(jié)構(gòu) 第二節(jié)基本概念和術(shù)語。第三節(jié)抽象數(shù)據(jù)類型的表示與實現(xiàn)第四節(jié)算法和算法分析量一、算法. 二、算法設(shè)計的要求 三、算法效率的度量四、算法的存儲空間需求第二章線性表（學(xué)時）【教學(xué)目標(biāo)】、了解：順序表的含義及特征。、了解：單鏈表的結(jié)構(gòu)、特點。帶表頭結(jié)點的單鏈表的優(yōu)點和類定義及相應(yīng)操作的實現(xiàn)。、了解：鏈表動態(tài)鏈表和靜態(tài)鏈表之分。鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分。、了解：循環(huán)鏈表的特點，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法。、熟練掌握：順序表和單鏈表的插入和刪除算法。、熟練掌握：順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能分析，解

7、決簡單應(yīng)用的問題?！局攸c難點】 重點是熟練掌握順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能分析。 難點是能夠使用本章所學(xué)到的基本知識設(shè)計有效算法解決與線性表相關(guān)的應(yīng)用問題?！窘虒W(xué)內(nèi)容】第一節(jié) 順序表的類型定義第二節(jié) 線性表的順序表示和實現(xiàn)第二節(jié)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)一、線性鏈表. 二、循環(huán)鏈表 三、雙向鏈表*第三節(jié)一元多項式的表示及其相加（選講）第三章棧和隊列（學(xué)時）【教學(xué)目標(biāo)】、熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。特別注意棧空和棧滿的條件。、了解：迷宮問題的遞歸求解思路及如何利用棧實現(xiàn)迷宮問題的非遞歸解法。、熟練掌握：隊列的定義、特性和

8、隊列的抽象數(shù)據(jù)類型，隊列的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。特別是循環(huán)隊列中隊頭與隊尾指針的變化情況?！局攸c難點】 重點是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算。 難點是循環(huán)隊列中對邊界條件的處理?！窘虒W(xué)內(nèi)容】第一節(jié)棧一、棧的抽象數(shù)據(jù)類型的定義. 二、棧的表示和實現(xiàn) 第二節(jié)棧的應(yīng)用舉例一、數(shù)制轉(zhuǎn)換. 二、括號匹配的檢驗 三、行編輯程序四、迷宮求解五、表達(dá)式求解*第三節(jié)棧與遞歸的實現(xiàn)(選講)第四節(jié)隊列一、抽象數(shù)據(jù)類型的定義. 二、鏈隊列 三、循環(huán)隊列*第五節(jié)離散事件模擬(選講)第四章串（學(xué)時）【教學(xué)目標(biāo)】、了解：串類型的定義。、了解：串的存儲表示。、掌握：串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。、掌握：

9、串的基本算法?！局攸c難點】 重點是掌握串上實現(xiàn)的模式匹配算法。 難點是掌握串上實現(xiàn)的模式匹配算法?！窘虒W(xué)內(nèi)容】第一節(jié)串的類型定義第二節(jié)串的表示和實現(xiàn)一、定長順序存儲表示. 二、堆分配存儲表示 三、串的塊存儲表示*第三節(jié)串的模式匹配算法（選講）一、求子串位置的定位函數(shù) 二、模式匹配的一種改進(jìn)算法 第五章數(shù)組和廣義表（學(xué)時）【教學(xué)目標(biāo)】、作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序存儲與按列順序存儲。、了解：數(shù)組的定義，數(shù)組的順序表示和實現(xiàn)、了解：稀疏矩陣的定義及其數(shù)組實現(xiàn)。、了解：廣義表的定義及其實現(xiàn)方法。、掌握：多維數(shù)組的存儲方式、矩陣的壓縮存儲方式。、掌握：廣義表的定義及其求表頭和表尾的運算

10、。、掌握：稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法?！局攸c難點】 重點是熟悉多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其求表頭和表尾的運算。 難點是稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法?！窘虒W(xué)內(nèi)容】第一節(jié)數(shù)組的定義第二節(jié)數(shù)組的順序表示和實現(xiàn)第三節(jié)矩陣的壓縮存儲一、特殊矩陣 二、稀疏矩陣第四節(jié)廣義表第五節(jié)廣義表的存儲結(jié)構(gòu)*第六節(jié)m元多項式的表示(選講)*第七節(jié)廣義表的遞歸算法（選講）一、求廣義表的深度. 二、復(fù)制廣義表 三、建立廣義表的存儲結(jié)構(gòu)第六章樹和二叉樹（學(xué)時）【教學(xué)目標(biāo)】、了解：樹和森林的概念。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型。、掌握：二叉樹的概念、性質(zhì)及二叉樹的表示。、熟練

11、掌握：二叉樹的遍歷方法。、掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法。、掌握：樹與森林的實現(xiàn)，重點在用二叉樹實現(xiàn)。、掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法。、掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法。、掌握：赫夫曼樹的實現(xiàn)方法、構(gòu)造赫夫曼編碼的方法及帶權(quán)路徑長度的計算。 【重點難點】 重點是掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用。 難點是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與樹或二叉樹相關(guān)的應(yīng)用問題?！窘虒W(xué)內(nèi)容】第一節(jié)樹的定義和基本術(shù)語第二節(jié)二叉樹一、二叉樹的定義 二、二叉樹的性質(zhì) 三、二叉樹的存儲結(jié)構(gòu)第三節(jié)遍歷二叉樹和線索二叉樹一、遍歷二叉樹. 二、線索二叉樹

12、第四節(jié)樹和森林一、樹的存儲結(jié)構(gòu). 二、森林與二叉樹的轉(zhuǎn)換 三、樹和森林的遍歷*第五節(jié)樹與等價問題(選講)第六節(jié)赫夫曼樹及其應(yīng)用一、最優(yōu)二叉樹（赫夫曼樹） 二、赫夫曼編碼 *第七節(jié)回溯與樹的遍歷(選講)*第八節(jié)樹的計數(shù) 第七章圖（學(xué)時）【教學(xué)目標(biāo)】、理解：圖的基本概念和圖的抽象數(shù)據(jù)類型。、掌握：圖的3種存儲表示：鄰接矩陣、鄰接表和鄰接多重表。對于前兩種，要求掌握典型操作，如構(gòu)造、求根、找第一個鄰接頂點、找下一個鄰接頂點等操作的實現(xiàn)算法。、熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)。、掌握：構(gòu)造最小生成樹的Prim算法和Kr

13、uskal算法，要求理解算法。、理解：如何用Dijkstra方法求解單源最短路徑問題(不要求算法)。、熟練掌握：活動網(wǎng)絡(luò)的拓?fù)渑判蛩惴?。、掌握：求解關(guān)鍵路徑的方法。【重點難點】 重點是圖的數(shù)組和鄰接表存儲方法，以及圖的深度優(yōu)先和廣度優(yōu)先搜索算法，了解圖的有關(guān)應(yīng)用問題及算法。 難點是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與圖相關(guān)的應(yīng)用問題?！窘虒W(xué)內(nèi)容】第一節(jié)圖的定義和基本術(shù)語第二節(jié)圖的存儲結(jié)構(gòu)一、數(shù)組表示法. 二、鄰接表三、十字鏈表四、鄰接多重表第三節(jié)圖的遍歷一、深度優(yōu)先搜索 二、廣度優(yōu)先搜索第四節(jié)圖的連通性問題一、無向圖的連圖分量 *二、有向圖的連通分量(選講) 三、最小生成樹*四、關(guān)節(jié)

14、點與重連通分量(選講)第五節(jié) 有向無環(huán)圖及其應(yīng)用一、拓?fù)渑判?二、關(guān)鍵路徑第六節(jié) 最短路徑一、從某個源點到其余各頂點的最短路徑 二、每一對頂點之間的最短路徑第九章查找（學(xué)時）【教學(xué)目標(biāo)】、了解：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時的調(diào)整方法及其性能分析。、了解：哈希表的定義。、熟練掌握：靜態(tài)查找表的順序搜索和折半搜索算法及其性能分析方法。、掌握：二叉排序樹的表示、搜索、插入、刪除算法及其性能分析方法。、熟練掌握：散列法，包括散列函數(shù)的構(gòu)造、解決沖突的方法?！局攸c難點】 重點是順序查找、二分查找，二叉查找樹上查找以及哈希表上查找的基本思想和算法實現(xiàn)。 難點是二叉查找樹的刪除算法及B樹上的插入和刪除算法，后者可根據(jù)學(xué)生情況作選講內(nèi)容?！窘虒W(xué)內(nèi)容】第一節(jié)靜態(tài)查找表一、順序表的查找 二、有序表的查找 *三、靜態(tài)樹表的查找(選講)四、索引順序表的查找第二節(jié)動態(tài)查找表一、二叉排序樹和平衡二叉樹（AVL樹）*二、和樹(選講) *三、鍵樹（選講）第三節(jié)哈希表一、什么是哈希表 二、哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法四、哈希表的查找及其分析第十章排序（4學(xué)時）【教學(xué)目標(biāo)】、掌握：排序的基本概念和性能分析方法。、