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

《校园导游图系统数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.设计目的通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。二.设计内容用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3

2、）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。[基本要求]（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离．为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择浏览路线。（3）画出景点分布图于屏幕上。[实现提示]（1）构造一个无向图G并用邻接矩阵来存储。（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，最短路径长度就用一维数组d[i]存放；i的范围：0～20。（3）一维数组have[]是用来

3、记录最短路径出现顶点的顺序。（4）根据起点和终点输出最短路径和路径长度。三．概要设计1．功能模块图；结束退出系统两景点最短距离浏览校园全景查看景点信息某一景点到其余景点开始定义变量VoidMenu()进入菜单Switch()选择功能2.各个模块详细的功能描述。1.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出2.查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最

4、短路径4.查看景点信息：直接用编号进行单个景点查询。四．详细设计重点设计及编码在求最短路径时采用迪杰斯特拉算法//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点voidShortestPath_DIJ(MGraph*G){//迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]//若p[v][w]为1，则w是从v0到v的最短路经上的顶点//final[v]类型用于设置访问标志intv,w,i,min,final[20],D[20],p[20][20],t=0,x,flag=1,v0;//

5、vo为起始景点的编号while(flag){printf("请输入一个起始景点编号:");scanf("%d",&v0);if(v0<0

6、

7、v0>G->vexnum){printf("景点编号不存在!请重新输入景点编号:");scanf("%d",&v0);}if(v0>=0&&v0vexnum)flag=0;}for(v=0;vvexnum;v++){final[v]=0;//初始化各顶点访问标志D[v]=G->arcs[v0][v].adj;//v0到各顶点v的权值赋值给d[v]for(w=0;w<

8、G->vexnum;w++)//初始化p[][]数组，各顶点间的路径全部设置为空路径0p[v][w]=0;if(D[v]vexnum;i++)//对其余g.vexnum-1个顶点w，依次求v到w的最短路径{min=INFINITY;for(w=0;w<

9、G->vexnum;w++)//在未被访问的顶点中，查找与v0最近的顶点vif(!final[w])if(D[w]vexnum;w++)//修改v0到其余各顶点w的最短路径权值d[w]if(!final[w]&&(min+G->arcs[v][w].adjarcs[v][w].adj;//修

10、改v0到w的权值d[w]for(x=0;xvexnum;x++)//所有v0到v的最短路径上的顶点x，都是v0到w的最短路径上的顶点p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;vvexnum;v++)//输出v0到其它顶点v的最短路径{if(v0!=v)printf("%s",G->ve