數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)2012-bluenew

《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》2012實(shí)驗(yàn)報(bào)告I—數(shù)據(jù)結(jié)構(gòu)_031020xxx_張三第7頁(yè)共7頁(yè)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)題2012報(bào)告要求簡(jiǎn)述每一部分的對(duì)象、目的和要求；畫(huà)出算法(程序)的流程圖；說(shuō)明程序的數(shù)據(jù)輸入要求；附源程序清單；實(shí)驗(yàn)的收獲：遇到的問(wèn)題以及解決的辦法、方法的優(yōu)缺點(diǎn)、對(duì)本實(shí)驗(yàn)的要求和建議；忌空、大話簡(jiǎn)述每一部分。對(duì)源程序的功能塊做適當(dāng)注釋。其他未盡事項(xiàng)按寫(xiě)報(bào)告的一般要求進(jìn)行（“如何撰寫(xiě)實(shí)驗(yàn)報(bào)告.PDF”）。報(bào)告統(tǒng)一采用A4紙打印（正文采用5號(hào)字體，1.25倍行距）或手寫(xiě)，左側(cè)裝訂（推薦雙面打印）。以班級(jí)為單位提交光盤(pán)形式的電子稿，包括實(shí)驗(yàn)報(bào)告打印稿的WORD2003版本，源程序（包括可以直接運(yùn)行演示的可執(zhí)行文件）。每班刻一張光盤(pán)，每個(gè)同學(xué)的程序放在一個(gè)以“DS2012_學(xué)號(hào)_姓名”方式命名的文件夾中，如：“DS2012_031020xxx_張三”。（此部分可與后續(xù)“軟件工程實(shí)驗(yàn)報(bào)告”電子稿一起刻錄）實(shí)驗(yàn)題求解的構(gòu)思、程序?qū)崿F(xiàn)可以適當(dāng)參考文獻(xiàn)資料，但應(yīng)避免直接照搬。每人獨(dú)立完成實(shí)驗(yàn)，如發(fā)現(xiàn)實(shí)驗(yàn)程序或報(bào)告的內(nèi)容有雷同，雷同雙方（或多方）報(bào)告視為無(wú)效。實(shí)驗(yàn)報(bào)告格式如附件提供的模板，提交的文檔格式應(yīng)嚴(yán)格按規(guī)定的模板格式（文字水印格式為“DS2012_學(xué)號(hào)_姓名”，如“DS2012_031020xxx_張三”），打印稿件和電子稿件內(nèi)容要一致。

實(shí)驗(yàn)一：約瑟夫斯問(wèn)題求解1）問(wèn)題描述約瑟夫斯（Josephus）問(wèn)題的一種描述是：編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较蛳乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)程序，按出列順序印出各人編號(hào)。2）基本要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序印出各人的編號(hào)。3）測(cè)試數(shù)據(jù) n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4。m初值為6（正確的出列順序應(yīng)為6，1，4，7，2，3，5）。4）提示 程序運(yùn)行后，首先要求用戶指定初始報(bào)數(shù)上限m，然后讀取個(gè)人的密碼。可設(shè)n≤30。注意鏈表中空表和非空表的界限。5）輸入輸出:輸入數(shù)據(jù)：建立輸入處理，輸入n輸入以及每個(gè)人的密碼；m的初值。輸出形式：建立一個(gè)輸出函數(shù)，輸出正確的序列。6）選作內(nèi)容 添加采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)問(wèn)題求解的模塊。實(shí)驗(yàn)二：停車場(chǎng)管理問(wèn)題1）問(wèn)題描述設(shè)停車場(chǎng)是一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端）。若停車場(chǎng)內(nèi)已經(jīng)停滿n輛車，那么后來(lái)的車只能在門(mén)外的便道上等候。一旦有車開(kāi)走，則排在便道上的第一輛車即可開(kāi)入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門(mén)外，其他車輛再按原次序進(jìn)入車場(chǎng)。每輛停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短繳納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。2）基本要求 以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車的“到達(dá)”（‘A’表示）或“離去”（‘D’表示）信息、汽車標(biāo)識(shí)（牌照號(hào)）以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或者便道上的停車位置；若是車輛離去，則輸出汽車在停車場(chǎng)停留的時(shí)間和應(yīng)繳納的費(fèi)用（便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。3）測(cè)試數(shù)據(jù)設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。其中：（‘A’，1，5）表示1號(hào)牌照車在5這個(gè)時(shí)刻到達(dá)，而（‘D’，1，15）表示1號(hào)牌照車在15這個(gè)時(shí)刻離去。4）提示 需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來(lái)的汽車。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。5）輸入輸出:輸入數(shù)據(jù)：程序接受5個(gè)命令，分別是：到達(dá)（‘A’,車牌號(hào),時(shí)間)；離去(‘D’,車牌號(hào),時(shí)間)；停車場(chǎng)（‘P’,0,0）顯示停車場(chǎng)的車數(shù)；候車場(chǎng)（‘W’,0,0）顯示候車場(chǎng)的車數(shù)；退出（‘E’,0,0）退出程序。輸出數(shù)據(jù)：對(duì)于車輛到達(dá)，要輸出汽車在停車場(chǎng)內(nèi)或者便道上的停車位置；對(duì)于車輛離去，則輸出汽車在停車場(chǎng)停留的時(shí)間和應(yīng)繳納的費(fèi)用（便道上不收費(fèi)）。實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案問(wèn)題1）問(wèn)題描述需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間都可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的最小生成樹(shù)。2）基本要求 在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。3）測(cè)試數(shù)據(jù) 使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。右側(cè)是給出的參考解。圖1小區(qū)煤氣管道鋪設(shè)網(wǎng)及其參考解4）輸入輸出:從鍵盤(pán)或文件讀入上圖中的無(wú)向網(wǎng)，以頂點(diǎn)對(duì)（i,j）的形式輸出最小生成樹(shù)的邊。實(shí)驗(yàn)四：內(nèi)部排序算法的實(shí)現(xiàn)與比較1）問(wèn)題描述在教科書(shū)中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。2）基本要求 (1)對(duì)常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序、簡(jiǎn)單選擇排序、冒泡排序、快速排序、希爾排序。(2)利用隨機(jī)函數(shù)產(chǎn)生N（如30000）個(gè)隨機(jī)整數(shù)，作為輸入數(shù)據(jù)作比較；比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）。(3)對(duì)結(jié)果作出簡(jiǎn)要分析。3）測(cè)試數(shù)據(jù) 隨機(jī)函數(shù)產(chǎn)生。4）提示 主要工作是設(shè)法在已知算法中適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操作。注意采用分塊調(diào)試的方法。5）輸入輸出:輸入數(shù)據(jù)：參加排序的整數(shù)個(gè)數(shù)n（如n=30000）；輸出數(shù)據(jù)：各種排序方法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)（從小到大排列）。

附件《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》實(shí)驗(yàn)報(bào)告I—數(shù)據(jù)結(jié)構(gòu)班號(hào)：學(xué)號(hào)：姓名：Email：