医院选址问题.doc

《医院选址问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法与数据结构》课程设计报告题目：医院选址问题完成日期：2013年12月27日一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上

2、机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计内容1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2)基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度。三、课程设计过程1．需求分析①输入的形式和输入值的范围：首先输入村庄数目、道路数目。接着按提示输入道路的起点和终点以及路程　　②输出的形式：输出临接矩阵，再输出偏心度数组，然后输出最适合建

3、立医院的村庄编号　　③程序所能达到的功能：根据录入的相关数据（包括村庄数目、道路数目、道路的起点和终点以及路程），找出最适合的医院选址，使所有的村庄离医院都比较近。　④测试数据：　　　A．村庄数目、道路数目：5，7　　　B．道路的起点和终点以及路程：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[

4、MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数}Graph;操作结果：构建邻接矩阵的存储结构②产生一个有向带权图的邻接矩阵voidCreateGraph(Graph&);//生成图的邻接矩阵操作结果：在屏幕生成一个有向带权图③用弗洛依德算法求最短路径voidfloyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);//用弗洛依德算法求每对顶点之间的最短路径操作结果：求得最短路径2）本程序包含3个函数：①主函数main()②构造邻接矩阵结构的图函数　CreateGra

5、ph()③用弗洛依德算法求最短路径函数floyd()各函数间关系如下：CreateGraph()Mainfloyd()3．详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。1.定义的数据结构类型typedefstruct{intarcs[MAX_NUM][MAX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点和边数}Graph;voidCreateGraph(Grap

6、h&);//生成图的邻接矩阵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.arcnum>k)}while(G.arcnum<1

7、

8、G.arcnum>k);for(i=1;i<=G.ve

9、xnum;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++