公路建设课程设计报告---公路设计问题.doc

计算机科学与技术系课程设计报告2011 2012 学年第二学期课程 数据结构与算法课程设计名称公路设计问题学生姓名 学号1004013008专业班级计算机科学与技术10级4班指导教师 2012 年 2 月题目：公路建设问题a国是一个新兴的国家，有n个城市，分别编号为1,2.3n。政府想大搞公路建设，提供了优惠政策：对于每一个投资方案的预计总费用，政府负担50%，并且允许投资的公司对过往的汽车收取连续5年的养路费。世界各地的大公司纷纷投资，并提出了自己的建设方案，他们的投资方案包括这些内容：公路连接的两座城市的编号，预计的总费用（假设他们的预计总是准确的）。你作为a国公路规划局的总工程师，有权利决定每一个方案是否接受。但是政府给你的要求是：（1）要保证各个城市之间都有公路直接或间接相连。 （2）因为是新兴国家，政府的经济实力还不强。政府希望负担最少的费用。 （3）因为大公司并不是同时提出方案，政府希望每接到一个方案，就可以知道当前需要负担的最小费用和接受的投资方案，以便随时开工。 （4）关于你给投资公司的回复可以等到开工以后再给。注意：a国一开始是没有公路的。设计要求：（1）输入第1行有两个数字：n、m ，a国的城市数目n=500，投资的方案总数mw) (*g).arcsij.adj=(*g).arcsji.adj=w; .minispantree_prim(*g),(*g).vexs0); 这是该函数的核心部分，其功能是录入图的邻接矩阵，且做到了当输入的俩顶点相同时，后输入的边的权值若比前输入的小，则后者代替前者将权值录入，反之则不做处理。求最小权值函数int minimum（）；int minimum(minside sz,mgraph g)int i=0,j,k,min;. .min=szj.lowcost;k=j;return k;帮助最小生成树求出closedgek.lowcost中最小一个；返回值为k。普利姆函数void minispantree_prim（）void minispantree_prim(mgraph g,int u)int i,j,k,l,r; . .if(closedgek.lowcost=infinity) printf(0n);return ; . .bi=g.;sum=sum+closedgek.lowcost;/ 新顶点并入u集后重新选择最小边 closedgej.adjvex=g.vexsk;closedgej.lowcost=g.arcskj.adj;本函数是该代码的重中之重；主要运用到了普利姆算法，其功能是将运行的这所生成的邻接矩阵转化为其最小生成树的权值和输出；同时解决了题目中当不可以最小生成树数时仅输出“0”的要求，方法为若所经过求最小权值函数int minimum（）后得到的权值中有等于无穷大时；则输出“0”，同时退出函数；算法思想：当非构成最小生成树则必有closedgek.lowcost为无穷大，反之则没有。顶点对焦函数int locatevex（）；int locatevex(mgraph g,int u)判断输入的顶点是否有实际的该点；4、 上机调试过程 图2：调试1图3：调试2图4：调试3图2、3、4以举例出所有的数据输入情况，解释了本程序的完整性。5、 测试结果及其分析在程序的编写过程中，我受挫无数。其中值得一提的就是编写最小生成树代码。输入 输出5 5 1 2 3 02 4 5 05 3 2 01 2 1 03 4 1 0原因有二种：1、建立邻接矩阵出错； 2、最小生成树求最小权值出错。6、用户使用说明程序适用于计算从任意城市出发连通各城市之间所的最小费用或距离。注意：输入的城市数目不得超过500，方案数目不得超过2000。7、参考文献（1） 王昆仑，李红。数据结构与算法。北京：中国铁道出版社，2007。（2） 严蔚敏，吴伟民。数据结构：c语言。北京清华大学出版社。2002。8、 附录源代码：#includemalloc.h #includestdlib.h #includestdio.h#include #define max_vertex_num 200/ 最大顶点个数#define infinity int_max/ 用整型最大值代替/ 邻接矩阵的数据结构typedef structint adj; / 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； / 对带权图，则为权值类型 int info; / 该弧相关信息的指针(可无) arccell, adjmatrixmax_vertex_nummax_vertex_num;/ 图的数据结构typedef structint vexsmax_vertex_num;/ 顶点向量adjmatrix arcs;/ 邻接矩阵int vexnum,/ 图的当前顶点数arcnum;/ 图的当前弧数 mgraph;/ 记录从顶点集u到v-u的代价最小的边的辅助数组定义typedef structint adjvex;int lowcost;minsidemax_vertex_num;int locatevex(mgraph g,int u);int createan(mgraph *g);int minimum(minside sz,mgraph g);void minispantree_prim(mgraph g,int u);/ 若g中存在顶点u,则返回该顶点在图中位置;否则返回-1。int locatevex(mgraph g,int u)int i;for(i = 0; i g.vexnum; +i)if(u=g.vexsi)return i;return -1;/ 采用数组(邻接矩阵)表示法,构造无向网g。int createan(mgraph *g)int i,j,k,w; int s;int va,vb;printf(请输入城市数目、方案数目:(空格区分) );scanf(%d%d%*c,&(*g).vexnum,&(*g).arcnum); for(i=0;i(*g).vexnum;+i) / 构造顶点向量 (*g).vexsi=i+1;for(i=0;i(*g).vexnum;+i) / 初始化邻接矩阵 for(j=0;j(*g).vexnum;+j)(*g).arcsij.adj=infinity; / 网初始化为无穷大 (*g).=0;printf(请输入各方案的二个城市和方案费用：(以空格作为间隔): n);for(k=0;kw) (*g).arcsij.adj=(*g).arcsji.adj=w; s=k+1;(*g).=(*g).=s; / 无向 minispantree_prim(*g),(*g).vexs0);return 1;/ 求closedge.lowcost的最小正值int minimum(minside sz,mgraph g)int i=0,j,k,min;while(!szi.lowcost)i+;min=szi.lowcost; / 第一个不为0的值 k=i;for(j=i+1;j0)if(minszj.lowcost)min=szj.lowcost;k=j;return k;/ 算法10.5 p330/ 用普里姆算法从第u个顶点出发构造网g的最小生成树t,输出t的各条边void minispantree_prim(mgraph g,int u)int i,j,k,l,r; int b2000;float sum=0;minside closedge;k=locatevex(g,u);for(j=0;jg.vexnum;+j) / 辅助数组初始化 if(j!=k)closedgej.adjvex=u;closedgej.lowcost=g.arcskj.adj;closedgek.lowcost=0; / 初始,u=u for(i=0;ig.vexnum-1;+i) / 选择其余g.vexnum-1个顶点 k=minimum(closedge,g); / 求出t的下一个结点：第k顶点 if(closedgek.lowcost=infinity) printf(0n);return ;l=closedgek.adjvex-1; r=g.vexsk-1; bi=g.; sum=sum+closedgek.lowcost;closedgek.lowcost=0; / 第k顶点并入u集 for(j=0;jg.vexnum;+j)if(g.arcskj.adjclosedgej.lowcost)/ 新顶点并入u集后重新选择最小边 closed