数据结构课程设计医院选址.doc

(完整word版)数据结构课程设计医院选址
医院选址
李* 计算机学院0304班
摘要:有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总体来说较短，设计较合理。可以将问题抽象为有n个接点，在这n个接点之间建立一个无向图，边上的权值w(i,j)表示村庄i到j之间道路的长度，我们知道，在无向图中n个顶点之间，最多可能设置n(n-1)/2条线路，如何在这些线路中选择n-1条线路，以使总的线路最短？对于n个顶点的连通网可以建立许多不同的无向图，每一个无向图都可以表示一个道路网，其中要选择一个最优图，使图上各边之小。
关键字:节点, 连通图, 最小生成树, 顶点, 邻接点
1.引言
图是建立和处理离散数学模型的一个重要工具，它是一门很重要的学科，也是一门很实用的学科，例如在社会科学，语言学，计算机科学，信息论等各个方面都有着广泛的应用，图有许多种表示方法，但是当图中的节点和边的数目都很大时，图的另一种方便的表示方法是用相应的矩阵表示，这种表示方法有很多优点，它使得图的有关信息能以矩阵的形式在计算机中存储起来并加以变换，利用矩阵的表示方法及其运算还可以得到图的一些有关性质。在这个程序中，用到了图论中的树的有关知识，医院选址这个问题有着明显的实际背景，例如要在n个城市之间铺设光缆，如何才能使付出的代价最小等问题，都要用到图的有关知识。在信息高速发展的今天，济济全球化已经呈现明显的趋势，如何在不同的地方建立最优的道路网和信息网，已成为社会竞争中很重要的因素，这不仅关系到要付出的经济代价，而且也关系到谁先占有主动权的问题。有鉴于此，我就做了这个程序。一则为了完成课程设计，二则也为了锻炼自己，多学些东西。
2.需求分析
数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．图的存储结构的选取应和所操作相适应。为了便于选择权值最小的边。此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储（带权）的数组表示图。基本要求如下： 用邻接矩阵表示无向网，应显示所选中的村庄到各村庄的最短矩离。具体解决办法见程序设计，此处先举例说明这个问题中的一个思想，假设i到j直接路径的距离为a，如果存在一接点k，使i到k的距离b，k到j的距离c，且b+c<a，那么就选择i--k--j这条路径而不选择的i和j的直接路径
3.数据结构与算法设计
3.1数据结构设计
<stdlib.h>，<string.h>，<iomanip.h>，<iostream.h>为包含的库函数
const int MAX_VEXNUM=30; 图的最大顶点数
const int LARGEST=43526; 定义无穷大
vexnum,arcnum; 图中当前顶点数和弧数
vexs[MAX_VEXNUM]; 顶点向量，用于存储顶点的信息(名称)
arcs[MAX_VEXNUM][MAX_VEXNUM]; 邻接矩阵，用于存储边的信息(权值)
3.2.算法设计
采用最短路径算法，求各村庄之间的最短路径，这是该程序的核心算法。
void FloydGetResult(VAGraph GRA)
{ //用Floyed算法求有向网G中个对顶点的最短路径长度D[v][w]
int D[MAX_VEXNUM][MAX_VEXNUM]; //最短路径的带权长度矩阵
for(u=0;u<GRA.vexnum;++u) //求各对顶点的最短路径
for(v=0;v<GRA.vexnum;++v)
for(w=0;w<GRA.vexnum;++w)
if(D[v][u]+D[u][w]<D[v][w])
D[v][w]=D[v][u]+D[u][w];
//从v经u到w的一条路径更短
}
4．程序设计
4.1引用库函数及变量的定义
#include <stdlib.h>
#include <string.h>
#include <iomanip.h>
#include <iostream.h>
const int MAX_VEXNUM=30; //图的最大顶点数
const int LARGEST=43526; //无穷大量
struct VAGraph //储存顶点信息和边的信息
{
int vexnum,arcnum; //图中当前顶点数和弧数
char* vexs[MAX_VEXNUM]; //顶点向量，用于存储顶点的信
息(名称)
int arcs[MAX_VEXNUM][MAX_VEXNUM]; //邻接矩阵，用于存储边的信
息(权值)
};
int LocateVex(VAGraph G,char *v)
{ //返回顶点v在图G中的位置，不存在则重新输入此顶点
int vfind=-1; //顶点在图中找到与否的标志
for(int i=0;i<=G.vexnum;i++)
{
if(strcmp(G.vexs[i],v)==0)
{
vfind=i; //顶点找到，s赋i，退出循环
break;
}
}
while(vfind==-1) //不存在则重新输入
{
cout<<"This vertex "<<*v<<" don't exist,please input again:\n";
exit(1);
}
return vfind; //返回顶点位置
}
4.2采用数组表示法，构造无向网
void CreateWXW(VAGraph &GRA)
{ //采用数组表示法，构造无向网GRA
int i,j,k,w; //定义循环变量
cout<<"Please input Vertexs and Arcs number:\n"; //输入图的顶点
数和弧数
cin>>GRA.vexnum>>GRA.arcnum;
while( GRA.vexnum<MAX_VEXNUM &&!(GRA.vexnum>2 ) ||
GRA.arcnum>GRA.vexnum*(GRA.vexnum-1)/2)
{ //弧数不能超过顶点数阶乘的一半，否则重新输入
cout<<"This is a Wrong Arc number,please input again:\n";
cin>>GRA.vexnum>>GRA.arcnum;
}
cout<<"Please input Vertex value:\n"; //输入顶点的值
for(i=0;i<GRA.vexnum;++i) //输入顶点信息(名称)
{
GRA.vexs[i]=new char[10];
cin>>GRA.vexs[i];
}
for(i=0;i<GRA.vexnum;++i) //初始化邻接矩阵
for(j=0;j<GRA.vexnum;++j)
{
if(i!=j)
GRA.arcs[i][j]=LARGEST;
else
GRA.arcs[i][j]=0; //一个点到它自身的距离是
}
for(k=0;k<GRA.arcnum;++k)
{ //构造邻接矩阵
char v1[10];
char v2[10]; //矩阵行和列
cout<<"Please input two Vertexs and Arc
weight,Group"<<k+1<<":\n";
cin>>v1>>v2>>w;
//输入顶点v1、v2的名称,边v1v2的权值w
i=LocateVex(GRA,v1);
j=LocateVex(GRA,v2);
GRA.arcs[i][j]=w; //边<v1,v2>的权值
GRA.arcs[j][i]=GRA.arcs[i][j]; //此矩阵是对称矩阵
}
}
4.3 求最短路径长度
void FloydGetResult(VAGraph GRA)
{ //用Floyed算法求有向网G中个对顶点的最短路径长度D[v][w]
int D[MAX_VEXNUM][MAX_VEXNUM]; //最短路径的带权长度矩阵
D[][]
static int P[MAX_VEXNUM]; //各顶点到最远点的距离P[]
int v,u,w;
for(v=0;v<GRA.vexnum;++v) //各对节点之间初始已知距离
{
for(w=0;w<GRA.vexnum;++w)
{
D[v][w]=GRA.arcs[v][w]; //给矩阵赋值
}
}
for(u=0;u<GRA.vexnum;++u) //求各对顶点的最短路径，如
果直接的路径不是最短就找合路径
{
for(v=0;v<GRA.vexnum;++v)
{
for(w=0;w<GRA.vexnum;++w)
{
if(D[v][u]+D[u][w]<D[v][w]) //从v经u到w的一条路径
更短
{
D[v][w]=D[v][u]+D[u][w]; //路径之和，舍弃直接的路
径
}
}
}
}
//--- 求出每个顶点到其它顶点的距离最大值存于P[u]中---
cout<<"The Adiacent Matrix is:\n"; //输出结果矩阵
for(u=0;u<GRA.vexnum;++u)
{
cout<<setiosflags(ios::left);
for(v=0;v<GRA.vexnum;++v)
{ //输出最短路径长度矩阵D[v][w]，并求P[u]
cout<<setw(4)<<D[u][v];
if(P[u]<D[u][v])
{
P[u]=D[u][v];
}
}
cout<<endl;
}
4.4 求P[u]的最小值,并输出其对应的顶点信息
char* result;
int i,temp=LARGEST;
for(u=0;u<GRA.vexnum;++u) //求P[u]的最小值，并记录它的位置
{
if(temp>P[u])
{
temp=P[u];
i=u;
}
}
result=GRA.vexs[i]; //所选村庄顶点为P[u]对应的顶点
4.5求出每个顶点到其它顶点的矩离最大值存于P[u]中
cout<<"The result is: "<<result<<endl;
for(u=0;u<GRA.vexnum;++u) //输出所选顶点到其它顶点的最短距离
{
if(u!=i)
{
cout<<result<<" to "<<GRA.vexs[u]<<" is: "<<D[i][u]<<endl;
}
}
}

4.6主函数
void main()
{
VAGraph GRA;
CreateWXW(GRA); //构造无向网G
FloydGetResult(GRA); //求顶点result,使result到其它顶点的距离最短
}//End main
5．程序测试

综合来看接点的选取，在横着的五行或者竖着的五行看发现a到其他四个接点的距离总体来说较小，所以选a做建医院的结点，程序所得的结果符合实际的要求所以该程序是正确的。
6.有关技术的讨论
（1）借助于邻接矩很容易判定任意两个顶点之间是否有边相连接，并容易求得各个顶点的度，对于无向图，顶点vi的度是邻接矩阵中第I行的元素之和。
（2）用Floyed算法求有向网G中个对顶点的最短路径长度D[v][w]及各顶点到最远点的矩离P[]是本次课程设计的核心任务，要完成这一步，必须很熟练掌握有关算法。
（3）该程序能够正确执行在一定数目的村庄中医院的选址操作，能够正确完成题目的相关要求。但是有很大局限性，首先是只能反映出最短路径的长度，而不能反映出最短路径上的所有顶点信息；其次对有向网无法操作，即其他题对它不能继承。
7.设计体会
通过数据结构课程设计，我的c语言水平有了比较大的提高，其中c语言关于指针，文件的操作理解的比以前深刻不少。另外是数据结构方面的提高，对存储结构，及各种查找排序方面也有不少的提高。虽然我的设计或许还有些问题，做的不够深入，但独立完成一个比较大一点的程序的经历也是很宝贵的。
经过此次实验使我对网的特点及其存储结构有了较深刻的了解，明白了图是一种较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用是极其广泛的。在完成实验的过程中，进行了反复的修改和调试，在写关于图的实验过程中，我明白了学习应该从简单到复杂，首先应该保证程序正确，其次才能去追求程序功能的完善。由于平时上网看一些别人写程序的心得和体会，还有在网上看别人写的程序的实例，故写程序的时候感觉还好。在写程序的时候的确碰到了一些困难，自己去努力的思考并在老师和同学的帮助下顺利的解决了这些问题。过这次课程设计，我对数据结构有了一个新的认识，自己的动手能力和思维能力也有所提高，但是在课程设计的过程中，我也深刻认识到了自己的不足，在知识的运用上面仍然不够灵活，主要表现在以下一个方面：
其一，数据结构的很多算法没有能熟练的掌握，以至在调试的时候花了很长时间，而且程序不够工程化，功能不够完善，很多方面还要不断学习和改善，从而使整个工程更加完美。
其二、程序设计的过程中，代码的编写很不熟练，而且很容易犯一些低级的错误，如：语句后面的分号忽略了，括号不匹配等等。
还有一个方面就是自己缺乏动手能力，虽然学计算机两年了，但真正去动手编一个真正的程序，这还是第一次，所以以后在这方面还要加强锻炼，把书本上学到的东西运用到实践当中去。
在这次实验中按时也较好的完成了这次老师交给的任务，由于自己的知识有限再加上平时锻炼发少，所以在程序设计中遇到了一些困难，也是程序存在着一些缺陷，希望老师在以后的学习中多给一些动手操作，亲自实践的机会，这样才能增强自己的动手能力。
结束语
本文描述了基于图的医院选址问题，采用n个顶点之间的最短路径算法，用c语言实现。
参考文献
[1] 严蔚敏吴伟名 编著，《数据结构》，清华大学出版社， 2001年1月
[2] 张颖江 胡燕 主编，《C语言程序设计》，科学出版社 ，1998年7月
[3] 殷人昆，《数据结构》，清华大学出版社， 2001年3月
[4] 徐孝凯，《数据结构实用教程》，清华大学出版社，1999年12月
[5] Adam Drozdek（美），《数据结构与算法》， 机械工业出版社 ，2003年7月