【正文】 先修課程。具體要求如下 ： 1． 掌握程序設計語言的基本概念。 2． 掌握結(jié)構(gòu)化程序設計的的基本原理、良好的設計習慣，并具備較好的程序調(diào)試能力。 3． 掌握離散數(shù)學的基本理論。 4．具有一定的邏輯思維和推理能力 四、課程的主要內(nèi)容、基本要求和學時分配建議（總學時數(shù) :18學時） 實驗內(nèi)容可根據(jù)實驗條件及教學情況由任課教師自定。上機課時為 18機時。實驗內(nèi)容的選擇要盡量結(jié)合基本內(nèi)容的應用實例，要具有一定的典型性和方法的靈活性，但一次實驗內(nèi)容不宜太多、太難。《數(shù)據(jù)結(jié)構(gòu)（ C++版）學習輔導和實驗指導》中每章有大量的習題，還有相當數(shù)量的實驗題，要 求學生根據(jù)自身學習基礎，選擇驗證性實驗或設計性實驗或綜合性實驗作為課程考核內(nèi)容的一部分，最好能選 3～ 5個設計性或綜合性的實驗題，要求完成上機調(diào)試、獲取實驗結(jié)果、寫出實驗報告。實驗一 線性表 (2 學時 )實驗內(nèi)容和基本要求： 分別設計兩類順序表。一類為順序存儲結(jié)構(gòu)的線性表，另一類為鏈式存儲結(jié)構(gòu)線性表。對這兩種線性表進行以下基本操作： 1．查找 2．插入 3．刪除 要求考慮時間復雜度和空間復雜度進行算法設計，編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告 。實驗二 棧（ 2學時）實驗內(nèi)容和基本要求： 設計一個或多個順序棧。實現(xiàn)對棧的以下基本操作： 1．建立初始棧 2．入棧 3．退棧 要求需要考慮?？蘸蜅M的情況，編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。實驗三 隊列（ 2學時） 實驗內(nèi)容和基本要求： 設計一個或若干多個順序（循環(huán)）隊列。實現(xiàn)對隊列的以下基本操作： 1．建立初始隊列 2．入隊 3．出隊 要求需要考慮隊列空和隊列滿的情況，編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運 行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。實驗四 二叉樹（ 2學時） 實驗內(nèi)容和基本要求： 1．設計一個二叉樹，采用鏈接存儲方式存儲。實現(xiàn)對該二叉樹遍歷的遞歸算法或非遞歸算法。 2．設計一個完全二叉樹，采用順序存儲方式存儲。實現(xiàn)對該二叉樹遍歷的遞歸算法或非遞歸算法。要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。 實驗五 哈夫曼樹（ 2學時） 實驗內(nèi)容和基本要求： 給定一組數(shù)據(jù)，根據(jù)這組數(shù)據(jù)建立一棵 Huffman樹，求出該樹的 WPL，并給出每一個數(shù)據(jù)的 Huffman編碼。 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。實驗六 圖的存儲（ 2學時）實驗內(nèi)容和基本要求： 設計一個無向圖或一個帶權(quán)的有向圖，采用鄰接表存儲該圖。實現(xiàn)對圖的以下基本操作： 1．建立圖（圖的鄰接表） 2．深度優(yōu)先遍歷或廣度優(yōu)先遍歷 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成 實驗報告。 實驗七 圖的應用（ 2學時） 實驗內(nèi)容和基本要求： 在實驗六的基礎上，實現(xiàn)或部分實現(xiàn)對圖的以下操作： 1．拓撲排序 2．構(gòu)造最小生成樹 3．求解關(guān)鍵路徑 4．求解最短路徑 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。 實驗八 查找（ 2學時） 實驗內(nèi)容和基本要求： 實現(xiàn)或部分實現(xiàn)以下功能： 1．給出一組有序數(shù)據(jù)，實現(xiàn)二分查找算法，并對這組數(shù)據(jù)中的任一數(shù)據(jù)進行查找。 2．給出一組數(shù)據(jù)，構(gòu)造二叉排序樹。 3．給出一組數(shù)據(jù)，構(gòu)造平衡二叉樹。 4．給出一組數(shù)據(jù)，選擇一種哈希函數(shù)構(gòu)造哈希表。給出一種解決沖突的方案。 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。 實驗九 排序（ 2學時） 實驗內(nèi)容和基本要求： 實現(xiàn)或部分實現(xiàn)以下功能： 1．給出一組數(shù)據(jù)，實現(xiàn)直接插入排序算法，并對這組數(shù)據(jù)進行排序。 2．給出一組數(shù)據(jù)，實現(xiàn)希爾排序算法，并對這組數(shù)據(jù)進行排序。 3．給出一組數(shù)據(jù)，實現(xiàn)快速排序算法，并對這組數(shù)據(jù)進行排序。 4．給出一組數(shù)據(jù)，實現(xiàn)堆排序算法，并對這組數(shù)據(jù)進行排序。 5．給出一組數(shù)據(jù) ，實現(xiàn)歸并排序算法，并對這組數(shù)據(jù)進行排序。 6．給出一組 3 位整數(shù)，實現(xiàn)基數(shù)排序算法，并對這組數(shù)據(jù)進行排序。 7．實現(xiàn)其它排序算法。 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn) 運行過程。按要求完成實驗報告。 說明：實驗報告的要求：見《數(shù)據(jù)結(jié)構(gòu)實驗報告模板》。 課外實踐（可選） 實驗項目名稱：應用實例的設計與實現(xiàn) 指導思想： 訓練學生自主學習、綜合知識和查閱、收集資料的能力。利用一些表現(xiàn)力強的平臺，以動畫形式展現(xiàn)數(shù)據(jù)結(jié)構(gòu)原理，需要學生自學 Flash、 Powerpoint、 網(wǎng)頁制作等，通過自主學習、查閱和收集所需的知識點完成。給學生充分展示才華的舞臺，對學生設計的軟件作品要提供一個自由展示的平臺、互動交流的平臺，可以大大提高學生的學習激情和科學研究的精神，也能顯著提高學習效果。實踐目的及要求： 在各個章節(jié)的基本編程訓練的基礎上，再結(jié)合課程重點和難點進行較大軟件編制的選題，并在具體題目上提倡與實際應用相結(jié)合并由學生自主選題，教師審核。引導學生利用 “ 思維導圖 ” 等工具進行設計和交流，提高教與學的效果。 該實踐項目主要占用課外時間進行，可由任課教師根據(jù)授課情況和學生的要求決定是否開展此項活動或部分開展此項活動。 五、教材及參考書 1．理論課教材 理論課教材： 王紅梅等．數(shù)據(jù)結(jié)構(gòu)（ C++版） [M]．北京：清華大學出版社， 2024 實驗課教材： 王紅梅等．數(shù)據(jù)結(jié)構(gòu)（ C++版）學習輔導和實驗指導 [M]．北京：清華大學出版社， 2024 2．主要參考文獻 [1] 許卓群．數(shù)據(jù)結(jié)構(gòu) [M]．北京：高等教育出版社， 2024 [2] 殷人昆．數(shù)據(jù)結(jié)構(gòu) C＋＋實現(xiàn) [M]．北京：清華大學出版社， 2024 [3] 黃國瑜，葉乃菁．數(shù) 據(jù)結(jié)構(gòu) [M]．北京：清華大學出版社， 2024 [4] 胡學剛．數(shù)據(jù)結(jié)構(gòu)算法設計指導 [M]．北京：清華大學出版社， 2024 [5] 胡元義，鄧亞玲，徐睿琳．數(shù)據(jù)結(jié)構(gòu)課程輔導與習題解析 [M]．北京：人民郵電出版社， 2024 [6] 羅文，王苗，石強．數(shù)據(jù)結(jié)構(gòu)習題解答與實驗指導 [M]．北京：中國鐵道出版社， 2024 [7] 王曉東．數(shù)據(jù)結(jié)構(gòu)（ C語言版） [M]．北京：電子工業(yè)出版社， 2024 [8] 陳慧南．數(shù)據(jù)結(jié)構(gòu) —— 使用 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ù)結(jié)構(gòu)導學 [M]．北京：清華大學出版社， 2024 [13] 嚴蔚敏等．數(shù)據(jù)結(jié)構(gòu)（ C語言版） [M]．北京：清華大學出版社， 2024 六、考核方式 以閉卷考試為主， 結(jié)合平時作業(yè)及自主應用和設計綜合評定成績。各部分分配比例為： 期末考試成績70%，平時作業(yè)及考勤 10%，實驗占 10%，自主設計作品或期中考核 10%。執(zhí)筆人： 編寫日期： 20241031 白明 第五篇：數(shù)據(jù)結(jié)構(gòu)課程教學大綱 數(shù)據(jù)結(jié)構(gòu)課程教學大綱 一、課程基本概況 課程名稱：數(shù)據(jù)結(jié)構(gòu) 課程名稱（英文）： Data Structures 課程編號： B09042 課程總學時： 60（其中，講課 48，實驗 12） 課程學分： 3 課程分類：專業(yè)選修課 開設學期： 4 適用專業(yè)：計算機網(wǎng)絡工程本科 先修課程：集合論，圖論， 高級語言（結(jié)構(gòu)或記錄，指針） 后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等 二、課程的性質(zhì)、目的和任務 數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學中占有十分重要的地位，是一門理論性非常強的課程。通過課堂教學、課外練習和上機實習，使學生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力以及培養(yǎng)良好的程序設計技能，為后續(xù)課程的學習和科研工作的參與打下良好的基礎。 三、主要內(nèi)容、重點及深度 本門課程共 60學時，其中理論教學 48 學時，實驗教學 12學時。其中，理論教學部分： 第一章 緒論 （一）目的要求 了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機科學中的作用、學習本課程的目的、任務及要求。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設計；掌握算法的時間和空間復雜度。 （二）教學內(nèi)容 本章知識點： (掌握 )； (掌握 )； （掌握）。 （三）重點與難點 重點：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。 難點：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復雜度及其計算。 第二章 線性表 （一）目的要求 掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)及操作的實現(xiàn)；理解一元多項式的表示； （二）教學內(nèi)容 本章知識點： (掌握 )； (掌握 )； (掌握 )； (掌握 )。 （三）重點與難點 重點：線性表的概念；線性表的順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)及其常用算法。難點：鏈式存儲結(jié)構(gòu) 及其常用算法；雙向循環(huán)鏈表。 第三章 棧和隊列 （一）目的要求 掌握棧的定義，表示及實現(xiàn)；表達式求值；棧與遞歸過程；隊列的定義、表示及實現(xiàn)。 （二）教學內(nèi)容 本章知識點： (掌握 )； (掌握 )； (熟練掌握 )； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程 (掌握 )。 （三）重點與難點 重點：堆棧和隊列的概念；遞歸的定義；循環(huán)隊列和鏈隊列的基本運算。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運算。 第四章 串 （一）目的要求 了解串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)；掌握串操作的實現(xiàn) (重點難點 BF 和 KMP算法 )串的應用。 （二）教學內(nèi)容 本章知識點： （了解）； (掌握 )； 的方法 (掌握 )； ，熟悉 NEXT函數(shù)和改進 NEXT函數(shù)的定義和計算 (掌握 )； 構(gòu)實現(xiàn)串操作的方法 (理解 )。 （三）重點與難點 重點：串定義和存儲方法；串的操作 難點：串操作實現(xiàn)方法 第五章 數(shù)組和廣義表 （一）目的要求 掌握數(shù)組的存儲結(jié)構(gòu)；稀疏矩陣的表示及操作的實現(xiàn)；廣義表的定義和存儲結(jié)構(gòu)；廣義表的遞歸算法。 （二）教學內(nèi)容 本章知識點： (掌握 )； 壓縮存儲時的下標變換 (掌握 )； ，領(lǐng)會以三元組表示稀疏矩陣時進行運算采用的處理方法 (掌握 )； ，學會廣義表的表頭，表尾分析方法 (掌握 )； 算法 (掌握 )。 （三）重點與難點 重點：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示 ；廣義表的存儲定義、操作。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。 第六章 樹和二叉樹 （一）目的要求 了解樹的基本概念；理解二叉樹的性質(zhì)和存儲結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應用； （二）教學內(nèi)容 本章知識點： (理解 )； (掌握 )； (掌握 )； ，在中序線索樹上找給定結(jié)點的前驅(qū)和后繼的方法 (掌握 )； 結(jié)構(gòu)及其特點 (掌握 )； (掌握 )； (掌握 )。 （三）重點與難點 重點：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。 第七章 圖 （一）目的要求 理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應用 {最小生成樹，最短路徑等 }；拓撲排序和關(guān)鍵路徑。 （二）教學內(nèi)容 本章知識點： ； (掌握 )； (掌握 )； （比如，最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑等） (掌握 )。 （三）重點與難點 重點：圖的存儲結(jié)構(gòu)；圖的遍歷 難點：圖遍歷的算法； 第八章 動態(tài)存儲管理 （一）目的要求 了解邊界標識法和伙伴系統(tǒng)；無用單元收集和緊縮； （二）教學內(nèi)容 本章知識點： （了解）； （了解）。 （三）重點與難點 存儲器分配策略和算法、無用單元收集時的標志算法 第九章 查找 （一）目的要求 了解靜態(tài)查找 表 (順序表，有序表，索引順序表 )；動態(tài)查找表 (二叉排序樹，平衡二叉樹， B樹和 B+樹 )的建立和查找；掌握哈希表的建立，查找及分析； （二）教學內(nèi)容 本章知識點： 、折半查找和索引查找的方法、應用 (掌握 )； (掌握 )； (掌握 )； ， B+樹和鍵樹的特點以及它們的建立過程（理解）； (掌握 )； ； (掌握 )。 （三）重點與