校园导游图系统数据结构实验报告.doc

一. 设计目的
通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。
二. 设计内容
用无向网表示学校的校园景点平面图，图中顶点表示主要景点，
存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问：
（1）从某一景点到另一景点的最短路径。
（2）游客从公园进入，选取一条最佳路线。
（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。
[基本要求]
（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，
边上的权值表示距离．为此图选择适当的数据结构。
（2）把各种路径都显示给游客，由游客自己选择浏览路线。
（3）画出景点分布图于屏幕上。
[实现提示]
（1）构造一个无向图G并用邻接矩阵来存储。
（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，
最短路径长度就用一维数组d[i]存放；i的范围：0～20。
（3）一维数组have[]是用来记录最短路径出现顶点的顺序。
（4）根据起点和终点输出最短路径和路径长度。
三．概要设计

1．功能模块图；
结束
退出系统
两景点最短距离
浏览校园全景
查看景点信息
某一景点到其
余
景点

开始
定义变量

Void Menu()进入菜单
Switch()选择功能

2.各个模块详细的功能描述。
1.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出

2.查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上
3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径
4.查看景点信息：直接用编号进行单个景点查询。
四．详细设计
重点设计及编码
在求最短路径时采用迪杰斯特拉算法
// 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点
void ShortestPath_DIJ(MGraph * G)
{ //迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]
//若p[v][w]为1，则w是从v0到v的最短路经上的顶点
//final[v]类型用于设置访问标志

int v,w,i,min, final[20], D[20], p[20][20],t=0,x,flag=1,v0; //vo为起始景点的编号

while(flag)
{
printf("请输入一个起始景点编号:");
scanf("%d",&v0);
if(v0<0||v0>G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&v0);
}
if(v0>=0&&v0<G->vexnum)
flag=0;
}
for(v=0;v<G->vexnum;v++)
{
final[v]=0;//初始化各顶点访问标志
D[v]=G->arcs[v0][v].adj; //v0 到各顶点 v 的权值赋值给d[v]
for(w=0;w<G->vexnum;w++) //初始化p[][]数组，各顶点间的路径全部设置为空路径0
p[v][w]=0;
if(D[v]<INFINITY)
{p[v][v0]=1;p[v][v]=1;} //v0 到v 有边相连，修改p[v][v0]的值为1
} //各顶点自己到自己要连通

D[v0]=0; //自己到自己的权值设为0
final[v0]=1; //v0的访问标志设为1，v 属于 s 集
for(i=1;i<G->vexnum;i++) //对其余g.vexnum-1个顶点w，依次求 v 到 w 的最短路径
{
min=INFINITY;
for(w=0;w<G->vexnum;w++)//在未被访问的顶点中，查找与 v0 最近的顶点v
if(!final[w])
if(D[w]<min)//v0 到 w (有边)的权值<min
{v=w;min=D[w];}

final[v]=1; //v 的访问标志设置为1，v 属于s集
for(w=0;w<G->vexnum;w++)//修改v0 到其余各顶点w 的最短路径权值d[w]
if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) //若w 不属于s，且v 到w 有边相连
{
D[w]=min+G->arcs[v][w].adj; //修改v0 到w 的权值d[w]
for(x=0;x<G->vexnum;x++) //所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点
p[w][x]=p[v][x];

p[w][w]=1;
}

}
for(v=0;v<G->vexnum;v++) //输出v0 到其它顶点v 的最短路径
{if(v0!=v)
printf("%s",G->vexs[v0].name); //输出景点v0 的景点名

for(w=0;w<G->vexnum;w++) //对图中每个顶点w，试探w 是否是v0 到v 的最短路径上的顶点
{
if(p[v][w]&&w!=v0) //若w 是且w 不等于v0，则输出该景点
printf("-->%s",G->vexs[w].name);
t++;
}
if(t>G->vexnum-1&&v0!=v)printf(" 总路线长%dm\n\n",D[v]);
}
}
五．测试数据及运行结果
1．正常测试数据和运行结果
1.浏览校园全部景点信息：

2.查看景点信息：

3.输出两个景点间的最短路径:

2．异常测试数据及运行结果
1.当输出错误编号时程序没有反映，继续输入直到输入正确：

2.当查询两景点编号相同时的最短路径时，结果如下：

六．调试情况，设计技巧及体会
每当写完一个函数的时候，一编译会出现很多错误，当时的信息一下就没了，但怎么样还得继续做下去，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。
1．改进方案
程序设计的不是很复杂，有的Bug没有修复，譬如，当输入景点编号为-1时，程序没有任何提示，也退不出系统；还有在功能方面，应该增加一项：路径的修改，这样就更便于管理改系统了，也就更方便用户使用。
2．体会

经过几周的课程设计，我学到了很多东西：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。
课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。
在这次课程设计中我遇到许多问题和麻烦，得到了老师的帮助和指导，才能够使得这次课程设计顺利的进行下去，另外，在程序编写和调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多宝贵意见。此对老师和同学们表示感谢！

七．参考文献
《数据结构》(c语言描述) 耿国华 主编 高等教育出版社；

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！