数据结构课程设计报告,校园导游图

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

数据结构试验报告校园导游《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题⽬：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：⼤⼆；学号：10054220；指导教师：王⽴波；2011年12⽉17⽇1 课程设计的⽬的 (x)2 需求分析 (x)3 课程设计报告内容 (x)1、概要设计 (x)2、详细设计 (x)3、调试分析 (x)4、⽤户⼿册 (x)5、测试结果 (x)6、程序清单 (x)4 ⼩结 (x)5 参考⽂献 (x)1.课程设计的⽬的：（1）熟练运⽤C++编写程序；（2）会⽤Floyd算法查找最短路径；2.需求分析：1.题⽬：【校园导游咨询】[问题描述]（1）设计你的学校的校园平⾯图，所含景点不少于10个。

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

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

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

[测试数据]由读者根据实际情况指定。

2.任务：通过此程序可实现以下功能：（1）⽤⼀维数组存放景点信息，⼆维数组存放景点间的距离，最短距离，最短路径；（2）Floyd算法计算最短距离和路径；（3）根据景点序号查询景点的⼀系列信息，及两景点间的最短路径和最短距离。

3.测试数据:查询类型：I（表⽰查询景点信息）；景点编号：3；查询类型：D（表⽰查询景点间的最短路径和最短距离）；景点编号：1 9；3. 课程设计报告内容：1. 概要设计：（1）⾸先我画了学校主要⼏个景点的分布图以及⾃⼰定的⼀些距离，图如下：（2）接着我定义了⼀个顶点结构体，定义如下：struct Date{int num; //景点编号char name[50]; //景点名称char introduce[100]; //景点介绍};（3）然后我定义了⼀个类，定义如下：class Travel{private:Date date[15];int distance[15][15];int Path[15][15];int ShortestDistance[15][15];void Floyd();public:Travel();~Travel(){}void Introduce(int);void Scanf();void ShortDistance(int,int);};（4）基本操作：void Floyd(); //Floyd算法，计算最短路径和最短距离Travel(); //构造函数~Travel(){} //析构函数void Introduce(int); //介绍景点函数void Scanf(); //外部输⼊函数void ShortDistance(int,int); //最短距离计算函数本程序分为2个模块：Int main(){初始化；Void Scanf();}函数调⽤关系基本结构图如下所⽰：2. 详细设计：（1）主函数初始化变量；（2）调⽤外部接⼝函数Scanf()；（3）输⼊查询类型，如果为“I”，调⽤景点介绍函数，如果为“D”，调⽤最短距离和路径函数。

《数据结构与算法》实验报告一、需求分析【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。

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

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

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

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

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

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

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

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

二、概要设计1）抽象数据类型定义描述#include<iostream>using namespace std;const int MaxSize=18;const int INFINITY=65535;//最大值无穷class direction;template <class T> class MGraph;template <class T>class VertexNode//定义景点结点，存储景点信息{friend class MGraph<T>;public:int vex;//景点名称T vexname;//景点名称T vexinf;//景点信息direction dir;//存放景点方位信息的direction类的dir。

};class direction{public:int ln;//存放在方向图中的横坐标，表示东西int col;//存放在方向图中的纵坐标，表示南北};template <class T>class MGraph//定义无向图的邻接矩阵{public:MGraph();//构造函数，初始化具有n个顶点的图void printvexname();//显示所有景点及景点代号void printvexinf(int i);//显示代号为i景点的名称及信息void printroad(int i,int j);//显示景点i~j的最短路径方案信息void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m”VertexNode<T> adjlist[MaxSize]; //存放景点全部信息的景点类数组int vertexNum,arcNum; //图的顶点数和边数void Root(int p,int q);//递归寻找pq间的最短路径int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int Line[MaxSize];//Line存放路径int kkk;//在floyed算法中，做Line[]数组的标记private:T vertex[MaxSize]; //存放图中顶点的数组int arc[MaxSize][MaxSize];//存放图中边的数组};2）功能模块设计（如主程序模块设计）int funcchoice()//系统功能选择页面{int choice;cout<<"=============================================================="<<endl;cout<<" 欢迎进入校园导游咨询平台"<<endl;cout<<" 1--显示校园所有景点信息"<<endl;cout<<" 2--查询校园景点信息"<<endl;cout<<" 3--问路查询系统"<<endl;cout<<" 4--退出导游资讯平台"<<endl;cout<<"=============================================================="<<endl;cout<<"请输入要选择的功能号：";cin>>choice;return choice;}3）模块层次调用关系图三、详细设计//程序的头文件#include<iostream>#include<iomanip>#include"guide.h"using namespace std;template <class T>MGraph<T>::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，d[]为景点方位信息的横坐标，e[]为景点方位信息的纵坐标，s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{i nt s[]={0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};i nt a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};c har* b[]={"南门","实验楼","南图","大活","睿思楼","大礼堂","南4教","知行楼","国交楼","南3教","南2教","南1教","北图","北3教","北4教","北2教","北1教","北门"};c har* c[]={"南校区正门","物理实验楼","南校区图书馆","大学生活动中心","教师办公楼、医务室及留学生公寓","大礼堂，用于举办各种文艺演出","南校区第4教学楼","实习基地，计算机房等","国际交流中心，教职工餐厅","南校区第3教学楼","南校区第2教学楼","南校区第1教学楼","北校区图书馆","北校区第3教学楼","北校区第4教学楼","北校区第2教学楼","北校区第1教学楼","北校区正门"};i nt d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};i nt e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};i nt i,j;v ertexNum=18;a rcNum=30;f or(i=0;i<vertexNum;i++){adjlist[i].vex=a[i];adjlist[i].vexname=b[i];adjlist[i].vexinf=c[i];adjlist[i].dir.ln=d[i];adjlist[i].dir.col=e[i];}f or (i=0; i<vertexNum; i++)//初始化邻接矩阵for (j=0; j<vertexNum; j++)arc[i][j]=arc[j][i]=s[(i*(i+1))/2+j]; //根据s[]的对称性，将一维数组中的数据赋给二维数组arc[][]}template<class T>void MGraph<T>::printvexname(){i nt i;f or(i=0;i<vertexNum;i++)cout<<adjlist[i].vex<<" "<<adjlist[i].vexname<<endl;;}template<class T>void MGraph<T>::printvexinf(int i){c out<<i<<" "<<adjlist[i].vexname<<":"<<adjlist[i].vexinf<<endl;}template<class T>void MGraph<T>::printdir(int i,int j){i nt dx,nb;//临时存放i与j之间的南北东西关系 j在i的哪边？？d x=adjlist[j].dir.col-adjlist[i].dir.col;n b=adjlist[j].dir.ln-adjlist[i].dir.ln;i f(dx>0)//即j在i的东边cout<<"向东"<<dx*100<<"m，";e lsecout<<"向西"<<dx*(0-100)<<"m，";i f(nb>0)//即j在i的南边cout<<"向南"<<nb*100<<"m";e lsecout<<"向北"<<nb*(0-100)<<"m";}template<class T>void MGraph<T>::Root(int p,int q){i f (Path[p][q]>0){Root(p,Path[p][q]);Root(Path[p][q],q);}e lse{Line[kkk]=q;kkk++;}}template<class T>void MGraph<T>::printroad(int i,int j){i nt p,q,m,k,item1,item2;f or(p=0;p<vertexNum;p++)for(q=0;q<vertexNum;q++)Dist[p][q]=arc[p][q];//邻接矩阵赋值f or(k=0;k<vertexNum;k++)for(p=0;p<vertexNum;p++)if (Dist[p][k]>0)for(q=0;q<vertexNum;q++)if (Dist[k][q]>0)if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}c out<<"\n=====================================================\n";c out<<"从"<<adjlist[i].vexname<<"到"<<adjlist[j].vexname<<"的最短路径为："<<endl;c out<<adjlist[i].vexname;k kk=2;R oot(i,j);i tem2=Line[2];c out<<"-->";p rintdir(i,item2);c out<<"-->"<<adjlist[item2].vexname;f or(m=3;m<=kkk-1;m++){item1=Line[m];cout<<"-->";printdir(item1-1,item1);cout<<"-->"<<adjlist[item1].vexname;}c out<<endl;c out<<"\n=====================================================\n";}========================以下为main.cpp文件中主函数的实现========================== #include<iostream>#include"guide.cpp"using namespace std;int funcchoice()//系统功能选择页面{i nt choice;c out<<"=============================================================="<<endl;c out<<" 欢迎进入校园导游咨询平台"<<endl;c out<<" 1--显示校园所有景点信息"<<endl;c out<<" 2--查询校园景点信息"<<endl;c out<<" 3--问路查询系统"<<endl;c out<<" 4--退出导游资讯平台"<<endl;c out<<"=============================================================="<<endl;c out<<"请输入要选择的功能号：";c in>>choice;r eturn choice;}void main(){M Graph<char*> mg;i nt funcchoice();i nt fc;w hile(1){fc=funcchoice();if(fc==1){int i;for(i=0;i<mg.vertexNum;i++)mg.printvexinf(i);}else if(fc==2){int i;mg.printvexname();cout<<endl<<"请输入所要查询景点代号：";cin>>i;mg.printvexinf(i);}else if(fc==3){int i,j;mg.printvexname();cout<<"请输入两景点代号（我们将把最短路线反馈予您）：";cin>>i>>j;mg.printroad(i,j);}else if(fc==4)break;elsecout<<"输入有误，请重新输入！"<<endl;}}if调试分析遇到的问题及解决的办法：在调试过程中，最常见到的问题有以下几种：1、忘记调用函数类模块template<class T>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。

软件学院学生实验报告册实验课程名称：数据结构与算法实验项目名称：校园导游咨询实验类型（打√）：（基础、综合、设计√）院系：信息工程学院计算机系专业：*****姓名：*** 学号：*****指导老师：***软件学院教务处编制一、实验预习报告内容二、实验原始（数据）记录实验时间：2007 年 6 月20日（星期三第7，8 节）实验同组人：三、实验报告内容2010年6 月21日注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。

2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。

【源程序】#include<iostream.h>#include<stdlib.h>#include<string.h>#include<conio.h>#include<stdio.h>#include<process.h>#define OK 1#define ERROR 0#define MAX_CHARSTRING 100#define MAX_NAME 30#define INFINITY 32767typedef bool Status;typedef int VRType;typedef FILE *PFILE;typedef char *Infotype;//模块一：用邻接矩阵存储校园的地图struct ArcCell//弧类型表示路径{VRType adj;//路径的权值Infotype info;//路径的相关信息};struct VertexType//顶点类型表示景点{char name[MAX_NAME],number[MAX_NAME]; //景点的名称name、代号numberInfotype info;//景点的简介};struct MGraph//图类型表示校园的地图{VertexType *Vexs;//顶点向量指针ArcCell *Arcs;//邻接矩阵指针int *Short_st_Path;//存放最短路径的三维数组指针int vexnum,arcnum;//图的顶点vexnum数和弧数arcnum};int CalTwoDimPos(int b,int i,int j)//把第一维为b的二维数组的下标为[i][j]的地址转换成一维数组的地址,并返回{return i*b+j;}int CalThreeDimPos(int b,int i,int j,int k)//把第一、二维为b的三维数组的下标为[i][j][k]的地址转换成一维数组的地址,并返回{return i*b*b+j*b+k;}Status OpenWriteFile(PFILE &fp,char string[MAX_NAME])//打开写的文件名为string的文件{if(!(fp=fopen(string,"wb"))){cout<<"文件打开失败"<<endl;cout<<"Press any key to exit"<<endl;getch();exit(ERROR);}return OK;}Status OpenReadFile(PFILE &fp,char string[MAX_NAME])//打开读的文件名为string的文件{if(!(fp=fopen(string,"rb "))){cout<<"文件打开失败"<<endl;cout<<"Press any key to exit"<<endl;getch();exit(ERROR);}return OK;}Status MakeString(Infotype &ch)//分配一个字符串成功则返回1,否则返回0{if(!(ch=new char[MAX_CHARSTRING])){cout<<"字符串存储空间分配失败"<<endl;return ERROR;}return OK;}Status GetVex(int &v,char string[MAX_NAME],MGraph M)//返回图string顶点的位置,如果找到则返回它的位置，否则返回-1{for(v=M.vexnum-1;v>=0;v--)if(!(strcmp(string,M.Vexs[v].name)))return OK; return ERROR;}Status InitMGraph(MGraph &M,int n)//初始化一个顶点数为n的图{int i,adr;if(!((M.Arcs=new ArcCell[n*n])&&(M.Vexs=new VertexType[n])&&(M.Short_st_Path=new int[n*n*n]))){cout<<"图的存储空间分配失败"<<endl;exit(ERROR);}for(i=0,adr=0;i<n*n;i++,adr++)//对表示弧的邻接矩阵进行初始化{M.Arcs[adr].adj=INFINITY;M.Arcs[adr].info=NULL;}for(i=0,adr=0;i<n*n*n;i++,adr++)M.Short_st_Path[adr]=-1;return OK;}Status DestroyGraph(MGraph &M){int i,adr;for(i=0;i<M.vexnum;i++){delete(M.Vexs[i].info);M.Vexs[i].info=NULL;}delete(M.Vexs);M.Vexs=NULL;for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++) {if(M.Arcs[adr].info!=NULL){delete(M.Arcs[adr].info);M.Arcs[adr].info=NULL;}}delete(M.Arcs);M.Arcs=NULL;delete(M.Short_st_Path);M.Short_st_Path=NULL;return OK;}Status PutMGrap(MGraph M,char string[MAX_NAME])//把内存中的图保存在string文件中{FILE *fp;int i,adr;OpenWriteFile(fp,string);fwrite(&M.vexnum,sizeof(int),1,fp);fwrite(&M.arcnum,sizeof(int),1,fp);fwrite(M.Vexs,sizeof(VertexType),M.vexnum,fp); for(i=0;i<M.vexnum;i++)fwrite(M.Vexs[i].info,sizeof(char),MAX_CHARSTRI NG,fp);fwrite(M.Arcs,sizeof(ArcCell),M.vexnum*M.vexnum ,fp);for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++)if(M.Arcs[adr].info!=NULL)fwrite(M.Arcs[adr].info,sizeof(char),MAX_CHARST RING,fp);fwrite(M.Short_st_Path,sizeof(int),M.vexnum*M.vex num*M.vexnum,fp);fclose(fp);return OK;}Status GetMGrap(MGraph &M,char string[MAX_NAME])//从文件中取出一个文件名为string的图调入内存{FILE *fp;int i,adr;OpenReadFile(fp,string);fread(&M.vexnum,sizeof(int),1,fp);InitMGraph(M,M.vexnum);fread(&M.arcnum,sizeof(int),1,fp);fread(M.Vexs,sizeof(VertexType),M.vexnum,fp);for(i=0;i<M.vexnum;i++){MakeString(M.Vexs[i].info);fread(M.Vexs[i].info,sizeof(char),MAX_CHARSTRI NG,fp);}fread(M.Arcs,sizeof(ArcCell),M.vexnum*M.vexnum, fp);for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++) if(M.Arcs[adr].info!=NULL){MakeString(M.Arcs[adr ].info);fread(M.Arcs[adr].info,sizeof(char),MAX_CHARST RING,fp); }fread(M.Short_st_Path,sizeof(int),M.vexnum*M.vexn um*M.vexnum,fp);fclose(fp);return OK;}Status CreateMGraph()//创建一个图，并保存在string文件中{MGraph M;int i,j,k,adr,adr1;charv1[MAX_NAME],v2[MAX_NAME],string[MAX_N AME];VRType w;cout<<"请输入图的景点数和路径数:";cin>>M.vexnum>>M.arcnum;InitMGraph(M,M.vexnum);cout<<"请输入图名称、代号、简介:"<<endl;for(i=0;i<M.vexnum;i++)//输入景点的名称、代号、简介{MakeString(M.Vexs[i].info);cin>>M.Vexs[i].name>>M.Vexs[i].number>>M.Vexs[ i].info; }cout<<"请输入路径的起点、终点、权值和相关信息"<<endl;for(k=0;k<M.arcnum;k++){LEAP:cin>>v1>>v2;GetVex(i,v1,M);GetVex(j,v2,M);while(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl; goto LEAP;}cin>>w;adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=w;MakeString(M.Arcs[adr].info);cin>>M.Arcs[adr].info;adr1=CalTwoDimPos(M.vexnum,j,i);MakeString(M.Arcs[adr1].info);M.Arcs[adr1].adj=w;strcpy(M.Arcs[adr1].info,M.Arcs[adr].info); }cout<<"请输入图的保存路径\\名称:";cin>>string;PutMGrap(M,string);DestroyGraph(M);return OK;}Status Shortest_Path_FLOYD(char string[MAX_NAME])//对以文件名为string的地图求最短路径{MGraph M;int i,j,k,n,adr,adr1,adr2,*d;GetMGrap(M,string);if(!(d=new int[M.vexnum*M.vexnum])){cout<<"数组D[i][j]存储空间分配失败"<<endl;exit(ERROR); }for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){adr=CalTwoDimPos(M.vexnum,i,j);d[adr]=M.Arcs[adr].adj;if(d[adr]<INFINITY){adr=CalThreeDimPos(M.vexnum,i,j,0);M.Short_st_Path[adr]=i;M.Short_st_Path[adr+1]=j;}}for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++)for(k=0;k<M.vexnum;k++)if(j!=k){adr=CalTwoDimPos(M.vexnum,j,k);adr1=CalTwoDimPos(M.vexnum,j,i);adr2=CalTwoDimPos(M.vexnum,i,k);if(d[adr1]+d[adr2]<d[adr]){d[adr]=d[adr1]+d[adr2]; adr=CalThreeDimPos(M.vexnum,j,k,0);for(n=0;n<M.vexnum;n++) M.Short_st_Path[adr+n]=-1;adr1=CalThreeDimPos(M.vexnum,j,i,0);adr2=CalThreeDimPos(M.vexnum,i,k,0);for(;M.Short_st_Path[adr1]!=-1;){M.Short_st_Path[adr++]=M.Short_st_Path[adr1++]; }adr--;for(;M.Short_st_Path[adr2]!=-1;){M.Short_st_Path[adr++]=M.Short_st_Path[adr2++]; }}}PutMGrap(M,string);DestroyGraph(M);return OK;}Status Search_Shortest_Path(char string[MAX_NAME])//查询地图文件名为string的最短路径{MGraph M;char v1[MAX_NAME],v2[MAX_NAME];int i,j,k,adr;GetMGrap(M,string);cout<<"请输入起始位置和终点位置名称:"; cin>>v1>>v2;GetV ex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;return ERROR;}adr=CalThreeDimPos(M.vexnum,i,j,0);if(M.Short_st_Path[adr]==-1){cout<<v1<<"到"<<v2<<"的路径:没有路径"<<endl;return OK;}cout<<v1<<"到"<<v2<<"的路径:";for(k=0;M.Short_st_Path[adr]!=-1&&k<M.vexnum;a dr++,k++)cout<<M.V exs[M.Short_st_Path[adr]].name<<"-->"; cout<<"\b\b\b "<<endl;cout<<v1<<"到"<<v2<<"途经路径的信息:"<<endl; adr=CalThreeDimPos(M.vexnum,i,j,0);for(k=0;M.Short_st_Path[adr+1]!=-1&&k<M.vexnum -1;k++){i=M.Short_st_Path[adr];j=M.Short_st_Path[++adr];cout<<M.V exs[i].name<<"-->"<<M.Vexs[j].name<<"路径信息:"<<M.Arcs[CalTwoDimPos(M.vexnum,i,j)].info<<end l; }DestroyGraph(M);return OK;}Status Search_Sight(char string[MAX_NAME])//查询地图文件名为string的景点{MGraph M;char v1[MAX_NAME];int i;GetMGrap(M,string);cout<<"请输入景点名称:";cin>>v1;GetV ex(i,v1,M);if(i==-1){cout<<"输入景点名错误,请重新输入"<<endl;return ERROR; }cout<<"代号:"<<M.Vexs[i].number<<";相关信息:"<<M.Vexs[i].info<<endl;DestroyGraph(M);return OK;}Status InsertArc(char string[MAX_NAME])//对保存在string的地图增加一条弧{MGraph M;char v1[MAX_NAME],v2[MAX_NAME];int i,j,adr,adr1,w;GetMGrap(M,string);cout<<"请输入路径的起点、终点、权值和相关信息:";cin>>v1>>v2;GetV ex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;return ERROR; }cin>>w;adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=w;MakeString(M.Arcs[adr].info);cin>>M.Arcs[adr].info;adr1=CalTwoDimPos(M.vexnum,j,i);MakeString(M.Arcs[adr1].info);M.Arcs[adr1].adj=w;strcpy(M.Arcs[adr1].info,M.Arcs[adr].info);M.arcnum++;PutMGrap(M,string);DestroyGraph(M);return OK;}Status DeleteArc(char string[MAX_NAME])//对保存在string的地图删除一条弧{MGraph M;char v1[MAX_NAME],v2[MAX_NAME];int i,j,adr;GetMGrap(M,string);cout<<"请输入景点的起点、终点:";cin>>v1>>v2;GetV ex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;return ERROR; }adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=INFINITY;if(M.Arcs[adr].info!=NULL)delete(M.Arcs[adr].info);M.Arcs[adr].info=NULL;adr=CalTwoDimPos(M.vexnum,j,i);M.Arcs[adr].adj=INFINITY;if(M.Arcs[adr].info!=NULL)delete(M.Arcs[adr].info);M.Arcs[adr].info=NULL;M.arcnum--;PutMGrap(M,string);DestroyGraph(M);return OK;}void PrintMGrap(char string[MAX_NAME]) {FILE *fp;char c;OpenReadFile(fp,string);while(!feof(fp)){c=getc(fp);cout<<c;}cout<<endl;}void main(){char string[MAX_NAME],str[MAX_NAME],c,c1; do{system("cls");cout<<"************************************* ******************************************" <<endl;cout<<" *主功能及主要命令:(1)建立及修改地图C;"<<endl;cout<<" *菜(2)导游咨询T."<<endl;cout<<" *单(3)退出程序Q"<<endl;cout<<"************************************* ******************************************" <<endl;cout<<"请输入命令(C,T,Q):";cin>>c;switch(c){case 'C':system("cls");cout<<"************************************* ******************************************" <<endl;cout<<" *子功能及主要命令:(1)创建地图C;"<<endl;cout<<" *菜(2)增加一条路径A;"<<endl;cout<<" *单(3)删除一条路径D;"<<endl;cout<<" (4)返回上一级菜单Q."<<endl;cout<<"************************************* ******************************************" <<endl;do{cout<<"请输入命令(C,A,D,Q):";cin>>c1;switch(c1){case 'C':CreateMGraph();break;case 'A':cout<<"请输入要修改的地图路径\\名称"; cin>>string;InsertArc(string);break;case 'D':cout<<"请输入要修改的地图路径\\名称"; cin>>string;DeleteArc(string);break;}}while(c1!='Q');break;case 'T':cout<<"请输入要查询的地区:";cin>>string;Shortest_Path_FLOYD(string);system("cls");cout<<"************************************* ******************************************" <<endl;cout<<" 功能及主要命令:(1)显示平面图O;"<<endl;cout<<" *子(2)查询任意景点的信息I;"<<endl;cout<<" *菜(3)查询任意景点的最短路径R;"<<endl;cout<<" *单(4)返回上一级菜单Q."<<endl;cout<<"************************************* ******************************************" <<endl;do{cout<<"请输入命令(O,I,R,Q):";cin>>c1;switch(c1) {case 'O':cout<<"请输入地图的路径\\名称";cin>>str;PrintMGrap(str);break;case 'I':Search_Sight(string);break;case 'R':Search_Shortest_Path(string);break;}}while(c1!='Q'); break;};cout<<"请输入任意键继续运行程序"<<endl;getch();}while(c!='Q');}。

3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径
4.查看景点信息：直接用编号进行单个景点查询。
四．详细设计
重点设计及编码
在求最短路径时采用迪杰斯特拉算法
//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点
void ShortestPath_DIJ(MGraph * G)
（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，
边上的权值表示距离．为此图选择适当的数据结构。
（2）把各种路径都显示给游客，由游客自己选择浏览路线。
（3）画出景点分布图于屏幕上。
[实现提示]
（1）构造一个无向图G并用邻接矩阵来存储。
（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，
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的最短路径
}
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

《数据结构》课程设计报告设计题目校园导游图学院名称信息工程学院专业班级计算机科学与技术（2）班姓名晁勉学号 1212210226一. 题目：校园导游图二. 设计目标通过设计一个校园导游图，进一步理解数据结构中有关于图的基本概念、定义术语、存储结构等,理解图在描述现实问题中的能力，明白数据结构在程序设计中的重要性等。

三. 问题描述给出学校的导游图（景点不少于10个），游客通过终端询问可知：任一景点的相关信息:从某一景点到另一景点的最短简单路径；游戏从校园大门进入,选一条最佳路线，使游客可以不重复地游览个景点，最后回到出口（出口就在入口旁边)。

四. 需求分析需求：(1)将导游图看作一张带权无向图,图中顶点表示主要景点，存放景点的编号、名称、简介等信息；（2）可以通过菜单提示操作，浏览校园全部景点；（3）查看所有游览路线,将某个景点的所有路线展示给游客;（4）选择出发点和目的地，将最短路线展示给游客;（5）输入景点编号，查看某个景点的信息。

分析：完成对整个校园导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。

有以下设计思路：（1）结合本校的实际情况，选出10个景点;（2）为选出的10个景点赋上相关信息（景点编号、名称、简介）；（3）根据选出来的10个景点用邻接矩阵存储校园图.（4)利用C语言和数据结构编写实现校园导游图系统各功能的实现；（5）根据人为赋值的路权，设计算法计算任意两点之间的最短路径并显示;（6）综上所诉，用一个主函数把这些板块合成,生产一个菜单界面呈现在用户面前。

五. 概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能.课题涉及的数据结构和数据库结构；即要存储什么数据,这些数据是什么样的结构，它们之间有什么关系等。

六. 详细设计采用C语言定义相关的数据类型写出各模块的类C码算法图的定义typedefstructArCell{intadj；//路径长度｝ArCell，AdjMatrix［MAX_VERTEX_NUM］[MAX_VERTEX_NUM];typedefstruct //图中顶点表示主要景点,存放景点的编号、名称、简介等信息,初始化图形MGraph ＊CreatUDN(MGraph ＊G）//接受用户输入{inti，j，k，w；char v1[20］,v2［20]；printf（"请输入图的顶点数,弧数:"）；scanf("%d%d",&G->vexnum，&G-〉arcnum）;printf(”请输入景点的编号、名称、简介:\n”);for(i=0；i〈G->vexnum;i++）{printf（”景点编号：”);scanf（”％d”，&G-〉vexs—>num)；printf("景点名称：”);scanf(”％s",G—〉vexs［i］.name);printf("景点简介：”);scanf("％s"，G-〉vexs—>introduction）；｝for(i=0；i<G—>vexnum；i++）for(j=0;j〈G—〉vexnum;j++)G-〉arcs[i][j]。

姓名：班级：学号：指导教师：2012年12月目录1、需求分析 (1)1.1 系统简介 (1)1.2 系统功能模块介绍 (1)2、概要设计 (1)2.1 系统功能结构图 (1)2.2 系统流程图 (2)2.3 主要函数概要设计 (3)2.3.1 主函数概要设计 (3)2.3.2 初始化图函数InitGraph() (3)2.3.4 查询景点信息函数设计SearchGraph() (4)2.3.5 显示图中信息函数设计ShowGraph() (4)2.3.6 弗洛伊德算法函数设计Floyd() (4)3、详细设计 (4)3.1 主函数详细设计 (4)3.2初始化图函数详细设计InitGraph() (5)3.3查询景点信息函数详细设计SearchGraph() (6)3.4 弗洛伊德算法函数详细设计Floyd() (7)4、调试分析 (8)4.1 显示主界面函数测试 (8)4.2 查找两景点间最短路径测试 (9)4.3 查看景点信息测试 (10)5.课程设计总结 (11)6、附录 (12)1、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。

考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。

开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。

本系统界面友好，提示信息充分，在实际使用过程中运行良好。

1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。

景德镇陶瓷学院信息工程学院班级：11计科（2）班学号：*************名：**指导老师：李娟、徐星时间：2013年6月27号题目：13*：图（校园导游图）7 ：建立二叉树，层序、先序遍历14 ：拓扑排序题目一：图（校园导游图）1.1、需求分析：需求：（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。

为此图选择适当的数据结构。

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

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

分析：完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。

有以下设计思路：（1）.结合本校的实际情况，选出10个景点；（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；（3）.根据选出来的10个景点用邻接矩阵存储校园图。

（4）.依照景点的相关信息创建校园图。

（5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。

（6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。

（7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。

1.2、设计与实现：选出本校10个景点结合景德镇陶瓷学院实际情况，我选出以下10个景点，从1到10编号：图的初始化由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。

所以，图采用带权的邻接矩阵存储。

决定了图的存储方式后，以华南农业大学10个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图2.2所示，途中数字代表线的权值。

1.3、模块的划分含有四个模块：（1）陶院地图信息（2）陶院景点信息（3）查找两点间最短路径（4）退出模板功能（1）将陶院的地图显示在程序运用上；（2）输入一个景点，运用程序上能够显示该景点的信息；（3）可以给游客提供两个景点的最短路径；（4）给游客提供方便。

课程设计报告课程名称数据结构课程设计题目校园导航指导教师设计起始日期学院计算机学院系别计算机科学与工程学生姓名班级/学号成绩一、需求分析本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。

设计要包括下列要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

本课题实现校园多个场所（至少10个）的最短路径求解。

（1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。

(2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。

(3) 程序所能达到的功能：本程序可供任何人使用，主要功能 1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

a.首先看到的是校园导航系统的菜单：b．查看浏览路线等待输入起始景点：C．选择出发点与目的地等待输入起始景点与目的地编号：d．参看景点信息等待输入景点编号：二、概要设计本系统包含一个文件。

设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。

主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。

系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。

选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。

姓名：班级：学号：指导教师：2012年12月目录1、需求分析 (1)1.1 系统简介 (1)1.2 系统功能模块介绍 (1)2、概要设计 (2)2.1 系统功能结构图 (2)2.2 系统流程图 (2)2.3 主要函数概要设计 (3)2.3.1 主函数概要设计 (3)2.3.2 初始化图函数InitGraph() (4)2.3.4 查询景点信息函数设计SearchGraph() (4)2.3.5 显示图中信息函数设计ShowGraph() (4)2.3.6 弗洛伊德算法函数设计Floyd() (5)3、详细设计 (5)3.1 主函数详细设计 (5)3.2初始化图函数详细设计InitGraph() (6)3.3查询景点信息函数详细设计SearchGraph() (7)3.4 弗洛伊德算法函数详细设计Floyd() (8)4、调试分析 (9)4.1 显示主界面函数测试 (9)4.2 查找两景点间最短路径测试 (10)4.3 查看景点信息测试 (11)5.课程设计总结 (12)6、附录 (13)1、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。

考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。

开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。

本系统界面友好，提示信息充分，在实际使用过程中运行良好。

1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。

西安郵電學院数据结构设计报告题目：校园导游系统院系名称：计算机学院专业名称：计算机科学与技术班级：学生姓名：学号（8位）：指导教师：设计起止时间：2011年12月12日~2011年12月16日一. 设计目的1 对自己学过的知识进一步巩固，对数据结构的算法思想要有更深的理解。

2 通过课程设计，学会通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。

3 学会综合运用数据结构课程中图类型数据结构，组建一个较为完整的系统。

二. 设计内容1 校园平面图2 选取有代表性的景点，用邻接链表存储相关信息3 查询图中任意景点的相关信息4 查询任意两个景点之间的一条最短的简单路径5 查询中转最少的路径6 查询两个景点间的全部路径三．概要设计1．功能模块图2．各个模块详细的功能描述ShortestPath_Floyd() 任意两个地点之间最短路径算法least() 两个地点之间中转最少算法main() 主函数xiaoyuantu() 校园概略图shuchu() 校园的全部信息输出CreatUDN() 创建图DFS_ path() 两个景点之间的全部路径四．详细设计2．各功能函数的数据流程图ShortestPath_Floyd()allpath()least()3．重点设计及编码两个景点之间的全部路径void DFS_path(AdjM g, int m,int n,int k){int s;if(pre[k]==n && k<11) //pre[k]存储路径顶点若pre[k]是终点，则输出该路径{ //递归出口，找到一条路径for(s=0;s<k;s++)printf("%s>>>>>",g.vertex[pre[s]].name); //输出该路径。

s=0 时为起点mprintf("%s",g.vertex[pre[s]].name); //输出最后一个景点名(即顶点n的名字，此时s==k)printf("\n\n");}else{s=0;while(s<g.vexnum) //从第m个顶点，试探至m到其他顶点是否有路径{if((g.arcs[pre[k]][s].adj<INFINITY) && (visited[s]==0)) //顶点k到顶点s有边，且未被访问{visited[s]=1;pre[k+1]=s; //存储顶点编号s至pre[k+1]中DFS_path(g,m,n,k+1); //求从下标为k+1的pre[k+1]个顶点开始的路径(递归调用)，同时打印出一条m至n的路径visited[s]=0; //将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径}s++; //试探从下一个顶点s 开始是否有到终点的路径}}}void all_path(AdjM g){int i,m,n;printf("\n\n请输入你要查询的两个景点编号:\n\n");scanf("%d %d",&m,&n);printf("\n\n");pre[0]=m; //存储路径起点ufor(i=0;i<g.vexnum;i++) //全部顶点访问标志初值设为0visited[i]=0;visited[m]=1; //表示已经访问过DFS_path(g,m,n,0); //对应起点pre[0]==u}任意两个地点之间最短路径算法ShortestPath_Floyd(AdjM *g) //弗洛伊德算法{int i,k,j,l,flag=1,path[maxnum][maxnum][maxnum],dist[maxnum][maxnum];//path[][][]三维数组保存任意两个顶点之间的最短路径,如果P[i][j][l]为1，那么l是从i到j 的路径上的一个顶点//dist[][]二维数组保存任意两个顶点之间的最短路径的权值printf("景点编号如下：\n");for(i=0;i<g->vexnum;i++)printf(" %-4d %-15s\n",i,g->vertex[i].name);for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++){dist[i][j]=g->arcs[i][j].adj; //从i到j的直接路径为弧i--j的权值for(l=0;l<g->vexnum;l++)path[i][j][l]=0; //假设从i到j的最短路径没有经过其他顶点置值为0if(dist[i][j]<INFINITY) //判断最短路径是否包括i--j自身{path[i][j][i]=1;path[i][j][j]=1;}}for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)for(l=0;l<g->vexnum;l++)if(dist[j][i]+dist[i][l]<dist[j][l]) //如果从j经过i到l的路径更小,调换值{dist[j][l]=dist[j][i]+dist[i][l];for(k=0;k<g->vexnum;k++)path[j][l][k]=path[j][i][k]+path[i][l][k];//从j到l的路径等于从v到i的路径加从i到l 的路径}while(flag==1) //标记量，无实际意义{printf("请输入出发地和目的地:");scanf("%d %d",&k,&j);if(k>=0&&k<g->vexnum&&j>=0&&j<g->vexnum) flag=0;}printf("%s",g->vertex[k].name);for(l=0;l<g->vexnum;l++)if(path[k][j][l]&&k!=l&&j!=l)printf(">>>>>%s",g->vertex[l].name);printf(">>>>>%s",g->vertex[j].name);printf(" 总路线长%d米\n",dist[k][j]);}五．测试数据及运行结果1．正常测试数据和运行结果最短路径全部路径中转最少路径六．调试情况，设计技巧及体会1．改进方案整个代码只是完成了基本的要求，并没用完成扩充的问题，对于文件没用完成，以及添加删除路径也没有进行编写，而且在查找方式中，只是进行了编号查询。

实验报告：导游图姓名：石栋伟班级：计师一班学号：222013321081006一、需求分析：1.从全国选取各个省份的省份城市作为旅游景点，抽象成为一个无向带权图。

以途中的顶点作为旅游景点，边上的权值表示两地之间的距离。

同时，本程序还可以为用户提供旅游景点的信息。

2.本程序的目的是为用户提供路径咨询。

根据用户指定的起点和终点输出相应的路径已经之间的距离。

3.为用户提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。

当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。

4.测试数据（附后）二、概要设计：1.抽象数据类型图的定义如下：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径}基本操作P：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中边的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph(&G)初始条件：图G存在。

操作结果：销毁图G。

LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。

GetVex(G,v)初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的信息。

FirstEdge(G,v)初始条件：图G存在，v是G中某个顶点。

操作结果：返回依附于v的第一条边。

若该顶点在G中没有邻接点，则返回“空”。

NextEdge(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：返回依附于v的（相对于w的）下一条边。

若不存在，则返回“空”。

InsertVex7(&G,v) 初始条件：图G存在，v和图中顶点有相同特征。

操作结果：在图中增添新顶点v。

数据结构实验报告——实验六简单校园导游程序的设计与实现本实验的目的是通过对校园导游程序的设计与实现来熟练掌握图型结构在实际问题中的应用。

一、【问题描述】当人们到一个陌生的地方去旅游的时候可能会找一个导游为自己在游玩的过程中提供方便。

导游可以提供很多服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，以及解答旅游者所提出的关于旅游经典的相关问询等等。

对于新生刚刚来到校园，对校园环境不熟悉的情况也如此，一般都是高年级的学生充当了“校园导游员”的角色，如果能够提供一个程序让新生或来访的客人自主的通过与机器的“对话”来获得相关的信息的话，将会节省大量的人力和时间。

而且所提供的信息也能够做到尽可能的准确、详尽。

一个成功的校园导游程序可以替代现实生活中这些“校园导游员”，更方便了大家查询校园相关的信息。

本次实验需要开发一个简单的校园导游程序，程序的主体功能为：1、显示校园平面图，方便用户直观的看到校园的全景示意图，并确定自己的位置。

2、为用户提供对平面图中任意场所的相关信息的查询。

3、为用户提供对平面图中任意场所的问路查询。

二、【数据结构设计】由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。

以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含道路的代号、路径的长度等信息。

顶点和边均使用结构体定义，整个图的数据结构可以采用教材中介绍的各种表示方法，例如带权的邻接矩阵。

三、【功能（函数）设计】1、显示校园平面图的功能模块。

通过读文件的方式将各个地点的信息读入程序中.平面图中应醒目的标识出场所的准确名称以备用户查询。

河北大学校园导游的基本地点信息。

***************欢迎进入河北大学校园导游系统!************** -----------------------景点名称---------------------------主楼多功能馆毓秀园图书馆操场留学生楼七教八教九教成教南大门北大门一教逸夫楼博物馆物理楼电信楼化学楼生科楼建工楼北院食堂南院食堂竹园梅园桂园菊园易百超市北院生活园区---------------------------------------------------------- 地点的存储typedef struct Vertex//顶点结构体{int No;//地点编号char name[20];//地点名称char info[1000];//地点简介}Vertex;typedef struct //无向图结构体{Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵int vnum,anum;//顶点和边的个数}Graph;2、查询任意场所的相关信息查询的功能模块。

栅格地图
将校园地图划分为若干个栅格，每个 栅格表示一定的地理范围，可以快速 进行地图的渲染和展示。
04
实现校园导游系统
系统架构设计
架构概述
本系统采用客户端-服务器架构， 分为前端和后端两部分。前端负 责展示校园地图和导航信息，后 端负责处理用户请求、路径搜索
和地图数据存储。
前后端交互
前后端通过API进行数据交换， 前端发送用户请求（起点和终 点），后端返回路径信息和导航
提示。
数据存储
使用关系型数据库存储校园地图 数据、路径信息和用户信息。
路径搜索算法实现
算法选择
采用Dijkstra算法实现路径搜索，该算法能够在加权图中找到从起点到终点的最短路径。
算法流程
初始化距离数组，将起点到各节点的距离设为0，其他节点距离设为无穷大；遍历未访问节点， 找到距离最小的节点，更新其相邻节点的距离；重复上述步骤直到所有节点都被访问。
图的应用
通过构建图的数据结构，可以方便地实现校园导航、路径查询、最短路径计算 等功能，提高校园内人员流动的效率和便利性。
实验目的
1 2
掌握图的基本概念和数据结构
通过实验，学生将深入了解图的基本概念、表示 方法和相关数据结构，如邻接矩阵和邻接表。
实现校园导航系统
学生将利用所学知识，构建一个校园导航系统， 实现地点查询、路径规划和最短路径计算等功能。
错误处理
测试了系统在异常情况下的表现，如输入错误、网络中断等，并优 化了错误处理机制。
性能评估
响应时间
评估了系统在不同负载下的响应时间，确保系统 能够快速响应用户操作。
稳定性
测试了系统在高负载下的稳定性，确保系统在高 并发情况下不会崩溃。

课程论文（设计）2011-2012 学年第2学期课程名称：数据结构课程设计课程性质：实践课专业班级：考核方式：考查学生：学号：学时：1周教师：目录1. 作业容 (1)2. 基本思路 (1)2.1 本校10个景点 (1)2.2 图的初始化 (2)2.3 图的遍历 (2)2.4 求最短路径 (3)3.系统流程 (4)3.1 系统的简单说明 (4)3.2 系统流程图 (5)4. 系统运行效果图 (5)4.1 校园导游界面 (5)4.2 华农校园地图 (6)4.3 景点的相关信息查询 (6)4.4 任意两个景点间的最短路径 (7)4.5 退出校园导游系统 (8)5.总结 (9)6.参考文献 (10)1. 作业容设计一个校园导游程序，为来访客人提供各种信息查询任务。

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

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

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

2. 基本思路要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。

有以下设计思路：（1）.结合本校的实际情况，选出10个景点；（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；（3）.根据选出来的10个景点用邻接矩阵存储校园图。

（4）.依照景点的相关信息创建校园图。

（5）.把纸质上的容，利用C++编程语言编写查找景点相关信息的程序。

（6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。

（7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。

为此，可把系统分为以下几个核心：图的初始化、图的遍历、求最佳路线。

齐齐哈尔大学计控学院数据结构课程设计选题名称:校园导游图系（院）:计算机与控制工程学院专业:软件工程班级:软件121班姓名:刘泽强学号:2012023019指导教师:吴迪2014年7月1日数据结构课程设计评分表90～100为优，80～89为良，70～79为中，60～69为及格，60分以下不及格目录一、问题描述 (4)二、程序设计 (5)三、运行结果： (8)四、总结 (11)附录： (12)一.问题描述设计你所在的学校的校园平面图，所含景点不少于10个。

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

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

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

二、程序设计1．用数据结构知识创建校园图。

void creatgraph(vexnode g[],int *n, EdgeType e[],adjmax *adj) //创建校园图{int b,i,s,d,len;struct edgenode *p,*q; //定义图的结构体2．手动给校园图赋上相关信息（景点名称、代号、简介），路径及路径长度。

得到一个模拟的校园图：图2.23．利用C语言知识编写查找景点相关信息的程序。

手动创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上真正的值。

主要代码：do{printf("是否继续? Y/N");scanf("%c",&ch);getchar();if(ch == 'Y' || ch == 'y') //继续{flag = 1;i = 1;printf("请输入您要查询的景点序号:\n");scanf("%d",&len);getchar();printf("此景点的名称是:");Name(len);printf("此景点的介绍是:");Information(len);4．利用迪杰斯特拉算法计算任意两点之间的最短路径。

图 4.3.1 景点 2 红满堂信息查询
图 4.3.2 景点 7 竹园信息查询 4.4 任意两个景点间地最短路径
根据用户地需求 , 在用户输入了起点和终点后计算出最短路径是哪一条路径 . 以下举两个例子 . 第一个例子地起点是 5 东区运动场 , 终点是 1 校史馆 . 第二个例 子地起点是 2 红满堂 , 终点是 10 黑山运动场 . 运行结果如图 4.4.1 和图 4.4.2 所 示 . 83lcPA59W9
图 4.1 校园导游节目图 4.2 华农校园地图
校园地图地查看是通过抽象化 10 个景点来用 printf( > 输入选择 1 之后弹出地界面 , 运行结果如图 4.2. HbmVN777sL
函数输出地图 , 在
图 4.2 抽象化地华南农业大学校园导游地图 4.3 景点地相关信息查询
景点地相关信息查询是通过 information( > 函数来调用输出地 , 在主菜单 那输入 2 之后 , 拿第 2 个景点红满堂和第 7 个景点竹园来当例子 , 第运行结果如 图 4.3.1 和图 4.3.2. V7l4jRB8Hs
2.2 输出 dist[j] 和 path[j] ；
2.3 修改数组 dist 和 path 。
2.4 将顶点 vk 添加到数组 s 中；
3. 系统流程
3.1 系统地简单说明 1. 创建校园图： <1）先手工画好华农地 10 个景点地草图 , 再用 C++语言输出抽象化地校园
地图 . <2）再用 C++语言定义节点个数 N,编写函数 name( >为景点赋值各类信息
为空串 . 1nowfTG4KI
数组 s[n] ：存放源点和已经生成地终点 <即集合 S）, 初态为只有一个源点 v.