數(shù)據(jù)結(jié)構(gòu)與算法 教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱一、基本信息課程編碼：英文名稱：Datastructuresandalgorithms授課語言：漢語學(xué)分：4學(xué)時(shí)：56學(xué)時(shí)（授課48，實(shí)驗(yàn)8，上機(jī)0，課外0）適用對象：面向計(jì)算機(jī)大類課程性質(zhì)：學(xué)科基礎(chǔ)必修課先修課程：C/C++程序設(shè)計(jì)開課院系：信息工程學(xué)院使用教材(或講義)：主教材：《數(shù)據(jù)結(jié)構(gòu)與算法—C++實(shí)現(xiàn)》，慕晨等編著，清華大學(xué)出版社，2022年5月輔助教材：嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版社，2011年11月參考教材：無二、課程簡介“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程之一，在整個(gè)專業(yè)教學(xué)中占有十分重要的地位。本課程既具有較強(qiáng)的理論性，同時(shí)又注重實(shí)際動(dòng)手能力的培養(yǎng)。通過課堂教學(xué)、課外練習(xí)和課程設(shè)計(jì)，使學(xué)生了解數(shù)據(jù)對象的特性，掌握數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，初步具備數(shù)據(jù)組織和算法設(shè)計(jì)能力，從而提高學(xué)生的程序設(shè)計(jì)技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。三、課程任務(wù)、目的與要求課程任務(wù)：數(shù)據(jù)結(jié)構(gòu)重點(diǎn)培養(yǎng)學(xué)生分析和解決非數(shù)值問題的能力，能夠獨(dú)立設(shè)計(jì)和開發(fā)相應(yīng)的解決方案；了解數(shù)據(jù)結(jié)構(gòu)在實(shí)際工程項(xiàng)目和社會(huì)領(lǐng)域的應(yīng)用，訓(xùn)練學(xué)生認(rèn)識(shí)工程與社會(huì)的關(guān)系；了解計(jì)算機(jī)學(xué)科的新領(lǐng)域，認(rèn)識(shí)各種算法在這些領(lǐng)域的可能應(yīng)用，培養(yǎng)終身學(xué)習(xí)的能力。課程目的：通過本課程的學(xué)習(xí)，使學(xué)生對基本數(shù)據(jù)結(jié)構(gòu)具備分析、設(shè)計(jì)和復(fù)用的能力，并初步具備算法分析和設(shè)計(jì)能力，能夠使用合適的數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)與開發(fā)本課程培養(yǎng)學(xué)生達(dá)到以下能力要求，并支撐對應(yīng)的畢業(yè)要求指標(biāo)點(diǎn)。1、能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)將復(fù)雜工程問題轉(zhuǎn)化為計(jì)算機(jī)能夠識(shí)別和處理的問題，并進(jìn)行分析和推演。2、理解不同存儲(chǔ)結(jié)構(gòu)、不同排序和查找算法的優(yōu)缺點(diǎn)及應(yīng)用場景，對于實(shí)際工程問題，能夠設(shè)計(jì)多種解決方案，并結(jié)合文獻(xiàn)查閱及研究，比較、尋求可替代的解決方案。3、理解各種查找、排序和其他算法的原理、方法和局限性，具備開發(fā)相應(yīng)的信息檢索工具的能力。4、能夠分析和評價(jià)基于不同存儲(chǔ)結(jié)構(gòu)、不同的算法思想和不同的算法復(fù)雜度設(shè)計(jì)出的解決方案對于社會(huì)、健康、安全、法律以及文化的影響，具備在工程實(shí)踐中考慮上述制約因素的意識(shí)。課程要求：要求學(xué)生掌握線性表、樹、圖等各種數(shù)據(jù)結(jié)構(gòu)的邏輯特點(diǎn)、存貯方法以及基本運(yùn)算，掌握大批量數(shù)據(jù)的組織方法。要求學(xué)生初步掌握算法分析與設(shè)計(jì)能力。要求學(xué)生掌握常用的查找，排序的原理與技術(shù)方法。要求學(xué)生能夠?qū)唧w問題選擇適當(dāng)?shù)慕Y(jié)構(gòu)，并編寫出結(jié)構(gòu)清晰的程序。四、教學(xué)內(nèi)容及要求序號章節(jié)參考學(xué)時(shí)教學(xué)內(nèi)容基本要求1第1章緒論4本章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法有關(guān)的基本概念和基本方法。本章難點(diǎn)是算法分析的基本思想以及算法復(fù)雜度的計(jì)算。掌握以下概念：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型等基本概念，能夠運(yùn)用大O符號描述算法時(shí)間復(fù)雜度。2第2章線性表8本章重點(diǎn)介紹數(shù)據(jù)的線性結(jié)構(gòu)，包括：1）線性表的邏輯結(jié)構(gòu)2）線性表的順序存儲(chǔ)及實(shí)現(xiàn)3）線性表的鏈接存儲(chǔ)及實(shí)現(xiàn)4）順序表和單鏈表的比較5）線性表的其他存儲(chǔ)方法本章難點(diǎn)在于鏈表的實(shí)現(xiàn)、模版類的作用以及靜態(tài)鏈表的設(shè)計(jì)思想。掌握以下知識(shí)：1）掌握線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)2）掌握順序表、單鏈表的特點(diǎn)、類定義、基本操作、實(shí)現(xiàn)方法及時(shí)間性能3）能夠利用線性表編程解決較簡單的實(shí)際問題4）理解構(gòu)造函數(shù)、析構(gòu)函數(shù)、模板類的作用及設(shè)計(jì)思想5）理解循環(huán)鏈表、雙鏈表、靜態(tài)鏈表以及間接尋址的應(yīng)用目標(biāo)及設(shè)計(jì)思想第3章棧和隊(duì)列4本章主要介紹兩類操作受限的線性表：棧和隊(duì)列1）棧和隊(duì)列的邏輯結(jié)構(gòu)以及抽象數(shù)據(jù)類型定義2）分別用順序結(jié)構(gòu)和單鏈表結(jié)構(gòu)實(shí)現(xiàn)棧和隊(duì)列3）棧和隊(duì)列的典型應(yīng)用，棧與遞歸本章難點(diǎn)在于遞歸的理解以及前綴、中綴、后綴表達(dá)式的轉(zhuǎn)換。掌握以下知識(shí)：掌握棧和隊(duì)列的邏輯結(jié)構(gòu)掌握順序棧、鏈棧、循環(huán)隊(duì)列和鏈隊(duì)列的特點(diǎn)、類定義、基本操作、實(shí)現(xiàn)方法及時(shí)間性能掌握遞歸的思想方法，能夠使用遞歸解決問題理解前綴、中綴、后綴表達(dá)式的轉(zhuǎn)換，以及計(jì)算機(jī)處理表達(dá)式求值的方法。第4章字符串和多維數(shù)組4本章主要介紹兩類特殊的線性表：字符串與數(shù)組1）字符串的存儲(chǔ)結(jié)構(gòu)2）字符串的模式匹配3）數(shù)組的存儲(chǔ)方式及尋址方法4）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法本章難點(diǎn)在于模式匹配的BF算法以及KMP算法掌握以下知識(shí)：掌握串的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)掌握模式匹配原理以及BF算法，理解KMP算法思想理解多維數(shù)組的存儲(chǔ)思想和尋址方法了解特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)思想第5章樹和二叉樹9本章學(xué)習(xí)樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)1）樹的邏輯結(jié)構(gòu)2）樹的存儲(chǔ)結(jié)構(gòu)3）二叉樹的邏輯結(jié)構(gòu)4）二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)5）樹、森林與二叉樹的轉(zhuǎn)換6）二叉樹的應(yīng)用本章難點(diǎn)在于二叉樹的非遞歸遍歷以及線索鏈表掌握以下知識(shí)：了解樹的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)掌握二叉樹的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)掌握二叉鏈表的構(gòu)造、析構(gòu)、遍歷等操作的實(shí)現(xiàn)理解線索鏈表的設(shè)計(jì)方法理解非遞歸遍歷的思想和實(shí)現(xiàn)掌握樹、森林與二叉樹的轉(zhuǎn)換掌握哈夫曼樹及哈夫曼編碼第6章圖9本章學(xué)習(xí)圖的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)以及圖的應(yīng)用。1）圖的邏輯結(jié)構(gòu)2）圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)3）圖的應(yīng)用最小生成樹最短路徑AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑本章難點(diǎn)在于最短路徑的迪杰斯特拉算法。掌握以下知識(shí)：掌握圖的邏輯結(jié)構(gòu)掌握鄰接矩陣和鄰接表的存儲(chǔ)方法與遍歷操作掌握最小生成樹與prim算法掌握最短路徑與迪杰斯特拉算法理解AOV網(wǎng)與AOE網(wǎng)第7章查找5本章學(xué)習(xí)查找概念和查找算法1）查找的基本概念2）線性表的查找技術(shù)3）樹表的查找技術(shù)4）散列表的查找技術(shù)掌握以下知識(shí)：掌握線性表的查找技術(shù)掌握二叉排序樹的構(gòu)造、插入、刪除和查找思想理解二叉平衡樹和B樹的構(gòu)造思想掌握哈希表的查找思想，掌握基本的散列函數(shù)和沖突處理方法能夠熟練運(yùn)用三種以上的查找算法第8章排序5本章學(xué)習(xí)排序概念和排序算法1）排序的基本概念2）插入排序3）交換排序4）選擇排序5）歸并排序6）分配排序掌握以下知識(shí)：掌握各類排序算法的總體思路掌握并熟練運(yùn)用各類簡單排序算法理解各類改進(jìn)排序的思想掌握快速排序、堆排序的實(shí)現(xiàn)方法掌握分配排序的思想方法能夠熟練運(yùn)用至少一種高效的排序方法五、課內(nèi)實(shí)驗(yàn)（上機(jī)）名稱及基本要求序號參考學(xué)時(shí)實(shí)驗(yàn)（上機(jī)）名稱基本要求14線性表基本操作自行設(shè)計(jì)并編程實(shí)現(xiàn)順序表與單鏈表的構(gòu)造、查找、插入、刪除、輸出等基本操作，掌握線性表的存儲(chǔ)原理和基本操作。選做：根據(jù)查找頻率重排單鏈表22二叉樹基本操作利用二叉樹解決實(shí)際問題，編程實(shí)現(xiàn)二叉樹的構(gòu)造、遍歷、查找、輸出等基本操作，掌握樹結(jié)構(gòu)的處理方法。選做：二叉樹的重構(gòu)22圖的基本操作選用鄰接矩陣和鄰接表實(shí)現(xiàn)以下操作：圖的構(gòu)造、遍歷，掌握圖的常用存儲(chǔ)結(jié)構(gòu)和基本操作。選做：最短路徑與最小生成樹六、課外學(xué)時(shí)分配、考核和評價(jià)方式本課程采用課堂講授結(jié)合實(shí)驗(yàn)和課程設(shè)計(jì)，注重思維方