山東大學(xué)軟件學(xué)院《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)?zāi)康摹稊?shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性很強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課，每個(gè)學(xué)生必須完成一定數(shù)量的上機(jī)作業(yè)。通過本課程的上機(jī)作業(yè)，要求在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及實(shí)現(xiàn)等方面加深對課程基礎(chǔ)內(nèi)容的理解，同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。實(shí)驗(yàn)要求⒈問題分析充分地分析和理解問題本身，弄清要求做什么，包括功能要求、性能要求、設(shè)計(jì)要求和約束以及基本數(shù)據(jù)特性，數(shù)據(jù)間的聯(lián)系等。2.概要設(shè)計(jì)概要設(shè)計(jì)是對問題描述中涉及到的數(shù)據(jù)定義抽象數(shù)據(jù)類型，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)算法的偽代碼描述。在這個(gè)過程中，要綜合考慮系統(tǒng)的功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單，抽象數(shù)據(jù)類型盡可能做到數(shù)據(jù)封閉，基本操作的說明盡可能明確。而不必過早地考慮存儲(chǔ)結(jié)構(gòu)，不必過早地考慮語言的實(shí)現(xiàn)細(xì)節(jié)，不必過早地表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。3.詳細(xì)設(shè)計(jì)在詳細(xì)設(shè)計(jì)階段，要設(shè)計(jì)具體的存儲(chǔ)結(jié)構(gòu)（即用C++描述抽象數(shù)據(jù)類型對應(yīng)的類）以及算法所需的輔助數(shù)據(jù)結(jié)構(gòu)，算法在偽代碼的基礎(chǔ)上要考慮細(xì)節(jié)問題并用C++描述。此外，還要設(shè)計(jì)一定的用戶界面。數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)的主要目的是為了培養(yǎng)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用能力，因此在實(shí)驗(yàn)中不要求圖形界面，只要在屏幕上提示用戶每一步操作的輸入，并將結(jié)果物出即可。4.編碼實(shí)現(xiàn)和靜態(tài)檢查將詳細(xì)設(shè)計(jì)階段的結(jié)果進(jìn)一步優(yōu)化為C++程序，并完成靜態(tài)檢查。很多初學(xué)者在編寫程序后都有這樣的心態(tài)：確信自己的程序是正確的，認(rèn)為上機(jī)前的任務(wù)已經(jīng)完成，檢查錯(cuò)誤是計(jì)算機(jī)的事。這種心態(tài)是極為有害的，這樣的上機(jī)調(diào)試效率是極低的。事實(shí)上，即使有幾十年經(jīng)驗(yàn)的高級軟件工程師，也經(jīng)常利用靜態(tài)檢查來查找程序中的錯(cuò)誤。注意： 采用良好的編程風(fēng)格；關(guān)鍵操作要有注釋。5.測試用例設(shè)計(jì)準(zhǔn)備典型測試數(shù)據(jù)和測試方案，測試數(shù)據(jù)要有代表性、敏感性，測試方案包括模塊測試和模塊集成測試。6.上機(jī)調(diào)試對程序進(jìn)行編譯，糾正程序中可能出現(xiàn)的語法錯(cuò)誤，測試前，先運(yùn)行一遍程序看看究竟將會(huì)發(fā)生什么，如果錯(cuò)誤較多，則根據(jù)事先設(shè)計(jì)的測試方案并結(jié)合現(xiàn)場情況進(jìn)行錯(cuò)誤跟蹤，包括打印執(zhí)行路徑或輸出中間變量值等手段。7.*為選做內(nèi)容實(shí)習(xí)報(bào)告內(nèi)容⒈問題描述：包括目標(biāo)、任務(wù)、條件和約束的描述。⒉設(shè)計(jì)：⑴數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和核心算法設(shè)計(jì)描述；⑵主控及功能模塊層次結(jié)構(gòu)；⑶主要功能模塊的輸入、處理(算法框架描述)和輸出；⑷功能模塊之間的調(diào)用與被調(diào)用關(guān)系等。⒊測試：測試范例，測試結(jié)果，測試結(jié)果的分析與討論，測試過程中遇到的主要問題及所采用的解決措施。⒋使用說明和作業(yè)小結(jié)：⑴使用說明主要描述如何使用你的程序以及使用時(shí)的主要事項(xiàng)；⑵在小結(jié)中說明程序的改進(jìn)思想、經(jīng)驗(yàn)和體會(huì)，并回答教師布置的討論題。⒌提交一份程序清單及運(yùn)行示例的結(jié)果。將以上各項(xiàng)文字材料及程序清單等整理成文檔，形成一個(gè)完整的報(bào)告。開發(fā)工具 MicrosoftVisualC++EclipseIDEForC++實(shí)驗(yàn)時(shí)間、地點(diǎn)5-13周

實(shí)驗(yàn)一遞歸練習(xí)一、實(shí)驗(yàn)?zāi)康氖煜ら_發(fā)工具的使用。掌握遞歸的實(shí)現(xiàn)思想。二、實(shí)驗(yàn)內(nèi)容1、輸出n個(gè)整數(shù)的全排列。2、輸出n個(gè)整數(shù)的所有子集。三．實(shí)現(xiàn)提示

實(shí)驗(yàn)二排序算法一、實(shí)驗(yàn)?zāi)康恼莆崭鞣N排序方法的實(shí)現(xiàn)思想。二、實(shí)驗(yàn)內(nèi)容1、創(chuàng)建排序類。2、提供操作:選擇排序、冒泡排序、插入排序、基數(shù)排序、快速排序、歸并排序。(快速排序、歸并排序講到之后再做)3、*能夠顯示各種排序算法的中間過程。

實(shí)驗(yàn)三線性表操作實(shí)驗(yàn)?zāi)康恼莆站€性表的基本操作：插入、刪除、查找。掌握鏈表遍歷器的使用方法。二、實(shí)驗(yàn)內(nèi)容創(chuàng)建線性表類。線性表的存儲(chǔ)結(jié)構(gòu)使用鏈表。提供操作:自表首插入元素、刪除指定元素、搜索表中是否有指定元素、輸出鏈表。接收鍵盤錄入的一系列整數(shù)（例10,25,8,33,60）作為節(jié)點(diǎn)的元素值，創(chuàng)建鏈表。輸出鏈表內(nèi)容。輸入一個(gè)整數(shù)（例33），在鏈表中進(jìn)行搜索，輸出其在鏈表中的位置。如果不存在輸出0。使用鏈表遍歷器實(shí)現(xiàn)鏈表的反序輸出。創(chuàng)建兩個(gè)有序鏈表，使用鏈表遍歷器實(shí)現(xiàn)鏈表的合并。

實(shí)驗(yàn)四堆棧的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆斩褩５氖褂?。二、?shí)驗(yàn)內(nèi)容1、計(jì)算數(shù)學(xué)表達(dá)式的值。輸入數(shù)學(xué)表達(dá)式，輸出表達(dá)式的計(jì)算結(jié)果。數(shù)學(xué)表達(dá)式由單個(gè)數(shù)字和運(yùn)算符“+”、“-”、“*”、“/”、“(、“)構(gòu)成，例如2+3*(4+5)–6/4。假定表達(dá)式輸入格式合法。*2、以一個(gè)

m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。⒈問題描述從一個(gè)迷宮的入口到出口找出一條最短路經(jīng)。用一個(gè)二維數(shù)組MAZE(1：m，1：n)模擬迷宮，數(shù)組元素為0表示該位置可以通過，數(shù)組元素為1表示該位置不可以通行。MAZE(1，1)和MAZE(m，n)分別為迷宮的入口和出口。⒉基本要求輸入數(shù)據(jù)輸入迷宮的大小m行和n列，兩者為整數(shù)由隨機(jī)數(shù)產(chǎn)生0或1，建立迷宮。輸出數(shù)據(jù)首先輸出模擬迷宮的二維數(shù)組，若存在最短路經(jīng)，則由出口回朔到入口打印這一條路徑，如下所示：(m，n)，……，(I，j)，……，(1，1)如無通道，則打?。篢HEREISNOPATH.⒊實(shí)現(xiàn)提示數(shù)據(jù)結(jié)構(gòu)a）為了在程序中判斷方便，把迷宮擴(kuò)展成為MAZE(0：m+1，0：n+1)，擴(kuò)展部分的元素設(shè)置為1，相當(dāng)于在迷宮周圍布上一圈不準(zhǔn)通過的墻，這樣，在迷宮的任一位置(I，j)上都有八個(gè)可以移動(dòng)的方向。b）用二維數(shù)組MOVE(1：8，1：2)存放八個(gè)方向上的位置量，如圖所示：(I+MOVE[1，1]，j+MOVE[1，2])(I+MOVE[8，1]，j+MOVE[8，2])(I+MOVE[1，1]，j+MOVE[1，2])(I+MOVE[7，1]，j+MOVE[7，2])(I+MOVE[3，1]，j+MOVE[3，2])(I+MOVE[6，1]，j+MOVE[6，2])(I+MOVE[4，1]，j+MOVE[4，2])(I+MOVE[5，1]，j+MOVE[5，2])MOVE的設(shè)置情況Ij121-102-1130141151061-170-18-1-1為了標(biāo)志已經(jīng)通過的位置，采用一個(gè)標(biāo)志數(shù)組MARK（1..m，1..n）初值為0，在尋找路徑的過程中，若通過了位置（I，j），則將MARK（I，J）置為為1。為了記錄查找過程中到達(dá)位置及其前一位置，建立一個(gè)Q（1..m*n-1，0..2）數(shù)組，對于某一個(gè)數(shù)組元素Q(P)，其中，Q(P，0)和Q(P，1)記下到達(dá)位置I和j，Q(P，2)記下其出發(fā)點(diǎn)在Q數(shù)組中的下標(biāo)。（2）算法基本思想將入口（1，1）作為第一個(gè)出發(fā)點(diǎn)，依次在八個(gè)反方向上搜索可通行的位置，形成第一層新的出發(fā)點(diǎn)，然后對第一層中各個(gè)位置分別搜索他所在八個(gè)方向上的可通行位置，形成第二層新的出發(fā)點(diǎn)，…，如此進(jìn)行下去，直至達(dá)到出口(m，n)或者迷宮所有位置都搜索完畢為止。具體實(shí)施：從(m，n)開始，將其記入Q數(shù)組，比如記入Q(1)，以它作為第一個(gè)出發(fā)點(diǎn)，依次對八個(gè)方向進(jìn)行搜索，若下一個(gè)位置(I，j)可通行并且尚未經(jīng)過（即MAZE(I，j)=0且MARK(I，j)=0），則記入Q數(shù)組，如記在Q(P)，則在Q(P，2)中要記下其出發(fā)點(diǎn)在Q數(shù)組中的下標(biāo)1，在八個(gè)方向上都搜索過以后，根據(jù)先進(jìn)先出的原則Q從數(shù)組中重新取出一個(gè)位置作為新的出發(fā)點(diǎn)（這里，我們實(shí)際上把Q數(shù)組作為一個(gè)順序表示的隊(duì)列），重復(fù)以上過程，若能達(dá)到位置(m，n)，表示找到最短路徑；若Q數(shù)組中已經(jīng)沒有位置可以作為新的出發(fā)點(diǎn)了，則表示迷宮沒有通路。

實(shí)驗(yàn)五二叉樹操作一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹的基本概念，鏈表描述方法；遍歷方法。二、實(shí)驗(yàn)內(nèi)容創(chuàng)建二叉樹類。二叉樹的存儲(chǔ)結(jié)構(gòu)使用鏈表。提供操作:前序遍歷、中序遍歷、后序遍歷、層次遍歷、計(jì)算二叉樹結(jié)點(diǎn)數(shù)目、計(jì)算二叉樹高度。對建立好的二叉樹，執(zhí)行上述各操作。接收鍵盤錄入的二叉樹前序序列和中序序列(各元素各不相同)，輸出該二叉樹的后序序列。

實(shí)驗(yàn)六堆和搜索樹一、實(shí)驗(yàn)?zāi)康?、掌握堆和搜索樹的基本概念，插入、刪除方法。二、實(shí)驗(yàn)內(nèi)容創(chuàng)建最大堆類。最大堆的存儲(chǔ)結(jié)構(gòu)使用鏈表。提供操作:堆的插入、堆