光纤通信网铺设方案设计

数据结构实验报告题 目： 光纤通信网铺设方案设计 班 级： 姓 名： 学 号： 完成日期： 2012/5/28 1问题描述在n个城市间建设光纤通信网络，要求仅选择n-1条线路铺设光缆，且达到每个城市都有光缆连通。请用C语言编写程序，求出以最低经济代价（光缆总量最短）建设这个通信网的方案。城市个数、两个城市间的距离由学生自己设计，存储结构和实现算法由学生自己选定并实现。2需求分析（1）输入的形式和输入值的范围； 形式：数字 范围：无限（2）输出的形式；最小生成树 （3）程序所能达到的功能。在n个城市间建设光纤通信网络，要求仅选择n-1条线路铺设光缆，且达到每个城市都有光缆连通。3概要设计（1）说明本程序中用到的所有抽象数据类型的定义（含数据对象、数据关系、基本操作）；typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum（2）系统中子程序及功能要求；子程序：将建立的网络各个连接的节点赋上权值void insit(adgeset>,int n,adjmatrix GA)for(int i=1;in;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; 子程序：初始化的无向图，将每条边的权值赋值为无穷void insitadj(adjmatrix &GA) for(int i=1;imaxvertexnum;i+)for(int j=1;jmaxvertexnum;j+)GAij=20000;子程序：以各个城市为基础建立一个网络void setadj(adjmatrix &GA,int n) /建立网络for(int i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)printf(请输入第%d个城市到第%d个城市的距离：,i,j);scanf(%d,&GAij);for(i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)GAji=GAij;子程序：输出我们所找到的最小生成树void fun(adjmatrix GA,adgeset>,int n) int i;for(i=1;in;i+)int min=10000,m=i;for(int j=i;jn;j+)if(GTj.weightmin)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;jn;j+)int t=GTj.rearvex;int w=GAkt;if(wGTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;in;i+)printf(第%d个城市到第%d城市修建一条电缆!n,GTi.frontvex,GTi.rearvex); printf(这样修建可以使距离最短！n);（3）主程序及各程序模块（函数）之间的层次（调用）关系。int main() printf(请问您要在几个城市间建立网络？n请在此输入：);int n; scanf(%d,&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;4详细设计普利姆算法求最小生成树的主要思想假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。对于最小生成树问题：最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个但是他们权值之和是相等的。5总结这次试验是关于最小生成树的一次试验，这次试验利用光纤这个实际问题，将如何设计最小生成树的理论知识应用在实践层面，巧妙地叫理论知识和实际情况结合起来，对我们有一个很好地锻炼方法。这次试验我收获很多，将老师在上课讲解的有关于最小生成树的相关知识很有效的结合起来了，充分的锻炼了自己的动手能力。 在本次试验的学习中让我很清楚的认识了利用普利姆和克鲁斯卡尔算法求解最小生成树的算法思想，明白了最小生成树是怎么样形成的。我们将我们的城市的空间分布抽象为一个带有权值的网络为我们利用普利姆算法和克鲁斯卡尔算法提供了基础。在完成此次试验之后我感触很深。认识到数据结构这门课的重要性，在以后的学习计算机方面的课程时我们要注意理论与实践并行。多多上机实践。只有实践才能出真知，在我们设计程序的时候遇到困难不要急躁，要耐心，细心认真的完成，只有这样才能得到事半功倍的效果。遇到挫折不要放弃，一步一个脚印，最终会得到自己想要的成果。6附录源程序代码：#include#define maxvertexnum 20 #define maxedgenum 40 typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;void insitadj(adjmatrix &GA);void setadj(adjmatrix &GA,int n);void fun(adjmatrix GA,adgeset >,int n);void display(adgeset GT,int n);void insit(adgeset >,int n,adjmatrix GA);void insit(adgeset>,int n,adjmatrix GA)for(int i=1;in;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; void insitadj(adjmatrix &GA)for(int i=1;imaxvertexnum;i+)for(int j=1;jmaxvertexnum;j+)GAij=20000;void setadj(adjmatrix &GA,int n) /建立网络for(int i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)printf(请输入第%d个城市到第%d个城市的距离：,i,j);scanf(%d,&GAij);for(i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)GAji=GAij;void fun(adjmatrix GA,adgeset>,int n) int i;for(i=1;in;i+)int min=10000,m=i;for(int j=i;jn;j+)if(GTj.weightmin)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;jn;j+)int t=GTj.rearvex;int w=GAkt;if(wGTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;in;i+)printf(第%d个城市到第%d城市修建一条电缆!n,GTi.frontvex,GTi.rearvex); printf(这样修建可以使距离最短！n);int main() printf(请问您要在几个城市间建立网络？n请在此输入：);int n; scanf(%d,&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;程序运行结果：请问您要在几个城市间建立网络？请在此输入：4请输入第1个城市到第2个城市的距离：10请输