医院选址.doc

数据结构课程设计报告设计题目: 医院选址 姓名： 李恒 学号： 2115110289 专业： 物联网工程 院系： 计算机科学与技术学院 班级： 1506 指导教师： 高秀梅 2017年 1月 6日 摘要医院是一个为人民服务的服务机构，对于医院选址的问题则关乎其利民程度，一个好的医院选址则可以更好的服务的百姓。本系统的功能就是医院选址。通过Floyd算法，实现该功能。在课程设计中，系统开发平台为Windows 7，程序设计设计语言采用Visual Studio 2010，设计简单目的明确，简易操作。关键词 程序设计；数据结构；Floyd算法；医院选址英文摘要The hospital is a service for people service for hospital location problem is related to the benefit degree, can better service the location of a good hospital of the people. The function of this system is hospital location. Through the Floyd algorithm, the realization of the function. In the curriculum design, the system development platform for Windows 7, programming design language using Visual Studio 2010, the design of simple and clear, simple operation. Key words ：programming; data structure; Floyd algorithm; hospital location 目 录摘要.1英文摘要.2问题描述.4需求分析.4概要设计.4数据结构设计.4算法设计.5程序设计与实现.8调试分析.10遇到的问题及解决方法.11心得体会.11源代码.11一、问题描述1.题目内容：问题描述：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。（n6）2.基本要求：输入各个村庄的距离（即图各结点直接弧长） 3.使用Floyd算法求最短路径4.求到所有结点路径最短的结点及其到其余结点的路径长度二、需求分析1.本程序的功能主要实现图的最短路径，2.输出最短路径的的起点，3.Floyd算法的实现。三、概要设计由于设计功能简单所有并未采用多文件结构处理；1.#define HUGE 1000000;/设最大弧长，用于最后的选择比较算法2.int n;/村庄数目 在函数外声明n 定义村庄数目的声明。3.void Shortest(int arcs1010) /用Floyd算法求出最短距离的矩阵4.int select(int arcs1010) / 选出使距离最长的那个村庄四、数据结构设计1 元素类型#define HUGE 1000000;/设最大弧长，用于最后的选择比较算法int n;/村庄数目 在函数外声明n 定义村庄数目的声明。void Shortest(int arcs1010) /用Floyd算法求出最短距离的矩阵int select(int arcs1010) / 选出使距离最长的那个村庄int v,w,u; v,w用于村庄标号同样用于计数 u用于计数 int arcs1010;数组用于存储村庄之间的距离（即结点直接的弧长）五、算法设计 1、算法分析1).Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。2).算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 2、算法实现 void Shortest(int arcs1010) /用Floyd算法求出最短距离的矩阵int u,v,w;cout=请输入相应初始指标=endl;coutn;coutn;if(n6)system(cls);coutPlease input the number more than 6!endl;Shortest(arcs);for(v=1;v=n;v+)for(w=v;w=n;w+)if(v!=w)cout村庄v与村庄warcsvw;coutn;else arcsvw=0;for(v=1;v=n;v+)for(w=1;w=v;w+)arcsvw=arcswv;for(u=1;u=n;u+)for(v=1;v=n;v+)for(w=0;wn;w+)if(arcsvu+arcsuwarcsvw)arcsvw=arcsvu+arcsuw;3、算法流程图在本题中假设输入弧长入下图所示六、程序测试与实现1、函数之间的调用关系 主函数调用算法函数2、主程序 void main()int w,arcs1010,m;Shortest(arcs);m=select(arcs);coutn-nendl;cout相应结果:选取村庄m作为医院endl;for(w=1;w=n;w+)if(w!=m) cout医院到村庄w最短距离为：arcsmwendl;coutn;coutn-nendl;3、测试数据4、测试结果七、调试分析1调试过程主要是运行编制好的程序，然后遇到错误根据系统的提示，找到相关的问题所在。运行完程序一次有错误提示，是因为忘记关闭上次调试的操作界面所导致的，这个问题经常出现，基本是粗心所导致的2算法的时空分析：时间复杂度:O(n3)；空间复杂度:O(n2)Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行V次SPFA算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：时间复杂度比较高，不适合计算大量数据。八、遇到的问题及解决办法主要问题就是Floyd算法的使用，通过参考教材及网上资料讲解，进一步认知Floyd算法通过不断编译将其实现。九、心得体会对于算法的使用和掌握必须通过践行和反复尝试才能正确调试，耐心和认真都是完成项目的重要关键。/源代码如下：#includeusing namespace std;#define HUGE 1000000; /弧长int n;/村庄数目void Shortest(int arcs1010) /用Floyd算法求出最短距离的矩阵int u,v,w;cout=请输入相应初始指标=endl;coutn;coutn;if(n6)system(cls);coutPlease input the number more than 6!endl;Shortest(arcs);for(v=1;v=n;v+)for(w=v;w=n;w+)if(v!=w)cout村庄v与村庄warcsvw;coutn;else arcsvw=0;for(v=1;v=n;v+)for(w=1;w=v;w+)arcsvw=arcswv;for(u=1;u=n;u+)for(v=1;v=n;v+)for(w=0;wn;w+)if(arcsvu+arcsuwarcsvw)arcsvw=arcsvu+arcsuw;int select(int arcs1010) / 选出使距离最长的那个村庄int v, w,i,max10; double Min=HUGE;int minmark;for(i=1;i=n;i+) maxi=0;for(v=1;v=n;+v)for(w=1;wmaxv) maxv=arcsvw;for(i=1;i=n;i+) if(maxiMin) Min=maxi;minmark=i;return minmark;void main()int w,arcs1010,m;Shortest(arcs);m=select(arcs);coutn-nendl;cout相应结果:选取村庄m作为医院endl;for(w=1;w=n;w+)if(w!=m) cout医院到村庄w最短距离为：arcsmwendl;coutn;coutn-nendl;