医院选址问题课程设计1

课程设计说明书课程名称：数据结构设计题目：医院选址问题院系：计算机科学与信息技术学生姓名：学号：专业班级：软件工程一班指导教师：2012年6月10日课程设计任务书设计题目医院选址问题学生姓名所在院系计算机科学与信息技术专业、年级、班10级软件工程1班设计要求：n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，要求找出能使所有的村庄到医院的距离都比较近的村庄。且满足以下要求：1、可根据顶点数目n随机生成村庄直接交通图，并输出显示。2、给出符合要求的村庄的名称。学生应完成的工作：使用C语言构造有向带权图，并将其用邻接矩阵的方式存储。使用Floyd算法对图进行操作，生成该图各点到各点的最短路径的邻接矩阵。求出其余点到某点的最短路径的和，并找出这些和里面的最小值，则该点即为所求点。参考文献阅读：数据结构（C语言版)工作计划：首先对题目进行理解，明白需要该问题所包含的数据类型与算法。然后进行程序的编写，对主要功能的实现。最后测试数据并完善程序相关功能。任务下达日期：2012年6月2日任务完成日期：2012年6月8日指导教师（签名）：学生（签名）：（设计题目）摘要：本程序使用C语言构造有向带权图，并将其用邻接矩阵的方式存储。使用Floyd算法对图进行操作，生成该图各点到各点的最短路径的邻接矩阵。求出其余点到某点的最短路径的和，并找出这些和里面的最小值，则该点即为所求点。关键词：图Floyd算法最短路径-1-目录1.设计背景.....................................................................................................-1-1.1可解决实际问题.................................................................................-1-1.2可进行数据测试.................................................................................-1-2.设计方案.......................................................................................................-1-2.1主函数进行分支的选择.....................................................................-1-2.2解决具体问题分支的设计.................................................................-2-2.3随机数据测试分支的设计.................................................................-2-3.方案实施.....................................................................................................-3-3.1图的结构体定义.................................................................................-3-3.2主函数.................................................................................................-3-3.3已知信息的图的构建.........................................................................-3-3.4随机生成图的构建.............................................................................-3-3.5核心算法（Floyd算法）..................................................................-4-3.6源程序.................................................................................................-4-4.结果与结论.................................................................................................-9-4.1功能选择界面.....................................................................................-9-4.2选择分支1（输入数据）..................................................................-9-4.3选择分支2（随机生成数据）.......................................................-10-5.收获与致谢...............................................................................................-11-6.参考文献..................................................................................................-12--2-7.附件..........................................................................................................-12--1-1.设计背景1.1可解决实际问题通过编写的程序，可以根据录入的相关数据（包括村庄数目、道路数目、道路的起点和终点以及路程），找出最适合的医院选址，使各村庄到该医院的路程最短。并对一些相关的关键数据进行输出，以便看到其实现过程。通过该过程可以使用其解决遇到的具体问题。1.2可进行数据测试通过编写的程序，可以随机生成相关数据（包括村庄数目、道路数目、道路的起点和终点以及路程），并找出最适合的医院选址，使各村庄到该医院的路程最短。并对一些相关的关键数据进行输出，以便看到其实现过程。通过该过程可以测试算法的普遍适用性。2.设计方案2.1主函数进行分支的选择开始分支1分支2-2-2.2解决具体问题分支的设计分支1输入产生村庄数与道路数输入道路起点、终点与路程CreateGraph函数构造图的邻接矩阵存储ShortestPath_Floyd函数寻找最短路径，并求其和的最小值输出结束2.3随机数据测试分支的设计分支2-3-3.方案实施3.1图的结构体定义对图的结构进行定义，存储方式为邻接矩阵的形式（arcs[MAX_NUM][MAX_NUM]），包含vexnum（顶点）与arcnum（边）2个基本变量（之前将点与点之间的最大值MAX定义为10000），在程序中为：typedefstruct{}Graph;这一部分。3.2主函数首先产生一个有向带权图G，然后使用P[MAX_NUM][MAX_NUM][MAX_NUM]存放每对顶点的最短路径，D[MAX_NUM][MAX_NUM]存放每对顶点的最短路径的距离。最后使用循环进行操作的选择：1的话根据输入数据寻找最佳村庄；2的话随机生成村庄数与道路数进行测试；0的话则跳出循环结束程序。在程序中为：voidmain（）这一部分。3.3已知信息的图的构建定义了start,end,weight3个变量分别保存边的起点，终点，权值。通过scanf录入图的顶点数（即村庄数）与边数（即道路数），然后根据录入信息初始化一个对应的图的邻接矩阵，最后录入图中边的起点，终点，权值并赋给相关变量。在程序中为：voidCreateGraph（）这一部分。3.4随机生成图的构建-4-定义了start,end,weight3个变量分别保存边的起点，然后通过rand（）产生随机数并赋给顶点数与边数，并输出产生的数字。然后根据相关信息初始化一个对应的图的邻接矩阵，最后循环产生随机数并赋给图中边的起点，终点，权值。在程序中为：voidCreateRGraph（）这一部分。3.5核心算法（Floyd算法）对已建成的有向带权图使用Floyd算法，可得到该图各点到各点的最短路径的邻接矩阵。然后对邻接矩阵进行纵向求和，并将和赋值给最短路径求和数组a[w]。最后比较a[w]数组中的各值，将最小值对应的顶点序号输出。期间，分别将最短路径的邻接矩阵和最短路径求和数组a[w]输出。在程序中为：voidShortestPath_Floyd（）这一部分。3.6源程序#includedos.h#includetime.h#includestdio.h#includeconio.h#includestdlib.h#includestring.h#defineINFINITY10000//定义权值的最大值#defineMAX_NUM20//图的最大顶点数enumBOOL{False,True};typedefstruct{intarcs[MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数}Graph;-5-voidCreateGraph(Graph&);//生成图的邻接矩阵voidShortestPath_Floyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);//用弗洛依德算法求每对顶点之间的最短路径voidCreateRGraph(Graph&G);//生成随机图voidmain(){GraphG;//采用邻接矩阵结构的图intu,i;BOOLP[MAX_NUM][MAX_NUM][MAX_NUM];//存放每对顶点的最短路径intD[MAX_NUM][MAX_NUM];//存放每对顶点的最短路径的距离do{//从菜单中选择遍历方式，输入序号。printf(\t**********select************\n);printf(\t1:根据输入数据寻找最佳村庄\n);printf(\t2:随机生成村庄数与道路数进行测试\n);printf(\t0:Exit\n);printf(\t*******************************\n);scanf(%d,&i);//输入菜单序号（0-2）switch(i){case1:printf(首先输入村庄数目（2-19）和道路数目：\n例如：3,5\n);printf(接着输入道路的起点和终点(i,j)及其路程。\n例如：\n1,2,4\n2,1,6\n1,3,11\n3,1,3\n2,3,2\n);CreateGraph(G);//生成邻接矩阵结构的图ShortestPath_Floyd(G,P,D);//利用弗洛依德算法求最短路径break;case2:printf(随机产生的村庄数目与道路数目：);CreateRGraph(G);//生成邻接矩阵结构的图ShortestPath_Floyd(G,P,D);//利用弗洛依德算法求最短路径-6-break;defau