數(shù)據(jù)結(jié)構(gòu)與算法 實(shí)驗(yàn)教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教學(xué)大綱一、課程性質(zhì)與基本要求數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)類(lèi)專(zhuān)業(yè)的一門(mén)重要基礎(chǔ)課程，是一門(mén)理論與工程實(shí)踐緊密結(jié)合的綜合性課程，它是研究非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象、對(duì)象間關(guān)系以及常用算法實(shí)現(xiàn)原理的課程。通過(guò)課程學(xué)習(xí)和實(shí)驗(yàn)，加深學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)和算法理論知識(shí)的理解，學(xué)會(huì)如何分析數(shù)據(jù)結(jié)構(gòu)的特征，為不同的應(yīng)用場(chǎng)景選擇設(shè)計(jì)合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及相應(yīng)的算法。在實(shí)驗(yàn)過(guò)程中要求學(xué)生編寫(xiě)符合軟件工程規(guī)范的程序，以培養(yǎng)其數(shù)據(jù)抽象能力和算法設(shè)計(jì)能力，為后續(xù)課程學(xué)習(xí)和實(shí)際工作打下堅(jiān)實(shí)的基礎(chǔ)。二、課程目標(biāo)本實(shí)驗(yàn)教材主要涉及如何合理地組織數(shù)據(jù)、有效地存儲(chǔ)和處理數(shù)據(jù)，正確地設(shè)計(jì)算法以及對(duì)算法的分析和評(píng)價(jià)。通過(guò)實(shí)驗(yàn)，使學(xué)生深刻理解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，提高程序設(shè)計(jì)與實(shí)現(xiàn)能力。實(shí)驗(yàn)?zāi)繕?biāo)如下：目標(biāo)1：理解數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)，具有對(duì)抽象數(shù)據(jù)類(lèi)型的理解能力。目標(biāo)2：掌握常用的數(shù)據(jù)結(jié)構(gòu)和算法，能根據(jù)實(shí)際問(wèn)題構(gòu)建合適的數(shù)據(jù)模型，選擇或構(gòu)思合適的算法。目標(biāo)3：能根據(jù)構(gòu)思的數(shù)據(jù)模型和算法編寫(xiě)具有良好風(fēng)格的實(shí)際可運(yùn)行程序，并對(duì)算法的復(fù)雜度進(jìn)行分析。三、實(shí)驗(yàn)環(huán)節(jié)教學(xué)安排序號(hào)實(shí)驗(yàn)項(xiàng)目名稱(chēng)實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容學(xué)時(shí)1順序表的建立及操作1.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)。2.掌握順序表基本操作的算法實(shí)現(xiàn)。3.了解順序表的應(yīng)用。任務(wù)1：按表格的方式打印顯示序順序表L中的所有信息。任務(wù)2：寫(xiě)一個(gè)函數(shù)刪除順序表L中某一元素。任務(wù)3：在有序的順序表中加入元素后，使表仍然有序。任務(wù)4：將線性表中L的數(shù)據(jù)保存到一個(gè)磁盤(pán)文件中。22鏈表的建立及操作1.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2.掌握鏈表基本操作的算法實(shí)現(xiàn)。任務(wù)1：在單鏈表L中的第i個(gè)學(xué)生后面插入一個(gè)新學(xué)生stu。任務(wù)2：統(tǒng)計(jì)單鏈表L中高等數(shù)學(xué)大于x并且大學(xué)英語(yǔ)大于x的學(xué)生人數(shù)。任務(wù)3：在任務(wù)2的基礎(chǔ)上，將單鏈表L中高等數(shù)學(xué)成績(jī)和大學(xué)英語(yǔ)成績(jī)?cè)趍in_score到max_score之間的學(xué)生組織成一個(gè)新的單鏈表L2。任務(wù)4（選做題）：編程實(shí)現(xiàn)在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入和刪除元素。23棧的建立及操作1．掌握棧的存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2．掌握棧的入棧和出棧等基本操作的算法實(shí)現(xiàn)。任務(wù)1：兩棧共享空間，設(shè)計(jì)兩棧共享空間的數(shù)據(jù)結(jié)構(gòu)，然后完成初始化算法、入棧、出棧等算法。任務(wù)2：五子棋游戲中悔棋操作，設(shè)計(jì)一個(gè)悔棋的數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)相關(guān)算法。任務(wù)3（選做題）：象棋游戲中的悔棋操作，設(shè)計(jì)一個(gè)悔棋的數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法。任務(wù)4（選做題）：表達(dá)式求值，實(shí)現(xiàn)算術(shù)表達(dá)式的求值問(wèn)題，假設(shè)表達(dá)式中只含加、減、乘、除四種運(yùn)算符。24隊(duì)列的建立及操作1．掌握隊(duì)列存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2．掌握隊(duì)列的入隊(duì)和出隊(duì)等基本操作的算法實(shí)現(xiàn)。任務(wù)1：使用隊(duì)列打印楊輝三角，寫(xiě)一個(gè)函數(shù)打印楊輝三角前n行。任務(wù)2：設(shè)計(jì)一個(gè)銀行排隊(duì)叫號(hào)系統(tǒng)，能模擬顧客到達(dá)取號(hào)、銀行工作人員準(zhǔn)備接待下一位顧客，系統(tǒng)檢測(cè)隊(duì)列長(zhǎng)度、顧客預(yù)計(jì)等待時(shí)間等。任務(wù)3：寫(xiě)一個(gè)模擬程序?qū)崿F(xiàn)鍵盤(pán)輸入循環(huán)緩沖區(qū)。假設(shè)有兩個(gè)進(jìn)程同時(shí)存在于一個(gè)應(yīng)用程序中，其中一個(gè)進(jìn)程在屏幕上連續(xù)顯示字符‘A’，與此同時(shí)，程序不斷檢測(cè)鍵盤(pán)是否有輸入，如果有輸入就讀入用戶輸入的字符并保存到緩沖區(qū)中。在用戶輸入時(shí)，鍵入的字符并不立即回顯在屏幕上。當(dāng)用戶鍵入一個(gè)逗號(hào)“，”時(shí)表示第一個(gè)進(jìn)程結(jié)束，第二個(gè)進(jìn)程從緩沖區(qū)中讀取那些已鍵入的字符并顯示在屏幕上。第二個(gè)進(jìn)程結(jié)束后，程序又進(jìn)入第一個(gè)進(jìn)程，重新顯示字符“A”，同時(shí)用戶又可以繼續(xù)鍵入字符，直到用戶輸入一個(gè)分號(hào)“；”鍵，才結(jié)束第一個(gè)進(jìn)程，同時(shí)也結(jié)束整個(gè)進(jìn)程。25二叉樹(shù)的建立及操作1．理解二叉樹(shù)的類(lèi)型定義與性質(zhì)。2.掌握二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。3．掌握二叉樹(shù)遍歷操作的算法實(shí)現(xiàn)。任務(wù)1：設(shè)計(jì)一個(gè)函數(shù)，根據(jù)二叉樹(shù)的先序遍歷序列和中序遍歷序列建立二叉樹(shù)。例如已知先序遍歷序列ABCDEFGH和中序遍歷序列BDCEAFHG，建立該二叉樹(shù)。任務(wù)2：實(shí)現(xiàn)二叉樹(shù)中序遍歷的非遞歸操作，設(shè)計(jì)一個(gè)函數(shù)，用非遞歸方法實(shí)現(xiàn)對(duì)任務(wù)1建立的二叉樹(shù)進(jìn)行中序遍歷。任務(wù)3：給定兩棵二叉樹(shù)，判斷兩棵二叉樹(shù)是否相等。任務(wù)4（選做題）：編程求從二叉樹(shù)根結(jié)點(diǎn)到指定結(jié)點(diǎn)p之間的路徑。26圖的建立及操作1．掌握?qǐng)D的相關(guān)概念。2．掌握用鄰接矩陣和鄰接表的方法描述圖的存儲(chǔ)結(jié)構(gòu)。3．掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法及其實(shí)現(xiàn)方法。4．掌握最小生成樹(shù)算法。5.掌握最短路徑算法。任務(wù)1：用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)無(wú)向圖。任務(wù)2：在任務(wù)1建立的無(wú)向圖鄰接表的基礎(chǔ)上，對(duì)圖進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列，并分析算法的時(shí)間復(fù)雜度。任務(wù)3（選做題）：用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)連通網(wǎng)，并構(gòu)造該網(wǎng)的最小生成樹(shù)。任務(wù)4（選做題）：校園導(dǎo)航系統(tǒng)。用無(wú)向圖表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求實(shí)現(xiàn)如下功能：（1）查詢各景點(diǎn)的相關(guān)信息。（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。27查找1.理解基于不同查找結(jié)構(gòu)的查找技術(shù)。2.掌握順序查找算法。3.掌握二分查找算法。4.掌握索引查找算法。任務(wù)1：二分查找（非遞歸算法），用二分查找的非遞歸算法實(shí)現(xiàn)范例2。任務(wù)2：二叉排序樹(shù)，編程實(shí)現(xiàn)如下功能。（1）按照輸入的n個(gè)關(guān)鍵字序列順序建立二叉排序樹(shù)，二叉排序樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)。（2）先輸入待查找記錄的關(guān)鍵字值key，然后在二叉排序樹(shù)上查找該記錄，如果在二叉排序樹(shù)中存在該記錄，則顯示“找到”的信息，否則顯示“找不到”的信息。（3）輸入待插入記錄的關(guān)鍵字值key，然后在二叉排序樹(shù)上查找該記錄，如果查找失敗，則在二叉排序樹(shù)中插入該記錄對(duì)應(yīng)的結(jié)點(diǎn)，并輸出插入操作后的二叉排序樹(shù)（以某種遍歷序列表示）。（4）輸入待刪除記錄的關(guān)鍵字值key，然后在二叉排序樹(shù)上查找該記錄，如果查找成功，則在二叉排序樹(shù)中刪除該記錄對(duì)應(yīng)的結(jié)點(diǎn)，并輸出刪除操作后的二叉排序樹(shù)（以某種遍歷序列表示）。假設(shè)二叉排序樹(shù)中元素的關(guān)鍵字值類(lèi)型為int。任務(wù)3：分塊查找（選做），編程實(shí)現(xiàn)如下功能。（1）建立索引查找表。（2）利用索引查找確定給定記錄在索引查找表中的塊號(hào)和在塊中的位置。28排序1.掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法。2.理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。3.了解各種方法的排序過(guò)程及其時(shí)間復(fù)雜度的分析方法。任務(wù)1：建立順序表，輸入n個(gè)學(xué)生的姓名和成績(jī)，將該順序表作為待排序序列，利用直接選擇排序?qū)Υ判蛐蛄邪闯煽?jī)從高到低進(jìn)行排序，并輸出排序后的結(jié)果，并分析算法的時(shí)間和空間復(fù)雜度。任務(wù)2：建立順序表，輸入n個(gè)學(xué)生的姓名和成績(jī)，將該順序表作為待排序序列，利用希爾排序?qū)Υ判蛐蛄邪闯煽?jī)從高到低進(jìn)行排序，并輸出排序后的結(jié)果，并分析算法的時(shí)間和空間復(fù)雜度。任務(wù)3：建立順序表，輸入n個(gè)學(xué)生的姓名和成績(jī)，將該順序表作為待排序序列，利用2路歸并排序?qū)Υ判蛐蛄邪闯煽?jī)從高到低進(jìn)行排序，并輸出排序后的結(jié)果，并分析算法的時(shí)間和空間復(fù)雜度。29貪心算法1.理解貪心算法中貪心選擇性質(zhì)。2.對(duì)于給定的問(wèn)題，識(shí)別是否適合用貪心算法求解。3.理解貪心算法的局限性，在某些時(shí)候貪心算法只能提供近似解。任務(wù)1：用貪心策略求解最優(yōu)裝載問(wèn)題。有n個(gè)集裝箱1、2、…、n需要裝上輪船，集裝箱i的重量wi，輪船裝載重量限制為C，每個(gè)集裝箱的重量小于C（wi≤C）,無(wú)體積限制，問(wèn)如何裝使得輪船上的集裝箱個(gè)數(shù)最多。任務(wù)2：用貪心策略解決最小延遲調(diào)度問(wèn)題。給定等待服務(wù)的客戶集合A={1,2,…,n}，各客戶的服務(wù)時(shí)間T=(t1,t2,…,tn)，其中客戶i的服務(wù)時(shí)間為ti（ti>0），各客戶的期望完成時(shí)刻D=(d1,d2,…,dn)，其中客戶i期望的服務(wù)完成時(shí)刻為di（di>0）。一個(gè)調(diào)度f(wàn)：A->N，f(i)為客戶i的開(kāi)始時(shí)刻。如果對(duì)客戶i的服務(wù)在di之前結(jié)束，那么客戶i的服務(wù)沒(méi)有延遲，如果在di之后結(jié)束，那么這個(gè)服務(wù)就被延遲了，延遲的時(shí)間等于該服務(wù)的實(shí)際完成時(shí)刻f(i)+ti減去預(yù)期結(jié)束時(shí)刻di。一個(gè)調(diào)度f(wàn)的最大延遲是所有客戶延遲時(shí)長(zhǎng)的最大值max{f(i)+ti-di}。要求找出一個(gè)調(diào)度使得最大延遲達(dá)到最小。210回溯法1.理解回溯法的基本原理。2.掌握如何定義問(wèn)題的狀態(tài)空間樹(shù)以及如何在樹(shù)中進(jìn)行深度優(yōu)先搜索來(lái)尋找可行解或最優(yōu)解。3.理解剪枝策略。任務(wù)1：利用回溯算法求解0-1背包問(wèn)題。給定n種物品和一個(gè)背包。第i種物品重量為wi，其價(jià)值為vi，其中i=1,2,3,…,n。背包的容量為c。問(wèn)如何選擇放入背包的物品，使得放入背包的物品的總價(jià)值最大。任務(wù)2：利用回溯算法求解旅行售貨員問(wèn)題。某售貨員要到n個(gè)城市去推銷(xiāo)商品，已知各城市之間的路程(或旅行所需的費(fèi)用)。要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。211動(dòng)態(tài)規(guī)劃算法1.理解動(dòng)態(tài)規(guī)劃算法中的最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題性質(zhì)。2.理解動(dòng)態(tài)規(guī)劃的核心概念，即通過(guò)將復(fù)雜問(wèn)題分解為更小的、相互關(guān)聯(lián)的子問(wèn)題來(lái)求解，并存儲(chǔ)這些子問(wèn)題的結(jié)果以避免重復(fù)計(jì)算。3.掌握動(dòng)態(tài)規(guī)劃算法的實(shí)際應(yīng)用方法。任務(wù)1：最大子數(shù)組問(wèn)題，給定一個(gè)數(shù)組X[1..n]，對(duì)于任意一對(duì)數(shù)組下標(biāo)為l、r（l≤r）的非空子數(shù)組，其和記為：S求S(l,r)的最大值。任務(wù)2：求最長(zhǎng)公共子序列，X的子序列是將序列X中零個(gè)或多個(gè)元素去掉后所得的序列。給定序列X和序列Y，求X和Y的最長(zhǎng)公共子序列。2四、實(shí)驗(yàn)評(píng)分標(biāo)準(zhǔn)實(shí)驗(yàn)項(xiàng)目基本評(píng)分標(biāo)準(zhǔn)如下。實(shí)驗(yàn)評(píng)分標(biāo)準(zhǔn)100~90分89~80分79~70分69~60分59~0分能夠?qū)o定的實(shí)際問(wèn)題抽象正確的數(shù)據(jù)模型；可以分析、選擇、設(shè)計(jì)、優(yōu)化存儲(chǔ)結(jié)構(gòu)；針對(duì)問(wèn)題正確設(shè)計(jì)滿足時(shí)間、空間約束條件的算法；算法實(shí)現(xiàn)正確，實(shí)驗(yàn)報(bào)告撰寫(xiě)規(guī)范；能夠?qū)?shí)驗(yàn)結(jié)果進(jìn)行分析。能夠?qū)o定的實(shí)際問(wèn)題抽象正確的數(shù)據(jù)模型；可以分析、選擇、設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)；可針對(duì)問(wèn)題設(shè)計(jì)滿足時(shí)間、空間約束條件的算法；算法實(shí)現(xiàn)正確，實(shí)驗(yàn)報(bào)告撰寫(xiě)規(guī)范；能夠?qū)o定的實(shí)際問(wèn)題抽象數(shù)據(jù)模型；可分析、選擇合適的存儲(chǔ)結(jié)構(gòu)；算法設(shè)計(jì)合理，滿足題目約束條件；算法實(shí)現(xiàn)正確，實(shí)驗(yàn)報(bào)告撰寫(xiě)較規(guī)范。能夠?qū)o定的實(shí)際問(wèn)題抽象數(shù)據(jù)模型；算法設(shè)計(jì)基本滿足題目約束條件；算法實(shí)現(xiàn)基本正確，實(shí)驗(yàn)報(bào)告撰寫(xiě)基本滿足規(guī)范。沒(méi)有完成實(shí)驗(yàn)任務(wù)，實(shí)驗(yàn)報(bào)告撰寫(xiě)存在較大的缺陷。五、課程思政在教學(xué)過(guò)程中，可從科技強(qiáng)國(guó)、科學(xué)素養(yǎng)、工匠精神、職業(yè)道德等方面融入思政內(nèi)容。介紹數(shù)據(jù)結(jié)構(gòu)與算法在重大項(xiàng)目中的應(yīng)用，如云計(jì)算、大數(shù)據(jù)分析等領(lǐng)域的創(chuàng)新應(yīng)用，強(qiáng)調(diào)算法創(chuàng)新對(duì)