《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱（示范）一、課程基本信息課程名稱：數(shù)據(jù)結(jié)構(gòu)（DataStructures）課程代碼：CS102學(xué)分/學(xué)時(shí)：3學(xué)分，總學(xué)時(shí)64（理論48學(xué)時(shí)，實(shí)驗(yàn)16學(xué)時(shí)）適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、人工智能等計(jì)算機(jī)類專業(yè)先修課程：程序設(shè)計(jì)基礎(chǔ)（C/C++）、離散數(shù)學(xué)二、課程目標(biāo)本課程旨在幫助學(xué)生建立“數(shù)據(jù)的邏輯結(jié)構(gòu)—存儲(chǔ)結(jié)構(gòu)—算法實(shí)現(xiàn)”的系統(tǒng)思維，掌握組織與處理復(fù)雜數(shù)據(jù)的核心方法，為后續(xù)算法設(shè)計(jì)、數(shù)據(jù)庫原理、操作系統(tǒng)等課程奠定基礎(chǔ)。（一）知識(shí)目標(biāo)1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型），掌握時(shí)間復(fù)雜度與空間復(fù)雜度的分析方法；2.熟練掌握線性表、棧、隊(duì)列、串、數(shù)組、樹、圖等經(jīng)典數(shù)據(jù)結(jié)構(gòu)的邏輯特征、存儲(chǔ)方式及核心操作（增刪改查、遍歷、排序等）；3.掌握查找（順序、二分、哈希）與排序（冒泡、快速、歸并）等算法的原理、實(shí)現(xiàn)及性能對(duì)比；4.了解數(shù)據(jù)結(jié)構(gòu)在實(shí)際工程（如搜索引擎、推薦系統(tǒng)、游戲開發(fā)）中的典型應(yīng)用場(chǎng)景。（二）能力目標(biāo)1.能根據(jù)問題場(chǎng)景選擇合適的數(shù)據(jù)結(jié)構(gòu)與算法，獨(dú)立完成中等復(fù)雜度的編程實(shí)現(xiàn)（如基于鏈表的多項(xiàng)式計(jì)算器、基于圖的最短路徑求解）；2.具備分析算法效率、優(yōu)化代碼性能的能力，能通過實(shí)驗(yàn)驗(yàn)證算法的時(shí)間/空間開銷；3.能運(yùn)用團(tuán)隊(duì)協(xié)作完成綜合性項(xiàng)目（如小型圖書管理系統(tǒng)、社交網(wǎng)絡(luò)拓?fù)浞治觯?，提升工程?shí)踐與溝通能力。（三）素質(zhì)目標(biāo)1.培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S與抽象建模能力，樹立“數(shù)據(jù)驅(qū)動(dòng)、效率優(yōu)先”的工程思維；2.激發(fā)對(duì)算法設(shè)計(jì)的創(chuàng)新意識(shí)，理解“trade-off（時(shí)空權(quán)衡）”的計(jì)算機(jī)科學(xué)核心思想；3.強(qiáng)化代碼規(guī)范與文檔撰寫習(xí)慣，培養(yǎng)遵守軟件倫理、重視知識(shí)產(chǎn)權(quán)的職業(yè)素養(yǎng)。三、教學(xué)內(nèi)容與學(xué)時(shí)安排（一）理論教學(xué)（48學(xué)時(shí)）模塊1：緒論（4學(xué)時(shí)）知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義、分類（邏輯/存儲(chǔ)結(jié)構(gòu)）；抽象數(shù)據(jù)類型（ADT）的概念；算法效率的度量（時(shí)間/空間復(fù)雜度的計(jì)算、漸進(jìn)符號(hào)）。重點(diǎn)：復(fù)雜度分析的方法（如遞歸算法的時(shí)間復(fù)雜度推導(dǎo)）；難點(diǎn)：大O表示法的本質(zhì)理解（區(qū)分最壞、平均、最好情況）。模塊2：線性表（8學(xué)時(shí)）知識(shí)點(diǎn)：線性表的邏輯特征；順序表的存儲(chǔ)結(jié)構(gòu)、操作（插入、刪除、查找）及性能分析；單鏈表、雙向鏈表、循環(huán)鏈表的結(jié)構(gòu)設(shè)計(jì)與代碼實(shí)現(xiàn)；線性表的應(yīng)用（多項(xiàng)式相加、約瑟夫環(huán)問題）。重點(diǎn)：鏈表的指針操作（如雙向鏈表的插入/刪除邏輯）；難點(diǎn)：復(fù)雜鏈表結(jié)構(gòu)（如循環(huán)雙向鏈表）的邊界條件處理。模塊3：棧與隊(duì)列（6學(xué)時(shí)）知識(shí)點(diǎn)：棧的“后進(jìn)先出”特性、順序棧與鏈棧的實(shí)現(xiàn)；隊(duì)列的“先進(jìn)先出”特性、循環(huán)隊(duì)列與鏈隊(duì)列的實(shí)現(xiàn)；棧（表達(dá)式求值、括號(hào)匹配）與隊(duì)列（廣度優(yōu)先搜索、生產(chǎn)者-消費(fèi)者模型）的典型應(yīng)用。重點(diǎn)：循環(huán)隊(duì)列的判空/判滿條件；難點(diǎn)：棧在遞歸算法中的隱式應(yīng)用（如二叉樹遍歷的遞歸轉(zhuǎn)迭代）。模塊4：串與數(shù)組（6學(xué)時(shí)）知識(shí)點(diǎn)：串的定義、存儲(chǔ)（定長/堆分配/塊鏈）與基本操作；數(shù)組的邏輯結(jié)構(gòu)與存儲(chǔ)映射（行/列優(yōu)先）；矩陣的壓縮存儲(chǔ)（對(duì)稱矩陣、稀疏矩陣）。重點(diǎn)：KMP算法的原理（部分匹配表的構(gòu)建）；難點(diǎn)：稀疏矩陣的快速轉(zhuǎn)置算法實(shí)現(xiàn)。模塊5：樹與二叉樹（10學(xué)時(shí)）知識(shí)點(diǎn)：樹的基本概念（節(jié)點(diǎn)、度、路徑）；二叉樹的性質(zhì)、遍歷（前序/中序/后序/層序）算法；二叉搜索樹（BST）、平衡二叉樹（AVL）、哈夫曼樹的構(gòu)建與應(yīng)用；樹、森林與二叉樹的轉(zhuǎn)換。重點(diǎn)：二叉樹遍歷的遞歸與非遞歸實(shí)現(xiàn)；難點(diǎn)：AVL樹的旋轉(zhuǎn)調(diào)整（LL、RR、LR、RL型）。模塊6：圖（10學(xué)時(shí)）知識(shí)點(diǎn)：圖的基本概念（頂點(diǎn)、邊、度）；圖的存儲(chǔ)（鄰接矩陣、鄰接表）；深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）；最小生成樹（Prim、Kruskal）、最短路徑（Dijkstra、Floyd）、拓?fù)渑判颉㈥P(guān)鍵路徑算法。重點(diǎn)：Dijkstra算法的貪心策略與優(yōu)化（優(yōu)先隊(duì)列實(shí)現(xiàn)）；難點(diǎn)：Kruskal算法的并查集優(yōu)化；關(guān)鍵路徑的AOE網(wǎng)分析。模塊7：查找與排序（4學(xué)時(shí)）知識(shí)點(diǎn)：靜態(tài)查找（順序、二分）、動(dòng)態(tài)查找（二叉搜索樹、哈希表）；內(nèi)部排序（冒泡、插入、選擇、快速、歸并、堆排序）的原理、實(shí)現(xiàn)及時(shí)間/空間復(fù)雜度對(duì)比；外部排序的基本思想。重點(diǎn)：快速排序的partition函數(shù)、歸并排序的分治思想；難點(diǎn)：哈希沖突的解決（鏈地址法、開放定址法）及負(fù)載因子設(shè)計(jì)。（二）實(shí)驗(yàn)教學(xué)（16學(xué)時(shí)）實(shí)驗(yàn)教學(xué)以“驗(yàn)證-設(shè)計(jì)-綜合”三級(jí)遞進(jìn)，強(qiáng)化理論到實(shí)踐的轉(zhuǎn)化：實(shí)驗(yàn)1：線性表的實(shí)現(xiàn)與應(yīng)用（4學(xué)時(shí)）內(nèi)容：用C語言實(shí)現(xiàn)順序表與單鏈表，完成“圖書借閱系統(tǒng)”的增刪查改功能；要求：分析兩種存儲(chǔ)結(jié)構(gòu)的性能差異，提交帶注釋的代碼與實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)2：棧與隊(duì)列的應(yīng)用（3學(xué)時(shí)）內(nèi)容：基于棧實(shí)現(xiàn)表達(dá)式求值（支持加減乘除與括號(hào)），基于隊(duì)列實(shí)現(xiàn)“銀行叫號(hào)系統(tǒng)”；要求：對(duì)比遞歸與非遞歸的棧操作效率，分析隊(duì)列的并發(fā)安全問題（選做）。實(shí)驗(yàn)3：二叉樹的遍歷與應(yīng)用（4學(xué)時(shí)）內(nèi)容：實(shí)現(xiàn)二叉樹的前中后序遍歷（遞歸+非遞歸），基于二叉搜索樹完成“學(xué)生成績管理系統(tǒng)”；要求：測(cè)試不同遍歷算法的時(shí)間開銷，優(yōu)化BST的插入/刪除操作。實(shí)驗(yàn)4：綜合項(xiàng)目（5學(xué)時(shí)）內(nèi)容：自選主題（如“校園導(dǎo)航系統(tǒng)”（圖的最短路徑）、“文件壓縮工具”（哈夫曼編碼）），團(tuán)隊(duì)完成需求分析、設(shè)計(jì)、編碼與測(cè)試；要求：提交項(xiàng)目文檔（含UML類圖、算法流程圖）與演示視頻，進(jìn)行小組答辯。四、教學(xué)方法與手段（一）教學(xué)方法1.問題導(dǎo)向教學(xué)：以“如何高效處理百萬級(jí)用戶的好友關(guān)系？”“搜索引擎如何快速檢索關(guān)鍵詞？”等工程問題引入，激發(fā)學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)選型的思考；2.案例驅(qū)動(dòng)教學(xué)：每個(gè)知識(shí)點(diǎn)配套1-2個(gè)經(jīng)典案例（如“微博熱搜榜”對(duì)應(yīng)堆結(jié)構(gòu)、“地鐵換乘”對(duì)應(yīng)圖的最短路徑），將抽象概念具象化；3.項(xiàng)目式學(xué)習(xí)：分階段布置小型項(xiàng)目（如“個(gè)人待辦事項(xiàng)管理系統(tǒng)”“迷宮尋路算法”），要求學(xué)生從需求分析到代碼實(shí)現(xiàn)全流程實(shí)踐；4.翻轉(zhuǎn)課堂：針對(duì)“KMP算法”“AVL樹旋轉(zhuǎn)”等難點(diǎn)，提前發(fā)布預(yù)習(xí)資料，課堂以小組討論、代碼調(diào)試競(jìng)賽的形式深化理解。（二）教學(xué)手段1.多媒體輔助：利用動(dòng)畫演示數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)變化（如鏈表的插入、二叉樹的旋轉(zhuǎn)），幫助學(xué)生直觀理解指針操作與結(jié)構(gòu)演變；2.在線教學(xué)平臺(tái)：通過雨課堂/Canvas發(fā)布預(yù)習(xí)資料、作業(yè)、測(cè)試，利用“代碼互評(píng)”功能促進(jìn)學(xué)生間的反饋與學(xué)習(xí)；3.實(shí)驗(yàn)平臺(tái)：依托實(shí)驗(yàn)室的Linux服務(wù)器與Git代碼托管平臺(tái)，培養(yǎng)學(xué)生的版本控制與協(xié)作開發(fā)習(xí)慣；4.學(xué)術(shù)前沿拓展：每學(xué)期邀請(qǐng)企業(yè)工程師分享“大數(shù)據(jù)場(chǎng)景下的分布式數(shù)據(jù)結(jié)構(gòu)（如HBase的LSM樹）”，拓寬學(xué)生視野。五、考核方式采用“過程性評(píng)價(jià)+終結(jié)性評(píng)價(jià)”的多元考核體系，全面考察學(xué)生的知識(shí)掌握與能力發(fā)展：（一）過程性評(píng)價(jià)（30%）1.作業(yè)與實(shí)驗(yàn)報(bào)告（15%）：包括理論作業(yè)（算法設(shè)計(jì)、復(fù)雜度分析）與實(shí)驗(yàn)報(bào)告（代碼注釋、問題分析、優(yōu)化思路），重點(diǎn)考察知識(shí)應(yīng)用能力；2.課堂表現(xiàn)（10%）：含考勤、提問互動(dòng)、小組討論貢獻(xiàn)度，鼓勵(lì)主動(dòng)思考與團(tuán)隊(duì)協(xié)作；3.階段性項(xiàng)目（5%）：如“鏈表版通訊錄”“二叉樹可視化工具”，考察知識(shí)整合與工程實(shí)踐能力。（二）終結(jié)性評(píng)價(jià)（70%）期末考試（閉卷，120分鐘）：題型：選擇題（20%，考察概念理解）、簡(jiǎn)答題（30%，考察原理分析）、算法設(shè)計(jì)題（50%，考察代碼實(shí)現(xiàn)與優(yōu)化）；范圍：覆蓋所有理論模塊，重點(diǎn)考察“復(fù)雜度分析”“鏈表操作”“樹/圖算法”等核心內(nèi)容；要求：算法設(shè)計(jì)需給出思路分析、偽代碼與關(guān)鍵注釋，部分題目允許用Python/C++等語言實(shí)現(xiàn)。六、教材與參考資料（一）主教材《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏、吳偉民編著，清華大學(xué)出版社（2020年第2版）。特點(diǎn)：理論體系嚴(yán)謹(jǐn)，代碼實(shí)現(xiàn)經(jīng)典，配套習(xí)題豐富，適合入門階段系統(tǒng)學(xué)習(xí)。（二）參考資料1.《DataStructuresandAlgorithmAnalysisinC++》，MarkAllenWeiss著，機(jī)械工業(yè)出版社（2021年版）；特點(diǎn)：從工程視角分析算法效率，含大量實(shí)際案例與復(fù)雜度優(yōu)化技巧。2.《算法導(dǎo)論（原書第3版）》，ThomasH.Cormen等著，機(jī)械工業(yè)出版社（2019年版）；特點(diǎn)：深入講解高級(jí)數(shù)據(jù)結(jié)構(gòu)（如紅黑樹、B樹）與算法設(shè)計(jì)策略，適合拓展學(xué)習(xí)。3.學(xué)術(shù)期刊與會(huì)議論文：如《ACMTransactionsonAlgorithms》《IEEETransactionsonKnowledgeandDataEngineering》，追蹤數(shù)據(jù)結(jié)構(gòu)的前沿研究（如量子數(shù)據(jù)結(jié)構(gòu)、分布式數(shù)據(jù)結(jié)構(gòu)）。七、教學(xué)建議1.分層教學(xué)：針對(duì)不同基礎(chǔ)的學(xué)生，提供“基礎(chǔ)版”（完成實(shí)驗(yàn)要求）與“進(jìn)階版”（優(yōu)化算法、閱讀外文文獻(xiàn)）的差異化任務(wù)；2.校企聯(lián)動(dòng)：邀請(qǐng)互聯(lián)網(wǎng)企業(yè)工程師參與實(shí)驗(yàn)指