论文数据结构课设居民小区光纤路线铺设最优方案.doc

《数据结构》课程设计 题目 居民小区光纤路线铺设最优方案设计 姓名 李楚富 院系 信息学院 班级 计科1113 学号 201111621314 时间 2012-12-12 问题描述 在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。 问题分析 居民小区及之间铺设的网络光纤类似于无向图的顶点及边,且最优方案要求:既能连通所有小区之间的网络又能使网络光纤铺设的代价最小，因此居民小区之间的网络采用图结构表示，其光纤铺设的最佳方案选择即为生成图的最小生成树。 逻辑结构和存储结构设计 1.逻辑结构设计: 由问题分析知,须采用图结构组织和处理各个居民区及任意居民区间距离的数据关系; 2.存储结构设计: 由于在算法执行过程中需要不断读取任意两个顶点之间的权值,所以图采用邻接矩阵存储. 算法设计 设G=(V,E)是一个无向连通网，令T=(U,TE)是G的最小生成树。T的初始化状态为U={ v0 }( v0 ∈V),TE={}，重复执行以下操作：在所有u∈U,v∈V–U的边中一条代价最小的边（u,v）并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1条边，则T就是一棵最小生成树。为了节省时间和空间，在边集中选取最短边时，对于V–U中的每个顶点，只保留从该顶点到U中某顶点的最短边。 伪代码描述如下： 1. 初始化：U={ v0 },TE={}； 2. 重复执行以下操作，直至U=V： 2.1 在E中寻找最短边(u，v)，且满足u∈U,v∈V–U； 2.2 U=U+{V}； 2.3 TE=TE+{（u,v）}； 时间复杂度和空间复杂度分析 1.时间复杂度分析: 由以下源代码中的最小生成树算法,设图中有n个顶点，则第一个进行初始化的循环语句需要执行n-1次，第二个循环共执行n-1次，内嵌两个循环：其一是在长度为n的数组中求最小值，需要执行n-1次；其二是调整辅助数组，需要执行n-1次。 所以——该算法的时间复杂度为O(n2),与图中的边数无关。 2.空间复杂度分析: 根据以下源代码,设图中有n个顶点，由于采用邻接矩阵存储存储数据，故该算法的空间复杂度为O(n2)。 源代码 #include iostream #include fstream using namespace std; #define undefineNum 9999;//默认初始化数据的值 const MaxNum=50;//存储图数据的数组的最大值 void main() { goon:cout**********************************************\n; cout**** 居民小区光纤路线铺设最优方案设计 ****\n; cout**** Author: 李楚富 练思安 朱礼雄 ****\n; cout**** Grade: 计科1113 ****\n; cout**** Time: 2101-12-12 ****\n; cout**********************************************\n\n; int areaNum,lineNum;// 居民区个数, 光纤线路条数 int area1,area2;// 某光纤路线的两个居民区 double price;//光纤线路单位长度价格 double distance,lower_distance=0;//两居民区间的距离,最短总路线长度 int areaArrary[MaxNum][MaxNum];//将表示居民区的无向图用邻接矩阵表示 int i,j;//变量 cout请输入居民区个数: ; cinareaNum; cout请输入光纤线路条数: ; cinlineNum; cout请输入光纤线路单位长度价格(元/米): ; cinprice; coutendl; for(i=0;iareaNum;i++) for(j=0;jareaNum;j++) areaArrary[i][j]=undefineNum;//初始化图的邻接矩阵 cout--请输入各光纤线路的两居民区及距离,如: 0 1 50\n; j=1;//j表示第n条线路 for(i=0;