校园导游咨询系统-数据结构课程设计.doc

1、 姓 名： 班 级： 学 号： 指导教师： 2012 年 12 月目录1、需求分析 .11.1 系统简介 .11.2 系统功能模块介绍 .12、概要设计 .22.1 系统功能结构图 .22.2 系统流程图 .22.3 主要函数概要设计 .32.3.1 主函数概要设计 .32.3.2 初始化图函数 InitGraph() .42.3.4 查询景点信息函数设计 SearchGraph().42.3.5 显示图中信息函数设计 ShowGraph().42.3.6 弗洛伊德算法函数设计 Floyd().53、详细设计 .53.1 主函数详细设计 .53.2 初始化图函数详细设计 InitGraph()

2、 .63.3 查询景点信息函数详细设计 SearchGraph().73.4 弗洛伊德算法函数详细设计 Floyd().84、调试分析 .94.1 显示主界面函数测试 .94.2 查找两景点间最短路径测试 .104.3 查看景点信息测试 .115.课程设计总结 .126、附录 .1311、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用 C 语言，基于数据结构中图的相关算法开发了“江西农业大学校园咨询系统” 。开发本系统目的在于为来访我校的游

3、客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。本系统界面友好，提示信息充分，在实际使用过程中运行良好。1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方；2、查询景点信息：用户在选择此功能模块后，按照屏幕上方提2示的景点名称及其对应的编

4、号，要求用户输入想要查询的景点的编号，回车后系统将在已存储的景点中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出景点信息，显示于幕上方；3、退出系统：用户在使用完本系统后，选择此功能模块，系统提示“欢迎再次使用”后，按任意键系统将自动退出。2、概要设计2.1 系统功能结构图用户主界面 查询两景点最短路径查询景点信息退出系统2.2 系统流程图32.3 主要函数概要设计2.3.1 主函数概要设计主函数首先是调用初始化图函数 InitGraph()函数创建一个图，而后调用显示主界面函数显示一个可视化主界面，内容包含本系统LOGO 以及景点信息及操作编号的提示信息。之后，当用户

5、成功输入操作编号后，使用一个 switch()函数，判断用户所需操作，匹配成开始创建无向图写入信息至无向图中Case 1Case 2Case 3查询路径查询景点息TTFFTendF退出系统4功后，调用相关函数实现用户所需功能。2.3.2 初始化图函数 InitGraph()InitGraph()函数首先使用 MyGraph 结构体声明一个用于存储图中信息的结构体，而后定义结构体中的景点数量以及路径数量，然后使用循环为景点信息和路径长度赋值，其中赋值景点信息时使用strcpy()函数将字符串复制给 G.siteArrayi.siteName 以及G.siteArrayi.siteInfo 两个数

6、组。2.3.3 显示主界面函数设计 MainGraph()MainGraph()函数主要用于显示主界面，函数中设计了本系统LOGO,同时，界面还提示了景点名称及其对应编号。主界面下方以列表方式提示用户系统可进行的操作及其对应编号，最后提示用户进行输入。2.3.4 查询景点信息函数设计 SearchGraph()该函数首先定义了一个变量 k(用于接收用户输入的查询编号)和一个标记位 flag(初始值设为 1)，而后使用 while()循环，判断条件为 flag=1,当输入编号不合法时提示错误，当输入合法时标记位flag 置为 0，此时跳出循环，调用 MyGraph 结构体对应编号的景点信息，以列

7、表方式输出。2.3.5 显示图中信息函数设计 ShowGraph()ShowGraph()函数主要功能为用循环将存储于图中的景点信息以5列表方式输出，方便用户对应着进行输入，同时提示用户进行输入。2.3.6 弗洛伊德算法函数设计 Floyd()本算法在设计时参考了数据结构 C 语言版一书中有关 Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。Floyd 算法首先将两景点间路径长度数据存储于数组 Dvw中，而后使用一个三

8、维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。以上部分完成后，当用于标记输入数据是否合法的 flag=1 时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。3、详细设计3.1 主函数详细设计#define InfiniteNum 10000 /定义一个无穷大数#define MaxInfoNum 100 /定义景点数据最大容量#include6#include#include#include“MyGraph.h“ /调用头文件void main(void

9、) MGraph g; /创 建 图int i;g = InitGraph(); /初始化校园地图MainGraph( /调用显示主界面函数scanf(“%d“,while(i!=3)switch(i) case 1:ShowGraph(Floyd(MainGraph(break;case 2:ShowGraph(SearchGraph(MainGraph(break;case 3:exit(0);break;default:break;scanf(“%d“,printf(“欢迎下次继续使用 !nn“);3.2 初始化图函数详细设计 InitGraph()MGraph InitGraph(vo

10、id) /初始化图中的信息MGraph G;int i,j;G.siteNumber = 6; /景点数量G.pathNumber = 8; /路 径 数量for(i=1;iG-siteNumber) /输入景点编号不合法时提示错误printf(“ 景点编号不存在!请重新输入景点编号:“);scanf(“%d“,if(k0printf(“ 8n“);printf(“ 编号 景点名称 简介 n“);printf(“ %-4d %-16s %-62s n“,G-siteArrayk.siteIdentifier,G-siteArrayk.siteName,G-siteArrayk.siteInfo

11、); /输出景点信息3.4 弗洛伊德算法函数详细设计 Floyd()void Floyd(MGraph *G) /使用弗洛伊德算法 2 求出最短路径int v,u,i,w,k,j;int flag = 1; /用于标记输入数据是否正确 ， 若输入数据符合要求 ，则将 flag 置为 0int p777,D77;for(v = 1;v siteNumber;v+)for(w = 1;wsiteNumber;w+)Dvw = G-pathArrayvw.path; /将路径数据存放至数组 Dvw 中for(u = 1;usiteNumber;u+)pvwu=0; /该三维数组用于存放两景点之间是否有直接路径，若有则记为 1，无则记为 0if(Dvw siteNumber;u+)for(v = 1;vsiteNumber;v+)for(w = 1;wsiteNumber;w+)if(Dvu + DuwsiteNumber;i+)pvwi = pvui|puwi; /获取两点之间路径所经过的景点编号while(flag)printf(“ 请输入出发点和目的地的编号:“);scanf(“%d%d“,