《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐》課程教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐一、課程概況所屬專業(yè):軟件工程開(kāi)課單位：數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院課程類型:專業(yè)實(shí)踐課程課程代碼:07414310開(kāi)課學(xué)期:4學(xué)分：1.5學(xué)時(shí)：51核心課程:否擬使用教材：徐慧. 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)實(shí)踐教程M. 清華大學(xué)出版社, 2012.國(guó)內(nèi)(外)現(xiàn)有教材：齊悅等著. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用M. 清華大學(xué)出版社, 2015.李文書. 數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用實(shí)踐教程(第2版)M. 北京大學(xué)出版社, 2015.學(xué)習(xí)參考資料：嚴(yán)蔚敏、吳偉民著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M.北京：清華大學(xué)出版社,2007.寧正元等著.數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)實(shí)驗(yàn)指導(dǎo)M.北京：中國(guó)水利水電出版社,2000.二、課程描述數(shù)

2、據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的算法理論基礎(chǔ)和軟件設(shè)計(jì)的技術(shù)基礎(chǔ)，是計(jì)算機(jī)專業(yè)的核心課程。本課程實(shí)驗(yàn)采用實(shí)驗(yàn)教學(xué)和學(xué)生實(shí)驗(yàn)相結(jié)合方式，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本原理和編程方法達(dá)到提高學(xué)生分析問(wèn)題和解決問(wèn)題的能力的目的。通過(guò)實(shí)驗(yàn)環(huán)節(jié)，學(xué)生應(yīng)學(xué)會(huì)和掌握本課程的基本和重點(diǎn)知識(shí)；理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本原理,深刻理解邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法設(shè)計(jì)之間的關(guān)系，掌握分析問(wèn)題, 建立模型,運(yùn)用程序進(jìn)行問(wèn)題求解的方法。本課程是一門實(shí)踐性極強(qiáng)的程序設(shè)計(jì)課程，旨在培養(yǎng)學(xué)生的實(shí)際動(dòng)手能力，加強(qiáng)學(xué)生創(chuàng)新思維能力的培養(yǎng)。三、課程目標(biāo)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生對(duì)計(jì)算機(jī)常用

3、算法有一個(gè)全盤的了解；通過(guò)此課的學(xué)習(xí)，學(xué)生應(yīng)該具有針對(duì)所給的問(wèn)題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。通過(guò)上機(jī)實(shí)驗(yàn)，將使學(xué)生熟悉、掌握課堂教學(xué)中所學(xué)的大部分算法。同時(shí)，上機(jī)實(shí)習(xí)是對(duì)學(xué)生在軟件設(shè)計(jì)方面的綜合訓(xùn)練，包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧等，以培養(yǎng)良好的編程風(fēng)格和科學(xué)作風(fēng)。通過(guò)理論聯(lián)系實(shí)際，以最終提高學(xué)生動(dòng)手操作的能力以及分析問(wèn)題的能力。四、教學(xué)要求本課程由15組設(shè)計(jì)性實(shí)驗(yàn)和2組綜合性大實(shí)驗(yàn)構(gòu)成，每次實(shí)驗(yàn)課，授課教師將對(duì)學(xué)生的相關(guān)基礎(chǔ)知識(shí)進(jìn)行傳授，并對(duì)實(shí)驗(yàn)的基本要求進(jìn)行分析講解，指導(dǎo)學(xué)生做好實(shí)驗(yàn)方案設(shè)計(jì)、實(shí)驗(yàn)提交等工作。對(duì)學(xué)生分組設(shè)計(jì)實(shí)現(xiàn)某個(gè)簡(jiǎn)單系統(tǒng)以完成綜合性作業(yè)。學(xué)

4、生應(yīng)熟悉遵守實(shí)驗(yàn)室管理相關(guān)規(guī)章制度，按時(shí)完成各項(xiàng)實(shí)驗(yàn)工作。參與實(shí)踐課程教學(xué)活動(dòng)不遲到、不早退，無(wú)正當(dāng)理由不請(qǐng)假，上課認(rèn)真聽(tīng)講，不做任何與實(shí)踐課堂教學(xué)無(wú)關(guān)事宜，不使用手機(jī)，積極與授課教師進(jìn)行實(shí)踐互動(dòng)。實(shí)驗(yàn)完成后做好撰寫實(shí)驗(yàn)報(bào)告提交工作，并對(duì)最后的綜合實(shí)驗(yàn)做好系統(tǒng)的演示或者講解工作。五、考核方式及要求為實(shí)現(xiàn)課程教學(xué)目標(biāo)，本門課程考核采用平時(shí)成績(jī)、實(shí)驗(yàn)考核與綜合實(shí)驗(yàn)相結(jié)合的方式進(jìn)行。平時(shí)成績(jī)用于考察學(xué)生考勤、參與課程教學(xué)的行為表現(xiàn)，占課程總成績(jī)的30%；實(shí)驗(yàn)考核主要用于檢驗(yàn)學(xué)生對(duì)于實(shí)驗(yàn)原理與實(shí)驗(yàn)完成情況，占課程總成績(jī)的40%；綜合實(shí)驗(yàn)考核為教師出題和學(xué)生自主選題相結(jié)合完成某項(xiàng)系統(tǒng)，根據(jù)系統(tǒng)功能、代碼

5、完成情況、實(shí)驗(yàn)報(bào)告撰寫情況與答辯結(jié)果進(jìn)行評(píng)分，占課程總成績(jī)的30%。六、課程內(nèi)容實(shí)踐一：數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)基礎(chǔ)（授課時(shí)間：第四學(xué)期第一周）教學(xué)目標(biāo)：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法設(shè)計(jì)的要求、時(shí)間復(fù)雜度的概念以及部分算法的時(shí)間效率。主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法緒論、算法的時(shí)間效率分析、選擇排序、快速排序、堆排序等排序算法分析比較、漢諾塔遞歸算法分析比較。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐二：順序表及其應(yīng)用（授課時(shí)間：第四學(xué)期第二周）教學(xué)目標(biāo)：理解線性表的順序表示和實(shí)現(xiàn)，順序表的存儲(chǔ)結(jié)構(gòu)，掌握順序表的基本操作；利用順序表實(shí)現(xiàn)有關(guān)問(wèn)

6、題的求解。主要內(nèi)容：線性表的類型定義、順序表示和實(shí)現(xiàn)、順序表的基本操作；設(shè)計(jì)算法實(shí)現(xiàn)約瑟夫問(wèn)題、并編程實(shí)現(xiàn)有序表的合并問(wèn)題。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐三：鏈表及其應(yīng)用（授課時(shí)間：第四學(xué)期第三周）教學(xué)目標(biāo)：掌握單鏈表的表示和實(shí)現(xiàn)，單鏈表的存儲(chǔ)結(jié)構(gòu)，掌握單鏈表的基本操作；利用鏈表實(shí)現(xiàn)有關(guān)問(wèn)題的求解；理解并掌握雙鏈表、循環(huán)單鏈表、循環(huán)雙鏈表的基本操作，編程實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：?jiǎn)捂湵?、雙鏈表、循環(huán)單鏈表、循環(huán)雙鏈表的類型定義及基本操作；設(shè)計(jì)算法實(shí)現(xiàn)多項(xiàng)式的求和、和求導(dǎo)問(wèn)題，實(shí)現(xiàn)集合并、交、差運(yùn)算問(wèn)題。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授

7、/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐四：棧及其應(yīng)用（授課時(shí)間：第四學(xué)期第四周）教學(xué)目標(biāo)：理解棧的概念和基本要素，掌握順序棧和鏈棧的存儲(chǔ)與基本運(yùn)算的算法，利用棧實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：順序棧和鏈棧的存儲(chǔ)結(jié)構(gòu)與基本操作；利用棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換；設(shè)計(jì)算法解決表達(dá)式求值問(wèn)題、掌握設(shè)計(jì)回溯算法的基本技巧并結(jié)合棧用于8皇后問(wèn)題的求解；編程實(shí)現(xiàn)、設(shè)計(jì)算法求解迷宮問(wèn)題、順序棧的公用問(wèn)題。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐五：隊(duì)列及其應(yīng)用（授課時(shí)間：第四學(xué)期第五周）教學(xué)目標(biāo)：理解隊(duì)列的概念和基本要素，掌握順序環(huán)形隊(duì)列和鏈?zhǔn)疥?duì)列的存儲(chǔ)與基本運(yùn)算的算法，利

8、用隊(duì)列實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：順序環(huán)形隊(duì)列和鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)與基本操作；利用鏈?zhǔn)疥?duì)列編寫程序模擬病人到醫(yī)院看病，排隊(duì)看醫(yī)生的情況；以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的候車場(chǎng)，編程實(shí)現(xiàn)停車場(chǎng)的模擬；設(shè)計(jì)鏈表表示輪渡，隊(duì)列存儲(chǔ)到達(dá)渡口的車，設(shè)計(jì)算法實(shí)現(xiàn)輪渡的模擬。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐六：串及其應(yīng)用（授課時(shí)間：第四學(xué)期第六周）教學(xué)目標(biāo)：理解串的概念和基本要素，掌握順序串、鏈串的基本操作；掌握串的模式匹配的各種算法，利用串實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：順序串和鏈串的存儲(chǔ)結(jié)構(gòu)與基本操作；Brute_Force算法、Boyer_Moore

9、算法、kmp算法實(shí)現(xiàn)串的模式匹配；設(shè)計(jì)算法進(jìn)行病毒感染檢測(cè)，編程實(shí)現(xiàn)最長(zhǎng)連續(xù)相同字符、字符串加密、計(jì)數(shù)的模式匹配。學(xué) 時(shí)：3學(xué)時(shí)教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐七：數(shù)組、廣義表及其應(yīng)用（授課時(shí)間：第四學(xué)期第七周）教學(xué)目標(biāo)：理解數(shù)組、廣義表的概念和基本要素，掌握數(shù)組、廣義表的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算；實(shí)現(xiàn)矩陣的壓縮存儲(chǔ)，廣義表的遞歸算法；利用數(shù)組和廣義表實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：數(shù)組的定義、順序表示和基本運(yùn)算的實(shí)現(xiàn)、矩陣的壓縮存儲(chǔ)；廣義表的定義、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算、遞歸算法求廣義表深度；設(shè)計(jì)算法實(shí)現(xiàn)存儲(chǔ)格式轉(zhuǎn)換問(wèn)題、矩陣求解魔方問(wèn)題、兩個(gè)對(duì)稱矩陣之和與乘積問(wèn)題。

10、學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐八：樹(shù)及其應(yīng)用（授課時(shí)間：第四學(xué)期第八周）教學(xué)目標(biāo)：理解樹(shù)、二叉樹(shù)的定義和基本術(shù)語(yǔ)；掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算、二叉樹(shù)的各種遍歷算法；利用二叉樹(shù)實(shí)現(xiàn)相關(guān)問(wèn)題的求解。主要內(nèi)容：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和基本操作；先序遍歷、中序遍歷、后序遍歷算法的分析比較；設(shè)計(jì)算法實(shí)現(xiàn)二叉樹(shù)中從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑、葉子結(jié)點(diǎn)個(gè)數(shù)的計(jì)算、由遍歷構(gòu)造二叉樹(shù)、二叉樹(shù)任一結(jié)點(diǎn)的特征計(jì)算。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐九：樹(shù)及其應(yīng)用（授課時(shí)間：第四學(xué)期第九周）教學(xué)目標(biāo)：掌握線索二叉樹(shù)的算法

11、、樹(shù)與森林、赫夫曼樹(shù)及其應(yīng)用、回溯法與樹(shù)的遍歷；解決一些相關(guān)的綜合問(wèn)題。主要內(nèi)容：實(shí)現(xiàn)中序線索化二叉樹(shù)的算法、樹(shù)和森林的遍歷算法、利用赫夫曼算法構(gòu)造赫夫曼樹(shù)；設(shè)計(jì)算法實(shí)現(xiàn)電文的編碼和譯碼、家族關(guān)系查詢系統(tǒng)。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十：圖及其應(yīng)用（授課時(shí)間：第四學(xué)期第十周）教學(xué)目標(biāo)：掌握?qǐng)D的定義和基本術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)和基本操作、圖的遍歷；利用圖解決一些相關(guān)問(wèn)題。主要內(nèi)容：圖的存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表、鄰接多重表存儲(chǔ)圖的分析比較、鄰接矩陣和鄰接表的轉(zhuǎn)化；深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法的實(shí)現(xiàn)與比較；有向圖的路徑問(wèn)題。學(xué) 時(shí)：

12、3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十一：圖及其應(yīng)用（授課時(shí)間：第四學(xué)期第十一周）教學(xué)目標(biāo)：掌握?qǐng)D的連通性問(wèn)題、有向無(wú)環(huán)圖及其應(yīng)用、最短路徑的算法。主要內(nèi)容：克魯斯卡爾算法、普利姆算法的實(shí)現(xiàn)；編程實(shí)現(xiàn)拓?fù)渑判虻男蛄?、求關(guān)鍵路徑、關(guān)鍵活動(dòng)的算法；設(shè)計(jì)算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑和每一對(duì)頂點(diǎn)之間的最短路徑。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十二：圖及其應(yīng)用（授課時(shí)間：第四學(xué)期第十二周）教學(xué)目標(biāo)：利用圖解決一些綜合性問(wèn)題。主要內(nèi)容：假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的

13、重要站點(diǎn)，弧代表已有的公交路線，弧上的權(quán)表示該路線上的票價(jià)（或者所需時(shí)間），設(shè)計(jì)一個(gè)交通指南系統(tǒng)，指導(dǎo)前來(lái)咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一站點(diǎn)到達(dá)另一站點(diǎn)。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十三：查找及其應(yīng)用（授課時(shí)間：第四學(xué)期第十三周）教學(xué)目標(biāo)：掌握靜態(tài)查找表、二叉排序樹(shù)、哈希表及其應(yīng)用，并利用查找解決一些相關(guān)問(wèn)題。主要內(nèi)容：順序表、有序表的查找算法，二叉排序樹(shù)查找算法的驗(yàn)證，設(shè)計(jì)哈希表的創(chuàng)建、查找、元素插入等算法并驗(yàn)證，順序查找與折半查找的性能比較、線性散列與鏈?zhǔn)缴⒘械男阅鼙容^。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)

14、驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十四：排序及其應(yīng)用（授課時(shí)間：第四學(xué)期第十四周）教學(xué)目標(biāo)：掌握各種內(nèi)部排序的特點(diǎn)和算法。主要內(nèi)容：直接實(shí)現(xiàn)插入排序、冒泡排序、選擇排序、快速排序、希爾排序、堆排序等6種內(nèi)部排序算法，比較各算法的比較次數(shù)和移動(dòng)次數(shù)。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十五：排序及其應(yīng)用（授課時(shí)間：第四學(xué)期第十五周）教學(xué)目標(biāo)：利用排序解決一些相關(guān)問(wèn)題。主要內(nèi)容：修改冒泡排序算法以實(shí)現(xiàn)雙向冒泡排序；用單鏈表作為待排序數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，在其上實(shí)現(xiàn)直接插入排序算法；學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十六：綜合實(shí)驗(yàn)（授課時(shí)間：第四學(xué)期第十六周）教學(xué)目標(biāo)：設(shè)計(jì)算法實(shí)現(xiàn)有關(guān)數(shù)據(jù)結(jié)構(gòu)的綜合問(wèn)題主要內(nèi)容：設(shè)計(jì)算法、編程實(shí)現(xiàn)通訊錄管理系統(tǒng)。主要涉及線性表的基本操作、查找操作、排序操作、索引表的創(chuàng)建與使用；根據(jù)通訊錄的操作情況，通訊錄的記錄可選擇順序表或鏈表；若提供多種有序顯示，如按姓名、關(guān)系等通過(guò)建立索引表來(lái)實(shí)現(xiàn)；建立索引表，可按關(guān)鍵字排序，可以對(duì)原記錄按關(guān)鍵字建立二叉排序樹(shù)。學(xué) 時(shí)：3學(xué)時(shí)。教學(xué)方法：演示法/講授/現(xiàn)場(chǎng)指導(dǎo)實(shí)驗(yàn)類型：設(shè)計(jì)型實(shí)驗(yàn)、綜合性實(shí)驗(yàn)實(shí)踐十七：綜合實(shí)驗(yàn)（授課時(shí)間：第四學(xué)期第十七周）教學(xué)目標(biāo)：設(shè)計(jì)算法實(shí)現(xiàn)有關(guān)數(shù)據(jù)結(jié)構(gòu)的綜合問(wèn)題主要內(nèi)容