课程设计报告小区网络光纤的铺设

1、广东海洋大学信息学院课程设计报告设计题目 小区网络光纤的铺设课程名称数据结构姓名（学号）庞东兴（2） 刘凯（2）梁杰生（2）联系电话（67）专业名称计算机科学与技术所在班级 计算机科学与技术 1 班指导教师谢仕义 教师职称教授起止时间2013 年10月29日至 2013年12月6日评定成绩一、 课程设计的主要内容设计数据结构和算法，实现居民小区之间网络光纤铺设的最佳方案选择，主要内容如下：需要在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先

2、随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。二、 功能和结构设计1、克鲁斯卡尔算法：1 克鲁斯卡尔算法的思想：设无向连通网为G=（V，E），令G的最小生成树为T=（U，TE）,其初态为U=V，TE=，这样T中个顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去

3、此边，以免造成回路，如此下来，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。2 算法过程描述：1. 初始化：U=V; TE=;2. 重复下述操作直到T中的连通分量个数为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）不参加后续最短边的选取；2、 模块分析根据对模型的功能分析，该管道铺设设计可以具有以下功能： 网络光纤铺设信息的输入； 最小生成树信息的输出；3、 抽象数据类型分析Vertex

4、 居民区Edge 邻接矩阵储存居民区的关系R 居民区之间的距离vertexNum 表示居民区数量edgeNum 表示居民区的路线数目4、 功能分析信息输入：程序输出：最短路径：三、 流程图和算法设计/居民区数据输入coutvertexNum;coutendl;cout分别输入居民区：;for(i=0;ivertexi;coutedgeNum;/二维数组存储居民区信息cout请按此格式输入边和权值：n, m, k（ 表示 n 居民区到 m 居民区的距离为 k 米）：endl;for(i=0;inmk;Edgenm=k;Edgemn=k;Ri=k;coutendl;/对储存权值的数组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从居民区edgei.from到居民区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分别输入居民区：;for(i=0;ivertexi;cout生成居民区序号表：endl;cout;for(int g=0;gvertexNum;g+)cout;coutendl;coutleftsetw(6)居民区

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输入条数有误，请重新输入!c;edgeN

10、um=c;for(i=0;iMaxVertex;i+)for(j=0;jMaxVertex;j+)Edgeij=0;cout请按此格式输入边和权值：n, m, k（ 表示 n 居民区到 m 居民区的距离为 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从居民区edgei.from到居民区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 个居民区之间铺设网络光纤总长度中最短的长度为：Sum 米endl;coutendl;templatevoid Graph:Price()coutprice;coutendl;cout所以,这 vertexNum 个居民区之间铺设网络光纤所需最小费用为：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网络光纤铺

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;五