數據結構課程設計報告.docVIP

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