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