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

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

;
结束
退出系统
两景点最短距离
浏览校园全景
查看景点信息
某一景点到其
余
景点
开始
定义变量
Void Menu()进入菜单
Switch()选择功能
。
:采用深度遍历遍历图进行所有景点浏览,将遍历景点信息输出
:用户输入一个景点,采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上
:用户输入一个出发点和一个目的地编号,采用弗洛伊德算法求出发点到目的地的最短路径
:直接用编号进行单个景点查询。

重点设计及编码
在求最短路径时采用迪杰斯特拉算法
// 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,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++)
{