《算法与数据结构》课程设计报告题目：医院选址问题完成日期： 2013 年 12 月 27 日一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识， 上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计， 要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计内容1)问题描述n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i 到村庄 j 的道路长度。现在要从这n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2) 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。三、课程设计过程1．需求分析① 输入的形式和输入值的范围：首先输入村庄数目、道路数目。接着按提示输入道路的起点和终点以及路程② 输出的形式：输出临接矩阵，再输出偏心度数组，然后输出最适合建立医院的村庄编号③ 程序所能达到的功能： 根据录入的相关数据 （包括村庄数目、 道路数目、道路的起点和终点以及路程） ，找出最适合的医院选址，使所有的村庄离医院都比较近。④ 测试数据：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.为了实现上述程序功能，需要定义有向带权图的抽象数据类型：①图的结构体定义： typedef struct { 数据对象： int arcs[MAX_NUM][MAX_NUM]; // 邻接矩阵 int vexnum,arcnum; //图的当前顶点和边数 }Graph; 操作结果：构建邻接矩阵的存储结构②产生一个有向带权图的邻接矩阵void CreateGraph(Graph &); //生成图的邻接矩阵操作结果：在屏幕生成一个有向带权图③用弗洛依德算法求最短路径void floyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[...
