云南大学软件学院数据结构实验六实验报告——校园自动导游系统

算法设计实践课程报告学院：计算机学院班级：学号：姓名：一、课程目的本课程设计为培养学生综合实践的能力，理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对C++系统编程有一个深入的了解。

二、题目3. 校园导游程序——最短路径应用问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

要求能够回答有关景点介绍、游览路径等问题。

基本要求：实现一简单的功能查询界面：（1）查询各景点的相关信息；（2）选定某一景点作为起始点，可查询从该景点出发到其余各景点的最佳游览路径。

三、算法分析与设计首先，此算法建立了类mgraph，通过邻接矩阵存储校园景点图，并通过构造函数初始化图，手动给校园图附上相关信息（包括景点编号、名称、简介、路径及路径长度等）。

然后，手动绘制了部分模拟校园图。

该函数包括深度优先遍历图和迪杰斯特拉最短路径算法，主要功能是实现校园七个景点（0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场）的简介和最短路径的算法，最后用主函数输出结果，用switch语句分别输出，最后求出两点之间的最短路径。

四、运行结果及分析输出结果：五、总结这个程序在调试时，我发现一次只能查找一个景点的相关介绍，之后的最短路径的计算生成时是成功的，但在调试时却不是很好，输出结果有误。

通过这次算法设计实践，我对数据结构的运用有了更深的体会，对无向图和创建无向图的理解更加深刻，理解了迪杰斯特拉算法的原理，不再是盲目地照搬书上的程序。

之后，我还发现了我的不足之处，对程序的设计还不过灵活。

附录：源程序清单#include<iostream>#include<string>using namespace std;const int maxsize=100;class mgraph{public:mgraph(string a[],int n,int e);//构造函数，建立n个顶点，e条边的图~mgraph(){} //析构函数void dfstraverse(int v);//深度优先遍历void shortpath(mgraph g,int v,int r);//求v到其余各个顶点的最短路径private:string vertex[maxsize];//存放图中顶点的数组int arc[maxsize][maxsize];//存放图中边的数组int vertexnum,arcnum;//图中的顶点数和边数};mgraph::mgraph(string a[],int n,int e){int i,j,k;vertexnum=n;arcnum=e;for( i=0;i<vertexnum;i++)vertex[i]=a[i];for(i=0;i<vertexnum;i++) //初始化邻接矩阵for(j=0;j<vertexnum;j++)arc[i][j]=0;for(k=0;k<arcnum;k++)//依次输入每一条边{cout<<"请输入两个景点的编号："<<endl;cin>>i>>j;//依次输入边依附的两个顶点的编号和距离if(i<7&&j<7)arc[i][j]=arc[j][i]=1;//置有边标志else cout<<"没有该景点！！！"<<endl;}}void mgraph::shortpath(mgraph g,int v,int r){for (int i = 0; i < vertexnum; i++)for (int j = 0; j < vertexnum; j++){arc[i][j] = 1000000;//初始化路径长度}arc[0][1]=arc[1][0]=10;arc[1][2]=arc[2][1]=5;arc[2][3]=arc[3][2]=8;arc[0][4]=arc[4][0]=15;arc[1][4]=arc[4][1]=9;arc[2][4]=arc[4][2]=10;arc[3][4]=arc[4][3]=11;arc[4][5]=arc[5][4]=12;arc[0][5]=arc[5][0]=10;arc[0][6]=arc[6][0]=14;arc[5][6]=arc[6][5]=9;int dist[maxsize]={0},s[maxsize];string path[maxsize];int k,i;for( i=0;i<g.vertexnum;i++){dist[i]=g.arc[v][i]; //初始化数组dist[n],path[n]if(dist[i]<10000)path[i]=g.vertex[v]+g.vertex[i];else path[i]="";}s[0]=v;//初始化集合sdist[v]=0;//标记顶点v为源点int num=1;while(num<g.vertexnum)//当顶点数num小于图的顶点数{for( k=0,i=0;i<g.vertexnum;i++)//在dist中查找最小值元素if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;s[num++]=k;//将新生成的终点加入集合sfor(i=0;i<g.vertexnum;i++)//修改数组dist和pathif(dist[i]>dist[k]+g.arc[k][i]){dist[i]=dist[k]+g.arc[k][i];path[i]=path[k]+g.vertex[i];}}cout<<"路径长度为："<<dist[k]<<"路径为："<<path[k];}int main(){int aa,x,y;cout<<"欢迎进入江苏大学校园导游系统！！"<<endl;cout<<"0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场"<<endl;string a[7]={"0","1","2","3","4","5","6"};string b[7]={"图书馆","三山楼","三江楼","教工浴室","西山操场","西山美食城","京江操场"};string c[7]={"图书馆：本建筑共有5层，有大量图书可供学生查阅，还可在其中自习","三山楼：2号教学楼，共8层，平时上课地点","三江楼：1号教学楼，共18层，平时上课地点","教工浴室：周二至周日开放，开放时间：14:00至20:00","西山操场：早操地点，平时自由锻炼的地方，每晚有大量人跑步","西山美食城：有大量美食可供选择，物美价廉","京江操场：位于六食堂附近，规模比西山操场略小"};mgraph tu(a,7,1);cout<<"主要景点平面图："<<endl;cout<<" 京江操场* * * * * * * 六食堂"<<endl;cout<<" * * "<<endl;cout<<" * * "<<endl;cout<<" * * "<<endl;cout<<" * * "<<endl;cout<<" * * "<<endl;cout<<" * * * *西山美食城* * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * 西山操场* *老一区* "<<endl;cout<<" * * * * * "<<endl;cout<<" * * * * * * * * * * * * * * *教工浴室"<<endl;cout<<" * * * * * "<<endl;cout<<" * * * * * "<<endl;cout<<"* * * * *东山操场* * * "<<endl;cout<<"* * * * "<<endl;cout<<"* * * * 图书馆* * * * * * * * * * * * * * * "<<endl;cout<<" * * * "<<endl;cout<<" * * * * * * * * * * * * * *三山楼 * * * *三江楼"<<endl;cout<<"请输入您想要了解的景点编号：";cin>>aa;switch(aa){case 0:cout<<"此景点为："<<b[0]<<"\n简介："<<c[0]<<endl;break;case 1:cout<<"此景点为："<<b[1]<<"\n简介："<<c[1]<<endl;break;case 2:cout<<"此景点为："<<b[2]<<"\n简介："<<c[2]<<endl;break;case 3:cout<<"此景点为："<<b[3]<<"\n简介："<<c[3]<<endl;break;case 4:cout<<"此景点为："<<b[4]<<"\n简介："<<c[4]<<endl;break;case 5:cout<<"此景点为："<<b[5]<<"\n简介："<<c[5]<<endl;break;case 6:cout<<"此景点为："<<b[6]<<"\n简介："<<c[6]<<endl;break;default:cout<<"您好，请输入编号为0-6的数字"<<endl;}cout<<"请输入当前所在景点的编号：";cin>>x;cout<<"请输入您要前往的景点编号："<<endl;cin>>y;cout<<"最短路径为："<<endl;tu.shortpath(tu,y,x);cout<<"祝大家旅途愉快！！！"<<endl;return 0;}。

一：设计目的1．进一步掌握图的存储，建立和遍历。

2．掌握弗洛伊德算法和迪杰斯特拉算法完成最短路径的有关问题。

3．文件的读写操作的练习与使用。

4．提供校园导游的实用地图。

二. 设计内容1．以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

2．为来访客人提供图中任意景点相关信息的查询。

3．为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

三．概要设计1．功能模块图2．各个模块详细的功能描述。

1．CreateGraph()---从文件中读出景点的信息，并创建无向图。

2．graph()---显示校园平面图，方便游客进行查询。

3．find()---查询任意景点的详细信息。

4．BrowsePath()---迪杰斯特拉算法，用于实现目前所在点到任意一景点的最短路径。

5．ShortestPath()---弗洛伊德算法，用于实现任意两景点间最短路径。

6．main_menu()，secord_menu()---用于实现菜单的显示并接受输入选择。

显示地图及 主菜单任一景点信息的查询任意两点之间的最短路径从某一点到其余任一点的最短路径四．详细设计1．功能函数的调用关系图2．各功能函数的数据流程图main 函数CreateGraph()main_me nu()函数find()函数graph()函数ShortestPath()BrowsePath()secord_menu()函数文件中3．重点设计及编码<1>.查询功能的实现。

while(ch<0||ch>=G .vexnum) { printf("\n\t 你所输入的景点编号不存在!\n"); printf("请重新输入:"); scanf("%d",&ch); } for(i=0;i<G .vexnum;i++) { if(i==ch) printf("\n %s %s",G .vexs[i].name,G .vexs[i].introduction); } printf("\n\n 是否继续查询(Y/N)"); getchar();<2>.从文件中读取信息并储存到图的结构体数组中。

数据结构与算法分析课程设计报告设计题目：校园导航咨询系统专业学号姓名2013 年3 月3 日一、问题描述设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）（参考课本P186-P192）。

二、需求分析本程序分为五个模块，分别是显示校园全景、查询景点信息、问路查询系统、查看游览路线和退出系统。

（1）显示校园全景展示校园概貌图和各景点编号、名称。

（2）查询景点信息输入要查询的景点编号，显示景点的编号、名称和景点的简单介绍。

（3）问路查询系统输入要参观的两个景点的编号（按从大到小输入），显示两个景点间的最短路径游览方式和最短路径长。

（4）查看游览路线查询某个景点到其他景点的所有路径，并显示其长度。

（5）退出系统查询完毕关闭窗口，显示退出系统的界面三、概要设计1、主要函数：void main() 主函数，程序入口csinfo() 初始化景点信息csroad() 初始化道路信息showpath() 显示校园全景search() 查询景点信息floyd() 弗洛伊德函数，查询两个景点之间的最短路径所要经过的中间节点print(int i,int j) 打印两个景点的路径及最短距离shortpath() 问路查询，求最短路径ShortestPath_DIJ(Maph * M) 利用Dijkstra算法来计算出起点到各个顶点之间的最短路径,以v0为起点menu() 显示菜单选项2、主要变量：ps[MaxPointNum] 定义主要景点信息，存放景点的编号、名称、简要介绍等信息char name[20] 景点名称char number[15] 景点编号char info[100] 景点简介信息MaxPointNum 最大景点个数INFINITY 近似无穷大，表示两景点不可达Maph M 全局变量,定义M为Maph类型int shortest[MaxPointNum][MaxPointNum] 定义全局变量存贮最短路径int path[MaxPointNum][MaxPointNum] 定义存贮路径3、存储结构：3.1 图的类型定义typedef struct{char name[20]; //景点名称char number[15]; //景点代号char info[100]; //景点信息}Elemtype; //景点类型3.2 定义景点typedef struct{int num; //顶点编号Elemtype data; //顶点信息}Point; //定义顶点3.3定义全局变量typedef struct{Point ps[MaxPointNum]; //存放顶点的一维数组int road[MaxPointNum][MaxPointNum];//存放路径的长度(邻接矩阵)int poinum,arcnum; //顶点数，边数}Maph;4、求解算法：迪杰斯特拉算法求解无向图的最短路径四、详细设计详细参见C语言源程序1.调试分析运行程序进行调试：1.进入主界面，出现校园导航咨询系统主菜单。

数据结构课程设计设计题目：校园导游咨询学院：信息学院班级：计算机1008班姓名：学号： 20101221180日期： 2012 年 3 月校园导航问题[问题描述]设计一个校园导游程序，为来访的客人提供各种信息查询服务。

[基本要求]（1）设计所在学校的校园平面图，所含景点不少于十个。

以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。

（2）为来访客人提供图中任意景点相关信息的查询。

（3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的一条最短的简单路径。

（4）校园导游图的景点和道路的修改扩充功能。

（5）扩充道路信息，如道路类别（车道、人行道），以致可按客人所需分别查询人行路径或车行路径。

（6）扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽的导向信息。

（7）实现校园导游的仿真界面。

一、概要设计 (4)二、详细设计 (6)三、调试分析 (12)四、调用关系 (12)五、用户操作指南 (13)[测试数据]一、概要设计1. 数据类型#define V_MAX 20#define E_MAX 200typedef struct {char name[10];//名字//char code[10];//代码char info[20];//信息，简介int x,y;//坐标}VType;//顶点类型typedef struct {int live;//标记是否存在，如果被删除则为0，存在为1 char name[10];// 路名int length;//路的长度char ivex[10],jvex[10];//路(边)连接的两个顶点的名字int type;//表示道路类型，0表示两个都是，1表示人行道，2表示行车道}EdgeType;//边类型typedef struct AdjNode{int length;// 弧的长度char name[10];//关联的顶点的名字struct AdjNode *next;//下一条弧}AdjNode;//弧结点typedef struct {int live;//标记是否存在，如果被删除则为0，存在为1int flag;//标记是否被访问过VType data;//顶点的信息AdjNode *first_adj;//指向该顶点的第一条弧}VNode;//景点（顶点）结点typedef struct {VNode vex[V_MAX];//顶点数组EdgeType edge[E_MAX];//边的数组int v_num,e_num;}Graph;//图类型////////////////////////////////Graph G;AdjNode *p;2.基本函数////////////////////////////////void creatGraph(Graph &G);//创建校园图void load(Graph &G);//从文件中读取数据void save(Graph &G);//保存数据入文件int find_v(Graph G,char name[10]);//通过输入景点名字，返回该景点在vex数组里的下标void print_Graph(Graph G);//以邻接矩阵的形式输出图信息int direction(Graph G,char bname[10],char fname[10]);//用于判断并输出一个景点在另外一个景点的方位信息void search_view(Graph G);//查询并输出景点的所有信息void del_v(Graph &G);//删除景点void add_v(Graph &G);//增加景点void add_e(Graph &G)//增加道路void modify_v(Graph &G);//修改景点信息void del_e(Graph &G);//删除道路二、详细设计本程序由m.cpp、head.h、Menu.h、dijie.h4个文件构成。