数据结构课程设计-最小通信网.doc

课 程 设 计 报 告课程名称 数据结构课程设计 题 目 最小通信网 指导教师 设计起始日期 5.25.9 学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号 成 绩 一、 需求分析 要在n个城市之间建立通信网，已知各个城市间的距离，建立的通信线路要使得这n个城市相连，而且建立的通信网络代价最小。（1） 输入：n个城市的距离关系图，即图的顶点和边上的权值 （2） 输出：含n个城市顶点的最小生成树中的边和代价（3） 功能：建立图的最小生成树（4） 测试数据：自选二、 概要设计1、 数据结构用图来描述n个城市之间的关系，顶点为城市，边位两个城市间的代价2、 使用算法：采用prim算法算法思想：假设G=(V,E)为待求图，其中V为图中所有顶点的集合，E为带权图中所有带权边的集合。设置两个新的集合U和TE，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最先生成树的边。令集合U的初值U=u1（假设构造最小生成树时，顶点从u0出发），集合TE的初值为TE=。Prim算法的思想是，从所有uU，vV-U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合TE中，如此不断重复，直到U=V，最小生成树树构造完毕，这时集合TE中包含了最小生成树的所有边 Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。（1）Uu1,T=; （2）while (UV)do (u，v)minwuv；uU，vVU TT(u，v) UUv （3）结束三、 详细设计 1、数据结构详细设计 图的邻接矩阵 typedef struct int Vnum;/*图的顶点数*/ int ArcsMAXNMAXN;/*邻接矩阵*/ Graph;/*图的邻接矩阵存储法*/2、最小生成树PRIM算法:在Prim算法中，应当考虑如何有效地找出满足条件iU,jV-U，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个一维数组closest和lowcost。Lowcostj中存储iU,jV-U且权最小的边(i,j)的权值cij，而closestj中存储的是最小边（i，j）的另一个端点i。在Prim算法执行过程中，先找出V-U中lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到U中，并对其他closest和lowcost作必要的修改。伪算法如下：int prim(Graph G, int u) 1. u0= 起始点u; 2. for 每个结点v 3. 初始化距离数组Closest()和Lowcost() 4. for V-U中的顶点i 5. for 所有顶点j 6 k使Lowcost()最小的顶点 7. 将顶点k及边(k,closest(k)加入MST中 8. for 所有顶点j 9. if 原Lowcost(j)c(k,j) 10. Lowcost(j)= c(k,j) 11. Clostest(j)=k 12. return MST一、 调试分析a调试过程中遇到的问题调试过程中出现了结果输出错误问题，经过跟踪调试发现是在修正Lowcost数组和Closest数组过程中数据未被修正，经改正后结果正确。b算法的时空分析算法中共四个for循环，第一个循环次数为n，第二个为n-1，第三个为n，第四个为n，并且第二个和第三、四个循环嵌套，所以循环次数为n的平方数量级。所以时间复杂度为O(n2)。算法中用到了两个辅助一维数组closest和lowcost，数组的大小为n，即图的顶点个数，所以算法的空间复杂度为O(n)。二、 程序清单1、图的建立程序：作为图的数据结构.#include#include#define MAXN 50#define INFINITY 32767 typedef struct int Vnum;/*图的顶点数*/ int ArcsMAXNMAXN;/*邻接矩阵*/ Graph;/*图的邻接矩阵存储法*/ int create_graph(Graph *p)/*图的创建,成功时返回非0值，失败时返回0*/ int i,j,n; int v1,v2,w; char c; printf(nInput the vexnumber of graph:); scanf(%d,&n); if(nVnum=n; for(i=0;in;i+) for(j=0;jArcsij=0; else p-Arcsij=INFINITY; printf(nWill you input the weight of an edge?(y or n):); while(tolower(c=getchar()=y) printf(nedge(vertex1,vertex2,weight):); scanf(%d%d%d,&v1,&v2,&w); if(v1=0&v1=0&v2Arcsv1v2=p-Arcsv2v1=w; printf(nWill you continue to input the weight of an edge?(y or n):); return 1; 2、Prim算法：int prim(Graph G,int u0,int tree3)/*返回生成树的代价,v是指定的起始顶点,生成树的边存放在数组tree中*/ int i,j,k,p,min,c; int lowcostMAXN,closestMAXN; for(i=0;iG.Vnum;i+) closesti=u0; /*初始时U中只有顶点v*/ lowcosti=G.Arcsu0i;/*U中顶点到V-U中顶点代价*/ c=0; /*记录生成树的代价*/ p=0; /*从序号为0的顶点出发求最小生成树*/ for(i=0;iG.Vnum-1;i+)/*从图中找出G.Vnum-1条边，构成最小生成树*/ min=INFINITY; for(j=0;jG.Vnum;j+) /*查找U中顶点到V-U中顶点的边中权值最小者*/ /*(closestk,k)为找到的最小权值的边*/ if(lowcostj!=0&lowcostjmin) min=lowcostj; k=j; treep0=closestk;/*存放找到的最小权值的边*/ treep1=k; treep2=min; p+; c+=min;/*计算当前生成树的代价*/ lowcostk=0;/*将k加入U*/ for(j=0;jG.Vnum;j+)/*更新V-U中与k邻接的顶点到U中顶点的代价*/ if(G.Arcskj!=0&G.Arcskjlowcostj) lowcostj=G.Arcskj; closestj=k; return c;/*返回最小生成树的代价*/ 3、测试程序：void main() int i; int treeMAXN3; int cost; Graph G; create_graph(&G); cost=prim(G,0,tree); printf(nMinimum-Cost spanning tree(prim):n); printf(edget weighttn); for(i=0;iG.Vnum-1;i+) printf(v%d,v%d)t %dn,treei0,treei1,treei2); printf(Cost:%dn,cost); 六、 使用说明和测试结果1、使用说明：首先用户输入图