課程設計報告小區(qū)網(wǎng)絡光纖的鋪設

1、廣東海洋大學信息學院課程設計報告設計題目 小區(qū)網(wǎng)絡光纖的鋪設課程名稱數(shù)據(jù)結構姓名（學號）龐東興（2） 劉凱（2）梁杰生（2）聯(lián)系電話（67）專業(yè)名稱計算機科學與技術所在班級 計算機科學與技術 1 班指導教師謝仕義 教師職稱教授起止時間2013 年10月29日至 2013年12月6日評定成績一、 課程設計的主要內(nèi)容設計數(shù)據(jù)結構和算法，實現(xiàn)居民小區(qū)之間網(wǎng)絡光纖鋪設的最佳方案選擇，主要內(nèi)容如下：需要在某個城市n個居民小區(qū)之間鋪設網(wǎng)絡光纖，假設任意兩個居民小區(qū)之間均需要鋪設光纖，則在這n個居民小區(qū)之間只需要鋪設n-1條光纖即可形成一個網(wǎng)絡，但由于地理環(huán)境不同，所需要的代價也不盡相同。本課程設計要求事先

2、隨機生成任意居民小區(qū)之間鋪設網(wǎng)絡光纖的代價，并將代價存入文件，然后設計一個最佳方案進行光纖鋪設，使得既能連通所有小區(qū)之間的網(wǎng)絡，又能使網(wǎng)絡光纖鋪設的代價最小，最終以圖形形式輸出所設計的最佳方案。二、 功能和結構設計1、克魯斯卡爾算法：1 克魯斯卡爾算法的思想：設無向連通網(wǎng)為G=（V，E），令G的最小生成樹為T=（U，TE）,其初態(tài)為U=V，TE=，這樣T中個頂點各自構成一個連通分量。然后，按照邊的權值由小到大的順序，依次考察邊集E中的各條邊。若被考察邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到TE中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去

3、此邊，以免造成回路，如此下來，當T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。2 算法過程描述：1. 初始化：U=V; TE=;2. 重復下述操作直到T中的連通分量個數(shù)為1； 2、1 在E中尋找最短邊（U,V）； 2、2 如果頂點u、v位于T的兩個不同連通分量，則 2 . 2 . 1、 將邊（u、v）并入TE； 2 . 2 . 2、 將這兩個連通分量合為一個； 2、3 在E中標記邊（u，v），使得（u，v）不參加后續(xù)最短邊的選??；2、 模塊分析根據(jù)對模型的功能分析，該管道鋪設設計可以具有以下功能： 網(wǎng)絡光纖鋪設信息的輸入； 最小生成樹信息的輸出；3、 抽象數(shù)據(jù)類型分析Vertex

4、 居民區(qū)Edge 鄰接矩陣儲存居民區(qū)的關系R 居民區(qū)之間的距離vertexNum 表示居民區(qū)數(shù)量edgeNum 表示居民區(qū)的路線數(shù)目4、 功能分析信息輸入：程序輸出：最短路徑：三、 流程圖和算法設計/居民區(qū)數(shù)據(jù)輸入coutvertexNum;coutendl;cout分別輸入居民區(qū)：;for(i=0;ivertexi;coutedgeNum;/二維數(shù)組存儲居民區(qū)信息cout請按此格式輸入邊和權值：n, m, k（ 表示 n 居民區(qū)到 m 居民區(qū)的距離為 k 米）：endl;for(i=0;inmk;Edgenm=k;Edgemn=k;Ri=k;coutendl;/對儲存權值的數(shù)組R進行排序vo

5、id Graph:InsertSort()int k;for(int i=1;iedgeNum;i+)k=Ri;for(int j=i-1;kRj;j-)Rj+1=Rj;Rj+1=k;/克魯卡爾算法生成最小生成樹void Graph:Kruskal()Sum=0;int i,b=0,d=0,num,vex1,vex2;for(i=0;ivertexNum;i+)parenti=-1;cout選取光纖鋪設路線：endl;for(num=0,i=0;iedgeNum;i+)vex1=FindRoot(parent,edgei.from);vex2=FindRoot(parent,edgei.to)

6、;if(vex1!=vex2)parentvex1=vex2;num+;cout從居民區(qū)edgei.from到居民區(qū)edgei.to，路徑長度為:edgei.weight 米vertexNum*(vertexNum-1)/2NYcincedgeNum=c輸權值(Edgenm), 并賦值給Ri對Ri 直接插入排序Kruskal算法輸出圖形計算代價結束四、 源程序代碼#ifndef Graph_H#define Graph_Hconst int MaxVertex=10;const int MaxEdge=100;struct EdgeTypeint from,to;int weight;temp

7、lateclass Graphpublic:Graph();Graph()void Kruskal();void InsertSort();void BubbleSort1();int FindRoot(int a,int n);void outSum();void Price();void Print();private:Datatype vertexMaxVertex;int EdgeMaxVertexMaxVertex;EdgeType edgeMaxEdge;EdgeType edgePMaxEdge;int parentMaxVertex;int vertexNum,edgeNum;

8、int RMaxEdge;int Sum;int price;#endif#includeusing namespace std;#include Graph.h#include#include#include #include#include templateGraph:Graph()getch();int i,j,k,n,m;coutvertexNum;coutendl;cout分別輸入居民區(qū)：;for(i=0;ivertexi;cout生成居民區(qū)序號表：endl;cout;for(int g=0;gvertexNum;g+)cout;coutendl;coutleftsetw(6)居民區(qū)

9、;for(int h=0;hvertexNum;h+)coutsetw(6)vertexh;coutendl;cout;for(int e=0;evertexNum;e+)cout;coutendl;coutleftsetw(6)序號;for(int f=0;fvertexNum;f+)coutsetw(6)f;coutendl;cout;for(int t=0;tvertexNum;t+)cout;coutendl;getch();coutendl;coutedgeNum;coutvertexNum*(vertexNum-1)/2)int c;cout輸入條數(shù)有誤，請重新輸入!c;edgeN

10、um=c;for(i=0;iMaxVertex;i+)for(j=0;jMaxVertex;j+)Edgeij=0;cout請按此格式輸入邊和權值：n, m, k（ 表示 n 居民區(qū)到 m 居民區(qū)的距離為 k 米）：endl;for(i=0;inmk;Edgenm=k;Edgemn=k;Ri=k;coutendl;templatevoid Graph:InsertSort()int k;for(int i=1;iedgeNum;i+)k=Ri;for(int j=i-1;kRj;j-)Rj+1=Rj;Rj+1=k;templatevoid Graph:BubbleSort1()int coun

11、t=0; while(count!=edgeNum) for(int i=0;ivertexNum;i+) for(int j=i;jvertexNum;j+) if(Edgeij=Rcount) edgecount.from=i; edgecount.to=j; edgecount.weight=Rcount; count+;templatevoid Graph:Kruskal()Sum=0;int i,b=0,d=0,num,vex1,vex2;for(i=0;ivertexNum;i+)parenti=-1;cout選取光纖鋪設路線：endl;for(num=0,i=0;iedgeNum

12、;i+)vex1=FindRoot(parent,edgei.from);vex2=FindRoot(parent,edgei.to);if(vex1!=vex2)parentvex1=vex2;num+;cout從居民區(qū)edgei.from到居民區(qū)edgei.to，路徑長度為:edgei.weight 米endl;edgePd.from=edgei.from;edgePd.to=edgei.to;d+;Sum=Sum+edgei.weight;if(num=vertexNum-1)return;templateint Graph:FindRoot(int parent,int v)int t

13、=v;if(parentt-1) t=parentt;return t;templatevoid Graph:outSum()coutendl;cout這 vertexNum 個居民區(qū)之間鋪設網(wǎng)絡光纖總長度中最短的長度為：Sum 米endl;coutendl;templatevoid Graph:Price()coutprice;coutendl;cout所以,這 vertexNum 個居民區(qū)之間鋪設網(wǎng)絡光纖所需最小費用為：Sum*price 元endl;templatevoid Graph:Print()int x1,x2,y1,y2;initgraph(500,500);if(vertex

14、Num0)circle(100,200,25);outtextxy(100,200,vertex0);if(vertexNum1)circle(250,100,25);outtextxy(250,100,vertex1); if(vertexNum2)circle(150,350,25);outtextxy(150,350,vertex2);if(vertexNum3)circle(350,350,25);outtextxy(350,350,vertex3);if(vertexNum4) circle(400,200,25);outtextxy(400,200,vertex4);if(vert

15、exNum5)circle(250,250,25);outtextxy(250,250,vertex5);for(int n=0,k=0;kedgeNum;k+) switch(edgePn.from)case 0:x1=100;y1=200;break;case 1:x1=250;y1=100;break;case 2:x1=150;y1=350;break;case 3:x1=350;y1=350;break;case 4:x1=400;y1=200;break;case 5:x1=250;y1=250;break; switch(edgePn.to)case 0:x2=100;y2=20

16、0;break;case 1:x2=250;y2=100;break;case 2:x2=150;y2=350;break;case 3:x2=350;y2=350;break;case 4:x2=400;y2=200;break;case 5:x2=250;y2=250;break; line(x1,y1,x2,y2);n+;getch();closegraph();#includeusing namespace std;#include Graph.cpp#include#includeint main()int a1;for(a1=0;a125;a1+) cout ; cout網(wǎng)絡光纖鋪

17、設的最佳方案選擇endl; for(a1=0;a121;a1+) cout ; for(a1=0;a134;a1+) cout*; coutendl; for(a1=0;a121;a1+) cout ; cout* *endl;for(a1=0;a121;a1+) cout ; cout* 歡迎使用本程序,希望本程序可以 *; coutendl; for(a1=0;a121;a1+) cout ; cout* 幫您選擇最佳鋪設方案 *; coutendl; for(a1=0;a121;a1+) cout ;cout* *; coutendl; for(a1=0;a121;a1+) cout ;

18、for(a1=0;a134;a1+)cout*;coutendl;GraphG;G.InsertSort();G.BubbleSort1();G.Kruskal();G.outSum();G.Price ();getch();G.Print ();coutendl;for(a1=0;a115;a1+) cout ; for(a1=0;a125;a1+) cout*; coutendl; for(a1=0;a115;a1+) cout ; cout* 謝 謝 您 的 使 用 ! *endl; for(a1=0;a115;a1+) cout ;for(a1=0;a125;a1+)cout*;coutendl;return 0;五