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

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

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

2、Z间均需要铺设光纤，则在这n个居民小区之间只需要铺设门-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。木课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输岀所设计的最佳方案。二.功能和结构设计1、克鲁斯卡尔算法：①克鲁斯卡尔算法的思想：设无向连通网％G=（V,E）,令G的最小生成树为丁=（U,TE），其初态为U=V,TE={},这样T中个顶点各自构成一个连

3、通分量。然后，按照边的权值由小到大的顺序,依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点屈于同一个连通分量，则舍去此边，以免造成回路，如此下来，当T中的连通分量个数为I时，此连通分量便为G的一棵最小生成树。②算法过程描述：1.初始化：U=V;TE={};2.重复下述操作直到T中的连通分量个数为1；2、1在E中寻找最短边（U,V）；2、2如果顶点u、v位于T的两个不同连通分量，则2.2.1.将边（U、v）并入TE

4、；2.2.2.将这两个连通分量合为一个；2^3在E中标记边（u,v）,使得（u,v）不参加后续最短边的选取;2、模块分析根据对模型的功能分析，该管道铺设设计可以具有以下功能:①.网络光纤铺设信息的输入；②.最小生成树信息的输出；3、抽象数据类型分析Vertcx[]Edge[][]R[]vertexNumedgeNum居民区邻接矩阵储存居民区的关系居民区之间的距离表示居民区数量表示居民区的路线数目4、功能分析信息输入：这5个居民区之间铺设网络光纤总长度中最短的长度为：55米请输入单位长度路线铺设的价格（元）:100所以

5、，这5个居民区之间铺设网络光纤所需最小费用为：5500元0程序输出:0022321210271833153526请输入网络光纤铺设路线的总条数：佃请按此格式输入边和权值：n,…k（表示n居民区到m居民区的距离为1243243344k米）：请输入居民区的个数：502581111为为为为度度度度n3434知区区区区H民民民民號居居居居hi0021纤

6、3&凶凶光民民民民取居居居居选最短路径:**欢迎便用本*稱您选*樽可以:*居民区AB■IMMOMVcDE序号01234分别输入居虽区：ABCDE圭成居民区序号表：三.流程图和

7、算法设计〃居民区数据输入cout〈〈〃请输入居民区的个数：〃；cin»vertexNum;cout<>vertex[i];cout«/z请输入网络光纤铺设路线的总条数：〃；cin>>edgeNum;〃二维数组存储居民区信息cout〈〈〃请按此格式输入边和权值:n,m,k(表示n居民区到m居民区的距离为k米):/z«endl;for(i=0;i>n>>m>>k;Edge[n][m]=k

8、;Edge[m][n]=k;R[i]二k;cout<::InsertSort(){intk;for(inti二1;i〈edgeNum;i++)k=R[i];for(intj=i-l;k::Kruskal(){Sum=0;inti,b=0,d=0,num,vexl,vex2;for(i=0;i

9、um;i++)parent[i]二T;cout«，z选取光纤铺设路线：〃〈〈cndl;for(num=0,i=0;i