數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告組員人數(shù)：2題目數(shù)：2姓名：學(xué)號(hào)：200925503230班級(jí)： 計(jì)093-2總分：姓名：學(xué)號(hào)：200925503204班級(jí)： 計(jì)093-2總分：題目1：熊貓燒香算法程序設(shè)計(jì)：分?jǐn)?shù)：測(cè)試與報(bào)告：分?jǐn)?shù)：題目2：室內(nèi)布線(xiàn)算法程序設(shè)計(jì)：分?jǐn)?shù)：測(cè)試與報(bào)告：分?jǐn)?shù)：日期：2010年12月31日第一部分 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目一：搜索算法效率比較一、 課程設(shè)計(jì)內(nèi)容現(xiàn)在某實(shí)驗(yàn)室感染了熊貓燒香病毒。實(shí)驗(yàn)室的機(jī)器排列為一個(gè)M行N列的矩陣，每臺(tái)機(jī)器只和它相鄰的奇跡直接相連（橫向和縱向）。開(kāi)始時(shí)有T臺(tái)機(jī)器被感染，每臺(tái)遭遇的熊貓變種類(lèi)型都不同，分別及為K1，K2,KT。每臺(tái)機(jī)器都具有一等級(jí)別的防御能力，將防御級(jí)別記為L(zhǎng) （0L1000）。熊貓燒香按照下列規(guī)則傳播：l 病毒只能從一臺(tái)被感染的機(jī)器傳到另一臺(tái)沒(méi)有被感染的機(jī)器。l 如果一臺(tái)機(jī)器已經(jīng)被某個(gè)變種的病毒感染過(guò)，就不能被其他變種感染。l 病毒的傳播能力每天都在增強(qiáng)。第1天，病毒只能感染它可以到達(dá)的，防御級(jí)別不超過(guò)1的機(jī)器，而防御級(jí)別大于1的機(jī)器可以阻止它從自己出繼續(xù)傳播。第D天，病毒只能感染它可以到達(dá)的，防御級(jí)別不超過(guò)D的機(jī)器，而防御級(jí)別大于D的機(jī)器可以阻止它從自己出繼續(xù)傳播。l 在同一天之內(nèi)，K1變種的病毒先開(kāi)始傳播，感染所有它可能感染的機(jī)器，然后是K2變種，K3變種依次進(jìn)行傳播。本題目的任務(wù)是：當(dāng)整個(gè)網(wǎng)絡(luò)被感染后，計(jì)算有多少臺(tái)機(jī)器被某個(gè)特定變種所感染。二、 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)1、 數(shù)據(jù)結(jié)構(gòu)定義圖結(jié)構(gòu) 存放二維數(shù)組圖節(jié)點(diǎn)的定義如下：typedef struct VertexType /節(jié)點(diǎn)信息int day;/第幾天感染的int dl;/防御級(jí)別int r,c;/行列號(hào)int vt;/ 病毒類(lèi)型圖定義如下：typedef struct MGraph VertexType mMAXNODEMAXNODE;int row,colum ,num;/行列數(shù)，感染的數(shù)目MGraph;2、 主要算法（1）最終矩陣的生成函數(shù)：四重循環(huán)函數(shù) 通過(guò)兩個(gè)WHILE實(shí)現(xiàn)病毒全部感染前天數(shù)的循環(huán)和病毒種類(lèi)的循環(huán)。通過(guò)兩個(gè)FOR函數(shù)實(shí)現(xiàn)圖節(jié)點(diǎn)中和病毒種類(lèi)相同的節(jié)點(diǎn)，運(yùn)行圖廣度查找并感染四周節(jié)點(diǎn)函數(shù)。（2）感染函數(shù)（運(yùn)用圖的廣度優(yōu)先遍歷查找）：建立隊(duì)列，定義頭尾指針。隊(duì)列初始為空，從輸入的節(jié)點(diǎn)開(kāi)始，將節(jié)點(diǎn)入隊(duì)。在隊(duì)列不空的前提下，反復(fù)將對(duì)頭出隊(duì)，將該節(jié)點(diǎn)的四個(gè)方向相鄰節(jié)點(diǎn)入隊(duì)并判斷能否感染，并實(shí)施感染。三、 程序?qū)崿F(xiàn)介紹實(shí)現(xiàn)算法所編制的程序，包括頭文件和源文件。簡(jiǎn)要說(shuō)明個(gè)文件的功能MGraph.h 記錄了矩陣圖和圖節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) MGraph。 Suanfa.h 記錄了最終矩陣生產(chǎn)函數(shù)和感染函數(shù)。main.cpp 實(shí)現(xiàn)算法的主程序。四、 測(cè)試結(jié)果l 測(cè)試輸入：1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 1；l 測(cè)試目的：輸入3*4矩陣 和病毒類(lèi)型 驗(yàn)證能否輸出正確感染相應(yīng)病毒機(jī)器個(gè)數(shù)和原輸入矩陣。l 正確輸出：你的輸入為l 1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 病毒類(lèi)型為1的病毒個(gè)數(shù)為9l 實(shí)際輸出：你的輸入為l 1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 病毒類(lèi)型為1的病毒個(gè)數(shù)為9ll 當(dāng)前狀態(tài)：通過(guò)五、 分析與探討1. 測(cè)試結(jié)果分析。解釋測(cè)試策略，對(duì)得到的結(jié)果進(jìn)行分析，總結(jié)出算法的時(shí)間和空間復(fù)雜度，對(duì)算法的性能進(jìn)行評(píng)價(jià)：測(cè)試結(jié)果正確實(shí)現(xiàn)算法功能。實(shí)現(xiàn)病毒感染天數(shù)和病毒感染天數(shù)的預(yù)測(cè)和輸出結(jié)果。病毒感染函數(shù)的時(shí)間復(fù)雜度是O（n2）。2. 探索算法改進(jìn)的可能性，提出自己的建議：(1病毒感染算法空間復(fù)雜度有縮小空間?？蓢L試放棄圖的廣度優(yōu)先遍歷使用其他算法。(2圖的定義復(fù)雜 可以適當(dāng)簡(jiǎn)化。 第二部分：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目二：室內(nèi)布線(xiàn)一：課程設(shè)計(jì)題目：最小生成樹(shù)：室內(nèi)布線(xiàn)1. 題目要求編寫(xiě)程序幫助房主世界室內(nèi)電線(xiàn)的布局。首先，墻上的插座是固定的。插座間需要有電線(xiàn)相連，而且要布置的整齊美觀，即要求每條線(xiàn)都至少與一條墻邊平行，且嵌入四壁或者地板（不能走屋頂）。另外，每個(gè)房間都有們，電線(xiàn)不可以穿門(mén)而過(guò)。要求將所有的插座連通，且告訴房主需要買(mǎi)的電線(xiàn)的最短長(zhǎng)度。輸入要求： 輸入有若干組測(cè)試數(shù)據(jù)組成。每組數(shù)據(jù)的第1行包含房間的長(zhǎng)寬高和插座的個(gè)數(shù)N=20。接下去的N行中，第i行給出第i個(gè)插座的位置坐標(biāo)（xi， yi， zi），最后一行包含4個(gè)3元組，分別是長(zhǎng)方形門(mén)框的4個(gè)交的三位坐標(biāo)。4個(gè)整數(shù)全部為0表示全部測(cè)試結(jié)束。注：房間是長(zhǎng)方體，位于三維指教坐標(biāo)系的第一象限內(nèi)，并且有一個(gè)角落在原點(diǎn)上。地板位于xy平面，插座位于墻上，門(mén)上沒(méi)有插座。要求每段線(xiàn)段的兩端僅與插座相連，電線(xiàn)之間不能互相連接。輸出要求：對(duì)每一組測(cè)試，在一行里輸出將所有插座連通需要買(mǎi)的電線(xiàn)的最短整數(shù)長(zhǎng)度。輸入例子：10 10 10 40 1 3.32.5 0 25 0 0.85 10 10 0 0 0 0 3 1.5 0 0 1.5 0 30 0 0 0輸出例子：212. 簡(jiǎn)要提示可以將每個(gè)插座看成圖中的一個(gè)結(jié)點(diǎn)，計(jì)算出任意兩插座之間的最短距離，作為兩結(jié)點(diǎn)間邊的權(quán)重。要求的布線(xiàn)結(jié)果是一個(gè)保證連通的子圖，其中包括邊的權(quán)重和最小，這實(shí)際上是一個(gè)最小生成樹(shù)，可以用求最小生成樹(shù)的算法解決。構(gòu)建圖的過(guò)程比較復(fù)雜，因?yàn)閳D中任意兩點(diǎn)間都有邊，所以采用鄰接矩陣表示圖較好。構(gòu)建圖的過(guò)程比較復(fù)雜，為了方便計(jì)算兩插座間的最短距離，每個(gè)插座除了要在數(shù)據(jù)結(jié)構(gòu)中記錄坐標(biāo)外，還需要判斷它屬于哪一面墻，為此建議增加墻的編號(hào)。兩插座的分布情況：在同一面墻，相鄰的兩面墻，在對(duì)面的墻。還要考慮是否有門(mén)。輸出時(shí)要輸出的整數(shù)長(zhǎng)度要上取。二：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)結(jié)構(gòu)體：typedef struct CZ (CZ即插座的意思)/定義插座結(jié)構(gòu)體int m; /m為插座所在墻(xz面為1；yz面為2；對(duì)xz面為3；對(duì)yz面為4)float x,y,z; /x,y,z分別為插座的三個(gè)坐標(biāo)CZ;全局?jǐn)?shù)組：float MIN2020; /定義全局矩陣存放每?jī)蓚€(gè)插座之間的最短連線(xiàn)主函數(shù)：void main()CZ CZ20;int L,W,H,N;T: coutLWHN; /L，W，H即X，Y，Z方向坐標(biāo) coutendl; for(int i=0;iN;i+) cout請(qǐng)輸入第i+1CZi.mCZi.xCZi.yCZi.z; if(CZi.m4|CZi.xL|CZi.yW|CZi.zH) cout輸入數(shù)據(jù)錯(cuò)誤!重新輸入: ; goto T2; coutendl;Count(N,L,W,CZ); /計(jì)算每?jī)蓚€(gè)插座間最短連線(xiàn)cout最短連線(xiàn)為：Calculate(N,MIN)endlendl; goto T;思路與算法實(shí)現(xiàn) ：首先根據(jù)提示輸入房間的長(zhǎng)寬高和插座總數(shù)N，然后輸入各個(gè)插座坐標(biāo)及所在面（事先給每面墻編上號(hào)），輸入數(shù)據(jù)錯(cuò)誤則重新輸入，坐標(biāo)全部輸入后調(diào)用Count函數(shù)計(jì)算每?jī)蓚€(gè)插座間連線(xiàn)的最短連線(xiàn)，并把連線(xiàn)的長(zhǎng)度存入全局變量數(shù)組中，（計(jì)算兩插座間最短連線(xiàn)分同面墻、臨面墻和對(duì)面墻三種，同面墻和臨面墻計(jì)算相似，對(duì)面墻有三種連線(xiàn)方式，調(diào)用Compare函數(shù)通過(guò)比較求得最短連線(xiàn)，其中以防距離有負(fù)數(shù)，在有可能出現(xiàn)負(fù)數(shù)的地方調(diào)用Contrary函數(shù)，正數(shù)不變負(fù)數(shù)取反），計(jì)算完之后調(diào)用Calculate函數(shù)（該函數(shù)實(shí)際是貪心算法即Dijkstra算法），計(jì)算所得對(duì)稱(chēng)矩陣即鄰接矩陣的最小連通圖權(quán)值之和，由于是對(duì)稱(chēng)的，計(jì)算了兩遍，返回結(jié)果除以二即所有插座間連線(xiàn)的最短值。實(shí)用性即：新建一房子，長(zhǎng)寬高知道，量出所有插座坐標(biāo)，輸入程序即可得出電線(xiàn)的最少值，買(mǎi)電線(xiàn)時(shí)就可以花最少的錢(qián)。三：程序?qū)崿F(xiàn)其中求每?jī)蓚€(gè)插座最短連線(xiàn)為：for(int i=0;iN;i+)for(int j=0;jN;j+) if(CZi.m=CZj.m) /同面或臨面墻 |(CZi.m=1&CZj.m=2)|(CZi.m=2&CZj.m=1) |(CZi.m=1&CZj.m=4)|(CZi.m=4&CZj.m=1) |(CZi.m=2&CZj.m=3)|(CZi.m=3&CZj.m=2) |(CZi.m=3&CZj.m=4)|(CZi.m=4&CZj.m=3) p1=CZi.x-CZj.x;p2=CZi.y-CZj.y;p3=CZi.z-CZj.z; p1=Contrary(p1);p2=Contrary(p2);p3=Contrary(p3); MINij=p1+p2+p3; else /對(duì)面墻 if(CZi.m=1&CZj.m=3)|(CZi.m=3&CZj.m=1) p1=CZi.x;p2=CZj.x;p3=W; a=p1+p2+p3; p1=CZi.z;p2=CZj.z;p3=W; b=p1+p2+p3; p1=L-CZi.x;p2=L-CZj.x;p3=CZi.z-CZj.z;p3= Contrary(p3); c=p1+p2+p3; MINij=Compare(a, b,c); /找出最短連線(xiàn) else if(CZi.m=2&CZj.m=4)|(CZi.m=4&CZj.m=2) p1=CZj.y;p2=CZi.y;p3=L; a=p1+p2+p3; p1=CZi.z;p2=CZj.z;p3=L; b=p1+p2+p3; p1=W-CZj.y;p2=W-CZi.y;p3=L; c=p1+p2+p3; MINij=Compare(a, b,c); Calculate函數(shù)為：float Calculate(int N,float MIN2020)/計(jì)算最短路徑float M=0,min=MIN00,k; /min為每一遍查找的最短連接長(zhǎng)度，k為循環(huán)次數(shù)for(k=0;kN;k+) for(int i=0;iN;i+)for(int j=0;j0,MINij0;j+)if(minMINij) min=MINij; MINij=0;M+=min; /總連線(xiàn)最短長(zhǎng)度return M/2; /所得矩陣為對(duì)稱(chēng)矩陣，數(shù)據(jù)加了兩邊四：測(cè)試結(jié)果測(cè)試過(guò)程是在草稿紙上畫(huà)一個(gè)三維坐標(biāo)，在第一卦限畫(huà)一個(gè)房子，并任意墻上找出幾個(gè)點(diǎn)作為插座，編上坐標(biāo)計(jì)算最短連線(xiàn)，有簡(jiǎn)單到復(fù)雜，計(jì)算結(jié)果同程序運(yùn)行結(jié)果對(duì)照，結(jié)果一樣。具體數(shù)據(jù)：墻長(zhǎng)寬高各為5，3個(gè)插座A（1 2 0 2）B（2 2 0 4）C（3 2 5 1）計(jì)算得AB間為6，結(jié)果正確；AC間