数据结构课程设计4.doc

数据结构

课程设计报告

广州大学
计算机科学与教育软件学院
计算机系 06级计算机科学与技术专业6班

姚子和
（学号：0623029015）

2008年11月10日

一、课程设计题目
寻径问题： （难度系数：1.3）
给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连接，边上的权Wij 表示这条道路的长度.现在要从这n个村庄选择一个村庄建一所医院，问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的距离最短?试设计一个算法来解决该问题.
二、课程设计目的及要求
更好的理解数据结构的在项目中的作用以及更加熟练的代码编写的能力。
而选定此题作为课程设计的内容更深层次的意思在于：对于许多地理问题，当它们被抽象为图论意义下的网络图时,问题的核心就变成了网络图上的优化计算问题.其中，最为常见的是关于路径和顶点的优选计算问题.在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。 掌握了图的最短路径算法思想,能够更好的为我们的生活工作学习服务。
三、题目需求分析及概要设计
把每个村庄假设成为图的一个节点,由于村庄之间存在一条道路,由题目可知,村庄之间的距离可以抽象也图中节点之间的权。问题的关键，建立一所医院,使其到距离最远的村庄都存在一条最短的路径.所谓最短，就是权值最小。所以，对问题实行简化处理，可将其看作是图论中求最短路径的问题.

抽象之后问题的模型（节点表示村庄，边上的权表示村庄之间的距离）
四、详细设计及算法分析
算法分析：
  问题求解的基本思路：为每个村庄编上代码1~n (n表示输入村庄的个数)。要求出最终结果，必须要经过两个步骤。首先就是必须求出多个结点的最短路径，求出的结果是一个邻接矩阵，将其存于二维数组ShortAdj［］［]中;其次就是必须求“离医院最远的村庄到医院的距离最短”的最优结果,得出的结果是村庄的编号。
针对问题求解的第一步，图的最短路径分为两种情况，一种是单元最短路径，另外一种是多源最短路径。单源最短路径问题，是求两个节点之间最短的一条路径的问题，适用的算法有算法。而多源最短路径问题，是求其中一个节点与其他所有节点的最短路径问题，适用的算法有Dijkstra算法、Floyd算法。题目要求的是n个村庄,并且比较的是其中一个村庄设立医院与其他村庄之间的问题，很显然，应该使用多源最短路径的情况来求解。
Floyd算法是最适合本题的解决算法.Dijkstra算法的时间复杂度为O（n^2）,若用以解决多源最短路径问题的时候，则必须对n个不同的结点都分别进行单源最短路径的运算，这样算法复杂度就变为O（n^3）.Floyd算法的时间复杂度同样为O（n^3）但是其算法的实现方式比Dijkstra算法简洁。因此，本题使用Floyd算法作为解题的主要算法。
实现方案与数据结构
在我的实现方案中，根据个人的实际情况，比如编码的能力还有对代码可能的简化,选择了面向过程的编程方法。另一方向，也因为是对面向对象方法实现方法足够的理解.
开与调试环境
Turbo C 2.0编译环境，windows xp系统.
简单的代码注释：
/****＊**＊*＊*******＊＊＊＊***＊＊＊＊*文件开始*＊*＊＊＊**＊＊＊*＊＊＊****＊＊**＊*＊＊＊**/
＃include
#includee nMax 20 /*村庄的最大值（理论上没有限制，但为了控制问题的规模和手工输入的不便,故控制在20*/
＃define WeighMax 65535 /*村庄之间距离的最大值，也是int型的最大值*/
int n； /*公共变量用于存放村庄的个数＊/
int final［nMax］； /＊用于存放最远的村庄到医院的最短距离*/
int Adj［nMax]［nMax］; /＊二维数组，用于存放村庄之间的初始距离*/
int ShortAdj［nMax][nMax]; /＊二维数组，用于存放村庄之间的最短距离＊/
void Floyd（）； /*最核心的算法,弗络伊德算法O(n^3)，用于计算村庄之间的最短距离*/
void Input_Output(）; /*用于手工输入村庄之间距离，和输出相应数值的函数＊/
void Out（）; /＊用于输出最终结果的函数*/
void ShortestPath（)； /＊计算离医院最远的村庄到医院的距离最短的函数,是对Floyd的后续处理＊/
void main(）｛ /＊主函数*/
Input_Output(）;
Floyd（）;
ShortestPath(）；
Out（)；
}/＊＊＊**＊＊**＊＊＊＊*＊*＊*＊＊*＊*＊*＊＊＊＊文件结束**＊*＊＊＊*＊＊＊＊*＊＊****＊*＊*＊*＊**＊＊/
复杂度分析（出现的问题及解决方案)
首先需要对可接受的村庄数量做人为的限制。题目要求并没有对于村庄的数量给出任何的限制。但是如果需要使用二维数组来存储边权值的话，输入的村庄数量为n，则需要存储n^2那么多的边，空间复杂度为QO(n^2） 。当n大于10以后，系统需要手工输入的权值就至少需要100次,这样已经超出了对于一个系统实用性的界限,并且在建立这样一个数据的时候还需要为几乎不会使用到的情况分配相当大量的空间,因此有必要对此情况做一定人为的限制。出于对极端情况的考虑，我人为地把村庄数n的值域限制在2—20的范围内
其次应该把输入的权值和最终最短路径运算结果分在两个不同的二维数组分别保存。Floyd算法的最节省方法只需要n^2的空间，最初输入的权值还有最后得出的最短路径结果都可以只在一个矩阵的结构里面完成。但是以这种方式计算完成之后，就不能完整保留最初的权值结果。因此为了保存原始的输入的数值，程序使用了两个二维数组的方式来分别保存原始数据和Floyd的结果。
最后,是对权值最大值的处理，因为权值PathWeigh的类型为int型,所以在开始的时候就定义了最大值为65535，当输入的数值大于65535时，只取其上限.
而比较遗憾的是，由于时间,和能力的问题。并没有对程序中一些数据的非法输入进行屏蔽以致影响程序的实用性。希望能在后面与同学和老师的交流中能解决这个问题。
调试结果

不考虑非正常输入情况下运行的结果
五、用户使用说明
根据程序的提示,输入村庄的数量，前面提到，这里输入的数值范围人为限制在2到20以内。接着根据提示，输入各个村庄之间的距离，注意使用的数据类型是int型。
之后程序会显示，输入原始数据的矩阵显示方式，以及使用Floyd算法之后，得出的各源点的最短路径.最后，输出医院选址的最终位置。
注意程序在设计的过程中,由于时间的和个人能力的缘故，并没有对，输入边权时出现的非法数据的处理，只是简单的结束程序的执行。所以输入测试，请以数值输入为主。
六、总结

此实验是没有程序框架，主要任务是自己设计程序.
我一开始的时候是没有头绪的，但我自己仔细的一想，这个程序和书本上Floyd算法只是小些改动，具体核心函数是相同的,因为我对代码的编写不够熟练，所以我还是照着书本的程序算法初始化图和邻阵矩形，最后是输入这个程序中最重要的函数—-最短路径算法，最后再输入主函数，问题就是这么出现了，经过我的调试后，小问题是我输错大小写，大问题就是各个函数编写过程总是有错误的,最后输出来的函数是不正确的。我自己慢慢的看了书本和自己的思考,发现自己原来是忘记了输入一个调用的函数。
最短路径的定义是：从某一点到别某一点（不重复的点）可能不止一条路径，把带权限路径长最短即其值最小）的那条路径。这种最短路径的算法，是先要你选择去到最终的目的地，再根据权限求出最短的路径。这种程序在我们日常的生活中是最常用的,当你要去几个城市旅游的时候，用这种最短路径的方法，可以帮我们确定一条路线是可以帮我们省最少的钱.就是说用一个图表示城市之间的运输网,图的顶点代表城市，图上的边表示两端点对应城市之间存在着运输线，边上的权表示运输线上的运输时间或单位重量的运费，考虑到两城市间的海拔高度不同,流水方向不同等因素，将造成来回运输时间或运费不同，所以这种图通常就是一个有向图。但这种最短路径的算法是有多种的,运算的速度就是不同的，而我选择的是Floyd算法。
而通过本次课程设计，同时也发现自己的文档编写实践能力很差.开始并不知道这个实验报告怎么写.后来还是根据报告的要求，一步一步地写，而在写的过程中,同样感觉到费力。这与个人，平时几乎不编写程序说明文档的关系很大.
总体而言，这次课程设计，收获很大，了解了自己的能力水平，以及哪些方向的欠缺。
七、参考资料
数据结构（C语言版）　　作者:严蔚敏 吴伟民　　清华大学出版社

八、附录：程序源代码及注释
/***＊＊＊***＊*＊*＊*＊＊＊*＊*＊*＊*＊＊＊＊文件开始＊＊*******＊＊＊＊****＊*＊**＊＊＊＊＊＊＊＊/
#includeefine nMax 20 /＊村庄的最大值(理论上没有限制，但为了控制问题的规模和手工输入的不便，故控制在20＊/
＃define WeighMax 65535 /＊村庄之间距离的最大值,也是int型的最大值*/
int n； /*公共变量用于存放村庄的个数＊/
int final[nMax］; /＊用于存放距离最远的最好村庄情况＊/
int Adj［nMax][nMax]; /*二维数组,用于存放村庄之间的初始距离＊/
int ShortAdj［nMax]［nMax］; /*二维数组，用于存放村庄之间的最短距离＊/
void Floyd（)； /＊最核心的算法，弗络伊德算法O（n^3）,用于计算村庄之间的最短距离＊/
void Input_Output（）； /＊用于手工输入村庄之间距离，和输入相应数值的函数*/
void Out(）； /＊用于输出最终结果的函数＊/
void ShortestPath(）； /＊计算离医院最远的村庄到医院的距离最短的函数，是对Floyd的后续处理*/
void main(){ /＊主函数＊/
Input_Output（);
Floyd（）;
ShortestPath(）;
Out();
}
void Input_Output(){
int i，j；
printf(”请输入村庄的数目（范围为2—50）:”）；
scanf(”％2d”, ＆n)；
while(n<=2||n>nMax){
printf(”您的输入有误，请再次输入：”）； /*根据空间复杂度，人为的限制手工输入的次数*/
scanf(”％2d”，＆n）;}
for(i=1； i〈=n; i++）{
for（j=1； j〈=n； j++）{
if(i==j) Adj[i]［j］ = ShortAdj[i]［j］ = 0; /此算法只考虑有向图的情况，如果是无向图的话，for循环中i,j的值〈=n/2*/
else{int PathWeigh = WeighMax； /＊初始化输入的值为int型的最大值＊/
printf（”\n请输入从第％d个村庄到第%d个村庄的距离:"， i， j）;
scanf("％d”,&PathWeigh）; /＊未能处理非数字输入的问题*/
if(PathWeigh〉WeighMax） Adj[i][j]=WeighMax; /*如果输比int型数值大,则取其上限＊/
else Adj[i］［j］=PathWeigh;
printf(”村庄％d到村庄％d的距离是：%d\n", i, j， Adj[i]［j］）；
ShortAdj［i][j] = Adj[i］[j];} /＊同时将输入的值存到ShortAdj中,用于下面Floyd函数的处理中*/
}
}
printf（"\n村庄之间路径的距离（矩阵）:\n"）;
for(i=1；i〈=n;i++）{ /*输出手工输入的数值，以矩阵的方式来显示,更加直观*/
for(j=1；j<=n；j++) printf(”\t%d”，Adj[i］[j］)；
printf（”\n”）;}
}
void Floyd(）｛ /＊弗络伊德算法,求多源点的最短路径*/
int i,j，tmp;
for(tmp=1；tmp<=n；tmp++)
for（i=1;i〈=n;i++)
for(j=1；j<=n;j++){ /＊三次循环*/
if（Adj［i][j]>ShortAdj[i][tmp］+ShortAdj[tmp］［j］） /＊如果通过中间路径，比原来存于数组里的值小,则代换!*/
ShortAdj［i]［j]=ShortAdj［i]［tmp］+ShortAdj［tmp][j］；}
printf（”\n村庄之间路径的最短距离(矩阵）：\n"）;
for（i=1;i〈=n;i++）｛ /＊打印村庄之间的最短路径，同样以矩阵的形式显示＊/
for（j=1;j〈=n;j++） printf(”\t％d”，ShortAdj[i][j]）；
printf("\n");｝
｝
void ShortestPath（）{ /＊计算离医院最远的村庄到医院的最短距离＊/
int i,j;
for（i=1；i<=n;i++）｛ /*找出每一组最短距离中的最大值！*/
final[i]=ShortAdj［i］[1］；
for（j=2;j<=n;j++）
if（final[i］〈ShortAdj[i］［j］） final［i］=ShortAdj［i］［j］;
｝
printf("\n村庄\t最长距离\n"); /＊打印每组的最长距离＊/
for（i=1;i〈=n;i++)
printf("%d\t%d\n”，i,final［i］）;
}
void Out(）{ /＊计算最终结果，并输出＊/
int i,tmp=1；
for(i=2；i<=n；i++)
if(final[tmp］〉final[i]) tmp=i；
printf(”\n建设医院的最佳位置是村庄%d\n”,tmp）;
｝