《校园导游咨询系统》数据结构课程设计说明书.doc

《《校园导游咨询系统》数据结构课程设计说明书.doc》由会员分享，可在线阅读，更多相关《《校园导游咨询系统》数据结构课程设计说明书.doc（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本文档经供参考，产生的后果概不负责中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:刘安光学 号：1507084143学生姓名:刘晨馨学 号：1507084103学生姓名:古文慧学 号：1507084118学生姓名:周顺帆学 号：1507084114学 院:计算机与控制工程学院专 业:网络工程专业题 目:校园导游咨询系统指导教师梁志剑、张建华2016 年 12月30日1目录1设计目的12设计内容13设计要求14模块分工15数据结构26详细设计36.1 主函数模块36.1.1 详细设计思想36.1.2 核心代码46.2 图的建立模块46.2.1详细设计思想46.2.2 核心代码56.3

2、信息查询模块66.3.1详细设计思想66.3.2 核心代码76.4 两景点最短路径模块86.4.1详细设计思想86.4.2 核心代码106.5 多景点最佳路径模块126.5.1详细设计思想126.5.2 核心代码126.6 求图的关节点模块136.6.1详细设计思想136.6.2 核心代码156.7 两景点所有路径模块176.7.1详细设计思想176.7.2 核心代码186.8 游客及管理员菜单模块196.8.1详细设计思想196.8.2 核心代码207源码文件257.1 源码257.2 文本文件307.2.1 map.txt307.2.2 liuyan.txt318运行截图328.1 主菜单

3、界面与功能一览328.2 中北校园景点信息查询328.3 两景点间最短路径查询328.4 两景点间所有路径查询338.5 多景点间访问路线查询338.6 输出校园景点图关节点338.7 公告查看及游客留言栏348.8 景点管理员后台管理栏358.9 退出校园导游咨询系统369经验总结379.1 关于分工379.2 关于答辩371设计目的数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：（1）了解并掌握数据结构与算法的设计方法，具备初步的独立

4、分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2设计内容设计一个校园导游程序，为来访的客人提供各种信息查询服务。（1）设计中北大学的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两相景点之间的一条最短的简单

5、路径。（4）求校园图的关节点。（5）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。（6）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳路径。3设计要求（1）符合课题要求，实现相应功能；（2）要求界面友好美观，操作方便易行；（3）注意程序的实用性、安全性；4模块分工刘安光：主函数模块、求图的关节点模、两景点所有路径模块。刘晨馨：两景点最短路径模块、多景点最佳路径模块。古文慧：游客菜单模块、管理员菜单模块。周顺帆：图的建立及输出模块、信息查询模块。5数据结构该程序用到的是图的数据结构，其中用到的是图的邻接矩阵存储结构。#define INFINITY 9999 /*此

6、处用9999代表无穷大*/#define M 20 /*最大顶点数*/typedef struct /*景点信息结构定义*/int num; /*景点代号*/char name20; /*景点名称*/char intro200; /*景点简介*/vertexType; /*邻接矩阵顶点结构*/typedef int edgeType; /*权值类型*/typedef struct /*校园景点图结构体定义*/vertexType vexsM; /*顶点值类型*/edgeType edgsMM; /*边权值类型-距离*/ int vexNum, edgNum; /*图顶点总数与边数*/mgrap

7、hType; /*邻接矩阵结构*/ /*函数一览表*/void main(); /*主函数*/ int Menu(); /*主菜单*/void Creat_Map(mgraphType *g); /*从文件读取信息建立图*/void Dis_Map(); /*显示校园景点地图*/void Admin_Menu(mgraphType *g); /*管理员菜单*/void Tour_Menu(mgraphType *g); /*游客菜单*/ int Judeg_Innum(int num); /*判断输入的编号是否合理*/void Search_Intro(mgraphType *g); /*景点

8、信息查询*/void ShortestPath_FLD(mgraphType *g); /*弗洛伊德算法求景点间最短的路径*/void Floyd_Print(mgraphType,int,int); /*递归实现打印两点间的最短路径*/void ShortestPath_Print(mgraphType); /*输出并打印两点间的最短路径*/void Dfs_Allpath(mgraphType,int,int); /*深度优先遍历查询两景点间所有路径*/void Allpath_Print(mgraphType *g); /*查询两景点之间的所有路径并打印*/void Bestpath_M

9、ultispot(mgraphType); /*多景点间求最佳路径*/void Dfs_Coila(mgraphType *g, int i); /*深度遍历找关节点*/void Coila_Query(mgraphType *g); /*求校园交通图关节点*/void System_Exit(int *quit); /*退出系统函数*/6详细设计6.1 主函数模块6.1.1 详细设计思想图1 主函数模块6.1.2 核心代码/*主函数*/void main()int quit=0;mgraphType g; Creat_Map(&g); /*从文件读取信息建立图*/ ShortestPath_

10、FLD(&g); /*floyed求dist与path*/ while(!quit) /*系统退出条件满足判定*/ switch(menu() /*打印主菜单等待输入项*/ case 1: Dis_Map();Search_Intro(&g);break; /*中北校园景点信息查询*/ case 2: Dis_Map();ShortestPath_Print(&g); break; /*两景点间最短路径查询*/ case 3: Dis_Map();Allpath_Print(&g); break; /*两景点间所有路径查询*/ case 4: Dis_Map();Bestpath_Multis

11、pot(&g);break; /*多景点间访问路线查询*/ case 5: Dis_Map();Coila_Query(&g);break; /*输出校园景点图关节点*/ case 6: Dis_Map();Tour_Menu(&g);break; /*公告查看及游客留言栏*/ case 7: Dis_Map();Admin_Menu(&g);break; /*景点管理员后台管理栏*/ case 8: System_Exit(&quit);break; /*退出校园导游咨询系统*/ default:printf(错误！没有该选项对应的操作。); /*按错选项反馈错误信息*/ system(pa

12、use); system(cls); 6.2 图的建立模块6.2.1详细设计思想当建立图存储结构时，图的信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边权。图的顶点信息则时按照编号、名字、简介的方式的方式在文件中存储。先初始化邻接矩阵，然后打开文件，若文件不为空则先读入顶点数与边数信息，然后按文件中所给信息初始化邻接矩阵的每个顶点，处理完定点后，把文件中的边权信息读入到邻接矩阵中建立无向图，最后关闭文件，以待稍后输出。如果文件不能打开，将无向图的顶点赋值为零。具体流程如下图（图2 图的建立）所示。图2 图的建立6.2.2 核心代码/*校园景点图的读取与创建*/void

13、 Creat_Map(mgraphType *g) /*从文件读取图的信息并建立图*/ int i, j, k, e; FILE *rf; /*定义带缓冲的文件指针*/rf = fopen(map.txt,r); /*从文件读取图的边信息*/if(rf) /*读入图的顶点数和边数*/fscanf(rf,%d%d,&g-vexNum, &g-edgNum); /*读入图的顶点数与边数*/for(i=0; ivexNum; i+) /*读入图的顶点信息*/fscanf(rf,%d%s%s,&g-vexsi.num,g-vexsi.name,g-vexsi.intro);for(i=0; ivexN

14、um; i+) /*初始化领接矩阵*/for(j=0; jvexNum; j+)if(i=j) g-edgsij=0; /*到本点的距离为0其余不可达*/else g-edgsij=INFINITY;for(k=0; kedgNum; k+) /*读入图的边权，建立无向图*/fscanf(rf,%d%d%d,&i,&j,&e); /*文件以三元组形式存储图信息*/g-edgsij=g-edgsji=e; /*建立无向图*/fclose(rf); /*关闭文件*/else g-edgNum=0;6.3 信息查询模块6.3.1详细设计思想信息查询为本程序功能一，在运行此功能时需要用到Judeg_I

15、nnum函数。先提示用户按显示的地图上的景点输入对应的编号进行查询。等待用户输入完编号后，读入游客输入要查询的景点编号，然后用Judeg_Innum函数判断输入的编号，如果游客输入值为-1，表示用户结束输入，则Judeg_Innum函数返回-1并结束信息查询。如果游客输入值不为-1，判断游客输入值是否合理（即是否在1-12范围类以及对应景点是否关闭），不合理的话提示游客输入有误，返回1，等待用户再次输入。如果游客输入正确的话，再次判断查询的景点是否关闭，如果景点关闭，输出景点关闭及原因并返回1。如果Judeg_Innum函数返回值为1，跳回开始，返回值不为-1和1，输出景点名称简介并结束。流程

16、图如下图（图3 信息查询）所示。图3 信息查询6.3.2 核心代码/*景点信息查询*/void Search_Intro(mgraphType *g) int s;doprintf(n请输入你要查找的景点编号：);scanf(%d,&s); /*输入的编号比实际景点编号大1*/while(judeg_Innum(s);printf(n景点名称：%snn,g-vexss-1.name);printf(景点简介： %snn,g-vexss-1.intro);/*判断用户输入的编号是否合理及对应景点是否开放*/int judeg_Innum(int num)int i=0;if(num=-1) re

17、turn i;if(num12)printf(nttt你输入的景点编号有误，请输入1-12之间的数！nn);i=1;else if (cloNumnum-1.close=INFINITY)printf(nttt%s暂时无法游览！n,cloNumnum-1.name);printf(ntt关闭原因：%sn,cloNumnum-1.reason);i=1;return i;6.4 两景点最短路径模块6.4.1详细设计思想用floyed算法通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵

18、D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。具体算法思想如下：（1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。（2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。（3）把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gij=d，d表示该路的长度；否则Gij=无穷大。定

19、义一个矩阵D用来记录所插入点的信息，Dij表示从Vi到Vj需要经过的点，初始化Dij=j。把各个顶点插入图中，比较插点后的距离与原来的距离，Gij = min( Gij, Gik+Gkj )，如果Gij的值变小，则Dij=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。进入该功能时，系统会首先提醒用户输入起点与终点编号，具体流程如图5所示，待编号无误后，利用floye

20、d算法得出两点间最短距离，算法流程如下。图4 弗洛伊德算法求两景点间的一条最短的路径图5 输出并打印两点间的最短路径6.4.2 核心代码/*弗洛伊德算法求两景点间的一条最短的路径*/int distMM; /*距离向量类型*/int pathMM; /*路径类型*/void ShortestPath_FLD(mgraphType *g) /*弗洛伊德算法求两景点间的一条最短的路径并输出所经结点*/int i, j, k;for(i=0; ivexNum; i+) /*初始化距离向量与路径向量矩阵*/for(j=0; jvexNum; j+)distij=g-edgsij;if(i!=j&dis

21、tijINFINITY) pathij=i;else pathij=-1; /*-1代表当前两点不可达*/for(k=0; kvexNum; k+) /*递推求解每两景点的最短路径*/for(i=0; ivexNum; i+)for(j=0; jvexNum; j+) /*更新distij的值*/if(distij(distik+distkj)distij=distik+distkj; pathij=k; /*path用于记录最短路径上的结点*/ /*递归实现打印两点间的最短路径*/void Floyd_Print(mgraphType *g, int sNum, int eNum) if(p

22、athsNumeNum=-1|pathsNumeNum=eNum|pathsNumeNum=sNum) return;else Floyd_Print(g,sNum,pathsNumeNum ); /*将中间点作为终点继续打印路径*/printf(%s-,g-vexspathsNumeNum.name); /*打印中间景点名字*/Floyd_Print(g,pathsNumeNum,eNum); /*将中间点作为起点继续打印路径*/6.5 多景点最佳路径模块6.5.1详细设计思想用户依次输入节点编号，即游览顺序。根据Floyd算法，算出第一个景点和第二个景点的最短路径，依次类推，算出多景点的最

23、短路径。具体流程如下图所示。图6 多景点求最佳路径6.5.2 核心代码/*多景点间求最佳路径*/void Bestpath_Multispot(mgraphType *g) int vNumM=0,j=1; /*记录用户输入的编号信息*/int d=0; /*统计全程总长*/printf(请输入你要游览的第%d个景点的编号（输入-1结束输入）：,j);scanf(%d,&vNumj-1);while(vNumj-1!=-1&j0&vNumi+10; i+)printf(%s-,g-vexsvNumi-1.name); /*输出路径上的起点*/Floyd_Print(g,vNumi-1,vNum

24、i+1-1); /*利用佛洛依德算法*/d+=distvNumi-1vNumi+1-1;printf(%snn,g-vexsvNumj-2-1.name); /*输出路径上的终点*/printf(全程总长为：%dmnn,d);6.6 求图的关节点模块6.6.1详细设计思想通过深搜优先生成树来判定。从任一点出发深度优先遍历得到优先生成树，对于树中任一顶点而言，其孩子节点为邻接点。由深度优先生成树可得出两类割点的特性：（）若生成树的根有两棵或两棵以上的子树，则此根顶点必为割点。因为图中不存在连接不同子树顶点的边，若删除此节点，则树便成为森林；（）若生成树中某个非叶子顶点V，其某棵子树的根和子树中的

25、其他节点均没有指向V的祖先的回边，则V为割点。因为删去v，则其子树和图的其它部分被分割开来。仍然利用深搜算法，只不过在这里定义visitedv表示为深度优先搜索遍历图时访问顶点v的次序号，定义lowv=Minvisitedv，loww，visitedk，其中w是顶点v在深度优先生成树上的孩子节点；k是顶点v在深度优先生成树上由回边联结的祖先节点。割点判定条件：如果对于某个顶点v，存在孩子节点w且loww=visitedv，则该顶点v必为关节点。因为当w是v的孩子节点时，loww=visitedv，表明w及其子孙均无指向v的祖先的回边，那么当删除顶点v后，v的孩子节点将于其他节点被分割开来，从来

26、形成新的连通分量。流程图如下。图7 深度遍历找关节点图8 求校园交通图关节点6.6.2 核心代码/*深度遍历找关节点*/#define ROOT -1 /*根节点标记*/ #define COILA 1 /*关节点标记*/int visiM，coilaM=0; /*根节点标记或访问标记及关节点*/int coilaNum; /*统计校园图关节点数目*/void Dfs_Coila(mgraphType *g, int i) int child=0; /*用于统计结点子树数目*/if(visii!=ROOT)visii=1; /*将不是根结点的i结点标记为已访问*/for(int j=0; jv

27、exNum; j+) if(g-edgsij!= 0 & g-edgsij!= INFINITY & !visij) /*表明i结点与j结点之间可达，且j结点未被访问*/child+; /*i结点子树加一*/Dfs_Coila(g, j); /*递归，对j结点执行同样的操作*/if(visii = ROOT & child = 2) /*若该点是根并有大于等于2的子树*/ coilaNum+; /*关节点总数加一*/ coilai=COILA; /*将该点标记为关节点*/ /*求校园交通图关节点*/void Coila_Query(mgraphType *g) /*关节点查询*/coilaNu

28、m = 0; /*关节点数目初始化*/ for(int i=0; ivexNum; i+) /*对每个结点进行DFS*/memset(visi, 0, sizeof(visi); /*标记数组初始化*/visii = ROOT; /*DFS之前，将该点标记为根节点*/ Dfs_Coila(g, i); /*深度遍历找关节点*/printf(ttt校园图的关节点个数为：%dnnttt分别为:, coilaNum);for(int i=0; ivexNum; i+) /*遍历输出关节点*/ if(coilai = COILA) printf(%st, g-vexsi.name); 6.7 两景点所

29、有路径模块6.7.1详细设计思想两景点间所有路径的查询依然是采用的DFS算法，每一次将起点压入栈内，并将其标记为已访问，然后检查其是否有未访问的邻接点，然后将其邻接点作为起点采取深度搜索做相同的操作，若遇到路不通的时候，依次将栈内的点推出，找其下一个未访问的邻接点，直到找到终点，算法结束。算法结合DFS与递归的方式，效率不高但很容易理解，具体实现如下图所示。图9 深度优先遍历查询任意两个景点之间的所有路径6.7.2 核心代码/*深度优先遍历查询任意两个景点之间的所有路径*int pathStackM,top,count /*路径栈,栈顶及路径计数器*/int visitedM /*入栈(访问)

30、标记*/ void Dfs_Allpath(mgraphType *g,int sNum, int eNum)int dis=0;pathStacktop=sNum; top+; /*将本趟起点入栈*/visitedsNum=1; /*将入栈点标记为已入栈*/for(int i=0; ivexNum; i+) /*表明两点可达，且该点未未被访问*/if(g-edgssNumi0&g-edgssNumi!=INFINITY&!visitedi) if(i=eNum) /*如果深搜到了终点，就输出刚才的路径*/printf(第%d条路:,count+);for(int j=0; j,g-vexsp

31、athStackj.name);if(jedgspathStackjpathStackj+1; dis=dis+g-edgspathStacktop-1eNum; printf(%sn,g-vexseNum.name);printf(总长度是：%dmnn,dis);else /*如果该点不是终点,接着深度搜索*/Dfs_Allpath(g,i,eNum); top-; /*支路全被访问一遍后，顶点出栈*/visitedi=0; /*将出栈点标记为已出栈，允许下次访问*/6.8 游客及管理员菜单模块6.8.1详细设计思想游客菜单的功能有：1.查看公告、2.我要留言。分别对应查看管理员发布的公告以

32、及留言给管理员的功能。这两项功能的灵感均来自校园网认证的网页，登录校园网时我们不仅能及时从公告中获取很多重要消息，也能通过留言反馈功能反馈自己在使用校园网中遇到的问题，对于游客来说，同样如此，所以这两项功能是必要的。管理员菜单的功能有：1. 关闭某景点的游览、2.恢复某景点的游览、3.发布公告、4.查看游客留言。管理员菜单的功能主要体现在能够关闭景点的游览和发布公告，对于现实生活中，这两项功能都是比较贴合实际的。这样游客就能及时知道哪些景点不能游览或者哪条路无法通行。具体实现如下方图10及图11所示。图10 游客菜单图11 管理员菜单6.8.2 核心代码/*管理员菜单*/structchar

33、name20;int close;int reason100;cloNumM;char Affiche200=NULL; /*公告*/void Admin_Menu(mgraphType *g)char buf1024; /*缓冲区*/int len; /*行字符个数*/FILE *fp;int s=1,num,account=0,password=0;while(account!=150708|password!=150708)printf(请输入你的管理账号：);scanf(%d,&account);printf(n请输入你的管理密码：);scanf(%d,&password);if(ac

34、count!=150708|password!=150708)printf(tttt账号或密码错误，请重新输入！n);elseprintf(nttttttt登录成功！nn);Sleep (1000);while(s0&s5)system(cls);Dis_Map();printf(1.关闭景点2.恢复景点3.发布公告 4.查看留言 n);printf(tn请选择你的操作（其余按键返回主菜单）：);scanf(%d,&s);switch(s)case 1:printf(n请输入你要关闭景点的编号：);scanf(%d,&num);if(num12) printf(ntttt对不起，没有该编号对应

35、的景点n);elsecloNumnum-1.close=INFINITY;strcpy(cloNumnum-1.name,g-vexsnum-1.name);printf(n关闭景点成功，请输入关闭%s的原因：,g-vexsnum-1.name);scanf(%s,cloNumnum-1.reason);printf(n关闭景点成功！n);system(pause);break;case 2:printf(n请输入你要恢复景点的编号：);scanf(%d,&num);if(num12) printf(ntttt对不起，没有该编号对应的景点n);elsecloNumnum-1.close=0;p

36、rintf(nt%s景点恢复成功！n,g-vexsnum-1.name);system(pause);break;case 3:printf(n请输入公告内容：);scanf(%s,Affiche);printf(ntttt公告发布成功！n);system(pause);break;case 4:if(fp = fopen(liuyan.txt,r) = NULL)printf(ntttt目前暂无游客留言);exit (1) ; printf(n以下是游客留言：n);while(fgets(buf,1024,fp) != NULL) /*gets读取一行*/len = strlen(buf);buflen-1 = 0; /*去掉换行符*/printf(t%sn,buf,len - 1);printf(n); system(pause); break;default:printf(n); /*游客菜单*/void Tour_Menu(mgraphType *g)int s=1,i=1;char ly250; FILE *fp; /*临时存放用户输入的留言*/while(s0&s3)system(cls);Dis_Map();printf(n n);printf(t 1.查看公告 2.