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

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

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

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

4、006年2、嚴(yán)蔚敏、吳偉民 編著，C語(yǔ)言版數(shù)據(jù)結(jié)構(gòu)題集，清華大學(xué)出版社 【參考書目】1、張乃孝 編著，C語(yǔ)言版算法與數(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)、施伯樂(lè)等編，數(shù)據(jù)結(jié)構(gòu)教程，復(fù)旦大學(xué)出版社 1994 12八、課程結(jié)構(gòu)和學(xué)時(shí)分配章節(jié)章節(jié)名稱講授學(xué)時(shí)輔導(dǎo)學(xué)時(shí)課外學(xué)時(shí)作業(yè)(數(shù)量）備注第一章緒論24第二章線性表6224第三章棧和隊(duì)列4224第

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

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

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

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

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

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

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

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

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

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