基于无向图的校园导游系统数据结构课程设计报告

目录一、需求分析 (2)二、概要设计 (2)三、详细设计 (4)四、设计和调试分析 (9)五、用户手册 (9)六、测试结果 (10)1．操作命令符为s/S, (10)2．操作命令符为v/V, (11)3．操作符为v/V, (11)4．操作符为e/E, (11)5．综上可以查得： (12)七、附录 (12)参考文献 (13)校园导游咨询系统一、需求分析1．从福建农林大学的平面图中选取28个有代表性的景点，抽象成一个无向带权图。

以图中顶点表示景点，边上的权值表示两地间的距离。

2．本程序的目的是为了用户提供路径咨询，根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。

3．测试数据（附后）。

二、概要设计1.抽象数据类型图的定义如下：ADT {struct arcnode{ int v;int w;struct arcnode *next;};struct node{ int degree;struct arcnode *first;}adjlist[28];}2.主程序V oid mian(){初始化临接矩阵windows(); / /初始化串口getch();}3.函数定义的变量#define infi 32767#define MAX 28int M,N; //无向图中的顶点M，无向图的变数int adjmatrix[MAX][MAX]; // 保存临接矩阵的2唯数组char *schoolIfo[MAX+1]={ //此数组用于界面显示信息"null","东台-dt","金1-j1","金2-j2","金3-j3","金4-j4","食堂-st","田径场-tjc","校大门-xdm","创业园-cyy","校医院-xyy","图书馆-tsg","映辉桥-yhq","观音湖-gyh","成教楼-cjl","生物楼-swl","博学楼-bxl","创新楼-cxl","明德楼-mdl","拓荒广场-thgc","南区公寓-nqgy","田家炳楼-tjbl","农大新区-ndxq","中华广场-zhgc","905终点站-zdz","蜂疗医院-flyy","研究生公寓-yjsgy","昌融学生街-crxsj","北区学生公寓-bqxsgy"};char *charcd2[MAX]={ //用于显示最短路径时走向的数组"校大门","金1","昌融学生街","创业园","东台","金2","田径场","拓荒广场","南区公寓","校医院","食堂","成教楼","创新楼","田家炳楼","农大新区","观音湖","金3","映辉桥","金4","明德楼","中华广场","905终点站","蜂疗医院","生物楼","博学楼","图书馆","研究生公寓","北区学生公寓"};char *charcd[MAX]={ //用于用户输入起始点与终止点时对应的数组"xdm","j1","crxsj","cyy","dt","j2","tjc","thgc","nqgy","xyy","st","cjl","cxl","tjbl","ndxq","gyh","j3","yhq","j4","mdl","zhgc","zdz","flyy","swl","bxl","tsg","yjsgy","bqxsgy"};char *infor[MAX]={ //介绍景点信息数组"校大门:\n 占不提供介绍","金1:\n 指金山大道的一处,由图可知","昌融学士街:\n 农大的小吃一条街,来农大一定要来尝尝!","创业园:\n 农大创业有志者的孵化地","东台:\n 农大老师所住之处","金2:\n 金山大道的第二处有图可看出","田径场:\n 农大的运动场地","拓荒广场:\n 大礼堂就在此处","南区公寓:\n 顾名思意,学生公寓","校医院:\n 希望你不要来","食堂:\n 学校八九十食堂都在这,不错蛮好吃的。

重庆科技学院课程设计报告院（系）:_电气与信息工程学院专业班级:计科普0902学生姓名:周杨学号: 2009441622设计地点（单位）____计算机基础自主学习中心I306___设计题目:_________校园导游咨询____________________ 完成日期： 2011 年 1 月 14 日指导教师评语: _______________________________________ ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________ __________ _成绩（五级记分制）:______ __________指导教师（签字）:________ ________重庆科技学院课程设计任务书设计题目：校园导游咨询教研室主任：指导教师：向毅、陈刘奎、熊茜2010年 12 月 20日摘要现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。

本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。

算法设计实践课程报告学院：计算机学院班级：学号：姓名：一、课程目的本课程设计为培养学生综合实践的能力，理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对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;}。

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称校园导游程序学生姓名张传乐学号0804012011专业班级计算机科学与技术08级（2）班指导教师王昆仑张贯虹2010年6月题目：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

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

要求：（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。

（3）查询图中任意两个景点间的所有路径。

选作内容：求多个景点的最佳（最短）游览路径。

一：问题分析和任务定义此程序需完成如下要求：用无向网表示所在学校的校园景点平面图，要做到可以查询各景点的相关信息，查询任意两个景点间的最短路径，查询图中任意两个景点间的所有路径。

实现本程序需要解决的几个问题：1，校园无线网应采用什么存储方式来存储 2，对大量信息的输入怎样处理。

3，Dirjstra 最短路径算法实现过程 4，所有路径的算法实现下图为合肥学院南区平面图：图1：校园拓扑图灯光球场南门五三 一栋主楼六四 二栋 转盘东门礼堂 操场欲求任意两点之间的最短路径，要将Dirjstra算法稍加改变一下，因为Dirjstra算法是求任意一点到其他所有点的最短路径，而本题只要求求任意两点之间的最短路径，故在找到要到的另一点后就可停止算法，跳出循环了。

在求任意两点间所有路径的函数中，在邻接表存储图中，要采用递归的思想求解两点间所用路径，从一点出发，在找到要找的另一点后，输出走过的路径path，并通过return跳出本次递归函数，继续寻找，知道所有的情况都被寻找过为止。

二、概要设计和数据结构选择对合肥学院校园平面图用邻接表存储，由于校园的景点之间的路较少，故如用邻接矩阵存储的话，该矩阵就是一个稀疏矩阵，这样就会造成存储空间的极度浪费。

故采用邻接矩阵存储对存储空间上就会不会造成太大的浪费了。

西安郵電大學数据结构课程设计报告书崔斌专业名称 计算机科学与技术专业计科1106系部名称计算机学院 学生姓名04111185指导教师2012年12月15日 至 间2012年12月21日实验题目：校园导游系统一、实验目的① ：为了让非本校的同学们，家长们能够充分了解本校 ---西安邮电大学。

② ：实践数据结构所学知识。

二、实验内容学校简易的俯视图。

各个景点的简单介绍。

任意两景点之间的所有路径。

任意两景点之间的最少中转景点路径。

任意两景点之间的带权路径长度。

三、需求分析①: ②: ③: ④: ⑤:Init();初始化两个顺序栈Menu();进行选择的模块函数；Intro();景点介绍函数；SearchO;判断是否有此编号的景点；Fin dall path();找路径函数；Fin dallway();找任意两个景点之间的所有路径；(存在栈里面) ShortestwayO;任意两个景点之间中转次数最少的路径；(从栈里面读取出来) NicewayO;任意两个景点之间总权值最小的路径；(从栈里面读取出来) Calculate();(从栈里面读取出来相关数据)，进行分析运算；Byebye();你懂得！四、概要设计1、方案设计对系统进行分析，给出景区图+++++++++++牛++++++++¥++++占-I-ILnJ一戸IJ]一(一恃//思想；递归结合循环，然后，找到终点时还要回溯；两点之间的所有路径void findallway(adjlist *G,int m,int n)//int i,t,k;arcnode *p;p a_th rp;p ush(s,m);G->vertex[m-1].flag=1;if(m==n)rp .sumweight=k=calculate(G);rp .sum=s->t op;rp.num=(y+1);p ush1(&z,r p);printf(" 路径%3d 为(途径%2d 个景点，长度为%3d) : ",y+1,s->top,k);for(i=O;iv=s->t op ;i++)p rintf("->%d",s->elem[i]);p rintf("\n");G->vertex[m-1].flag=1;y++;//外部全局变量二for(p=G->vertex[m-1].firstarc ;p!=NULL ;p=p-> nextarc)t=p->num;if(G->vertex[t-1].flag==0)findallway(G,t,n);G->vertex[s->elem[s->to p]-1].flag=0;// pop s(s);}//从文件里读取数据;错误1 ;不知道此节点有几个邻接点，因为%s 的原因，就会只把第一个节点的相关数据读出来，从第二个节点的相关信息处，开始读出错误(即烫烫烫烫烫烫烫烫烫烫烫)不超过m;错误2 ;读文件时，因为有链表的部分，就按照单链表的创建些写，结果总是此节点的 最后一个邻接点没被读到内存里，究其原因，是最后一个 (不仅我把 p2->nextarc=NULL;还把 free(p1);)void readnet(adjlist *G) {int i,count,m;arcnode *head,* p2,* p1; FILE *fp;fp=fo pen(U,"rt"); if(fp==NULL) {printf(-文件打开失败！ ！ ");exit(0);}for(i=0;i<vnum;i++) {fscanf(fp,"%d %s %s %d %d",&G->vertex[i].num,G->vertex[i].name,G->vertex[i].introduce,&G->vertex[ i].sum,&G->vertex[i].flag);//fprintf()的''后面不加第一个空格也可以。

竭诚为您提供优质文档/双击可除校园导游系统实验报告篇一：校园导游图系统数据结构实验报告一.设计目的通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。

二.设计内容用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

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

游客通过终端可询问：（1）从某一景点到另一景点的最短路径。

（2）游客从公园进入，选取一条最佳路线。

（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。

[基本要求]（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离．为此图选择适当的数据结构。

（2）把各种路径都显示给游客，由游客自己选择浏览路线。

（3）画出景点分布图于屏幕上。

[实现提示] （1）构造一个无向图g并用邻接矩阵来存储。

（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，最短路径长度就用一维数组d[i]存放；i的范围：0～20。

（3）一维数组have[]是用来记录最短路径出现顶点的顺序。

（4）根据起点和终点输出最短路径和路径长度。

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

1.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出2.查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径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;//vo为起始景点的编号while(flag){printf("请输入一个起始景点编号:");scanf("%d",if(v0g->vexnum){printf("景点编号不存在!请重新输入景点编号:");scanf("%d",}if(v0>=0}for(v=0;vvexnum;v++){fin al[v]=0;//初始化各顶点访问标志D[v]=g->arcs[v0][v].adj;//v0到各顶点v的权值赋值给d[v]for(w=0;wvexnum;w++)//初始化p[][]数组，各顶点间的路径全部设置为空路径0p[v][w]=0;if(D[v]final[v0]=1;//v0的访问标志设为1，v属于s集for(i=1;ivexnum;i++)//对其余g.vexnum-1个顶点w，依次求v到w的最短路径{min=InFInITY;for(w=0;wvexnum;w++)//在未被访问的顶点中，查找与v0最近的顶点vif(!final[w])if(D[w]vexnum;w++)//修改v0到其余各顶点w的最短路径权值d[w]if(!final[w]//修改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->vexs[v0].name);//输出景点v0的景点名for(w=0;wvexnum;w++)//对图中每个顶点w，试探w是否是v0到v的最短路径上的顶点{if(p[v][w]t++;}if(t>g->vexnum-1}}五．测试数据及运行结果1．正常测试数据和运行结果1.浏览校园全部景点信息：2.查看景点信息：3.输出两个景点间的最短路径:2．异常测试数据及运行结果1.当输出错误编号时程序没有反映，继续输入直到输入正确：2.当查询两景点编号相同时的最短路径时，结果如下：篇二：校园导游实验报告[1]校园导游实验报告学号：20XX30457018姓名：熊博班级：09计科1班完成日期：20XX-12-211、问题描述制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。

一、需求分析设计一个校园导游系统程序，为来访的客人提供各类效劳的信息查询。

(1).设计工商学院校园无向图，所含的景点很多于10个。

以图中极点表示校内各景点，寄存景点名称、代号、简介等信息；以边表示途径，寄存途径长度等相关信息。

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

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

二、设计思路校园旅行模型是由景点和景点之间的途径组成的，因此这完全能够用数据结构中的图来模拟。

用图的结点代表景点，用图的边代表景点之间的途径。

因此第一应设计一个图类。

结点值代表景点信息，边的权值代表景点间的距离。

结点值及边的权值用顺序表存储，因此需要设计一个顺序表类。

本系统需要查询景点信息和求一个景点到另一个景点的最短途径长度及线路，为方便操作，因此给每一个景点一个代码，用结构体类型实现。

计算途径长度和最短线路时可用弗洛伊德（Floyd）算法实现。

最后用switch选择语句选择执行阅读景点信息或查询最短途径。

3 算法设计概要设计3.1.1 程序中包括的模块（1）主程序模块主函数：void main(void)void cmd(void) cmd修改显示框大小,字体背景颜色,初始化景点，景点信息打印菜单，MGraph InitGraph(void); 3.1.2dj=INFINITY;[0][1].adj=80;/*途径度*/[0][2].adj=180;[0][6].adj=200;[1][11].adj=120;[1][2].adj=100;[2][5].adj=50;[3][4].adj=60;[4][9].adj=140;[5][9].adj=250;[5][7].adj=150;[6][7].adj=190;[6][9].adj=150;[8][7].adj=130;[8][6].adj=50;[10][12].adj=100;[9][10].adj=150;[3][4].adj=190;[5][13].adj=150;[14][7].adj=350;[2][3].adj=190;[2][9].adj=150;[2][11].adj=120;[0][8].adj=120;[1][2].adj=50;[10][12].adj=170;[12][15].adj=160;for(i=0;i<;i++)for(j=0;j<;j++)[j][i].adj=[i][j].adj;return G;界面菜单设计：菜单项选择择void Menu(){printf("\n 武汉工商学院院导游图\n");printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf(" ┃ 1.阅读校园全景┃\n"); printf(" ┃ 2.查看所有游览线路┃\n"); printf(" ┃ 3.确信两景点之间最短距离┃\n"); printf(" ┃ 4.查看景点信息┃\n"); printf(" ┃ 5.退出导游系统┃\n"); printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("Option-:");}Menu();scanf("%d",&i);while(i!=5){switch(i){case 1:system("cls");Browser(&b);Menu();break;case 2:system("cls");ShortestPath_DIJ(&b);Menu();break;case 3:system("cls");Floyd(&b);Menu();break;case 4:system("cls");Search(&b);Menu();break;case 5:exit(1);break;default:break;}介绍景点：void Browser(MGraph *G){int v;printf("┏━━┳━━━━━━━━━━┳━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); printf("┗━━┻━━━━━━━━━━┻━━━━━━━━━┛\n"); for(v=0;v<G->vexnum;v++)printf("┃%-4d┃%-20s┃%-60s\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction);printf("┗━━┻━━━━━━━━━━┻━━━━━━━━━┛\n"); }要查找的两个景点的最短距离：用floyd算法求两个景点的最短途径void Floyd(MGraph *G)dj;for(u=0;u<G->vexnum;u++)p[v][w][u]=0;if(D[v][w]<INFINITY){ p[v][w][v]=1;p[v][w][w]=1; }}for(u=0;u<G->vexnum;u++)for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++)if(D[v][u]+D[u][w]<D[v][w]){ D[v][w]=D[v][u]+D[u][w];for(i=0;i<G->vexnum;i++)p[v][w][i]=p[v][u][i]||p[u][w][i]; }while(flag){ printf("请输入动身地编号:");scanf("%d",&k);if(k<0||k>G->vexnum){ printf("景点编号存!\n请输入动身地编号:");scanf("%d",&k); }printf("请输入目的地编号:");scanf("%d",&j);if(j<0||j>G->vexnum){ printf("景点编号存!\n请输入目的地编号:");scanf("%d",&j); }if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)flag=0; }printf("%s",G->vexs[k].name);for(u=0;u<G->vexnum;u++)if(p[k][j][u]&&k!=u&&j!=u)printf("-->%s",G->vexs[u].name);printf("-->%s",G->vexs[j].name);printf(" 总线路%dm\n",D[k][j]); }查看所有游览线路算法计算，引进一个辅助向量D，它的每一个分量D表示当前所找到的从始点v0到每一个终点vi的的长度。

（强烈推荐）基于⽆向图的校园导游系统_数据结构毕业论⽂报告课程设计报告院（系）:_电⽓与信息⼯程学院专业班级:计科普0902 设计地点（单位）____计算机基础⾃主学习中⼼I306___设计题⽬:_________校园导游咨询____________________课程设计任务书设计题⽬：校园导游咨询教研室主任：指导教师：向毅、陈刘奎、熊茜2010年 12 ⽉ 20⽇摘要现代快节奏的⽣活使得都市⼈越来越渴望亲近⾃然，因此外出旅游现在被越来越多的都市⼈所看中，所以如何快速⽅便的找到我们想要的旅游景点的信息和最短路径就成了⼀个很重要的问题。

本设计基于图的结构，创建⼀个⽆向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放⼊到图的顶点当中并保存在景点⽂本⽂件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值⽂本⽂件当中，利⽤迪杰斯特拉算法来求从⼀个景点到另⼀个景点的最短距离，利⽤strcmp();函数来查找景点，并显⽰出它的信息，从⽽解决了要查找景点信息和景点之间的最短路径的问题，最后按照显⽰屏上的提⽰进⾏相关的操作。

关键词：⽆向图、查找信息、最短距离、校园导游咨询⽬录摘要 ................................................................................................................................................... I 1 设计内容和要求 .. (1)1.1设计内容 (1)1.1设计要求 (1)2 概要设计 (2)2.1 程序的模块图 (2)2.2 主函数的概要设计 (3)2.3 查找介绍函数的概要设计 (3)2.4 查找最短路径函数的概要设计 (3)2.5 退出函数的概要设计 (3)3 详细设计 (4)3.1 程序的流程图 (4)3.2 主函数的详细设计 (5)3.3 查找介绍函数的详细设计 (5)3.4 查找最短路径函数的详细设计 (6)3.5 退出函数的详细设计 (8)3.6 数据结构的详细设计 (8)4 软件测试 (10)4.1 菜单的测试 (10)4.2 查找景点简介的测试 (10)4.3 查找两个景点之间的最短距离的测试 (11)4.4 退出的测试 (11)5 软件使⽤说明 (12)6 致谢 (13)7 参考⽂献 (14)8 附录 (15)1 设计内容和要求1.1设计内容依据课程设计的要求，利⽤⼀个⽆向图的结构，将景点当作图的顶点，将景点之间的距离当作权值来储存，然后根据游客⾃⼰的需求，按照显⽰屏上的提⽰来进⾏查找景点介绍，查找两个景点之间的最短距离，退出程序等基本操作。

上海电力学院数据结构C++课程设计题目: 校园导游咨询学生姓名：学号：院系：专业年级：2011年7月1日一、设计题目校园导游咨询；1、实验目的（1）熟练掌握图的创建及遍历基本操作算法。

（2）熟练掌握最短路径算法。

（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。

2、实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。

【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。

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

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

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

【测试数据】由读者根据实际情况指定。

【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。

顶点和边均含有相关信息。

【选作内容】(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。

二、小组成员分工说明略三、需求分析1）运行环境（软、硬件环境）硬件环境：windows2000、windows XP、windows7 皆可；软件环境：Microsoft (R) Developer Studio (2)2）输入的形式和输入值的范围输入形式：整形数据（景点代号、路径长度、地图上的方位信息），字符串（景点名称及简介）；输入值范围：景点代号为：整形0~17（共18个景点）路径长度为：整形1~10（两景点间距离，以近似1：:100m比例换算，最远1km）景点名称字符串长度：整形1~15（景点名称）字符串长度为：字符数组1~50（对景点进行简要介绍）景点在地图方位图上的位置：整形0~103）输出的形式描述景点代号、景点名称、信息的关联以cout形式输出，告知来访客人，以便查询；景点信息查询结果的输出形式为cout字符串；两景点间最短路径输出形式为cout字符串符号、以及嵌套的printroad（）函数以显示路径信息及方位信息，方便客人获取最佳路线；4）功能描述(1)设计学校的校园平面图，所含景点18个。