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

PAGE1PAGE1“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)大綱課程編號(hào)：08051060課程名稱：數(shù)據(jù)結(jié)構(gòu)/DataStructures學(xué)時(shí)：48學(xué)分：3適用專業(yè)：計(jì)算機(jī)相關(guān)專業(yè)開課學(xué)期：2開課部門：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院先修課程：C/C++語(yǔ)言程序設(shè)計(jì)考核要求：考試使用教材及主要參考書：王紅梅編，《數(shù)據(jù)結(jié)構(gòu)（C++版）（第2版）》，清華大學(xué)出版社，2011年王紅梅編，《數(shù)據(jù)結(jié)構(gòu)（C++版）學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)（第2版）》，清華大學(xué)出版社，2011年管致錦、徐慧編，《數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社，2010年陳德裕主編，《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題集》,清華大學(xué)出版社,2010年徐慧主編，《數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程》,清華大學(xué)出版社,2010年一、課程的性質(zhì)和任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門必修課程。本課程主要介紹如何合理地組織數(shù)據(jù)、有效地存儲(chǔ)和處理數(shù)據(jù)，正確地設(shè)計(jì)算法以及對(duì)算法的分析和評(píng)價(jià)。內(nèi)容包括：線性表和鏈表、棧和隊(duì)列、多維數(shù)組、廣義表、樹和二叉樹、圖、堆與優(yōu)先級(jí)隊(duì)列、集合、搜索結(jié)構(gòu)、排序、索引與散列結(jié)構(gòu)等。課程采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過(guò)程和面向?qū)ο箅p重特色的C++語(yǔ)言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和面向?qū)ο蟪绦蛟O(shè)計(jì)基本能力的雙重訓(xùn)練。通過(guò)本課程的學(xué)習(xí)，使學(xué)生深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能，編制高效可靠的程序，為后續(xù)計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。二、教學(xué)目的與要求1、掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實(shí)現(xiàn)技術(shù)；2、學(xué)會(huì)做簡(jiǎn)單的算法分析，包括算法的時(shí)間代價(jià)和空間代價(jià)。三、學(xué)時(shí)分配章節(jié)課程內(nèi)容學(xué)時(shí)1緒論42線性表63棧和隊(duì)列64字符串和多維數(shù)組45樹和二叉樹86圖87查找技術(shù)48排序技術(shù)49索引技術(shù)4四、教學(xué)中應(yīng)注意的問題本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，內(nèi)容多且?guī)в幸欢ǖ某橄笮?，學(xué)習(xí)起來(lái)有一定難度。盡可能利用多種媒體進(jìn)行教學(xué)，使學(xué)生能夠很快掌握課程的主要知識(shí)和解決問題的方法。本課程教學(xué)過(guò)程中，面授輔導(dǎo)和答疑是必不可少的教學(xué)環(huán)節(jié)。以習(xí)題課、專題討論或答疑的方式，對(duì)課程中的重要概念和典型問題的解決方法進(jìn)行總結(jié)和深入討論，鞏固和加深課堂內(nèi)學(xué)到的知識(shí)。自學(xué)是獲取知識(shí)的重要手段。教師講課只是起到拋磚引玉的作用，關(guān)鍵還在于學(xué)生的自學(xué)。為達(dá)到自學(xué)的效果，除讀懂教科書中所講內(nèi)容外，還需大量做題。其目的是要通過(guò)做題弄懂、加深對(duì)概念的理解，提高程序設(shè)計(jì)，解決問題的能力。除學(xué)校提供的時(shí)間外，要求課外學(xué)生利用自己可能擁有的計(jì)算機(jī)條件，完成更多的練習(xí)，不通過(guò)大量的實(shí)踐，能力和知識(shí)水平得不到有效得提高。五、教學(xué)內(nèi)容第一章：緒論1．基本內(nèi)容什么是數(shù)據(jù)結(jié)構(gòu)？抽象數(shù)據(jù)類型及面向?qū)ο蟾拍睿簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；描述?shù)據(jù)結(jié)構(gòu)的語(yǔ)言數(shù)據(jù)結(jié)構(gòu)的抽象層次；算法定義；性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度的漸進(jìn)表示法；漸進(jìn)的空間復(fù)雜度2．教學(xué)基本要求了解：什么是數(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ù)抽象和信息隱蔽原則。了解什么是面向?qū)ο罅私猓核惴ǖ亩x、算法的特性、算法的時(shí)間代價(jià)、算法的空間代價(jià)掌握：用C++語(yǔ)言描述算法的方法，能夠使用C++語(yǔ)言編寫程序3．教學(xué)重點(diǎn)難點(diǎn)用C++語(yǔ)言描述算法的方法4．教學(xué)建議注意使用案例教學(xué)法第二章：線性表1．基本內(nèi)容順序表：順序表的定義和特點(diǎn)；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例單鏈表：?jiǎn)捂湵淼慕Y(jié)構(gòu)；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點(diǎn)的單鏈表；用模板定義的單鏈表類；靜態(tài)鏈表、循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；多項(xiàng)式及其相加：多項(xiàng)式的類定義；多項(xiàng)式的加法

2．教學(xué)基本要求了解：線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲(chǔ)實(shí)現(xiàn)方式熟練掌握：順序表的定義與實(shí)現(xiàn)，包括搜索、插入、刪除算法的實(shí)現(xiàn)及其平均比較次數(shù)的計(jì)算，掌握應(yīng)用順序表作為集合的簡(jiǎn)單操作了解：鏈表與數(shù)組一樣，是一種實(shí)現(xiàn)級(jí)結(jié)構(gòu)。有動(dòng)態(tài)鏈表和靜態(tài)鏈表之分了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分了解：?jiǎn)捂湵淼慕Y(jié)構(gòu)、特點(diǎn)掌握：?jiǎn)捂湵淼念惗x、構(gòu)造函數(shù)、單鏈表的插入與刪除算法了解：帶表頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)和類定義及相應(yīng)操作的實(shí)現(xiàn)熟練掌握：用模板定義的單鏈表類了解：循環(huán)鏈表的特點(diǎn)，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法掌握：雙向鏈表的特點(diǎn)，雙向鏈表的類定義及相關(guān)操作的實(shí)現(xiàn)，用雙向鏈表解決問題的方法。3．教學(xué)重點(diǎn)難點(diǎn)鏈表的存儲(chǔ)實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第三章：棧和隊(duì)列1．基本內(nèi)容棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲(chǔ)表示；棧的鏈接存儲(chǔ)表示表達(dá)式求值：中綴表達(dá)式求值；中綴表示到后綴表示的轉(zhuǎn)換隊(duì)列：隊(duì)列的抽象數(shù)據(jù)類型；隊(duì)列的順序存儲(chǔ)表示；隊(duì)列的鏈接存儲(chǔ)表示；隊(duì)列的應(yīng)用舉例優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義；優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示

2．教學(xué)基本要求熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別注意?？蘸蜅M的條件了解：在表達(dá)式計(jì)算時(shí)棧是如何使用的，重點(diǎn)了解用后綴表示計(jì)算表達(dá)式及中綴表示改后綴表示的方法和算法思路熟練掌握：隊(duì)列的定義、特性和隊(duì)列的抽象數(shù)據(jù)類型，隊(duì)列的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況掌握：優(yōu)先級(jí)隊(duì)列的定義、特性和優(yōu)先級(jí)隊(duì)列的抽象數(shù)據(jù)類型，優(yōu)先級(jí)隊(duì)列的插入與刪除算法教學(xué)重點(diǎn)難點(diǎn)棧和隊(duì)列的存儲(chǔ)實(shí)現(xiàn)以及相關(guān)操作的實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第四章：字符串和多維數(shù)組1．基本內(nèi)容字符串：字符串的抽象數(shù)據(jù)類型；字符串操作的實(shí)現(xiàn)；字符串的模式匹配作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義和初始化；作為抽象數(shù)據(jù)類型的數(shù)組；數(shù)組的順序存儲(chǔ)方式廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)；廣義表的訪問算法；廣義表的遞歸算法

2．教學(xué)基本要求熟練掌握：字符串的定義及實(shí)現(xiàn)了解：作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序存儲(chǔ)與按列順序存儲(chǔ)了解：稀疏矩陣的定義及其數(shù)組實(shí)現(xiàn)掌握：廣義表的定義及其實(shí)現(xiàn)方法掌握：廣義表的遞歸算法3．教學(xué)重點(diǎn)難點(diǎn)字符串的實(shí)現(xiàn)和稀疏矩陣的實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第五章：樹和二叉樹1．基本內(nèi)容樹和森林的概念：樹的定義；樹的術(shù)語(yǔ)；樹的抽象數(shù)據(jù)類型二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型二叉樹的表示：順序表示；二叉鏈表表示遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹遍歷的事例；二叉樹的計(jì)數(shù)

線索化二叉樹：線索；中序線索化二叉樹堆：堆的定義；堆的建立；堆的插入與刪除；堆的調(diào)整算法樹與森林：樹的存儲(chǔ)表示；森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林霍夫曼樹：路徑長(zhǎng)度；霍夫曼樹；霍夫曼編碼2．教學(xué)基本要求了解：樹和森林的概念。包括樹的定義、樹的術(shù)語(yǔ)、樹的抽象數(shù)據(jù)類型掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來(lái)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法掌握：樹與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹實(shí)現(xiàn)掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法掌握：二叉樹的計(jì)數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：哈夫曼樹的實(shí)現(xiàn)方法、構(gòu)造哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算3．教學(xué)重點(diǎn)難點(diǎn)二叉樹的存儲(chǔ)和基本操作實(shí)現(xiàn)、哈夫曼樹的實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第六章：圖1．基本內(nèi)容圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的存儲(chǔ)表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點(diǎn)與重連通分量最小生成樹：kruskul算法；prim算法單源最短路徑問題：dijkstra算法活動(dòng)網(wǎng)絡(luò)：AOV網(wǎng)絡(luò)與拓?fù)渑判?；AOE網(wǎng)絡(luò)與關(guān)鍵路徑2．教學(xué)基本要求理解：圖的基本概念和圖的抽象數(shù)據(jù)類型掌握：圖的3種存儲(chǔ)表示：鄰接矩陣、鄰接表和鄰接多重表。對(duì)于前兩種，要求掌握典型操作，如構(gòu)造、求根、找第一個(gè)鄰接頂點(diǎn)、找下一個(gè)鄰接頂點(diǎn)等操作的實(shí)現(xiàn)算法熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)理解：求解關(guān)節(jié)點(diǎn)及構(gòu)造重連通圖的方法(不要求算法)掌握：構(gòu)造最小生成樹的Prim算法和Kruskal算法，要求理解算法理解：如何用Dijkstra方法求解單源最短路徑問題(不要求算法)熟練掌握：活動(dòng)網(wǎng)絡(luò)的拓?fù)渑判蛩惴ㄕ莆眨呵蠼怅P(guān)鍵路徑的方法3．教學(xué)重點(diǎn)難點(diǎn)圖的存儲(chǔ)和基本操作實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第七章：查找技術(shù)1．基本內(nèi)容簡(jiǎn)單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除AVL樹：AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析2．教學(xué)基本要求熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法掌握：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時(shí)的調(diào)整方法及其性能分析熟練掌握：散列法，包括散列函數(shù)的構(gòu)造、處理沖突的方法3．教學(xué)重點(diǎn)難點(diǎn)基本查找算法的實(shí)現(xiàn)4．教學(xué)建議注意使用案例教學(xué)法第八章：排序技術(shù)1．基本內(nèi)容插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序交換排序：起泡排序；快速排序選擇排序：直接選擇排序；錦標(biāo)賽排序；堆排序歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序外排序：外排序的基本過(guò)程；k路平衡歸并；初始?xì)w并段的生成；最佳歸并樹2．教學(xué)基本要求掌握：排序的基本概念和性能分析方法掌握：插入排序、交換排序、選擇排序、歸并排序等內(nèi)排序的方法及其性