数据结构课程设计4

《数据结构课程设计4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告广州大学计算机科学与教育软件学院计算机系06级计算机科学与技术专业6班姚子和（学号：0623029015）2008年11月10日一、课程设计题目寻径问题：（难度系数：1.3)给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连接，边上的权Wij表示这条道路的长度。现在要从这n个村庄选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的距离最短？试设计一个算法来解决该问题。二、课程设计目的及要求更好的理解数据结构的在项目中的作用以及更加熟练的

2、代码编写的能力。而选定此题作为课程设计的内容更深层次的意思在于：对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。掌握了图的最短路径算法思想，能够更好的为我们的生活工作学习服务。三、题目需求分析及概要设计把每个村庄假设成为图的一个节点，由于村庄之间存在一条道路，由题目可知，村庄之间的距离可以抽象也图中节点之间的

3、权。问题的关键，建立一所医院，使其到距离最远的村庄都存在一条最短的路径。所谓最短，就是权值最小。所以，对问题实行简化处理，可将其看作是图论中求最短路径的问题。抽象之后问题的模型（节点表示村庄，边上的权表示村庄之间的距离）四、详细设计及算法分析算法分析： 问题求解的基本思路：为每个村庄编上代码1～n(n表示输入村庄的个数)。要求出最终结果，必须要经过两个步骤。首先就是必须求出多个结点的最短路径，求出的结果是一个邻接矩阵，将其存于二维数组ShortAdj[][]中；其次就是必须求“离医院最远的村庄到医院的距离最短”

4、的最优结果，得出的结果是村庄的编号。针对问题求解的第一步，图的最短路径分为两种情况，一种是单元最短路径，另外一种是多源最短路径。单源最短路径问题，是求两个节点之间最短的一条路径的问题，适用的算法有算法。而多源最短路径问题，是求其中一个节点与其他所有节点的最短路径问题，适用的算法有Dijkstra算法、Floyd算法。题目要求的是n个村庄，并且比较的是其中一个村庄设立医院与其他村庄之间的问题，很显然，应该使用多源最短路径的情况来求解。Floyd算法是最适合本题的解决算法。Dijkstra算法的时间复杂度为O（n^

5、2），若用以解决多源最短路径问题的时候，则必须对n个不同的结点都分别进行单源最短路径的运算，这样算法复杂度就变为O（n^3）。Floyd算法的时间复杂度同样为O（n^3），但是其算法的实现方式比Dijkstra算法简洁。因此，本题使用Floyd算法作为解题的主要算法。实现方案与数据结构在我的实现方案中，根据个人的实际情况，比如编码的能力还有对代码可能的简化，选择了面向过程的编程方法。另一方向，也因为是对面向对象方法实现方法足够的理解。开与调试环境TurboC2.0编译环境，windowsxp系统。简单的代码注释

6、：/*****************************文件开始******************************/#include#include#definenMax20/*村庄的最大值(理论上没有限制，但为了控制问题的规模和手工输入的不便，故控制在20*/#defineWeighMax65535/*村庄之间距离的最大值，也是int型的最大值*/intn;/*公共变量用于存放村庄的个数*/intfinal[nMax];/*用于存放最远的村庄到医院的最短距离

7、*/intAdj[nMax][nMax];/*二维数组，用于存放村庄之间的初始距离*/intShortAdj[nMax][nMax];/*二维数组，用于存放村庄之间的最短距离*/voidFloyd();/*最核心的算法，弗络伊德算法O(n^3)，用于计算村庄之间的最短距离*/voidInput_Output();/*用于手工输入村庄之间距离，和输出相应数值的函数*/voidOut();/*用于输出最终结果的函数*/voidShortestPath();/*计算离医院最远的村庄到医院的距离最短的函数,是对Floy

8、d的后续处理*/voidmain(){/*主函数*/Input_Output();Floyd();ShortestPath();Out();}/*****************************文件结束******************************/复杂度分析(出现的问题及解决方案)首先需要对可接受的村庄数量做人为的限制。题目要求并没有对于村庄的数量给出任何的限制