数据结构课程设计——校园导游图

《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题目：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：大二；学号：10054220 ；指导教师：王立波；2011 年12 月17 日1 课程设计的目的 (x)2 需求分析 (x)3 课程设计报告内容 (x)1、概要设计 (x)2、详细设计 (x)3、调试分析 (x)4、用户手册 (x)5、测试结果 (x)6、程序清单 (x)4 小结5 参考文献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 ）首先我画了学校主要几个景点的分布图以及自己定的一些距离，图如下：struct Date{int num; char n ame[50]; char in troduce[100]; }；(3 )然后我定义了一个类，定义如下:class Travel {private:Date date[15]; int dista nce[15][15]; int Path[15][15];int ShortestDista nce[15][15]; void Floyd(); public:Travel(); ~Travel(){}void In troduce(i nt); void Sca nf();void ShortDista nce(i nt,i nt); }; (4)基本操作： void Floyd();8C2030202010⑦①④(2 )接着我定义了一个顶点结构体，定义如下:II 景点编号//景点名称 II 景点介绍IIFloyd 算法，计算最短路径和最短距离Travel 。

西安郵電學院数据结构实验报告题目：校园导游系统院系名称：计算机学院专业名称：计算机科学与技术班级：1006学生姓名: **＊＊学号（8位）：＊**＊＊指导教师：＊*＊＊*＊设计起止时间:2011年12月12日~2011年12月16日一. 题目要求1、设计学校的校园平面图，地点（地点名称、地点介绍）不少于10个。

2、提供图中任意地点相关信息的查询。

3、提供图中任意地点的问路查询：1）任意两个地点之间的一条最短（中转最少）的简单路径；2)任意两个景点的最佳访问路线（带权）查询；3）任意两个地点之间的所有路径。

4、地点和道路的扩充以及撤销；地点基本信息的文件存储。

（附加：加分题）二．概要设计1．功能模块的调用关系图2．各个模块详细的功能描述。

1.首先，main(）函数调用loge（）函数，输出欢迎界面,然后调用showmenu()函数来选择用户所要进行的操作。

其中showmenu(）函数就是一个菜单供使用者来选择他所要进行的相关操作，比如信息的查询,最短路径查询之类。

2.browser（)函数,用于输出校园平面图,给用户提供校园的景点分布状况,方便用户选择景点参观。

3.Search(）函数,用于查询用户所选的景点信息，用户需要输入要查询的景点编号，函数会对编号进行判断，如果是合法输入，则在屏幕上输出该景点的相关信息，包括景点名字,景点的相关介绍，否则返回重新输入。

4.SearchAllpath(）函数,用于查询用户所选的任意两个景点间的所有路径,用户需要输入要查询的起始景点编号，函数会对编号进行判断，如果是合法输入，用户需要输入要查询的终点景点编号，函数会对编号进行判断,如果是合法输入，则在屏幕上输出输查询的两个景点间的所有路径，否则返回重新输入。

函数使用深度遍历DeepFirstSeach(）查找路径。

5.Wellway(）函数，用于查询用户所选的任意两个景点间的最短路径,用户需要输入要查询的起始景点编号，函数会对编号进行判断,如果是合法输入，用户需要输入要查询的终点景点编号，函数会对编号进行判断,如果是合法输入，则在屏幕上输出输查询的两个景点间的最短路径，否则返回重新输入。

景德镇陶瓷学院信息工程学院班级：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.退出系统。

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

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

基本要求：⑴设计华东交通大学的校园平面图，所含景点不少于10个。

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

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

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

#include <stdio.h>#define MAXV 100 //最大顶点个数#define INF 32767 //用32767表示∞#include <stdlib.h> //调用函数system改变字体颜色的头文件typedef int InfoType;#define MAXV 100 //最大顶点个数//以下定义邻接矩阵类型typedef struct{ int no; //顶点编号InfoType info; //顶点其他信息} VertexType; //顶点类型typedef struct //图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int vexnum,arcnum; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息} MGraph;void ecjtumap()//建立华东交通大学地图{ printf("\t|-------------------------------------------------------------|\n");printf("\t| |\n");printf("\t| |\n");printf("\t| ---------- |\n");printf("\t| ==============================| 国防生宿舍| |\n");printf("\t| 。

《数据结构》课程设计报告设计题目校园导游图学院名称信息工程学院专业班级计算机科学与技术（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].adj=INFINITY;printf("请输入路径长度:\n");for(k=0;k<G->arcnum;k++){printf("第%d条边:\n",k+1);printf("景点对(x,y):");scanf("%s",v1);scanf("%s",v2);printf("路径长度:");scanf("%d",&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i>=0&&j>=0){G->arcs[i][j].adj=w;G->arcs[j][i]=G->arcs[i][j];}}return G;}主菜单void main(){printf("\n 榆林学院导游图 \n");printf("********************************************\n");printf(" * 1.浏览校园全景 *\n");printf(" * 2.查看所有游览路线 *\n");printf(" * 3.选择出发点和目的地 *\n");printf(" * 4.查看景点信息 *\n");printf(" * 5.退出系统 *\n");printf(" ********************************************\n");printf("请选择您所需要的操作:");}画出主要函数的流程图七.测试分析白盒：查看代码完整性代码完整。

数据结构课程设计——校园导游咨询系统在当今数字化的时代，信息的高效获取和处理变得至关重要。

对于一个大型校园来说，拥有一个便捷的导游咨询系统能够极大地提升访客和新生的体验。

本次数据结构课程设计的目标就是创建一个实用的校园导游咨询系统。

一、系统需求分析首先，我们需要明确这个校园导游咨询系统的主要功能和用户需求。

对于访客和新生来说，他们可能希望了解校园内各个景点的位置、简介，以及如何从当前位置到达目标景点的最优路径。

系统应该能够提供清晰准确的地图信息、景点介绍和导航指引。

从学校管理的角度出发，系统需要易于更新和维护，能够及时添加新的景点或者修改已有景点的信息。

同时，为了保证系统的稳定性和安全性，需要有一定的权限管理机制，防止未经授权的修改和访问。

二、数据结构选择为了实现上述功能，我们需要选择合适的数据结构来存储和管理校园的相关信息。

对于校园地图的表示，可以使用图（Graph）这种数据结构。

将校园中的各个景点看作图中的节点，景点之间的道路看作边，边的权重可以表示道路的长度或者行走所需的时间。

为了存储景点的详细信息，如名称、简介等，可以使用结构体或者类。

每个景点的结构体或类成员包含景点的标识符、名称、简介等属性。

对于路径搜索和导航，我们可以选择迪杰斯特拉（Dijkstra）算法或者 A算法来计算最短路径。

三、系统功能模块设计1、地图显示模块能够以直观的方式展示校园的地图，包括各个景点的位置和连接关系。

支持缩放、平移等操作，方便用户查看不同区域的细节。

2、景点信息查询模块用户可以输入景点名称或关键词，系统能够快速检索并显示相应景点的详细信息。

3、路径规划模块根据用户输入的起始景点和目标景点，计算并显示最优的行走路径。

能够提供多种路径选择，如最短路径、最少转弯路径等。

4、周边设施查询模块用户可以查询某个景点周边的餐厅、商店、卫生间等设施的位置。

5、用户管理模块只有授权的管理员能够对校园景点信息和地图进行修改和更新。

《数据结构课程设计》报告题目旅游区导游图专业计算机科学与技术班级（2）班学生###13 旅游区导游图题目内容问题描述：设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。

以(V i,V j,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：V i和V j 表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构(数组)。

实现要求：⑴旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。

⑵相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。

⑶景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。

⑷景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。

⑸最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。

⑹设计一个菜单，上述操作要求都作为菜单中的主要菜单项。

⒈本人完成的工作完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。

⒉所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义//邻接矩阵结构体typedef struct{ char vex1, vex2 ; /* 弧或边所依附的两个顶点 */int ArcVal ; /* 弧或边的权值 */}ArcType ; /* 弧或边的结构定义 */typedef struct{int vexnum, arcnum ; /* 图的当前顶点数和弧数 */char vexs[MAXVEX] ; /* 顶点向量 */int adj[MAXVEX][MAXVEX];}MGraph ; /* 图的结构定义 *///邻接链表结构体typedef struct ANode //弧的结点结构类型{ int adjvex; //该弧的终点位置int info; //该弧的相关信息,这里用于存放权值struct ANode *nextarc; //指向下一条弧的指针} ArcNode;typedef struct Vnode //邻接表头结点的类型{char data; //顶点信息ArcNode *firstarc; //指向第一条弧} VNode;typedef struct{VNode AdjList[MAXVEX];int vexnum,arcnum; //图中顶点数n和边数e} ALGraph; //图的邻接表类型⒊所设计的函数对于每个主要函数必须给出所采用的算法思想和程序框图；邻接矩阵和邻接链表初始化函数MGraph *Init_MGraph()/* 图的初始化 */{MGraph *G;G=(MGraph *)malloc(sizeof(MGraph)) ;G->vexnum=0 ; G->arcnum=0 ; /* 初始化顶点数、边数 */ return(G) ;}ALGraph *Init_ALGraph()/* 图的初始化 */{ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph)) ;G->vexnum=0 ;G->arcnum=0; /* 初始化顶点数 */return(G) ;}图中顶点定位的函数，判断顶点是否重复输入了int LocateVex(MGraph *G, char vp)/* 图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值 */ {int k ;for (k=0; k<=G->vexnum; k++)if (G->vexs[k]==vp) return(k) ;}{int k, j ;if (G->vexnum>=MAXVEX)printf("图中顶点数已达到最多 !\n");else{if (LocateVex(G, vp)==-1){k=G->vexnum ; G->vexs[G->vexnum++]=vp ;for (j=0 ; j<G->vexnum ; j++){G->adj[j][k]=INFINITY ;G->adj[k][j]=INFINITY ;/* 是带权的有向图或无向图 */}}}往图的邻接矩阵中添加边(弧)void AddArc(MGraph *G , ArcType *arc)/* 往图的邻接矩阵中添加边(弧) */{int k=0, j=0;k=LocateVex(G, arc->vex1) ;j=LocateVex(G, arc->vex2) ;if (k==-1||j==-1)printf("边或弧的顶点不存在，错误 !\n") ;else{G->arcnum++ ;G->adj[k][j]=arc->ArcVal ;G->adj[j][k]=arc->ArcVal ;/* 是无向图或带权的无向图,需对称赋值 */}输出图的顶点矩阵和邻接矩阵void output_graphic(MGraph *G)/* 输出图的顶点矩阵和邻接矩阵 */ {int k, j ;printf("图的顶点如下：\n") ;for (k=0; k<G->vexnum; k++)printf("%4c",G->vexs[k]) ;printf("\n\n") ;printf("图的邻接矩阵如下：\n") ; for (k=0; k<G->vexnum; k++){for (j=0; j<G->vexnum; j++)}}Y以邻接矩阵作为图的存储结构建立图MGraph *create_graph()/* 以邻接矩阵作为图的存储结构建立图 */{char inchar[100], enchar[100],fvex,lvex ;int count=0;int weight ;MGraph *G;ArcType *arc ;printf("首先进行图的初始化!!\n\n") ;G=(MGraph *)malloc(sizeof(MGraph)) ;G=Init_MGraph() ;arc=(ArcType *)malloc(sizeof(ArcType)) ;printf("\n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：\n") ;while(1){scanf("%s",inchar) ;fvex=inchar[0] ; /* 输入第一个顶点，?结束 */if (fvex=='?') break ;else{AddVertex(G, fvex) ;scanf("%s",enchar) ;lvex=enchar[0] ;AddVertex(G, lvex) ;scanf("%d",&weight) ; /* 输入第二个顶点和权值 */arc->vex1=fvex ; arc->vex2=lvex ;arc->ArcVal=weight ; AddArc(G, arc) ;printf("\n请继续输入下一条边(或弧)!!\n") ;}}return(G) ;}将邻接矩阵g转换成邻接表GALGraph *MGraphToALGraph(MGraph *g,ALGraph *G){int i,j,n=g->vexnum; //n为顶点数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));G->arcnum = g->arcnum;G->vexnum = g->vexnum;for(i=0;i<G->vexnum;i++)G->AdjList[i].firstarc = NULL;for (i=0;i<n;i++) //检查邻接矩阵中每个元素{for (j=n-1;j>=0;j--)if (g->adj[i][j]!=INFINITY) //邻接矩阵的当前元素不为{p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*pG->AdjList[j].data=g->vexs[j];p->adjvex = g->vexs[j];p->info=g->adj[i][j];p->nextarc=G->AdjList[i].firstarc; //将*p链到链表后G->AdjList[i].firstarc=p;}}return G;}邻接链表的输出void output_graphic_c(MGraph *g,ALGraph *G) {int i;ArcNode *p;for (i=0;i<g->vexnum;i++){printf("%c",G->AdjList[i].data) ;p=G->AdjList[i].firstarc;while(p!=NULL){printf("%s","->") ;printf("(%c,%d)",p->adjvex,p->info) ;p=p->nextarc ;}printf("\n\n");}}相邻景点查询并输出void output_Find_ALGraph(ALGraph *G){ /* 相邻景点查询并输出 */int j;ArcNode *p;printf("请输入你要查询的景点(下标值):\n");scanf("%d",&j);p=G->AdjList[j].firstarc;while(p){printf("景点%c到景点%c的距离是%d (该两个景点之间有直接的道路相通)\n",G->AdjList[j].data,p->adjvex,p->info);p=p->nextarc;}}景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。