校园导游系统

1、课程设计报告课程名称： 数据结构与算法 题目名称： 校园导游系统 学生学院： 数学与计算机科学系 专业班级： 2016级计算机科学与技术本科班 小组组长： 王明 小组成员: 王明 郑双凤 吕运发 指导老师： 熊小颖 老师 2017年10月15日目录一、设计目的3二、问题描述3三、基本要求3四、概要设计3五、主程序4六、测试数据136.1调试程序所用数据136.2程序的调试结果七、总结一、设计目的 随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于数据结构中

2、图的相关算法开发了“南昌师范学院导游系统”。 开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。二、问题描述 设计校园导游程序，为来访的客人提供服务，为来访我校的游客提供一条在游客当前位置到目的地的最短游览路径，找到游玩景点最省时，最高效的路径。三、 基本要求1. 假设有一所校园的平面图，所含景点不小于10个，请选择适当的坐标来表示出该图上的各个景点。2. 为来访的客人提供从当前位置到其他景点的最短路径的咨询；3. 必须具有校园平面图的修改和扩充功能（即某些景点坐标的修改和景点个数

3、的增加）。四、 概要设计算法思路本设计的重难点在于问题二的解决。利用了弗洛伊德算法函数设计Floyd()  本算法在设计时参考了数据结构C语言版一书中有关Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。Floyd算法首先将两景点间路径长度数据存储于数组Dvw中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为

4、简介路径所经过的顶点信息。以上部分完成后，当用于标记输入数据是否合法的flag=1时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。五、 主程序#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM 100 /最大顶点数#define MAX_INT 10000 /无穷大 typedef int AdjType; typedef struct int piMAX_VERTEX_NUM;/存放v到vi的一条最短路径 int end;PathType;typedef char VType;

5、 /设顶点为字符类型typedef struct VType VMAX_VERTEX_NUM; /顶点存储空间 AdjType AMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵 MGraph;/邻接矩阵表示的图/Floyd算法/求网G（用邻接矩阵表示）中任意两点间最短路径 /D是最短路径长度矩阵，path最短路径标志矩阵 void shortdistance(MGraph * G,int pathMAX_VERTEX_NUM,int DMAX_VERTEX_NUM,int n) int i,j,k; for(i=0;i<n;i+)/初始化 for(j=0;j<

6、;n;j+) if(G->Aij<MAX_INT) pathij=j; else pathij=-1; Dij=G->Aij; for(k=0;k<n;k+)/进行n次试探 for(i=0;i<n;i+) for(j=0;j<n;j+) if(Dij>Dik+Dkj) Dij=Dik+Dkj;/取小者 pathij=pathik;/改Vi的后继 for(i=0;i<n;i+)/输出每对顶点间最短路径长度及最短路径 for(j=0;j<n;j+) printf("V%d到V%d的最短长度:",i,j); printf(&q

7、uot;%dt",Dij);/输出Vi到Vj的最短路径长度 k=pathij;/取路径上Vi的后续Vk if(k=-1) printf("There is no path between V%d and V%dn",i,j);/路径不存在 else printf("最短路径为:"); printf("(V%d",i);/输出Vi的序号i while(k!=j)/k不等于路径终点j时 printf(",V%d",k);/输出k k=pathkj;/求路径上下一顶点序号 printf(",V%d)n

8、",j);/输出路径终点序号 printf("n"); int introduce(char scenery)getchar();printf("请输入景点对应的大写字母n");scanf("%c",&scenery);switch(scenery)default:printf("没有该景点n");case 'A':printf("图书馆，距离南大门100米n");break;case 'B':printf("实验楼，距离南大门200米

9、n");break;case 'C':printf("理科楼，理科类学生上课地点n");break;case 'D':printf("女宿舍楼，南昌师范学院的女孩子的家n");break;case 'E':printf("男宿舍楼，南昌师范学院的男孩子的家n");break;case 'F':printf("大学生活动中心，大学生活动休闲场所n");break;case 'G':printf("田径场，运动会举办场地

10、n");break;case 'H':printf("逸夫大礼堂，各种活动举办场所n");break;case 'I':printf("体育馆，正在建设中n");break;case 'J':printf("综合楼，领导办公处n");break;case 'K':printf("北大门，学校出口n");break;return 0; int main()char kk; char scenery; int i,j,k,v='A'

11、;,m=11;/v为起点，n为顶点个数 MGraph G; int pathMAX_VERTEX_NUMMAX_VERTEX_NUM;/v到各顶点的最短路径向量 int DMAX_VERTEX_NUMMAX_VERTEX_NUM;/v到各顶点最短路径长度向量 char VMAX_VERTEX_NUM='A','B','C','D','E','F','G','H','I','J','K' int aMAX_VERTEX_N

12、UMMAX_VERTEX_NUM= /初始化 0,50,200,100,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT, 50,0,100,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT, 200,100,0,MAX_INT,MAX_INT,100,50,MAX_INT,MAX_INT,MAX_INT,MAX_INT, 100,MAX_INT,MAX_INT,0,500,200,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_I

13、NT, MAX_INT,MAX_INT,MAX_INT,500,0,300,MAX_INT,300,MAX_INT,300,500, MAX_INT,MAX_INT,100,200,300,0,400,200,100,MAX_INT,MAX_INT, MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,400,0,100,300,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,200,200,100,0,MAX_INT,400,MAX_INT,MAX_INT,MAX_INT,50,MAX_INT,MAX_INT,100

14、,300,MAX_INT,0,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT,300,MAX_INT,MAX_INT,400,MAX_INT,0,300,MAX_INT,MAX_INT,MAX_INT,MAX_INT,500,MAX_INT,MAX_INT,MAX_INT,MAX_INT,300,0 ; for(i=0;i<m;i+) for(j=0;j<m;j+) G.Aij=aij; printf("*n");printf("* *n");printf("* *n");p

15、rintf("* 欢迎使用南昌师范学院校园咨询系统！*n");printf("* *n "); printf("* *n "); printf("*n");printf("n");while(1)printf("1.景点信息查询请按“1”键:n");printf("2.景点最短路径查询（弗洛伊德算法）请按“2”键:n");printf("3.景点最短路径查询（迪杰斯特拉算法）请按“3”键:n");printf("4.校内景点地

16、图查询请按“4”键:n");printf("5.退出系统请按“5”键 :n");printf("请选择：n");scanf("%c",&kk);switch(k)case'1':printf("景点介绍查询n");introduce(scenery);break;case'2':printf("景点最短路径查询（弗洛伊德算法）n");shortdistance(&G,path,D,11);break;case'5':printf("谢谢使用！n");exit(0);return 0;六、 测试数据6.1调试程序所用数据6.2程序的调试结果七、 总结 经过小组同学的努力，我们终于结束了这次的课程设计，虽然我们尽了很大的努力，但是其中仍显现出许多的不足。其中在处理查询两景点最短路径这一问题时：一开始对于题目的阅读不够仔细，将随机的当前位置当成了，一进校门的位置作为与其他建筑物的路径距离。浪费了一些时间，之后与重新思考思路。所以由此发现对于需求的正确分析确实很重要。另外经过这次课程设计，我对