数据结构校园导游咨询系统课程设计报告及课程总结.

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

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

数据结构试验报告校园导游《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题⽬：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：⼤⼆；学号：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>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。

西安郵電大學数据结构课程设计报告书崔斌专业名称 计算机科学与技术专业计科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()的''后面不加第一个空格也可以。

软件学院学生实验报告册实验课程名称：数据结构与算法实验项目名称：校园导游咨询实验类型（打√）：（基础、综合、设计√）院系：信息工程学院计算机系专业：*****姓名：*** 学号：*****指导老师：***软件学院教务处编制一、实验预习报告内容二、实验原始（数据）记录实验时间：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');}。

一、设计目的与内容1．设计目的设计一个校园导游程序，为来访的客人提供各种信息查询服务。

2．设计内容1> 设计学校的校园平面图，所含13个景点，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

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

3> 为来访客人提供景点的问路查询，即已知一个某紫薇.ylbqhm.景点，查询到某景点之间的一条最短路径及长度。

4> 退出导游程序。

二、算法的基本思想1．使用菜单页，选择不同的功能（景点信息查询、求最短路径、最短路径距离、退出程序等），进行相应的操作；2．采用数组作为数据的存储结构，存储检索出的路径、最短距离等；3．利用short函数运算，求两地间的距离，并输出其路径；4．主程序有掌控函数调用，选择功能模块执行，在程序运行工程中可以反复操作。

算法的思路是三、需求分析1．本系统是把校园平面图抽象成一个无向网，取校园中 13 个代表性景点作为图的顶点，存放顶点名称、代号、简介等有关信息、并以边表示路径，两景点间的距离作为边的权值。

以二维数组的数据结构存储构建无向图，cost[i][j];当i=j及i点与j点无直接连通时，其值为无穷大，定义一个很大的整数Init_Length代替无穷大。

当i与j点连接时，其值为两点间的权值即两点间距离。

2．本程序的目的是为用户提供路径咨询和景点查询。

根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。

1> 查询景点信息将相应景点信息存入函数print中，依据需要调用读取该函数，并显示在屏幕上。

2> 两点间最短路径利用shortestdistance函数逐级循环，查训两景点间所有路径距离，将最短路径距离存入D[v]中；并将所查得的景点存储在二维数组path[i][j]中；执行输出命令输出最短路径及距离。

3> 执行exit（0）；函数跳入退出界面执行退出操作。

西安邮电大学（计算机学院）数据结构课程设计报告题目：校园导游系统专业名称：班级：学生姓名：学号（8位）：指导教师：设计起止时间:一. 设计目的1.数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发2.通过课程设计，使学生通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。

3.学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。

二. 设计内容1.完成校园导游咨询系统。

2.校园平面图（景点、路径等信息）3.利用深度优先和广度优先搜索搜索所有景点4.查询图中任意景点的相关信息5.问路信息（查询任意两个景点之间的一条最短的简单路径，任意两景点之间的所有路径）校园图的关节点、多个景点的最佳访问路线6.校园导游图的界面仿真。

7.添加删除道路信息。

三．概要设计1．功能模块图；选择显示标识信息2．各个模块详细的功能描述。

1.登录模块进入后可添加删除道路信息。

2.路线选择模块选择路线，在右侧窗口显示最短路径3.其他查询景点信息，查看深度优先遍历查看广度优先遍历四．详细设计*重点设计及编码//结点function Node(vexdata){this.vexdata=vexdata;this.node=[];this.weight=[];}//类定义function AdjList(vexnum,arr){this.vexnum=vexnum;this.arcnum=0;this.vertex=[];=[];//名称r=[];//信息this.flag=[];//标记this.arr=[];//存储路径this.ar=[];//存储路径2for(var i=0;i<this.vexnum;i++){this.vertex[i]=new Node(arr[i]);this.flag.push(0);}//增加结点this.addarc=addarc;//增加边this.addvex=addvex;//深度优先搜索this.dfs=dfs;this.edfs=edfs;//广度优先搜索this.guangdu=guangdu;this.guang=guang;//输出存储结构this.printf=printf;//求最短路径this.getpath=getpath;//输出景点信息函数this.printinfor=printinfor;}function addarc(a1,a2,weight){this.vertex[a1].node.push(a2);this.vertex[a1].weight.push(weight);this.vertex[a2].node.push(a1);this.vertex[a2].weight.push(weight);this.arcnum++;}function addvex(v){var temp=new Node(v);this.vertex.push(temp);this.vexnum++;}function edfs(flag,v,g,arr){arr.push(v);flag[v]=1;for(var i=0;i<g.vertex[v].node.length;i++){if(1!=flag[g.vertex[v].node[i]]){edfs(flag,g.vertex[v].node[i],g,arr);}}}function dfs(){var temp=parseInt(document.getElementById('last').value);this.arr=[];for(var i=0;i<this.vexnum;i++)this.flag[i]=0;edfs(this.flag,temp,this,this.arr);for(var i=0;i<this.vexnum;i++){if(this.flag[i]!=1) edfs(this.flag,i,this,this.arr);}var showpath="<b>深度遍历路线：</b>";for(var i=0;i<this.arr.length;i++){showpath+="->";showpath+=[this.arr[i]];}document.getElementById('footer').innerHTML=showpath; }function guangdu(temp,g){var v,k,w=temp;var que=[];que.push(w);g.flag[w]=1;while(que.length!=0){w=que[0];g.ar.push(que[0]);que.splice(0,1);k=0;v=parseInt(g.vertex[w].node[k++])while(k<g.vertex[w].node.length){if(g.flag[v]!=1){g.flag[v]=1;que.push(v);}v=parseInt(g.vertex[w].node[k++]);}}}function guang(){var temp=parseInt(document.getElementById('last').value);this.ar=[];for(var i=0;i<this.vexnum;i++)this.flag[i]=0;guangdu(temp,this);for(var i=0;i<this.vexnum;i++)if(this.flag[i]!=1)guangdu(i,this);var showpath="<b>广度遍历路线：</b>";for(var i=0;i<this.ar.length;i++){showpath+="->";showpath+=[this.ar[i]];}document.getElementById('footer').innerHTML=showpath; }function printf(){for(var i=0;i<this.vexnum;i++){document.write('<br>'+this.vertex[i].vexdata+" :");for(var j=0;j<this.vertex[i].node.length;j++)document.write('->'+this.vertex[i].node[j]+":"+this.vertex[i].weight[j]);}}function getpath(/*start,end*/){var start=parseInt(document.getElementById('first').value);var end=parseInt(document.getElementById('last').value);var mindist;var k;var a=[];var path=new Array(this.vexnum);//初始化for(var i=0;i<this.vexnum;i++){document.getElementById('b'+i).style.color='#000';}for(var i=0;i<this.vexnum;i++){path[i]=[];}for(var i=0;i<this.vexnum;i++){a[i]=10000;path[i][0]=0;}path[start][0]=1;for(var i=0;i<this.vertex[start].node.length;i++){a[this.vertex[start].node[i]]=this.vertex[start].weight[i];path[this.vertex[start].node[i]].push(start);}//找各条最短路径for(var i=1;i<this.vexnum;i++){mindist=10000;//找最小权值路径for(var j=0;j<this.vexnum;j++){if(!path[j][0]&&a[j]<mindist){k=j;mindist=a[j];}}if(10000==mindist) return;path[k][0]=1;//改变记录for(var j=0;j<this.vertex[k].node.length;j++){if(!path[this.vertex[k].node[j]][0]&&a[this.vertex[k].node[j]]>a[k]+this.vertex[k].weight[j]){a[this.vertex[k].node[j]]=a[k]+this.vertex[k].weight[j];path[this.vertex[k].node[j]]=[0];for(var t=1;t<path[k].length;t++){path[this.vertex[k].node[j]].push(path[k][t]);}path[this.vertex[k].node[j]].push(k);}}}//返回最短路径var showpath="路线：";for(var i=1;i<path[end].length;i++){document.getElementById('b'+path[end][i]).style.color='#fff';showpath+=[path[end][i]];showpath+="->";}document.getElementById('b'+end).style.color='#fff';showpath+="<b>"+[end]+"</b>";document.getElementById('path').innerHTML=showpath;}function printinfor(){var last=document.getElementById('last').value;document.getElementById('footer').innerHTML=r[parseInt(last)]; }五．测试数据及运行结果六．调试情况，设计技巧及体会每当写完一个函数的时候，都会出现很多错误，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。

琼州学院电子信息工程学院课程设计报告课程名称：《数据结构》课程设计设计题目：校园导游咨询专业：软件工程班级：2010软件工程学生姓名：学号：起止日期：指导教师：注意事项一、设计目的《数据结构》是一门实践性较强的软件基础课，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、设计要求1．通过这次课程设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

2．学生必须仔细研读《数据结构》课程设计要求，以学生自学为主、指导教师指导为辅，独立完成课程设计的任务，有问题及时主动与指导教师沟通。

3．本次课程设计按照教学要求需要在本学期15周前完成，学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向指导教师汇报。

4．编程语言：C 语言。

三、课程设计说明书的格式要求设计文档的撰写必须提前进行，以保证使文档与程序同步提交。

1．设计题目2．运行环境（软、硬件环境）3．算法的需求分析4．算法概要设计5．算法详细设计6．算法的测试7．运行结果分析8．收获及体会四、问题分析、设计和测试过程要规范化1．需求分析：将题目中要求的功能进行叙述分析。

2．概要设计：算法的设计说明，描述解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。

3．详细设计：即各个算法的具体实现步骤，每个题目要有相应的源程序，其中每个功能模块采用不同的函数实现。

源程序要规范编写：结构要清晰，注释要清楚。

目录1、需求分析2、总体设计2.1 抽象数据类型图的定义 .................................................................................2.2 程序中包含的模块 .........................................................................................2.3模块间的调用关系 ..........................................................................................3、详细设计3.1 代码设计 .........................................................................................................3.1.1 定义结构体和全局变量 ....................................................................3.1.2 平面图的初始化 ................................................................................3.1.3 最短路径查询 ....................................................................................3.1.4 景点信息查询 ....................................................................................3.1.5景点信息更新 .....................................................................................3.2 界面分析 .........................................................................................................3.2.1 主程序界面 ........................................................................................3.2.2 景点信息的查询 ................................................................................3.2.3 最短路径查询 ....................................................................................3.2.4 管理校园查询系统 ............................................................................4、总结报告参考文献1、需求分析设计一个校园导游系统程序，为来访的客人提供各种服务的信息查询。

姓名：班级：学号：指导教师：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．改进方案整个代码只是完成了基本的要求，并没用完成扩充的问题，对于文件没用完成，以及添加删除路径也没有进行编写，而且在查找方式中，只是进行了编号查询。

图1
当输入1时进入一个选择子菜单（输入错误时，保持原有状态），正确输入
图2
图3
按100推出此环节，当在选择主菜单选择2时，出现如下图4所示子菜单：
图4
当输入1时，则按景点编号查询，当输入6（地球科学博物馆）时，屏幕上打印出此景点信息：里面有著名的不寻常恐龙化石；当输入4（实验楼）时，屏
图5
当输入2时，则按景点名称查询，当输入“图书馆”时，屏幕上打印出此景点信息：图书馆是莘莘学子学习的园地，里面有各科资料，每人可以任借五本书；当输入“计算机实验室”时，屏幕上打印出此景点信息：计算机专业实验实习场所；当输入“教学三号楼”时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！；如下图6所示：
图6
图7
在选择主菜单输入错误时，程序不作反应，当输入e时，则退出，如下图8所示
图8。

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 选题名称： 姓 名： 专业班级： 系 （院）： 设计时间： 设计地点：数据结构课程设计校园导游学 号：软件工程软件 091计算机工程学院2010.12.20~2010.12.31 软件工程实验室、教室指导教师评语：成绩：签名：年月日数据结构课程设计报告第 1 页，共 页1．课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求 解指定问题。

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平， 并在此过程中培养他们严谨的科学态度和良好的工作作风。

2．课程设计任务与要求：任务 根据教材《数据结构-C 语言描述》（耿国华主编）和参考书《数据结构题集（C 语言版）》（严蔚敏、 吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应 用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。

设计题目从任务书所列选题表中选取，每班每题不得超过 2 人。

学生自选课题 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够 巩固数据结构课程所学的知识。

学生自选课题需在 18 周前报课程设计指导教师批准方可生效。

要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实 现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。

前期准备工 作完备与否直接影响到后序上机调试工作的效率。

在程序设计阶段应尽量利用已有的标准函数，加大代码 的重用率。

2、.设计的题目要求达到一定工作量（300 行以上代码），并具有一定的深度和难度。

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

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

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

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

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

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

本次实验需要开发一个简单的校园导游程序，程序的主体功能为：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、查询任意场所的相关信息查询的功能模块。

课程设计说明书课程名称数据结构课程设计设计课题校园导游程序专业计算机科学与技术班级学号姓名完成日期课程设计任务书设计题目：校园导游程序设计容与要求：[问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

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

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

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

（4）增加、删除、更新有关景点和道路的信息。

指导教师：2016年12月20日课程设计评语成绩：指导教师：_______________年月日目录一、问题描述1二、基本要求1三、测试数据2四、算法思想3五、模块划分45.1应用函数45.2.1主函数65.2.2查询景点信息函数75.2.3查询两景点之间最短路径函数85.2.4查询两景点之间所有路径函数85.2.6删除已有的顶点和路径95.2.7修改已有的顶点和路径11六、数据结构13七、测试14八、心得26九、源程序28一、问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

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

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

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

（4）增加、删除、更新有关景点和道路的信息。

三、测试数据菜单函数：依次输入：1，2，3，4，5，6，0分别对应景点信息查询，最短路径查询，所有路径查询，添加景点及路径信息，删除景点及路径信息，修改景点及路径信息，退出。

查询景点信息：输入：1，2分别对应按编号查询，按景点名称查询按编号查询：输入编号：1按景点名称查询：输入名称：大明桥最短路径查询：输入起始景点和终点景点编号：1，7所有路径查询：输入起始景点和终点景点编号：2，8添加景点及路径信息：输入新景点序号：9输入新景点名称：南门输入新景点相关信息：充满古韵的门，适合拍照输入到其余各景点的距离：50，100，20…删除景点及路径信息：输入：1，2分别对应按编号查询，按景点名称查询按编号查询：输入需要删除的景点编号：8修改景点及路径信息：输入：1，2分别对应修改景点信息，修改道路信息修改景点信息：输入1，2分别对应修改景点名称，修改景点描述修改景点信息：输入修改序号：1输入修改后的名称：图书馆123四、算法思想先利用CreateUDN 创建初始无向网，通过main主函数调用显示，操作功能的选择通过Menu函数输出，根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信息。

姓名：班级：学号：指导教师：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、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。

南京航空航天大学《数据结构》课程设计报告校园导游系统目录一、需求分析 (2)二、程序的主要功能 (2)三、程序运行平台 (2)四、数据结构 (2)五、算法设计思想及时间复杂度 (2)六、测试用例及结果 (5)七、存在的不足与对策及编程体会 (6)八、程序源代码 (6)一、需求分析南航学生家长及入学新生很需要一个导游程序，来引领他们参观和了解南航。

二、程序的主要功能1、查询各景点的相关信息2、查询任意两景点间的所有路径3、查询任意两景点间的最短路径 1、增加景点4、推荐参观路线 2、删除景点5、更新导游信息（操作需管理员密码） 3、更新道路信息6、对景点联通性的浏览（2阶矩阵表示）4、更新景点信息7、学校全景一览 5、修改管理员密码三、程序运行平台Microsoft Visual C++ 6.0四、数据结构图的邻接矩阵存储表示，栈的顺序存储表示五、算法设计思想及时间复杂度主要函数介绍：1、求两点间的所有路径：a)相关函数：void dfs(MGraph G,SqStack path,int *used,int u,int w);//深度优先遍历b)主要算法思想：栈的相关操作+深度优先搜索创建一个空栈保存路径，一个空数组保存已标记节点，首先让起点进栈，并标记为已访问，然后调用深度优先搜索，如果该顶点的相邻顶点（即与其有直接通路的顶点）未被访问过就标记为已访问，进栈，然后对它调用深度优先搜索，依次类推，直到获得所有到指定终点的路径。

c)时间复杂度：O（VE），其中V为图的顶点数目，E为图中边的数目。

2、求两点间的最短路径：a)相关函数：void ShortestPath(MGraph G,int v0,int P[][Nmax],int *D);//查询任意两景点间的最短路径void PrintShortest(MGraph G,int v1,int v2,int P[][Nmax],int *D); //输出最短路径b)主要算法思想：迪杰斯特拉算法假设起点为v0，S为已找到的从v0出发的最短路径的终点的集合，其初始状态为空集。

《数据结构与算法》课程设计说明书题目：桂电尧山导游系统学院：计算机科学与工程学院专业：信息安全姓名：学号：指导教师：2014年10月8日成绩评定标准及成绩1、能按照格式进行写作，无抄袭现象（10分）2、报告内容行文通畅，有条理性，无错别字，结构严谨。

（10分）3、能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。

（10分）4、在验收过程中，能合理的回答问题（20分）5、软件能正常运行，实现所提出的功能（40分）6、软件代码规范性较好（5分）7、具有自己的创新或特色（5分）总成绩：随着计算机科学的迅速发展，计算机已深入到人类社会的各个领域，它的应用已不再局限于科学计算，以解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说校园导游系统，学生成绩管理，进销存促系统等实际问题。

如今程序设计的语言很多，有发展比较完善高级语言，也有最基本的低级语言，然而再好的程序设计也要有一个比较清晰的思路——算法。

为了编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。

数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门必修课。

本系统基于图的结构，创建一个无向图，针对用户的实际需求，实现了各个景点的查询、修改以及两个景点间的最短路径和景点的扩充。

本系统侧重于软件工程规范的的分析、设计及测试，采用了结构化程序设计思想，通过功能模块分级实现系统功能。

关键词：数据结构；图；最短路径；校园导游系统1 前言 (5)2 系统分析 (5)2.1设计目的 (5)2.2 需求分析 (5)2.3设计内容 (6)2.4 概要设计 (7)2.5详细设计 (7)2.5.1主函数的设计 (7)2.5.2查找函数的设计 (7)2.5.4修改函数的设计 (11)2.5.5增加函数的设计 (11)3 功能分析 (11)6 开发环境 (16)7 总结 (16)参考文献 (18)1 前言随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。

姓名：班级：学号：指导教师：2012年12月目录1、需求分析.................................................. 错误!未定义书签。

系统简介................................................ 错误!未定义书签。

系统功能模块介绍........................................ 错误!未定义书签。

2、概要设计.................................................. 错误!未定义书签。

系统功能结构图.......................................... 错误!未定义书签。

系统流程图.............................................. 错误!未定义书签。

主要函数概要设计........................................ 错误!未定义书签。

主函数概要设计...................................... 错误!未定义书签。

初始化图函数InitGraph() ............................ 错误!未定义书签。

查询景点信息函数设计SearchGraph() .................. 错误!未定义书签。

显示图中信息函数设计ShowGraph() .................... 错误!未定义书签。

弗洛伊德算法函数设计Floyd() ........................ 错误!未定义书签。

3、详细设计.................................................. 错误!未定义书签。

主函数详细设计.......................................... 错误!未定义书签。