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

1、材料5:數(shù)據(jù)結(jié)構(gòu)理論教學(xué)大綱數(shù)據(jù)結(jié)構(gòu)理論教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)（Data Structure）學(xué)分/總學(xué)時(shí)：4/54+36開(kāi)課單位：計(jì)算機(jī)科學(xué)與工程學(xué)院一、課程的性質(zhì)、目的和任務(wù)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。算法與數(shù)據(jù)結(jié)構(gòu)的 研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法等）的研究范 圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無(wú)論是編譯程序還是操作系統(tǒng)， 都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問(wèn)題。在研究信息檢索時(shí)也必須考慮如何組織 數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。因此，可以認(rèn)為算法與數(shù)據(jù)結(jié)構(gòu)是介于 數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程，在計(jì)

2、算機(jī)科學(xué)中，數(shù)據(jù) 結(jié)構(gòu)不僅是一般程序設(shè)計(jì)（特別是非數(shù)值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和 實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程作為計(jì)算機(jī)專業(yè)重要的主干課程，它要求學(xué)生學(xué)會(huì)分析和研 究需解決的問(wèn)題中的數(shù)據(jù)的特性，為其選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)描述，在此數(shù)據(jù)結(jié)構(gòu) 的基礎(chǔ)上寫出相應(yīng)的算法，并初步掌握算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析技 術(shù)。另一方面，通過(guò)本課程的學(xué)習(xí)，培養(yǎng)和訓(xùn)練學(xué)生編寫復(fù)雜程序的能力，要求編 寫的程序結(jié)構(gòu)清楚、正確易讀，符合軟件工程的規(guī)范，使學(xué)生的編程能力有一個(gè)質(zhì) 的提高。二、學(xué)習(xí)本課程學(xué)生應(yīng)掌握的前設(shè)課程知識(shí)本課程的先行課程有：計(jì)算機(jī)導(dǎo)論

3、、C語(yǔ)言程序設(shè)計(jì)、離散數(shù) 學(xué)。三、學(xué)時(shí)分配課程授課時(shí)間為90學(xué)時(shí)，其中講課54學(xué)時(shí)，實(shí)驗(yàn)36學(xué)時(shí)早節(jié)學(xué) 時(shí)理論實(shí)驗(yàn)合計(jì)氏U 第一早224第二早7411第三章549第四章204第五早448第八早10616第七章10616第八章8612第九章6410合計(jì)543690四、課程內(nèi)容和基本要求1緒論（2+2學(xué)時(shí)）1 數(shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語(yǔ)2 抽象數(shù)據(jù)類型3 算法與算法分析基本要求：熟悉數(shù)據(jù)結(jié)構(gòu)中各名詞、術(shù)語(yǔ)的含義，掌握其基本概念；理解數(shù)據(jù)類型和抽象 數(shù)據(jù)類型的含義；理解算法五個(gè)要素的確切含義，注意算法與程序的區(qū)別；掌握計(jì) 算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。2線性表（7+4學(xué)時(shí)）1 線性表的概念2

4、 線性表的順序存儲(chǔ)和實(shí)現(xiàn)3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)4 循環(huán)鏈表和雙向鏈表5 線性表的具體應(yīng)用基本要求：了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示 這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；熟練掌握這兩類 存儲(chǔ)結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)；能夠從時(shí)間和空間復(fù)雜 度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合；掌握用線性表來(lái) 表示一兀多項(xiàng)式的方法及相應(yīng)操作的實(shí)現(xiàn)。3. 棧和隊(duì)列（5+4學(xué)時(shí)）1 順序棧和鏈棧的表示和基本操作2 棧的應(yīng)用3 鏈?zhǔn)疥?duì)列的表示和基本操作4 循環(huán)隊(duì)列的表示和基本操作隊(duì)列的應(yīng)用基本要求：掌握棧和隊(duì)列類型的特

5、點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；熟練掌握 棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法；熟練 掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法；理 解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。4. 串（2學(xué)時(shí)）1 串的定義2 串的表示和實(shí)現(xiàn)3串的模式匹配算法基本要求：熟悉串的定義及串的基本操作；熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的 各種操作的方法；了解串的堆存儲(chǔ)結(jié)構(gòu)及塊鏈存儲(chǔ)結(jié)構(gòu)；掌握串的模式匹配算法的 基本算法和改進(jìn)算法。5. 數(shù)組（4+4學(xué)時(shí)）1 數(shù)組的定義2 數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)3 稀疏矩陣的壓縮存儲(chǔ)表示和實(shí)現(xiàn)4 廣義表的基本概念基本要

6、求：了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì) 算方法；掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；了解稀疏矩陣的三類壓 縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的 處理方法；了解廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法。6. 樹(shù)和二叉樹(shù)（10+6學(xué)時(shí)）1 樹(shù)和二叉樹(shù)的基本概念2 二叉樹(shù)的性質(zhì)3 二叉樹(shù)的存儲(chǔ)表示和實(shí)現(xiàn)4 二叉樹(shù)的遍歷算法5 線索二叉樹(shù)6 樹(shù)和森林的存儲(chǔ)表示和實(shí)現(xiàn)7 樹(shù)和森林與二叉樹(shù)之間的相互轉(zhuǎn)換8 Huffman算法的實(shí)現(xiàn)和Huffman編碼基本要求：熟練掌握二叉樹(shù)的結(jié)構(gòu)特性（五個(gè)性質(zhì)），了解相應(yīng)的證明方法；熟悉二叉樹(shù)的 各種存

7、儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)，熟練掌握 各種遍歷策略的遞歸算法，了解其非遞歸算法；理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié) 點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹(shù)的線索化過(guò)程 以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及 其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)之間的相互轉(zhuǎn)換方法；了解Huffman樹(shù)的特性，掌握建立Huffman樹(shù)和Huffman編碼的算法。7. 圖（10+6學(xué)時(shí)）1 圖的基本概念2 圖的存儲(chǔ)結(jié)構(gòu)3 圖的遍歷算法4 求最小生成樹(shù)的Prim算法和Kruskal算法5 求最短路徑的Dijkstra算法和Floyd算法拓?fù)渑判?/p>

8、和關(guān)鍵路徑基本要求：熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存 儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系；熟練掌握?qǐng)D的兩種搜索路徑（深度優(yōu)先和廣度優(yōu)先）的 遍歷算法，注意圖的遍歷算法與樹(shù)的遍歷算法之間的類似和差異；熟練掌握求最小 生成樹(shù)的Prim算法和Kruskal算法；熟練掌握求最短路徑的 Dijkstra算法，了解求 任意兩點(diǎn)之間的最短路徑的 Floyd算法；掌握求拓?fù)渑判虻乃惴捌鋺?yīng)用，了解求 關(guān)鍵路徑的方法及其應(yīng)用。8. 查找（8+6學(xué)時(shí)）1 查找表的基本概念2 順序查找算法和折半查找算法3 二叉排序樹(shù)及有關(guān)算法4 平衡二叉樹(shù)及有關(guān)算法5 B-樹(shù)和B+樹(shù)哈希表基本要求：熟練掌握

9、順序表和有序表的查找方法及其平均查找長(zhǎng)度的計(jì)算方法；熟練掌握 二叉排序樹(shù)的構(gòu)造和查找方法，掌握在二叉排序樹(shù)上插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的算法； 熟練掌握平衡二叉樹(shù)（AVL樹(shù)）的定義及平衡旋轉(zhuǎn)技術(shù)，了解其相應(yīng)的算法；簡(jiǎn)單了 解B-樹(shù)、B+樹(shù)的特點(diǎn)以及它們的建樹(shù)和查找的過(guò)程；熟練掌握哈希表的構(gòu)造方 法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別；掌握按定義計(jì)算各種查找方 法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。9. 內(nèi)部排序（6+6學(xué)時(shí)）1 排序的基本概念2 直接插入排序和Shell排序3 冒泡排序和快速排序4 簡(jiǎn)單選擇排序和堆排序5 歸并排序各種排序方法的比較基本要求：了解排序的定義和各種排序方法的特

10、點(diǎn)，熟悉各種方法的排序過(guò)程及其依據(jù)的 原則；熟練掌握直接插入排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序和歸 并排序的實(shí)現(xiàn)算法；掌握各種排序方法的時(shí)間復(fù)雜度的分析方法，能從關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能；了解排序方法穩(wěn)定”或 不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。五、教材及學(xué)生參考書（黑體小四）教材：1、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 嚴(yán)蔚敏吳偉民編著.清華大學(xué)出版社1997年 4月出版參考書：1、算法與數(shù)據(jù)結(jié)構(gòu)一C語(yǔ)言描述 張乃孝主編.高等教育出版社2002 年9月出版2、 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 李云清等編著人民郵電出版社 2004年6月 出版3、 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言篇）一習(xí)題與解析 李春葆編著清華大學(xué)出版社 2002年4月出版4、算法與數(shù)據(jù)結(jié)構(gòu)（C與C+描述）陳松喬等編著清華大學(xué)出版社 2002年8月出版六、課外學(xué)習(xí)要求為了培養(yǎng)