【正文】 輯結構特性，以及線性表的兩種存儲實現(xiàn)方式 了解 ：作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序存儲與按列順序存儲 熟練掌握：順序表的定義與實現(xiàn)，包括搜索、插入、刪除算法的實現(xiàn)及其平均比較次數(shù)的計算，掌握應用順序表作為集合的簡單操作 了解：稀疏矩陣的定義及其數(shù)組實現(xiàn) 熟練掌握：字符串的定義及實現(xiàn) 三、鏈表 3學時 教學內容： 單鏈表：單鏈表的結構；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結點的單鏈表；用模板定義的單鏈表類；靜態(tài)鏈表 循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題； 多項式及其相加：多項式的類定義；多項式的加法 雙向鏈表 教學要求： 了解：鏈表與數(shù)組一樣，是一種實現(xiàn)級結構。 四、棧和隊列 3學時 教學內容： 棧：棧的抽象數(shù)據(jù)類型； 棧的順序存儲表示；棧的鏈接存儲表示 表達式求值：中綴表達式求值；中綴表示到后綴表示的轉換 隊列 ：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示；隊列的應用舉例 優(yōu)先級隊列：優(yōu)先級隊列的定義；優(yōu)先級隊列的存儲表示 教學要求： 熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應操作的實現(xiàn)。特別是循環(huán)隊列中隊頭與隊尾指針的變化情況 掌握：優(yōu)先級隊列的定義、特性和優(yōu)先級隊列的抽象數(shù)據(jù)類型，優(yōu)先級隊列的插入與刪除算法 五、遞歸 3學時 教學內容： 遞歸的概念：遞歸問題的求解 遞歸過程與遞歸工作棧：單向遞歸和尾遞歸的迭代實現(xiàn)；一般遞歸問題利用棧實現(xiàn)非遞歸解法 廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結構的實現(xiàn)；廣義表的訪問算法；廣義表的遞歸算法 教學要求： 掌握：遞歸的概念。包括樹的定義、樹的術語、樹的抽象數(shù)據(jù)類型 掌握：二叉樹的概念、性質及二叉樹的表示 熟練掌握：二叉樹的遍歷方法 掌握：線索化二叉樹的特性及尋找某結點的前驅和后繼的方法 熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調整等算法以及用來實現(xiàn)優(yōu)先級隊列的方法 掌握：樹與森林的實現(xiàn)，重點在用二叉樹實現(xiàn) 掌握：森林與二叉樹的轉換；樹的遍歷算法 掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結果得到二叉樹的方法 掌握：霍夫曼樹的實現(xiàn)方法、構造霍夫曼編碼的方法及帶權路徑長度的計算 七、集合與搜索 5學時 教學內容： 集合及其表示：集合基本概念；以集合為基礎的抽象數(shù)據(jù)類型；用位向量實現(xiàn)集合抽象據(jù)類型；用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型 并查集：并查集的定義；并查集的實現(xiàn) 簡單的搜索結構：搜索的概念；靜態(tài)搜索結構；順序搜索；基于有序順序表的順序搜索和折半搜索 二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除 AVL樹： AVL樹定義；平衡化旋轉； AVL樹的插入和刪除； AVL樹高度 教學要求： 掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關操作的實現(xiàn)算法 掌握：利用并查集實現(xiàn)集合的方法 熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法 熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法 掌握： AVL樹的平衡化旋轉、構造、插入、刪除時的調整方法及其性能分析 八、圖 7學時 教學 內容： 圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型 圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表 圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關節(jié)點與重連通分量 最小生成樹： kruskul算法； prim算法 單源最短路徑問題： dijkstra 算法 活動網(wǎng)絡： AOV網(wǎng)絡與拓撲排序； AOE網(wǎng)絡與關鍵路徑 教學要求： 理解：圖的基本概念和圖的抽象數(shù)據(jù)類型 掌握：圖的 3種存儲表示：鄰接矩陣、鄰接表和鄰接多重表。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法 (不要求算法 ) 理解：求解關節(jié)點及構造重連通圖的方法 (不要求算法 ) 掌握：構造最小生成樹的 Prim算法和 Kruskal算法，要求理解算法 理解：如何用 Dijkstra方法求解單源最短路徑問題 (不要求算法 ) 熟練掌握：活動網(wǎng)絡的拓撲排序算法 掌握：求解關鍵路徑的方法 九、排序 7學時 教學內容： 概述 插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序 交換排序：起泡排序；快速排序 選擇排序：直接選擇排序；錦標賽排序；堆排序 歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序 基數(shù)排序：多關鍵碼排序；鏈式基數(shù)排序 外排序：外排序的基本過程； k路平衡歸并；初始歸并段的生成；最佳歸并樹 教學要求： 掌握：排序的基本概念和性能分析方法 掌握：插入排序、交換排序、選擇排序、歸并排序等內排序的方法及其性能分析方法 了解：基數(shù)排序方法及其性能分析方法 掌握：多路平衡歸并等外排序方法及敗者樹構造方法 掌握：生成初始歸并段及敗者樹構造方法 掌握：最佳歸并樹的建立方法 十、索引與散列結構 5學時 教學內容： 靜態(tài)索引結構：線性索引；倒排索引； m路靜態(tài)查找樹 動態(tài)索引結構：動態(tài)的 m路查找樹； B樹的定義； B樹的插入； B樹的刪除； B+樹 散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析 教學要求： 熟練掌握：靜態(tài)索引結構，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構造方法 熟練掌握：動態(tài)索引結構，包括 B樹、 B+樹的搜索和構造方法 熟練掌握：散列法，包括散列函數(shù)的構造、解決沖突的方法 第四篇： 006A1060《數(shù)據(jù)結構》實驗教學大綱 [小編推薦 ] 《數(shù)據(jù)結構》課內實驗教學大綱 課程英文名稱： Data Structure 課程編號： 006A1060 學時： 54+18(實驗 ) 學分： 一、課程教學對象 本教學大綱適用于五邑大學信息學院計算機科學與技術專業(yè)的普通本科生數(shù)據(jù)結構課程的教學。本實驗課程是配合理論課程的實踐環(huán) 節(jié)，其主要任務是理論與實踐相結合，通過實踐提高學生對數(shù)據(jù)結構的基本原理和算法的理解和認識，進而提高對程序設計語言的理解和算法設計的能力。要求學生編寫符合軟件工程規(guī)范的文件，程序代碼應體現(xiàn)結構清晰、正確易讀，通過上機調試程序、排除錯誤。具體要求如下 ： 1． 掌握程序設計語言的基本概念。 3． 掌握離散數(shù)學的基本理論。上機課時為 18機時?！稊?shù)據(jù)結構（ C++版）學習輔導和實驗指導》中每章有大量的習題，還有相當數(shù)量的實驗題，要 求學生根據(jù)自身學習基礎，選擇驗證性實驗或設計性實驗或綜合性實驗作為課程考核內容的一部分，最好能選 3～ 5個設計性或綜合性的實驗題，要求完成上機調試、獲取實驗結果、寫出實驗報告。一類為順序存儲結構的線性表，另一類為鏈式存儲結構線性表。按要求完成實驗報告 。實現(xiàn)對棧的以下基本操作： 1．建立初始棧 2．入棧 3．退棧 要求需要考慮?？蘸蜅M的情況，編寫完整程序，調試，程序執(zhí)行的輸出結果要求至少包含輸入數(shù)據(jù)和運行結果，最好能體現(xiàn)運行過程。實驗三 隊列（ 2學時） 實驗內容和基本要求： 設計一個或若干多個順序（循環(huán)）隊列。按要求完成實驗報告。實現(xiàn)對該二叉樹遍歷的遞歸算法或非遞歸算法。實現(xiàn)對該二叉樹遍歷的遞歸算法或非遞歸算法。按要求完成實驗報告。 要求編寫完整程序，調試，程序執(zhí)行的輸出結果要求至少包含輸入數(shù)據(jù)和運行結果，最好能體現(xiàn)運行過程。實驗六 圖的存儲（ 2學時）實驗內容和基本要求： 設計一個無向圖或一個帶權的有向圖，采用鄰接表存儲該圖。按要求完成 實驗報告。按要求完成實驗報告。 2．給出一組數(shù)據(jù)，構造二叉排序樹。 4．給出一組數(shù)據(jù)，選擇一種哈希函數(shù)構造哈希表。 要求編寫完整程序，調試，程序執(zhí)行的輸出結果要求至少包含輸入數(shù)據(jù)和運行結果，最好能體現(xiàn)運行過程。 實驗九 排序（ 2學時） 實驗內容和基本要求： 實現(xiàn)或部分實現(xiàn)以下功能： 1．給出一組數(shù)據(jù)，實現(xiàn)直接插入排序算法，并對這組數(shù)據(jù)進行排序。 3．給出一組數(shù)據(jù)，實現(xiàn)快速排序算法，并對這組數(shù)據(jù)進行排序。 5．給出一組數(shù)據(jù) ，實現(xiàn)歸并排序算法，并對這組數(shù)據(jù)進行排序。 7．實現(xiàn)其它排序算法。按要求完成實驗報告。 課外實踐（可選） 實驗項目名稱：應用實例的設計與實現(xiàn) 指導思想： 訓練學生自主學習、綜合知識和查閱、收集資料的能力。給學生充分展示才華的舞臺，對學生設計的軟件作品要提供一個自由展示的平臺、互動交流的平臺，可以大大提高學生的學習激情和科學研究的精神，也能顯著提高學習效果。引導學生利用 “ 思維導圖 ” 等工具進行設計和交流，提高教與學的效果。 五、教材及參考書 1．理論課教材 理論課教材： 王紅梅等．數(shù)據(jù)結構（ C++版） [M]．北京：清華大學出版社， 2024 實驗課教材： 王紅梅等．數(shù)據(jù)結構（ C++版）學習輔導和實驗指導 [M]．北京：清華大學出版社， 2024 2．主要參考文獻 [1] 許卓群．數(shù)據(jù)結構 [M]．北京：高等教育出版社， 2024 [2] 殷人昆．數(shù)據(jù)結構 C＋＋實現(xiàn) [M]．北京：清華大學出版社， 2024 [3] 黃國瑜，葉乃菁．數(shù) 據(jù)結構 [M]．北京：清華大學出版社， 2024 [4] 胡學剛．數(shù)據(jù)結構算法設計指導 [M]．北京：清華大學出版社， 2024 [5] 胡元義，鄧亞玲，徐睿琳．數(shù)據(jù)結構課程輔導與習題解析 [M]．北京：人民郵電出版社， 2024 [6] 羅文，王苗，石強．數(shù)據(jù)結構習題解答與實驗指導 [M]．北京：中國鐵道出版社， 2024 [7] 王曉東．數(shù)據(jù)結構（ C語言版） [M]．北京：電子工業(yè)出版社， 2024 [8] 陳慧南．數(shù)據(jù)結構 —— 使用 C++語言描述 [M]．北京：人民郵電出版社， 2024 [9] 呂國英．算法設計與分析 [M]． 北京：清華大學出版社， 2024 [10] Sartaj Sahni． Data Structures, Algorithms and Applications in C++[M]．北京：機械工業(yè)出版社， 2024 [11] William Ford． Data Structure with C++[M]．北京：清華大學出版社， 2024 [12] 蘇光奎．數(shù)據(jù)結構導學 [M]．北京：清華大學出版社， 2024 [13] 嚴蔚敏等．數(shù)據(jù)結構（ C語言版） [M]．北京：清華大學出版社， 2024 六、考核方式 以閉卷考試為主， 結合平時作業(yè)及自主應用和設計綜合評定成績。執(zhí)筆人： 編寫日期： 20241031 白明 第五篇：數(shù)據(jù)結構課程教學大綱 數(shù)據(jù)結構課程教學大綱 一、課程基本概況 課程名稱：數(shù)據(jù)結構 課程名稱（英文）： Data Structures 課程編號： B09042 課程總學時： 60（其中，講課 48，實驗 12） 課程學分： 3 課程分類：專業(yè)選修課 開設學期： 4 適用專業(yè)：計算機網(wǎng)絡工程本科 先修課程：集合論，圖論， 高級語言（結構或記錄，指針） 后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等 二、課程的性質、目的和任務 數(shù)據(jù)結構是計算機專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學中占有十分重要的地位，是一門理論性非常強的課程。 三、主要內容、重點及深度 本門課程共 60學時，其中理論教學 48 學時，實驗教學 12學時。理解數(shù)據(jù)結構的基本概念；算法設計；掌握算法的時間和空間復雜度。 （三）重點與難點 重點：數(shù)據(jù)結構的定義；算法的描述方法。 第二章 線性表 （一）目的要求 掌握線性表的邏輯結構；線性表的存儲結構及操作的實現(xiàn)；理解一元多項式的表示； （二）教學內容 本章知識點： (掌握 )； (掌握 )； (掌握 )； (掌握 )。難點：鏈式存儲結構 及其常用算法；雙向循環(huán)鏈表。 （二）教學內容 本章知識點： (掌握 )； (掌握 )； (熟練掌握 )； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程 (掌握 )。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運算。 （二）教學內容 本章知識點： （了解）； (掌握 )； 的方法 (掌握 )； ，熟悉 NEXT函數(shù)和改進 NEXT函數(shù)的定義和計算 (掌握 )； 構實現(xiàn)串操作的方法 (理解 )。 （二）教學內容 本章知識點： (掌握 )； 壓縮存儲時的下標變換 (掌握 )； ，領會以三元組表示稀疏矩陣時進行運算采用的處理方法 (掌握 )； ，學會廣義表的表頭，表尾分析方法 (掌握 )； 算法 (掌握 )。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。 （三）重點與難點 重點：二叉樹的概念、性質；二叉樹的遍歷方式；構造二叉排序樹。 第七章 圖 （一）目的要求 理解圖的基本概念；圖的存儲結構；掌握圖的遍歷及應用 {最小生成樹，最短路徑等 }；拓撲排序和關鍵路徑。 （三）重點與難點 重點：圖的存儲結構；圖的遍歷 難點：圖遍歷的算法； 第八章 動態(tài)存儲管理 （一）目的要求 了解邊界標識法和伙伴系統(tǒng)；無用單元收集和緊縮； （二）教學內容 本章知識點： （了解）； （了解）。 （三）重點與