校园导游咨询(最短路径)

综合实验十二校园导游咨询一、实验目的（1）熟练掌握图的创建及遍历基本操作算法。

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

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

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

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

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

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

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

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

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

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

【选作内容】(1)求校园图的关节点。

(2)提供图中任意景点问路查询，即求任意两个景点之间的所有路径。

(3)提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳(短)路径。

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

(5)扩充道路信息，如道路类别(车道、人行道等)、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。

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

(7) 实现校园导游图的仿真界面。

程序代码及结果：#include<iostream>#include<iomanip>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。

一、设计题目[问题描述]设计一个校园导游程序，为来访的客人提供各种信息查询服务。

（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息；（2）提供基本信息的修改功能；（3）为来访客人提供图中任意景点相关信息的查询；（4）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。

二、需求分析本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度，满足用户查询的需要：1、中原工学院信息商务学院地图，从中选取出13个有代表性的景点。

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

当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。

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

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

4、为来访客人和新生推荐参观路线。

三、算法设计1.算法思想抽象数据类型图的定义如下：ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

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

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

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

操作结果：销毁图G。

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

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

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

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

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

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

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

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

4．编程语言：C 语言。

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

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

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

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

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

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

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

（2）为来访客人供给图中随意景点有关信息的查问。

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

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

（5）扩大道路信息，如道路类型（车道、人行道），致使可按客人所需分别查问人行路径或车行路径。

（6）扩大每个景点的林洁景点的方向等信息，使得路径查问结果能供给详细的导向信息。

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

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

《算法与数据结构》课程设计报告班级：专业级班姓名：学号：课程设计题目：校园导游咨询所属课程：算法与数据结构实验室(中心)：指导教师：完成时间：年月日学院信息科学与工程学院课程设计任务书信息科学与工程学院课程设计成绩单指导教师：A课程设计课程名称：算法与数据结构性别男班级学号姓名指导教师算法与数据结构班级课程A2201完成时校园导游咨 201主介绍校园的景点，同时提供任意两点之间最短的路径内．封面．课程设计成绩单、课程设计任务．内容提要．“课程设计报告”正文部分主要应包括①问题分析和任务定义②环境简介③设计：主要是指数据结构与核心算法的设计描述；操作界设的设计；主要功能的算法框架；测试用例设计等内容（要求使报C+）要④编译参数与步骤的说明⑤上机调试总结与分析⑥用户使用说明⑦测试数据与测试结果等内容⑧课程设计总结：可以包括课程设计过程的收获、遇到的问及解决过程的思考、对数据结构这门课程的思考和认识等内容⑨附录程序清．参考文1题目用黑体三号，段后1磅（行），居中对齐2标题用黑体四号，段前、段后磅（0.版行）3正文用小四号宋体，行距1.2倍行距要4标题按“一”、“㈠”、“1”、“⑴”顺序编号星周指11-时1-安11-5-指专业实验406/40地点综合成绩□能正确运行□基本能正确运行□能运行但结果不完善程序运行情况15分）（（10分）分）（20（占总成绩20%）□不完善□基本完善□完善程序功能完善程度分）（5（8分）（分）10）10%（占总成绩□不太合理□基本合理程序结构的合理性□合理5分）（8分）（）（占总成绩10%分）（10□基本能正确回答□概念正确有创新□能正确回答所有问题30（分）40（分）（35分）对问题的答辩情况□部分问题回答概念不清晰40%（占总成绩）（20分）□工作态度认真能独立完成任务□工作态度认真但独立性较差学生的工作态度与（10分）（分）8独立工作能力□工作态度基本认真但缺乏独立性（占总成绩10%）（5分）□规范性较差□符合规范□基本符合规范设计报告的规范性（5分）10分）（8（分））10%（占总成绩．摘要数据结构课程设计对于训练学生掌握程序设计技术、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

校园导游目录摘要 ......................................................................................... 错误！未指定书签。

1绪论 .......................................................................................... 错误！未指定书签。

2系统分析 .................................................................................. 错误！未指定书签。

2.1功能需求 ........................................................................... 错误！未指定书签。

2.2数据需求............................................................................ 错误！未指定书签。

2.3性能需求 ........................................................................... 错误！未指定书签。

3总体设计 .................................................................................. 错误！未指定书签。

3.1系统设计方案.................................................................... 错误！未指定书签。

3.2功能模块设计.................................................................... 错误！未指定书签。

实验八：校园交通咨询系统设计（最短路径）8.1 问题描述设计一个校内交通咨询系统，能让旅客咨询从任一教学楼到其余所有教学楼之间的最短路径，以及任意两幢教学楼之间的最短路径。

校园内简图见图8-1，为通俗化程序，用数字序号代替楼的名称。

图8-18.2 输入与输出输入：输入图的顶点数，以及边数。

输出：一幢楼到其他楼之间的最短路径，以及任意两幢楼之间的最短路径。

8.3 需求分析1.建立交通网络图的存储结构。

2.解决单源最短路径问题。

3.最后实现两幢楼之间的最短路径。

8.4概要设计1.结构定义图的存储结构（邻接矩阵）#define MVNum 50 /*最大顶点数*/typedef int VertexType;typedef int Adjmatrix;typedef struct{VertexType vexs[MVNum];Adjmatrix arcs[MVNum][MVNum];}MGraph;2.函数模块void CreateMGraph( MGraph *G, int n,int e)/*采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数*/void Dijkstra(MGraph *G, int v1,int n) /*迪杰斯特拉算法*/void Floyd(MGraph *G, int n)/*费洛伊德算法*/8.5详细设计#include "stdio.h"#include "stdlib.h"#define MVNum 50 /*最大顶点数*/#define Maxvalue 32767enum boolean {FALSE ,TRUE};typedef int VertexType;typedef int Adjmatrix;typedef struct{VertexType vexs[MVNum];Adjmatrix arcs[MVNum][MVNum];}MGraph;int D1[MVNum], path1[MVNum];//D都是表示路径长度，p都是表示路径经过的顶点。