公路建设课程设计报告公路设计问题.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，投资的方案总数M<=2000。第2行到第M+1行给出了各个投资方案，第i行的方案编号为i-1；编号小的方案先接到，一个方案占一行，每行有3个数字，分别是连接的两个城市编号a、b，和投资的预计总费用cost。（2）输出文件共有M行。每一行的第一个数字是当前政府需要负担的最少费用（保留1位小数），后面是X个数字，表示当前政府接受的方案的编号，不要求从小到大排列。但如果此时接受的所有投资方案不能保证政府的第一条要求，那么这一行只有一个数字0。（3）应用“数据结构与算法”课程知识建立该问题的数据结构模型；（4）分析算法的时间性能。1、问题分析和任务定义这道题看起来很复杂，其实就是要求你对一个最小生成树进行动态维护。 通过对问题的认真分析，初步得到结论：（1）问题中涉及的具体事物可以抽象为数据结构中图的存储。（2）图可以用邻接矩阵来储存，邻接矩阵记录城市数目（顶点数）、投资方案数（边数）、投资方案费用（权值）以及投资方案的编号（次权值），且存储的数据类型均为整型，其中投资方案费用、投资方案的编号要用较复杂的结构体定义。（3）将图的数据信息存储的邻接矩阵时，要注意录入方案的俩个城市可能会一样；这时就必须对录入的权值进行选择，让较小的权值录入。（4）该问题的核心在于如何求出所有城市间的最短路径；由于方案的逐一录入的，所有需要判断已录入的方案是否可以生成最小生成树；若生成则输出费用等信息，否则输出0。问题要求的输入输出的格式较为苛刻；故需认真考虑所给的信息，该输入什么，不该输入什么；该输出什么，不该输出什么。如当不满足生成最小生成树的时候，输出“只有一个数字0”。上述具体的解决方案见详细设计。2、 数据结构的选择和概要设计程序分为两大部分 1 存储部分， 2 算法部分；存储部分分为邻接矩阵；算法部分分为普里母算法。时间复杂度:邻接矩阵创建：每次读入一条边 e(a,b)，要检查a, b之间是否有路径相连，我们需要一个深搜的过程 ,如果我们用链表的话，深搜的时间复杂为 O(e)，而最小树形图中最多只有 n-1 条边，所以这个过程为 O(n)级的 ,然后我们要去边与加边，这都是小于O(n)级的， ,所以维护的时间复杂的是O(n)级的。 因为有m要增加，我们总共要维护 m次， 所以总的时间复杂度为O(n*m)级的，这是可以承受的。普里姆算法的建立为O（n*n）级的。邻接矩阵的算法思想：用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。补充：closedgev的类型： 用来存储从U到V-U之间具有最小代价的边。其中一个是权值域lowcost存储最小代价的边上的权值，另一个是顶点域adjves，存储依附于该边在U中的顶点。 动态维护最小生成树的处理方法： 读入一条a到b的边之后，先不将这一条边加入图中，检查 a到 b之间是否有路径相连，若相连则找到路径上权值最大的一条边 e(u,v)；若e(u,v)的权值比新读入的这条边的权值要小或相等，则去掉新读入的边；若e(u,v)的权值比新读入的这条边的权值要大，则去掉 e(u,v)，加入新读入的边；若不相连则直接将新读入的边。这样，每次读入一条边后，仍能使图保持为最小树形图。本程序包含5个函数：主函数int main()；顶点对焦函数int LocateVex（）；创建邻接矩阵函数int CreateAN（）；求最小权值函数int minimum（）；普利姆函数void MiniSpanTree_PRIM（）；各函数间关系如图1所示： int main int CreateAN（） void MiniSpanTree_PRIM（） int LocateVex（） int minimum（）图1 :各函数之间关系 3、详细设计和编码（1）结点类型邻接矩阵的数据结构typedef struct int adj;/ 顶点关系类型 int info;/该弧相关信息ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; 使边不仅记录了权值还记录了边相关信息（如编号）图的数据结构typedef struct int vexsMAX_VERTEX_NUM;/ 顶点向量 AdjMatrix arcs;/ 邻接矩阵 int vexnum,/ 图的当前顶点数 arcnum;/ 图的当前弧数 MGraph;记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structint adjvex; int lowcost;minsideMAX_VERTEX_NUM;（2）诠释各函数的功能：主函数int main()MGraph G;CreateAN(&G);system("pause");return 0; 创建邻接矩阵数据结构变量G；调用函数CreateAN(&G)。创建邻接矩阵函数int CreateAN（）int CreateAN(MGraph *G)int i,j,k,w; . .if(*G).arcsij.adj=INFINITY)/判断原是否存在边(*G).arcsij.adj=(*G).arcsji.adj=w; / 无向 else if(*G).arcsij.adj>w) (*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.arcslr.info;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、 附录源代码：#include"malloc.h" #include"stdlib.h" #include"stdio.h"#include <limits.h>#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).arcsij.info=0;printf("请输入各方案的二个城市和方案费用：(以空格作为间隔): n");for(k=0;k<(*G).arcnum;+k)printf("方案%d:",k+1);scanf("%d%d%d%*c",&va,&vb,&w); / %*c吃掉回车符 i=va-1;j=vb-1;if(*G).arcsij.adj=INFINITY)/判断原是否存在边(*G).arcsij.adj=(*G).arcsji.adj=w; / 无向 else if(*G).arcsij.adj>w) (*G).arcsij.adj=(*G).arcsji.adj=w; s=k+1;(*G).arcsij.info=(*G).arcsji.info=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;j<G.vexnum;j+)if(SZj.lowcost>0)if(min>SZj.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;j<G.vexnum;+j) / 辅助数组初始化 if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; / 初始,U=u for(i=0;i<G.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.arcslr.info; sum=sum+closedgek.lowcost;closedgek.lowcost=0; / 第K顶点并入U集 for(j=0;j<G.vexnum;+j)if(G.arcskj.adj<closedgej.lowcost)/ 新顶点并入U集后重新选择最小边 closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;printf("以连通 总费用%.1f ",sum);printf("所用方案：");for(i=0;i<G.vexnum-1;+i)printf("%d ",bi);printf("n");int main()MGraph G;CreateAN(&G);system("pause");return 0;