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

《课程设计报告-- 小区网络光纤的铺设》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。二、功能和结构设计1、克鲁斯卡尔算法：①　克鲁斯卡尔算法的思想：设无向连通网为G=（V，E），令G的最小生成树为T=（U，TE）,其初态为U=V，TE={}，这样T中个顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，依次考察

3、边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下来，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。②　算法过程描述：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、将这两个连通分量合

4、为一个；2、3在E中标记边（u，v），使得（u，v）不参加后续最短边的选取；2、模块分析根据对模型的功能分析，该管道铺设设计可以具有以下功能：①．网络光纤铺设信息的输入；②．最小生成树信息的输出；3、抽象数据类型分析Vertex[]居民区Edge[][]邻接矩阵储存居民区的关系R[]居民区之间的距离vertexNum表示居民区数量edgeNum表示居民区的路线数目4、功能分析信息输入：程序输出：最短路径：一、流程图和算法设计//居民区数据输入cout<<"请输入居民区的个数：";cin>>vertex

5、Num;cout<>vertex[i];cout<<"请输入网络光纤铺设路线的总条数：";cin>>edgeNum;//二维数组存储居民区信息cout<<"请按此格式输入边和权值：n,m,k（表示n居民区到m居民区的距离为k米）："<>n>>m>>k;Edge[n][m]=k;Edge[m][n]=k;R[i]=k;}cout<

6、l;//对储存权值的数组R[]进行排序voidGraph::InsertSort(){intk;for(inti=1;i::Kruskal(){Sum=0;inti,b=0,d=0,num,vex1,vex2;for(i=0;i

7、-1;cout<<"选取光纤铺设路线："<

8、dgeP[d].from=edge[i].from;edgeP[d].to=edge[i].to;d++;Sum=Sum+edge[i].weight;if(num==vertexNum-1)return;}}}流程图：开始输入顶点数(vertexNum)，小区序号(vertex[i])，边数(edgeNumedgeNum>vertexNum*(vertexNum-1)/2NYcin>>cedgeNum=c输权值(Edge[n][m]),并赋值给R[i]