1、 课程设计报告 设 计 题 目 小区网络光纤的铺设小区网络光纤的铺设 课 程 名 称 姓名（学号） 联 系 电 话 专 业 名 称 计算机科学与技术 所 在 班 级 计算机科学与技术 1 班 指 导 教 师 教 师 职 称 起 止 时 间 2013 年 10 月 29 日至 2013 年 12 月 6 日 评 定 成 绩 一、一、 课程设计的主要内容课程设计的主要内容 设计数据结构和算法，实现居民小区之间网络光纤铺设的最佳方案选择，主要内容如 下：需要在某个城市 n 个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要 铺设光纤，则在这 n 个居民小区之间只需要铺设 n-1 条光纤即可形
2、成一个网络，但由于地 理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间 铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既 能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设 计的最佳方案。 二、二、 功能和结构设计功能和结构设计 1、克鲁斯卡尔算法、克鲁斯卡尔算法： 克鲁斯卡尔算法的思想： 设无向连通网为 G=（V，E） ，令 G 的最小生成树为 T=（U，TE）,其初态为 U=V， TE=， 这样 T 中个顶点各自构成一个连通分量。 然后， 按照边的权值由小到大的顺序， 依次考察边集 E 中的各条边。若被
3、考察边的两个顶点属于 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、 将这两个连通分量合为一个； 2、3 在 E 中标记边
4、（u，v） ，使得（u，v）不参加后续最短边的选取； 2、模块分析模块分析 根据对模型的功能分析，该管道铺设设计可以具有以下功能： 网络光纤铺设信息的输入； 最小生成树信息的输出； 3 3、抽象数据类型分析抽象数据类型分析 Vertex 居民区 Edge 邻接矩阵储存居民区的关系 R 居民区之间的距离 vertexNum 表示居民区数量 edgeNum 表示居民区的路线数目 4 4、功能分析功能分析 信息输入： 程序输出： 最短路径： 三、三、 流程图和算法设计流程图和算法设计 /居民区数据输入 coutvertexi; coutnmk; Edgenm=k; Edgemn=k; Ri=k; c
5、outc edgeNum=c 输权值(Edgenm), 并赋 值给 Ri 对 Ri 直接插入排序 Kruskal 算法 输出图形 四、四、 源程序代码源程序代码 #ifndef Graph_H #define Graph_H const int MaxVertex=10; const int MaxEdge=100; struct EdgeType int from,to; int weight; ; template class Graph public: Graph(); Graph() void Kruskal(); void InsertSort(); void BubbleSort1
6、(); 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; int RMaxEdge; int Sum; int price; 计算代价 结束结束 ; #endif #include using namespace std; #include “Graph.h“ #include #include #include #include #include template Graph:Graph() ge
