医院选址问题

《算法与数据结构》课程设计报告题目：医院选址问题完成日期：2013年12月27日一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计内容1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2)基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度。三、课程设计过程1．需求分析①输入的形式和输入值的范围：首先输入村庄数目、道路数目。接着按提示输入道路的起点和终点以及路程②输出的形式：输出临接矩阵，再输出偏心度数组，然后输出最适合建立医院的村庄编号③程序所能达到的功能：根据录入的相关数据（包括村庄数目、道路数目、道路的起点和终点以及路程），找出最适合的医院选址，使所有的村庄离医院都比较近。④测试数据：A．村庄数目、道路数目：5，7B．道路的起点和终点以及路程：1，2，1；2，3，2；3，4，2；3，5，4；4，2，1；4，3，3；5，4，5.2．概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。1.为了实现上述程序功能，需要定义有向带权图的抽象数据类型：①图的结构体定义：typedefstruct{数据对象：intarcs[MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数}Graph;操作结果：构建邻接矩阵的存储结构②产生一个有向带权图的邻接矩阵voidCreateGraph(Graph&);//生成图的邻接矩阵操作结果：在屏幕生成一个有向带权图③用弗洛依德算法求最短路径voidfloyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);//用弗洛依德算法求每对顶点之间的最短路径操作结果：求得最短路径2）本程序包含3个函数：①主函数main()②构造邻接矩阵结构的图函数CreateGraph()③用弗洛依德算法求最短路径函数floyd()各函数间关系如下：3．详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。1.定义的数据结构类型typedefstruct{intarcs[MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数CreateGraph()Mainfloyd()}Graph;voidCreateGraph(Graph&);//生成图的邻接矩阵voidfloyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);//用弗洛依德算法求每对顶点之间的最短路径2.主函数的基本操作voidmain(){do{switch(i){case1:break;default:exit(1);}}while(i!=0);}3.构造邻接矩阵结构的图函数基本操作voidCreateGraph(Graph&G){//构造邻接矩阵结构的图Gdo{if(G.arcnumk)}while(G.arcnum1||G.arcnumk);for(i=1;i=G.vexnum;i++)for(j=1;j=G.vexnum;j++)for(i=1;i=G.arcnum;i++){}}3，弗洛依德算法的基本操作voidfloyd(Graph*G,intpath[MAX_NUM][MAX_NUM],intA[MAX_NUM][MAX_NUM]){//用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径path[v][w]//及其带权路径长度D[Av][w],//若path[v][w][u]为True,表明u是从v到w当前求得最短路径上的顶点//偏心度数组for(v=0;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=0;w=G-vexnum;w++){}for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离{for(w=1;w=G-vexnum;w++){}}///////////////////////for(k=1;k=G-vexnum;k++)for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=1;w=G-vexnum;w++)if(A[v][k]+A[k][w]A[v][w]){}///邻接矩阵和path矩阵对角线应该为0(上1面的结果不是0)for(k=1;k=G-vexnum;k++){}/////////for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=1;w=G-vexnum;w++){if(A[v][w]==INFINITY){}};}4．调试分析1.for(k=1;k=G-vexnum;k++)for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=1;w=G-vexnum;w++)if(A[v][k]+A[k][w]A[v][w]){A[v][w]=A[v][k]+A[k][w];path[v][w]=k;}///邻接矩阵和path矩阵对角线应该为0(上1面的结果不是0)2.while(next!=0){//课本上有出入printf(-%d,next);next=path[next][w];};printf(-%d\n,w);5．用户使用说明程序名为gg.cpp，运行环境为MicrosoftVisualC++6.0。程序执行后显示=======================1:根据输入数据寻找最佳村庄0:Exit=======================SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的数据，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择0：退出程序选择1：显示“首先输入村庄数目（2-19）和道路数目：请输入村庄数目（2-19）和道路数目，格式：村庄数目，道路数目”，要求输入村庄数目和道路数目的值（都是整数）。6．测试结果程序名为gg.cpp，运行环境为MicrosoftVisualC++6.0。程序执行后显示SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的数据，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择0：退出程序选择1：显示“首先输入村庄数目（2-19）和道路数目：请输入村庄数目（2-19）和道路数目，格式：村庄数目，道路数目”，要求输入村庄数目和道路数目的值（都是整数）。7．附录带注释的源程序。#includestdio.h#includestdlib.h#includestring.h#defineINFINITY10000//定义权值的最大值#defineMAX_NUM20//图的最大顶点数typedefstruct{intarcs[MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数}Graph;voidCreateGraph(Graph&);//生成图的邻接矩阵voidfloyd(Graph*G,intpath[MAX_NUM][MAX_NUM],intA[MAX_NUM][MAX_NUM]);//用弗洛依德算法求每对顶点之间的最短路径voidmain(){GraphG;//采用邻接矩阵结构的图inti;intpath[MAX_NUM][MAX_NUM];//存放每对顶点的最短路径intA[MAX_NUM][MAX_NUM];//存放每对顶点的最短路径的距离do{//从菜单中选择遍历方式，输入序号。printf(\t1:根据输入数据寻找最佳村庄\n);printf(\t0:Exit\n);scanf(%d,&i);//输入菜单序号（0-1）switch(i){case1:printf(首先输入村庄数目（2-19）和道路数目：\n);CreateGraph(G);//生成邻接矩阵结构的图Graph*k;k=&G;floyd(k,path,A);//利用弗洛依德算法求最短路径break;default:exit(1);}printf(\n);}while(i!=0);}voidCreateGraph(Graph&G){//构造邻接矩阵结构的图Ginti,j,k;intstart,end,weight;do{printf(请输入村庄数目（2-19）和道路数目，格式：村庄数目，道路数目\n);scanf(%d,%d,&G.vexnum,&G.arcnum);//输入图的顶点数和边数k=G.vexnum*(G.vexnum-1);if(G.arcnumk)printf(error!!\n);}while(G.arcnum1||G.arcnumk);for(i=1;i=G.vexnum;i++)for(j=1;j=G.vexnum;j++)G.arcs[i][j]=INFINITY;//初始化邻接矩阵printf(请输入道路的起点和终点(i,j)及其路程，格式：起点，终点，路程：\n);for(i=1;i=G.arcnum;i++){scanf(%d,%d,%d,&start,&end,&weight);//输入边的起点和终点及权值G.arcs[start][end]=weight;}}voidfloyd(Graph*G,intpath[MAX_NUM][MAX_NUM],intA[MAX_NUM][MAX_NUM]){//用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径path[v][w]//及其带权路径长度D[Av][w],//若path[v][w][u]为True,表明u是从v到w当前求得最短路径上的顶点intv,w,k,next,min;inta[10];//偏心度数组for(v=0;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=0;w=G-vexnum;w++){A[v][w]=G-arcs[v][w];path[v][w]=0;}////////////////打印出初始矩阵printf(\n出初始矩阵:\n);for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离{for(w=1;w=G-vexnum;w++){printf(%8d,A[v][w]);}printf(\n);}///////////////////////for(k=1;k=G-vexnum;k++)for(v=1;v=G-vexnum;v++)//各对顶点之间的初始已知路径及距离for(w=1;w=G-vexnum;w++)if(A[v][k]+A[k][w]A[v][w]){A[v][w]=A[v][k]+A[k