C++数据结构医院选址课设

目录一、问题描述....................................................................................................2二、基本要求....................................................................................................2三、概要设计....................................................................................................21.数据结构的设计....................................................................................22.算法的设计............................................................................................33.抽象数据类型的设计............................................................................3四、详细设计..................................................................................................4五、运行与测试..............................................................................................61.遇到的错误与解决................................................................................62.调试分析................................................................................................73.运行结果................................................................................................7六、总结与心得..............................................................................................8七、程序清单..................................................................................................9参考文献..........................................................................................................15一、一、问题描述n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？二、基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度。三、概要设计1.数据结构的设计医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图G=（V，E），对任一顶点k，称E(k)=max{d(i,k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。abcde1253214顶点偏心度ab6b8d5e7(a)(b)带权有向图及各顶点的偏心度医院选址问题的算法用伪代码描述如下：1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度矩阵；2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3．具有最小偏心度的顶点即为所求。2.算法的设计本程序从总体上划分为三个模块：（1）MGraph.h定义一个头文件，包括了使邻接矩阵实现的一系列变量和数组。伪代码如下:1)定义实现基于邻接矩阵结构的抽象数据类MGraph2)在public：里定义MGraph构造函数和floyd算法和min算法3)在private：里定义实现邻接矩阵的变量（2）MGrah.cpp实现程序的具体功能伪代码如下：1)结构函数MGraph()的实现，输出初始的邻接矩阵2)实现Floyd算法，输出最终的邻接矩阵3)min()函数的实现，输出偏心度（3）Main.cpp程序实行的接口伪代码如下：1)定义输入函数input，实现数据的输入，包括村庄的个数和名字以及路的条数2)定义main（）函数，创建MGraph的对象MG来调用floyd和min算法，输出最后的结果3.抽象数据类型的设计用C++语言中的类实现基于邻接矩阵存储结构下图的抽象类数据类型定义。由于图中顶点的数据类型不确定，因此采用C++的模板机制。所以程序中定义了templateclassMGraph的模板类。四、详细设计1.设计抽象类数据类型对应的C++类定义定义了templateclassMGraph的模板类采用C++的模板机制，因为顶点的数据类型不确定。2.设计每个函数成员1)定义输入函数input（），从键盘输入村庄的个数、道路的个数、以及各个村庄之间的距离，采用邻接矩阵存储，带有相应的异常处理。核心代码如下：voidinput(){boolflag=true;while(flag){cout请输入村庄的个数：;if(cincountry_number)//异常检测break;else{cout输入有误！endl;cin.sync();//清空流cin.clear();//清除流错误标记continue;}}while(flag){cout请输入道路的条数：;if(cinroad_number&&road_number0&&road_number=country_number*(country_number-1))break;else{cout输入有误！endl;cin.sync();//清空流cin.clear();//清除流错误标记continue;}}for(inti=1;i=country_number;i++){cout请输入第i个村庄的名字：;cincountry_name[i];}}2)定义MGraph()构造函数实现输出有向图的原始邻接矩阵核心代码如下：cout初始的邻接矩阵为：endl;for(i=1;i=vertexNum;i++)for(j=1;j=vertexNum;j++){coutsetiosflags(ios::left);coutsetw(6)arc[i][j];if(j==vertexNum)coutendl;}3)定义floyd（）函数，每对顶点间最短路径长度的矩阵，实现最终邻接矩阵的输出。核心代码如下：voidMGraphDataType::Floyd()//Floyd算法{inti,j,k;for(i=1;i=vertexNum;i++)for(j=1;j=vertexNum;j++){dist[i][j]=arc[i][j];}for(k=1;k=vertexNum;k++)for(i=1;i=vertexNum;i++)for(j=1;j=vertexNum;j++)if(dist[i][k]+dist[k][j]dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}3.设计主函数定义main（）主函数，创建MGraph的对象MG来调用floyd（）和min（）算法，输出最后的结果voidmain(){input();MGraphstringMG(country_name,country_number,road_number);MG.Floyd();cout医院应该建在country_name[MG.min()]村庄！endl;}五、运行与测试1.遇到的错误与解决1)遇到了全局变量和局部变量弄串的错误,导致部分变量出现未定义的错误,后来调整了变量的位置,才消除了错误.2)在照书上使用Floyd算法时因为不熟悉使用出错,经过向他人询问才改正3)出现了缺少分号或者英文符号的情况,因为忘记修改输入法,最终经过一点一点的修改方才改正。2.调试分析1)输入调试输入相应的数据，查看能不能输出相应的邻接矩阵，从键盘输入任意的数据，查询程序能否正常运行。2)最小路径调试运行程序，查看能否将正确结果输出，测试三次以上。3)最小偏心度调试运行程序，查看能否将正确结果输出，测试三次以上。4)输出调试如果以上三步都调试成功，输出则调试成功。3.运行结果六、总结与心得编程是一件很枯燥的事情，但也是一件很有意义的事情，经过一个星期的设计学习，使我对C++语言和数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对C++语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C++语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过这次的课程设计，我感觉自己写代码的水平还有待提高，要想精通一门编程语言，写大量的代码是必不可少的。以后我将更加努力学习专业知识，努力提高写代码的能力。七、程序清单MGraph.h：constintMaxSize=10;//图中最多顶点个数templateclassDataTypeclassMGraph{public:MGraph(DataTypea[],intn,inte);//构造函数建立具有n个顶点e条边~MGraph(){}//析构函数为空voidFloyd();//Floyd算法intmin();//求最小偏心度private:DataTypevertex[MaxSize];//放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组intdist[MaxSize][MaxSize];//存放中间结果的数组intvertexNum;//图的顶点数intarcNum;//图的边数};MGraph.cpp：#includeiostream#includestring#includeiomanip#includeMGraph.husingnamespacestd;templateclassDataType//图的存储结构：带权的邻接矩阵存储结构MGraphDataType::MGraph(DataTypea[],intn,inte)//构造函数{inti,j,w;vertexNum=n;arcNum=e;for(i=1;i=vertexNum;i++)//数组下标均从1开始vertex[i]=a[i];for(i=1;i=vertexNum;i++)for(j=1;j=vertexNum;j++)if(i==j)arc[i][j]=0;elsearc[i][j]=9999;//9999表示无穷大for(intk=1;k=arcNum;k++){cout请输入两个村庄的序号和它