数据结构报告 校园导航问题

数据结构试验报告校园导游《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题⽬：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：⼤⼆；学号：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”，调⽤最短距离和路径函数。

数据结构与算法分析课程设计报告设计题目：校园导航咨询系统专业学号姓名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.进入主界面，出现校园导航咨询系统主菜单。

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

【基本要求】(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>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。

数据结构课程设计报告题目：校园导航系统学生姓名：谌幼华学号： 09110806班级：091108指导教师：邹国华2011 年6 月3 日目录一、需求分析说明 (3)二、总体设计 (3)三、详细设计 (5)四、实现部分 (8)五、程序测试 (13)六、总结 (15)七、参考文献 (15)校园导航系统一、需求分析说明：（一）课程设计目的：本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

（二）设计要求：设计一个校园导航系统，为来访的客人提供导航服务，具体要求：1. 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

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

3. 提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意景点到其他所有景点的最短路径查询。

4.列出所有校内无重复排列的景点，将所有景点的距离以邻接矩阵的方式呈现给使用者，提供使用者选择功能界面，按照提示进行操作。

5.在邻接矩阵中MAX表示最大距离即两个景点之间是不可到达的。

用实际权值来表示两个景点之间的距离，并且是可达的。

二、总体设计：1.数据结构：用图（无向网）来描述学校n个景点之间的关系，顶点为单位代号，权值为两景点的距离。

本系统基于东华理工大学校园平面图为基准而设计，先将校园内15个具有代表性的顶点列出，然后绘制出其平面图，标出任意两顶点间是否有直达的边，同时在图上有直达边的两顶点边的权值，本系统中设计的东华理工大学校园平面图如下（景点前面所对应的代号为系统中无向网的顶点号）：东华理工大学学校平面图2.系统功能图：三、详细设计：一、按所设想的功能，把程序化分为7个模块，各模块的名称和其数据类型如下表所示：各模块的说明如下：1.类模块：本系统中只涉及了一个Graph（无向网类）类，其数据成员为无向网的相关信息，例如图的邻接矩阵(程序中用数组arcs[n+1][n+1]存放有关邻接矩阵的相关信息)、原点到各定点的相关信息（存放在dist[n+1数组中]）、最短路径上该顶点的前一顶点相关信息（存放在path[n+1]数组中）、以求得到的最短路径上的顶点的顶点号（存放在s[n+1]数组中），同时将求最小路径的实现函shortest_path（）定义为其成员函数。

《校园导航系统》课程设计报告姓名：蒋小文学号：110236100123 班级：1班专业：网络工程指导教师：唐轶媛蒋荣萍时间：2012年7月5日信息科学与工程学院目录摘要 (1)1.目的 (2)2.要求 (2)3.题目 (2)4.任务 (2)1).需求分析 (3)2).概要设计 (4)3).详细设计 (5)4).调试分析 (8)5.课设总结 (18)6.附录源代码 (19)1.目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。

课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C （C++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。

2.要求2.1 课程设计时间为2周；2.2 设计语言C（C++）不限；2.3 课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。

上机时带上源程序、数据结构教材、C语言教材。

2.4 上机任务（1）选择并定义合适的数据结构；（2）根据程序所要完成的基本要求，设计出完整的算法；（3）设计出主程序（main函数），使其成为完整的程序。

2.5 上机时间：上午8:30--11:30，下午3:00--5:303.题目题目：校园导航系统设计一个校园导游程序，后台操作：3.1、操作员信息管理如修改密码等3.2、能根据学校的规模进行添加景点信息、修改景点信息等功能，3.3、若临时有交通管制，能进行交通管制的设置和撤销（如某某时间段那条路进行那个方向的交通管制等）3.4、前台为来访的客人提供各种信息查询服务：3.4.1、设计学校的校园平面图，所含景点不少于10个。

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

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

3.4.3、提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。

课程设计报告学院、系：大学学院计算机科学与技术系专业：软件工程班级：2008级9班课程设计科目数据结构学生：04080904 喆指导教师：娄雅芳完成时间：2010年10月-12月校园导航系统设计报告一、设计任务与目标设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

本系统是一个涉及大学学院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。

本系统为用户提供以下功能:(一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。

(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。

校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。

(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。

(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。

(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。

二、方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。

用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。

所以首先应创建图的存储结构。

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

结点值及边的权值采用图存储。

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

计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。

最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。

课程设计（数据结构）院、系计算机与软件学院专业网络工程姓名顾容宇徐鹏学号20091346087、20091346088 指导教师郑玉二Ｏ一Ｏ年十二月二十五日校园导航问题王耀南京信息工程大学计算机与软件学院，南京 210044摘要：程序设计目的是用哈斯图方式计算两个旅游点的最短距离以及路线。

编程所实现的功能除了可以查询两个旅游点的最短距离以及最短的路线，还可以看到旅游点的介绍，以及逛遍所有旅游点所能组成的所有路线可能，实现全面查询。

关键字：景点；路线；距离；校园导航1．课程设计题目设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

2．分析2．1设计基础：要掌握最短路径的实现方式。

2．2分析设计课题的要求，要求编程实现以下功能：（1）查询景点路径（2）查询景点信息（3）查看参观路线（4）查询各景点之间的距离2．3主控菜单设计为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

程序运行后，给出菜单项的内容和输入提示，如下：1．学校简介2．查询景点路径3. 查询景点信息4. 查看参观路线5. 查询各景点之间的距离6. 退出2．4设计课题已明确要求，有关的定义如下：typedefstructArcCell{intadj; // 相邻接的景点之间的路程char *info;}ArcCell; // 定义边的类型typedefstructVertexType{int number; // 景点编号char *sight; // 景点名称char *description; // 景点描述}VertexType; // 定义顶点的类型typedefstruct{VertexType vex[NUM]; // 图中的顶点，即为景点ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离intvexnum,arcnum; // 顶点数，边数}MGraph; // 定义图的类型3．步骤3.1函数调用图函数调用关系3.2主代码#include<iostream >#include <string.h>#include <stdio.h>#include <stdlib.h>#define Max 32767#define NUM 11typedef struct ArcCell{int adj; // 相邻接的景点之间的路程char *info;}ArcCell; // 定义边的类型typedef struct VertexType{int number; // 景点编号char *sight; // 景点名称char *description; // 景点描述}VertexType; // 定义顶点的类型typedef struct{VertexType vex[NUM]; // 图中的顶点，即为景点ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离int vexnum,arcnum; // 顶点数，边数}MGraph; // 定义图的类型MGraph G; // 把图定义为全局变量int P[NUM][NUM]; // //long int D[NUM]; // 辅助变量存储最短路径长度int x[13]={0};void CreateUDN(int v,int a); // 创建图的函数void pingmu(); //屏幕输出函数void introduce();void ShortestPath(int num); //最短路径函数void output(int sight1,int sight2); //输出函数void PrintMGraph();char Menu(); // 主菜单void search();;// 查询景点信息char SearchMenu(); // 查询子菜单void HaMiTonian(int); // 哈密尔顿图的遍历void NextValue(int);void display(); // 显示遍历结果void main() // 主函数{ int v0,v1;char ck;system("color 0");CreateUDN(NUM,11);do{ck=Menu();switch(ck){case'1':introduce();printf("\n\n\t\t\t%-25s\n\n",G.vex[0].description); getchar();getchar();break;case '2':system("cls");pingmu();printf("\n\n\t\t\t请选择起点景点（1～10）："); scanf("%d",&v0);printf("\t\t\t请选择终点景点（1～10）：");scanf("%d",&v1);ShortestPath(v0); // 计算两个景点之间的最短路径output(v0,v1); // 输出结果printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;case '3':search();break;case '4':system("cls");pingmu();x[0]=1;HaMiTonian(1);printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;case'5':PrintMGraph();printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;};}while(ck!='e');}char Menu() // 主菜单 //{char c;int flag;do{flag=1;system("cls");pingmu();introduce();printf("\n\t\t\n");printf("\t\t \n");printf("\t\t 1.学校简介 \n");printf("\t\t 2.查询景点路径 \n");printf("\t\t 3.查询景点信息 \n");printf("\t\t 4.查看参观路线 \n");printf("\t\t 5.查询各景点之间的距离 \n");printf("\t\t e.退出 \n");printf("\t\t \n");printf("\t\t\n");printf("\t\t\t\t请输入您的选择：");scanf("%c",&c);if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e') flag=0;}while(flag);return c;}char SearchMenu() // 查询子菜单{char c;int flag;do{flag=1;system("cls");pingmu();introduce();printf("\n\t\t\n");printf("\t\t \n");printf("\t\t 1、按照景点编号查询 \n");printf("\t\t 2、按照景点名称查询 \n");printf("\t\t e、返回 \n");printf("\t\t \n");printf("\t\t \n");printf("\t\t\t请输入您的选择：");scanf("%c",&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);return c;}void search() // 查询景点信息{int num;int i;char c;char name[20];do{system("cls");c=SearchMenu();switch (c){case '1':system("cls");introduce();pingmu();printf("\n\n\t\t请输入您要查找的景点编号："); scanf("%d",&num);for(i=0;i<NUM;i++){if(num==G.vex[i].number){printf("\n\n\t\t\t您要查找景点信息如下:");printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); printf("\n\t\t\t按任回车返回...");getchar();break;}}if(i==NUM){printf("\n\n\t\t\t没有找到！");printf("\n\n\t\t\t按回车键返回...");getchar();getchar();}break;case '2':system("cls");pingmu();introduce();printf("\n\n\t\t请输入您要查找的景点名称："); scanf("%s",name);for(i=1;i<NUM;i++){if(!strcmp(name,G.vex[i].sight)){printf("\n\n\t\t\t您要查找景点信息如下:");printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); printf("\n\t\t\t按回车键返回...");getchar();getchar();break;}}if(i==NUM){printf("\n\n\t\t\t没有找到！");printf("\n\n\t\t\t按回车键返回...");getchar();}break;}}while(c!='e');}void CreateUDN(int v,int a) // 创建图的函数{int i,j;G.vexnum=v; // 初始化结构中的景点数和边数G.arcnum=a;for(i=1;i<G.vexnum;++i) G.vex[i].number=i; // 初始化每一个景点的编号// 初始化没一个景点名及其景点描述G.vex[0].sight="学校简介";G.vex[1].sight="东大门";G.vex[2].sight="培训楼";G.vex[3].sight="气象楼";G.vex[4].sight="文德楼";G.vex[5].sight="明德楼";G.vex[6].sight="尚贤楼";G.vex[7].sight="电影院";G.vex[8].sight="北辰楼";G.vex[9].sight="图书馆";G.vex[10].sight="实验楼";// 这里把所有的边假定为32767，含义是这两个景点之间是不可到达for(i=1;i<G.vexnum;++i){for(j=1;j<G.vexnum;++j){G.arcs[i][j].adj=Max;G.arcs[i][j].info=NULL;}}//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，// 所以要对图中对称的边同时赋值。

课程设计报告课程名称：数据结构设计题目：校园导航问题院系：信息技术学院班级：设计者：学号：指导教师：设计时间：目录一、设计目的 0二、设计要求和设计指标 0三、设计内容 03.1需求分析 03.1.1程序所能达到的功能 03.1.2输入的形式和输入值的范围 03.1.3输出的形式 (1)3.1.4测试数据和输出结果 (1)3.2总体设计 (1)3.2.1抽象数据类型定义 (1)3.2.2主程序模块的整体流程 (2)3.2.3各模块调用关系如下 (2)3.3详细设计 (2)3.3.1有向网节点结构体类型定义 (2)3.3.2 主程序和其它主要函数伪码算法 (3)3.3.3 函数的调用关系 (10)3.4测试与分析 (10)3.4.1测试 (10)3.4.2分析 (12)四、总结 (13)五、参考文献 (13)六、附录 (13)课程设计（大作业）报告一、设计目的1．加深对《数据结构》这一课程所学内容的进一步理解与巩固2．通过完成课程设计，逐渐培养自己的编程能力；3．培养给出题目后，构建框架，用计算机解决的能力；4．通过调试程序积累调试C程序设计的经验；二、设计要求和设计指标设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）三、设计内容3.1需求分析3.1.1程序所能达到的功能(1) map——输出辽宁工程技术大学平面图。

(2) init()——按相应编号输入各个节点内容，对相应路径赋值的函数。

(3) menu()——菜单函数(4) information()——输出简介的函数(5) way()——最短路径的输出函数(6) shortestpath()——调用弗洛伊德和最短路径输出的函数(7) main()——主函数3.1.2输入的形式和输入值的范围输入数字和字母：字母：以s查询最短路径；以i查询信息；以e退出程序。

校园导航问题【问题描述】以我校为例，设计一个校园导航系统，主要为来访的客人提供信息查询。

系统有两类登陆账号，一类是游客，使用该系统方便校内路线查询；一类是管理员，可以使用该系统查询校内路线，可对校园景点路线可编辑。

【需求分析】设计学校的平面图，至少包括10个以上景点（场所），每两个景点间可以有不同道路，且路长也可能不同，找出在游人所在景点到其他景点的最短路径，或游人输入的任意两个景点的最短路径。

要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，路径权重为路径长度。

（2）为游人提供任意景点相关信息查询。

（3）为游人提供任意景点的问路查询，即任意两个景点之间的最短路径。

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

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

选做内容：（1）提供图的编辑功能：增删景点；增删道路；修改已有信息等。

（2）校园导游图的仿真界面。

【概要设计】1. 抽象数据类型定义：（1）景点顶点名称代号顶点信息简介Typedef struct{Int num;Char name[100];Char features[200];} VertexType;（2）图的存储结构：Typedef int EdgeType;Typedef struct{VertexType vexs[MaxVertexNum];EdgeType edges[MaxVertexNum][MaxVertexNum];Int n, e;} MGraph;2 主要功能模块（1）创建图的邻接矩阵存储结构void create( Graph *G );（2）浏览图中任一景点介绍VertexType GetVex(Graph *G, int v);（3）修改景点信息void PutVertex(Grahp *G, int v);（4）增加景点信息void InsertVertex(Graph*G, VertexType v);（5）删除景点信息void DeleteVertex(Graph *G, VertexType v);（6）增加道路void InsertArc(Graph *G,int v, int w);（7）删除道路void DeleteArc(Graph*G ,int v,int w);（8）查找某一景点到其他景点的最短路径void ShortestPath(Graph *G, int P[ ], int D[ ]); （9）查找任一两个景点之间的最短路径。