景区旅游信息管理系统1 实习目的数据结构课程设计是使学生融会贯通本课程所学专业理论知识完成一个较完整的程序设计和程序调试过程以加深学生对所学理论的理解与应用进一步认识和熟悉数据结构中各种算法的实现与具体应用了解解决实际问题的一般过程培养学生综合运用基础理论知识和专业知识去解决实际问题的能力。通过综合性课程设计训练使学生达到以下的目的和要求结合该课程中所学的各种数据结构及其操作设计一个综合的程序解决具体的问题将所学知识应用到具体实际中去学会查阅相关手册和资料通过查阅手册和资料进一步熟悉常用方法的用途和技巧并掌握这些方法的具体含义和如何使用这些方法解决实际问题掌握综合性程序设计的基本过程以及具体问题中数据结构的选择与应用掌握综合性程序设计的调试技术熟悉常用调试方法的使用认真撰写总结报告培养严谨的作风和科学的态度。2 问题描述2.1 设计内容设计一个德州学院校园导游程序为来访的客人提供各种信息查询服务。2.2 具体功能设计德州学院的校园平面图以图中顶点表示校内各景点存放景点名称、代号、简介等信息以边表示路径存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询即查询任意两相景点之间的一条最短的简单路径。提供图中任意景点问路查询即求任意两个景点之间的所有路径。提供德州学院景点的最小生成树查询。提供校园图中多个景点的最佳访问路线查询即求途经这多个景点的最佳路径。图 1 系统功能结构图图 2 德院信息管理地图2.3 所需知识图的各种遍历算法单源最短路径Dijkstra 算法所有顶点对的最短路径Floyd 算法图的基本存储结构邻接矩阵图的最小生成树Kruskal 算法文件的读取存储操作界面交互3 概要设计3.1 数据结构设计系统用到的抽象数据类型定义1ADT graphtype {数据对象 VV 是具有相同特性的数据元素的集合该集合中的所有元素具有相同的特性称为顶点集。数据关系 RR {VR}VR {v,w|v,w属于V且Pv,w,v,w表示从v到w的弧谓词Pv.w定义了弧v,w的意义或信息。基本操作Create_Mapgraphtype *g;} ADT graphtype2ADT Stack{定义栈是限定仅在表尾进行插入或删除操作的线性表。数据对象 D一个集合该集合中所有元素具有相同的特性。数据关系 R若 D 为空则为空栈。若 D 中仅含有一个数据元素则 R 为空集否则 R{ai-1,ai|ai-1,ai 属于 Di2,···约定 an 端为栈顶a1 端为栈底。}基本操作InitStackS; PushS,e; PopS,e; } ADT Stack3.2 函数及功能要求int menu;/*主菜单*/ void Create_Mapgraphtype *g; /*从文件读取信息建立图*/ int Judge_Inputint num; /*判断输入的编号是否合理*/ void Search_Locationgraphtype *g; /*景点信息查询*/ void ShortPathgraphtype *g; /*求景点间最短路径*/ void Floyd_Printgraphtype *g, int sNum, int eNum; /*递归打印两点间最短路*/ void Shortpath_Printgraphtype *g; /*输出并打印两点间的最短路径*/ void Dfs_Printgraphtype *g, int sNum, int eNum; /*深度优先遍历查询两景点间所有路径*/ void BestPathgraphtype *g; /*多顶点间求最佳路径*/ int write_csv;/*疫情防控采集信息*/ int cmpconst void *a, const void*b /*qsort排序函数中使用使edges结构体中的边按照权值大小升序排序*/ void Kruskal_minTreegraphtype *g; /*克鲁斯卡尔求最小生成树*/ void view/*界面加初始化结构体*/ void Dis_Map/*校园景点图的显示*/ void System_Exit;/*退出系统*/ void Allpath_Printgraphtype *g; /*查询两顶点间的所有路径并打印*/3.3 模块调用关系各程序模块之间的调用关系子程序编号见上主函数调用子程序 13。子程序 9 可调用子程序 6。子程序 12 可调用子程序 11。子程序 13 调用子程序 251014,4,689121516。子程序 16 可调用子程序 38。4 详细设计4.1 疫情防控信息采集伪码为防控新型冠状病毒需要收集来访者的基本信息到访人员需要提供自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息。系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和本系统相同的路径下。采集来访人员信息的算法的伪码描述如下int write_csv { systemcls; FILE *fp NULL, *fp_flag NULL; //需要注意 char name[30], phone[18], dangerous[5],health[10]; printf\t\t ┌───────────────────┐ \n; printf\t\t ├── 欢迎您到访德州学院──┤ \n; printf\t\t └───────────────────┘ \n; printf\t由于疫情防控需要本校需要收集您的基本信息与最近概况\n; printf\t\t请输入您的姓名; scanf%s, name; printf\t\t请输入您的手机号; scanf%s, phone; printf\t\t您最近14天是否到访高风险地区; scanf%s, dangerous; printf\t\t您的健康码是否是绿色; scanf%s, health; time_t timep; struct tm *p; //定义时间结构体为了生成csv文件的名字 char nowTime[30]; timetimep; gmtimetimep; sprintfnowTime,%d%.2d%.2d, 1900 p-tm_year, 1 p-tm_mon, p-tm_mday; strcatnowTime, 到访名单.csv; fp_flag fopennowTime, r; // fp_flag检测csv文件是否存在 /*if 存在 不写入表头 如果不存在 写入表头*/ fp fopennowTime, a; if NULL fp return -1; //返回错误代码 //判断csv表是否已经存在 如果存在则不需要写表头 if fp_flag NULL fprintffp, 姓名,手机号,是否到访高风险,健康码是否为绿色,来访时间\n; else fclosefp_flag; fprintffp, %s,%s,%s,%s,%s, name, phone, dangerous, health, asctimelocaltimetimep;//获取本地时区时间 fclosefp; fp NULL; //需要指向空否则会指向原打开文件地址 fp_flag NULL; systemcls; }4.2 录入景点信息模块算法伪码本系统采用邻接矩阵进行图的存储地图信息保存在了“map.txt”文件中文件中包括顶点数目、边的数目、顶点的介绍。校园景点图的读取与创建算法的伪码描述如下void Create_Mapgraphtype *g { int i, j, k, e; FILE *rf; rf fopenmap.txt, r;//景点信息存储在map.txt文件中if rf { fscanfrf, %d%d, g-vexNum, g-edgNum; for i 0; i g-vexNum; i//写如顶点信息 fscanfrf, %d%s%s, g-vexs[i].num, g-vexs[i].name, g-vexs[i].intro; /*初始化邻接矩阵1 对角线元素设置为 02 其它的设置成不可达即无穷大在本系统中 INFINITY 10000*/for i 0; i g-vexNum; i//把权重写入邻接矩阵 for j 0; j g-vexNum; j {if i j g-edge[i][j] 0; else g-edge[i][j] INFINITY; } /*写入边的信息*/ for k 0; k g-edgNum; k { fscanfrf, %d%d%d, i, j, e; g-edge[i][j] g-edge[j][i] e; } fcloserf; } else g-edgNum 0; }4.3 景点信息查询模块算法伪码景点信息查询中的 Judge_Input函数用于判断输入数据是否合法是否是 1-12通过旅客输入自己要查询的景点系统返回该景点的信息景点信息查询模块算法的伪码描述如下int Judge_Inputint num { int i 0;if num -1 return i; if num 1 || num12 { printf\n输入的编号有误请输入1-12之间的数字\n; 1; } return i; }void Search_Locationgraphtype *g { int s; /*Judge_Input函数的功能为检测输入是否为1-12的数字 如果是则返回 0 如果不是 返回 1*/do { printf\n请输入你要查找的景点编号; scanf%d, s; } while Judge_Inputs; /*景点信息存储在结构体g的vexs中*/ printf\n景点名称[%s]\n\n, g-vexs[s - 1].name; printf景点简介 %s\n\n, g-vexs[s - 1].intro; }4.4 两景点间最短路径模块算法伪码两景点间最短路径采用 Floyd 的思想首先初始化一个距离和路径向量利用递归的思想打印二点间的最短路径,两景点间最短路径模块算法的伪码描述如下void Floyd_Printgraphtype *g, int sNum, int eNum { /*递归实现打印两点间的最短路径*/ /*递归的出口 判断路径是否是起点 是否是终点 是否不可达*/ if path[sNum][eNum] -1 || path[sNum][eNum] eNum || path[sNum][eNum] sNum return; else { Floyd_Printg, sNum, path[sNum][eNum]; /*将中间点作为终点继续打印路径*/ printf%s-, g-vexs[path[sNum][eNum]].name; /*打印中间景点名字*/ } } /*输出并打印两点间的最短路径*/void Shortpath_Printgraphtype *g { int sNum, eNum; /*起点编号终点编号*/ do { printf\n请输入起点编号; scanf%d, sNum; } while Judge_InputsNum; do { printf\n请输入终点编号; scanf%d, eNum; } while Judge_InputeNum; printf\n%s到%s的最短距离是%dm\n, g-vexs[--sNum].name, g-vexs[--eNum].name, dist[sNum][eNum];//已经自减 printf\n这是最佳游览路线; printf%s-, g-vexs[sNum].name; /*输出路径上的起点*/ Floyd_Printg, sNum, eNum; /*输出路径上的中间点*/ printf%s\n\n, g-vexs[eNum].name; /*输出路径上的终点*/ }4.5 两景点间所有路径模块算法伪码两景点间所有路径采用深度遍历思想利用路径栈pathStack进行存储路径信息top 作为栈顶标记visited 数组为入栈标记防止形成回路。两景点间所有路径模块算法的伪码描述如下int pathStack[M]; /*路径栈存储路径信息*/ int top; /*栈顶*/ int visited[M]; /*入栈标记防止形成回路*/ int count;void Dfs_Printgraphtype *g, int sNum, int eNum { int dis 0; /*用于记录路径长度*/ pathStack[top] sNum; /*将本趟起点入栈*/ top; visited[sNum] 1; /*将入栈点标记为已入栈*/ for int i 0; i g-vexNum; i { if g-edge[sNum][i] 0 g-edge[sNum][i] ! INFINITY !visited[i] { /*表明前一个入栈点与该点可达且该点未入栈未被访问*/if i eNum { /*如果深度遍历搜到了终点就输出刚才的路径*/ printf第%d条路:, count; for int j 0; j top; j { printf%s-, g-vexs[pathStack[j]].name;if j top - 1 dis dis g-edge[pathStack[j]][pathStack[j 1]]; /*统计路径长度*/ } dis dis g-edge[pathStack[top - 1]][eNum]; /*最后一条路单独出来因为eNum没有入栈*/ printf%s\n, g-vexs[eNum].name; printf总长度是%dm\n\n, dis; } else { Dfs_Printg, i, eNum; /*如果该点不是终点,接着深度搜索*/ top--; /*支路全被访问一遍后顶点出栈*/ visited[i] 0; /*将出栈点标记为已出栈允许下次访问*/ } } } } /*查询任意两个景点之间的所有路径并打印*/void Allpath_Printgraphtype *g { int sNum, eNum; count 1; /*路径计数器*/ top 0; /*栈顶*/ do { printf\n请输入起点编号; scanf%d, sNum; } while Judge_InputsNum; do { printf\n请输入终点编号; scanf%d, eNum; } while Judge_InputeNum; printf\n; Dfs_Printg, sNum - 1, eNum - 1; }4.6 多景点访问路线模块算法伪码多景点间求最佳路径算法采用弗洛伊德初始化的路径和距离向量vNum 数组存储旅客输入的顶点数Judge_Input 判断输入的顶点是否合法利用多景点间求最佳路径算法的伪码描述如下void BestPathgraphtype *g { int vNum[M] { 0 }, j 1; /*记录用户输入的编号信息*/ int d 0; /*统计全程总长*/ printf\n请输入你要游览的第%d个景点的编号输入-1结束输入, j; scanf%d, vNum[j - 1];while vNum[j - 1] ! -1 j 12 { while Judge_InputvNum[j - 1] { printf\n请输入你要游览的第%d个景点编号, j; scanf%d, vNum[j - 1]; } if vNum[j - 1] -1 break; printf\n请输入你要游览的第%d个景点编号, j; scanf%d, vNum[j - 1]; } printf\n这是最佳访问路径; for int i 0; vNum[i] 0 vNum[i 1] 0; i { printf%s-, g-vexs[vNum[i] - 1].name; /*输出路径上的起点*/ Floyd_Printg, vNum[i] - 1, vNum[i 1] - 1; /*利用Floyd算法*/ dist[vNum[i] - 1][vNum[i 1] - 1]; } printf%s\n\n, g-vexs[vNum[j - 2] - 1].name; /*输出路径上的终点*/ printf全程总长为%dm\n\n, d; }4.7 最小生成树Kruskal 思想模块算法伪码最小生成树采用了克鲁斯卡尔的思想结构体 edges 储存边的信息然后利用 C 语言内置函数 cmp 按照 edges.weight 进行排序定义 flag 数组作为标志防止形成回路克鲁斯卡尔求最小生成树算法的伪码描述如下typedef struct edge {//存放边的结构体最大可储存50条 int initial; int end; int weight; } edges; // qsort排序函数中使用使edges结构体中的边按照权值大小升序排序int cmpconst void *a, const void*b { return struct edge*a-weight - struct edge*b-weight; }void Kruskal_minTreegraphtype *g { int i, j,edges_index0; /*把边写入edges数组*/ edges edges[50], minTree[25];; for i 0; i g-vexNum; i { for j 0; j g-vexNum; j { printf%5d\t, g-edge[i][j]; if g-edge[i][j] ! INFINITYij { edges[edges_index].initial j; edges[edges_index].end i; edges[edges_index].weight g-edge[i][j]; } } printf\n; } qsortedges, g-edgNum, sizeofedges[0], cmp;//排序函数 使用c语言内置 /*判断是否形成回路 - 在初始状态下给每个顶点赋予不同的标记对于遍历过程的每条边 - 都有二个状态判断状态是否一致 - 如果一直说明标志在同一个链上 不能链接 - 如果不一致说明二个顶点不在同一个链上可以连接*/int flag[20];//顶点标志 最大20 for i 0; i g-vexNum; i flag[i] i;//初始化这个数组 int minnum 0; for i 0; i g-edgNum; i { int initial edges[i].initial; int end edges[i].end;if flag[initial] ! flag[end] { minTree[minnum] edges[i]; minnum; //将标志和end相同的全部更换成intial for j 0; j g-vexNum; j if flag[end] flag[j] flag[j] flag[initial]; flag[end] flag[initial]; } //如果边的最小生成树边的数量等于顶点的数量-1跳出循环 if minnum g-vexNum - 1 break; } //输出语句 printf\t德州学院地图最小生成树为\n; for i 0; i g-vexNum-1; i { printf\t\t\t\t %d.%s-%d.%s\n, minTree[i].initial1, g-vexs[minTree[i].initial].name, minTree[i].end1, g-vexs[minTree[i].end].name; } }5 调试与测试结果分析由于使用的编译环境不同输入时使用 scanf 报错 scanf 函数的 C4996 错误在网上查找后发现在 2 种解决办法1在项目-TestProject3 属性-预处理器-预处理器定义在它里面添加_CRT_SECURE_NO_WARNINGS2将项目属性中 SDL 检查关闭在调试过程中发现在将来访人员的个人信息写入到 CSV 文件时表头总是重复写入经过查询发现需要定义一个空的文件指针判断 CSV 文件时否存在如果不存在写入表头。如果存在则只需写入基本信息。又发现写入到 CSV 文件的信息总在同一个表格中最后经过查询CSV 文件为逗号分隔符在写入文件信息的时候不能以空格分隔应该使用逗号来进行分割。5.1 疫情防控信息采集界面当我们运行系统后首先出现访问信息登记界面。到访人员需要输入自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息如图 3 所示。图 3 疫情防控信息采集界面系统获取输入的信息系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和系统相同的路径下如图 4 所示。图 4 疫情防控信息文件界面5.2 德州学院校园导游主界面填写完信息后即可进入主界面。主界面包括六个选项景点信息查询两景点间最短路径查询两景点间所有路径查询多景点间访问路线查询德院最小生成树退出信息查询系统如图 5 所示。图 5 德州学院校园导游主界面5.3 景点信息查询查询界面景点信息查询。选择该项可进行各景点的信息查询景点信息查询界面会显示德州学院的具体地图通过选择要查询的景点系统返回该景点的信息。例如选择擢英园公寓如图 6 所示。图 6 景点信息查询界面5.4 两景点间最短路径查询界面两景点间最短路径查询选择该项可进行两个景点之间最短路径的查询根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的最短路程为多少以及两景点之间的具体路线。例如输入起始编号为 1 德州学院西大门终点编号为 7 紫藤长廊如图 7 所示。图 7 两景点间最短路径查询界面当输入编号有误时例如输入起始编号为 1 德州学院西大门终点编号为 15如图 8 所示。图 8 景点编号输入有误界面5.5 两景点间所有路径查询界面两景点间所有路径查询选择该项可显示两个景点之间的所有路经, 根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的所有路线。例如输入起始编号为 1 德州学院西大门终点编号为 8 厚德楼如图 9 所示。图 9 两景点间所有路径查询查询界面5.6 多景点间访问路线查询界面多景点间访问路线查询选择该项可进行从一个景点到多个景点的最短路径查询根据系统提示输入你要游览的第 1 个景点的编号再输入你要游览的第 2 个景点的编号依次进行直到你输入的编号为-1代表结束。系统会显示你输入所有顶点的最佳访问路径以及全程总长。例如输入游览的第 1 个景点的编号为 1 德州学院西大门输入游览的第 2 个景点的编号 3 擢英园公寓输入游览的第 3 个景点的编号为 8 厚德楼下一步输入-1 代表游览结束系统会显示最佳访问路径如图 10 所示。图 10 多景点间访问路线查询界面5.7 德院最小生成树查询界面德院最小生成树选择该选项可以看到本系统的邻接矩阵和最小生成树中的边如图 11 所示。图 11 德州学院最小生成树查询界面5.8 退出咨询系统退出咨询系统在主界面输入 6即出现欢迎您到访德州学院并出现德州学院的英文缩写如图 12 所示。图 12 退出咨询系统界面6 使用说明本系统为德州学院校园导游程序为来访的客人提供各种信息查询服务。系统运行后为防控新型冠状病毒首先出现访问信息登记界面。到访人员需要输入自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息。系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和系统相同的路径下。填写完信息后即可进入主界面。主界面包括六个选项1选项 1景点信息查询。选择该项可进行各景点的信息查询景点信息查询界面会显示德州学院的具体地图通过选择要查询的景点系统返回该景点的信息。例如选择 3 擢英园公寓系统会显示景点名称 [擢英苑公寓]景点简介 擢英苑是位于德州学院内2020 级新生学生公寓德州学院男神聚集地。2选项 2两景点间最短路径查询选择该项可进行两个景点之间最短路径的查询根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的最短路程为多少以及两景点之间的具体路线。例如输入起始编号为 1 德州学院西大门终点编号为 7 紫藤长廊系统会显示德州学院西大门到紫藤长廊的最短距离是1180m这是最佳游览路线德州学院西大门- 日晞园- 体育楼- 紫藤长廊3选项 3两景点间所有路径查询选择该项可显示两个景点之间的所有路经, 根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的所有路线。例如输入起始编号为 1 德州学院西大门终点编号为 5 体育楼系统会显示第 1 条路:德州学院西大门- 日晞园- 体育馆- 体育楼总长度是950m第 2 条路:德州学院西大门- 日晞园- 体育楼总长度是600m第 3 条路:德州学院西大门- 擢英园公寓- 日晞园- 体育馆- 体育楼总长度是1430m第 4 条路:德州学院西大门- 擢英园公寓- 日晞园- 体育楼总长度是1080m4选项 4多景点间访问路线查询选择该项可进行从一个景点到多个景点的最短路径查询根据系统提示输入你要游览的第 1 个景点的编号再输入你要游览的第 2 个景点的编号依次进行直到你输入的编号为-1代表结束。系统会显示你输入所有顶点的最佳访问路径以及全程总长。例如输入游览的第 1 个景点的编号为 1 德州学院西大门输入游览的第 2 个景点的编号 3 擢英园公寓输入游览的第 3 个景点的编号为 8 厚德楼下一步输入-1 代表游览结束系统会显示最佳访问路径德州学院西大门- 擢英园公寓- 日晞园- 体育楼- 紫藤长廊- 厚德楼全程总长为1760m。5选项 5德院最小生成树选择该选项可以看到本系统的邻接矩阵和最小生成树中的边。6选项 6退出景点程序选择该项将退出景点程序进入疫情防控输入界面。7 总结随着德州学院知名度的提高来访的客人逐渐增多因此开发了德州学院校园导游程序为来访的客人提供各种信息查询服务。具体功能有设计德州学院的校园平面图以图中顶点表示校内各景点存放景点名称、代号、简介等信息以边表示路径存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询即查询任意两相景点之间的一条最短的简单路径。提供图中任意景点问路查询即求任意两个景点之间的所有路径。提供校园图中多个景点的最佳访问路线查询即求途经这多个景点的最佳路径。本系统仍存在很多的不足例如疫情防控模块没有判断输入的手机号是否为 11 位数字。但是由于时间等原因没有继续完善系统。回想这次课程设计感触颇深从小组选题到不断完善系统。这次课程设计是我们小组一起合力完成的让我们深刻体会到团队的重要性。在设计过程中虽然遇到了一些问题但经过一次又一次的思考,一遍又一遍的检查终于找出了原因所在也暴露出了前期我们在这方面的知识欠缺和经验不足。此次设计也让我们明白了思路即出路有什么不懂不明白的地方要及时请教或上网查询只要认真钻研动脑思考动手实践就没有弄不懂的知识收获颇丰。最后在戎老师的指导下终于游逆而解。在今后社会的发展和学习实践过程中一定要不懈努力不能遇到问题就想到要退缩一定要不厌其烦的发现问题所在然后一一进行解决只有这样才能成功的做成想做的事。8 参考文献[1]曾海尚鲜连主编.数据结构[M].北京高等教育出版社.2019.[2]管纪文刘大有编.数据结构[M].北京高等教育出版社.1985.[3]许卓群编.数据结构[M].北京高等教育出版社.1987.[4]吴陈著.数据结构[M].北京科学出版社.2016.[5]陈锐于聚然主编.数据结构[M].合肥合肥工业大学出版社.2012.[6]廖滨华郭思培唐向阳编著.数据结构[M].武汉湖北科学技术出版社.2006.[7]齐景嘉主编陈炯张三群苗树红编.数据结构[M].南京东南大学出版社.2006.[8]唐策善黄刘生编著.数据结构[M].合肥中国科学技术大学出版社.1992.[9]叶乃文郑晓红编著.数据结构[M].北京人民邮电出版社.2001.[10]王忠义主编.数据结构[M].西安西安交通大学出版社.2003.[11]周娅主编.数据结构[M].重庆重庆大学出版社.2003.[12]冯建新主编.数据结构[M].沈阳东北财经大学出版社.2000.[13]陆松年等编著.数据结构[M].上海上海交通大学出版社.1995.♻️ 资源大小4.88MB➡️资源下载https://download.csdn.net/download/s1t16/87415922注更多内容可关注微信公众号【神仙别闹】如当前文章或代码侵犯了您的权益请私信作者删除
基于C语言实现的（控制台）景区旅游信息管理系统
景区旅游信息管理系统1 实习目的数据结构课程设计是使学生融会贯通本课程所学专业理论知识完成一个较完整的程序设计和程序调试过程以加深学生对所学理论的理解与应用进一步认识和熟悉数据结构中各种算法的实现与具体应用了解解决实际问题的一般过程培养学生综合运用基础理论知识和专业知识去解决实际问题的能力。通过综合性课程设计训练使学生达到以下的目的和要求结合该课程中所学的各种数据结构及其操作设计一个综合的程序解决具体的问题将所学知识应用到具体实际中去学会查阅相关手册和资料通过查阅手册和资料进一步熟悉常用方法的用途和技巧并掌握这些方法的具体含义和如何使用这些方法解决实际问题掌握综合性程序设计的基本过程以及具体问题中数据结构的选择与应用掌握综合性程序设计的调试技术熟悉常用调试方法的使用认真撰写总结报告培养严谨的作风和科学的态度。2 问题描述2.1 设计内容设计一个德州学院校园导游程序为来访的客人提供各种信息查询服务。2.2 具体功能设计德州学院的校园平面图以图中顶点表示校内各景点存放景点名称、代号、简介等信息以边表示路径存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询即查询任意两相景点之间的一条最短的简单路径。提供图中任意景点问路查询即求任意两个景点之间的所有路径。提供德州学院景点的最小生成树查询。提供校园图中多个景点的最佳访问路线查询即求途经这多个景点的最佳路径。图 1 系统功能结构图图 2 德院信息管理地图2.3 所需知识图的各种遍历算法单源最短路径Dijkstra 算法所有顶点对的最短路径Floyd 算法图的基本存储结构邻接矩阵图的最小生成树Kruskal 算法文件的读取存储操作界面交互3 概要设计3.1 数据结构设计系统用到的抽象数据类型定义1ADT graphtype {数据对象 VV 是具有相同特性的数据元素的集合该集合中的所有元素具有相同的特性称为顶点集。数据关系 RR {VR}VR {v,w|v,w属于V且Pv,w,v,w表示从v到w的弧谓词Pv.w定义了弧v,w的意义或信息。基本操作Create_Mapgraphtype *g;} ADT graphtype2ADT Stack{定义栈是限定仅在表尾进行插入或删除操作的线性表。数据对象 D一个集合该集合中所有元素具有相同的特性。数据关系 R若 D 为空则为空栈。若 D 中仅含有一个数据元素则 R 为空集否则 R{ai-1,ai|ai-1,ai 属于 Di2,···约定 an 端为栈顶a1 端为栈底。}基本操作InitStackS; PushS,e; PopS,e; } ADT Stack3.2 函数及功能要求int menu;/*主菜单*/ void Create_Mapgraphtype *g; /*从文件读取信息建立图*/ int Judge_Inputint num; /*判断输入的编号是否合理*/ void Search_Locationgraphtype *g; /*景点信息查询*/ void ShortPathgraphtype *g; /*求景点间最短路径*/ void Floyd_Printgraphtype *g, int sNum, int eNum; /*递归打印两点间最短路*/ void Shortpath_Printgraphtype *g; /*输出并打印两点间的最短路径*/ void Dfs_Printgraphtype *g, int sNum, int eNum; /*深度优先遍历查询两景点间所有路径*/ void BestPathgraphtype *g; /*多顶点间求最佳路径*/ int write_csv;/*疫情防控采集信息*/ int cmpconst void *a, const void*b /*qsort排序函数中使用使edges结构体中的边按照权值大小升序排序*/ void Kruskal_minTreegraphtype *g; /*克鲁斯卡尔求最小生成树*/ void view/*界面加初始化结构体*/ void Dis_Map/*校园景点图的显示*/ void System_Exit;/*退出系统*/ void Allpath_Printgraphtype *g; /*查询两顶点间的所有路径并打印*/3.3 模块调用关系各程序模块之间的调用关系子程序编号见上主函数调用子程序 13。子程序 9 可调用子程序 6。子程序 12 可调用子程序 11。子程序 13 调用子程序 251014,4,689121516。子程序 16 可调用子程序 38。4 详细设计4.1 疫情防控信息采集伪码为防控新型冠状病毒需要收集来访者的基本信息到访人员需要提供自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息。系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和本系统相同的路径下。采集来访人员信息的算法的伪码描述如下int write_csv { systemcls; FILE *fp NULL, *fp_flag NULL; //需要注意 char name[30], phone[18], dangerous[5],health[10]; printf\t\t ┌───────────────────┐ \n; printf\t\t ├── 欢迎您到访德州学院──┤ \n; printf\t\t └───────────────────┘ \n; printf\t由于疫情防控需要本校需要收集您的基本信息与最近概况\n; printf\t\t请输入您的姓名; scanf%s, name; printf\t\t请输入您的手机号; scanf%s, phone; printf\t\t您最近14天是否到访高风险地区; scanf%s, dangerous; printf\t\t您的健康码是否是绿色; scanf%s, health; time_t timep; struct tm *p; //定义时间结构体为了生成csv文件的名字 char nowTime[30]; timetimep; gmtimetimep; sprintfnowTime,%d%.2d%.2d, 1900 p-tm_year, 1 p-tm_mon, p-tm_mday; strcatnowTime, 到访名单.csv; fp_flag fopennowTime, r; // fp_flag检测csv文件是否存在 /*if 存在 不写入表头 如果不存在 写入表头*/ fp fopennowTime, a; if NULL fp return -1; //返回错误代码 //判断csv表是否已经存在 如果存在则不需要写表头 if fp_flag NULL fprintffp, 姓名,手机号,是否到访高风险,健康码是否为绿色,来访时间\n; else fclosefp_flag; fprintffp, %s,%s,%s,%s,%s, name, phone, dangerous, health, asctimelocaltimetimep;//获取本地时区时间 fclosefp; fp NULL; //需要指向空否则会指向原打开文件地址 fp_flag NULL; systemcls; }4.2 录入景点信息模块算法伪码本系统采用邻接矩阵进行图的存储地图信息保存在了“map.txt”文件中文件中包括顶点数目、边的数目、顶点的介绍。校园景点图的读取与创建算法的伪码描述如下void Create_Mapgraphtype *g { int i, j, k, e; FILE *rf; rf fopenmap.txt, r;//景点信息存储在map.txt文件中if rf { fscanfrf, %d%d, g-vexNum, g-edgNum; for i 0; i g-vexNum; i//写如顶点信息 fscanfrf, %d%s%s, g-vexs[i].num, g-vexs[i].name, g-vexs[i].intro; /*初始化邻接矩阵1 对角线元素设置为 02 其它的设置成不可达即无穷大在本系统中 INFINITY 10000*/for i 0; i g-vexNum; i//把权重写入邻接矩阵 for j 0; j g-vexNum; j {if i j g-edge[i][j] 0; else g-edge[i][j] INFINITY; } /*写入边的信息*/ for k 0; k g-edgNum; k { fscanfrf, %d%d%d, i, j, e; g-edge[i][j] g-edge[j][i] e; } fcloserf; } else g-edgNum 0; }4.3 景点信息查询模块算法伪码景点信息查询中的 Judge_Input函数用于判断输入数据是否合法是否是 1-12通过旅客输入自己要查询的景点系统返回该景点的信息景点信息查询模块算法的伪码描述如下int Judge_Inputint num { int i 0;if num -1 return i; if num 1 || num12 { printf\n输入的编号有误请输入1-12之间的数字\n; 1; } return i; }void Search_Locationgraphtype *g { int s; /*Judge_Input函数的功能为检测输入是否为1-12的数字 如果是则返回 0 如果不是 返回 1*/do { printf\n请输入你要查找的景点编号; scanf%d, s; } while Judge_Inputs; /*景点信息存储在结构体g的vexs中*/ printf\n景点名称[%s]\n\n, g-vexs[s - 1].name; printf景点简介 %s\n\n, g-vexs[s - 1].intro; }4.4 两景点间最短路径模块算法伪码两景点间最短路径采用 Floyd 的思想首先初始化一个距离和路径向量利用递归的思想打印二点间的最短路径,两景点间最短路径模块算法的伪码描述如下void Floyd_Printgraphtype *g, int sNum, int eNum { /*递归实现打印两点间的最短路径*/ /*递归的出口 判断路径是否是起点 是否是终点 是否不可达*/ if path[sNum][eNum] -1 || path[sNum][eNum] eNum || path[sNum][eNum] sNum return; else { Floyd_Printg, sNum, path[sNum][eNum]; /*将中间点作为终点继续打印路径*/ printf%s-, g-vexs[path[sNum][eNum]].name; /*打印中间景点名字*/ } } /*输出并打印两点间的最短路径*/void Shortpath_Printgraphtype *g { int sNum, eNum; /*起点编号终点编号*/ do { printf\n请输入起点编号; scanf%d, sNum; } while Judge_InputsNum; do { printf\n请输入终点编号; scanf%d, eNum; } while Judge_InputeNum; printf\n%s到%s的最短距离是%dm\n, g-vexs[--sNum].name, g-vexs[--eNum].name, dist[sNum][eNum];//已经自减 printf\n这是最佳游览路线; printf%s-, g-vexs[sNum].name; /*输出路径上的起点*/ Floyd_Printg, sNum, eNum; /*输出路径上的中间点*/ printf%s\n\n, g-vexs[eNum].name; /*输出路径上的终点*/ }4.5 两景点间所有路径模块算法伪码两景点间所有路径采用深度遍历思想利用路径栈pathStack进行存储路径信息top 作为栈顶标记visited 数组为入栈标记防止形成回路。两景点间所有路径模块算法的伪码描述如下int pathStack[M]; /*路径栈存储路径信息*/ int top; /*栈顶*/ int visited[M]; /*入栈标记防止形成回路*/ int count;void Dfs_Printgraphtype *g, int sNum, int eNum { int dis 0; /*用于记录路径长度*/ pathStack[top] sNum; /*将本趟起点入栈*/ top; visited[sNum] 1; /*将入栈点标记为已入栈*/ for int i 0; i g-vexNum; i { if g-edge[sNum][i] 0 g-edge[sNum][i] ! INFINITY !visited[i] { /*表明前一个入栈点与该点可达且该点未入栈未被访问*/if i eNum { /*如果深度遍历搜到了终点就输出刚才的路径*/ printf第%d条路:, count; for int j 0; j top; j { printf%s-, g-vexs[pathStack[j]].name;if j top - 1 dis dis g-edge[pathStack[j]][pathStack[j 1]]; /*统计路径长度*/ } dis dis g-edge[pathStack[top - 1]][eNum]; /*最后一条路单独出来因为eNum没有入栈*/ printf%s\n, g-vexs[eNum].name; printf总长度是%dm\n\n, dis; } else { Dfs_Printg, i, eNum; /*如果该点不是终点,接着深度搜索*/ top--; /*支路全被访问一遍后顶点出栈*/ visited[i] 0; /*将出栈点标记为已出栈允许下次访问*/ } } } } /*查询任意两个景点之间的所有路径并打印*/void Allpath_Printgraphtype *g { int sNum, eNum; count 1; /*路径计数器*/ top 0; /*栈顶*/ do { printf\n请输入起点编号; scanf%d, sNum; } while Judge_InputsNum; do { printf\n请输入终点编号; scanf%d, eNum; } while Judge_InputeNum; printf\n; Dfs_Printg, sNum - 1, eNum - 1; }4.6 多景点访问路线模块算法伪码多景点间求最佳路径算法采用弗洛伊德初始化的路径和距离向量vNum 数组存储旅客输入的顶点数Judge_Input 判断输入的顶点是否合法利用多景点间求最佳路径算法的伪码描述如下void BestPathgraphtype *g { int vNum[M] { 0 }, j 1; /*记录用户输入的编号信息*/ int d 0; /*统计全程总长*/ printf\n请输入你要游览的第%d个景点的编号输入-1结束输入, j; scanf%d, vNum[j - 1];while vNum[j - 1] ! -1 j 12 { while Judge_InputvNum[j - 1] { printf\n请输入你要游览的第%d个景点编号, j; scanf%d, vNum[j - 1]; } if vNum[j - 1] -1 break; printf\n请输入你要游览的第%d个景点编号, j; scanf%d, vNum[j - 1]; } printf\n这是最佳访问路径; for int i 0; vNum[i] 0 vNum[i 1] 0; i { printf%s-, g-vexs[vNum[i] - 1].name; /*输出路径上的起点*/ Floyd_Printg, vNum[i] - 1, vNum[i 1] - 1; /*利用Floyd算法*/ dist[vNum[i] - 1][vNum[i 1] - 1]; } printf%s\n\n, g-vexs[vNum[j - 2] - 1].name; /*输出路径上的终点*/ printf全程总长为%dm\n\n, d; }4.7 最小生成树Kruskal 思想模块算法伪码最小生成树采用了克鲁斯卡尔的思想结构体 edges 储存边的信息然后利用 C 语言内置函数 cmp 按照 edges.weight 进行排序定义 flag 数组作为标志防止形成回路克鲁斯卡尔求最小生成树算法的伪码描述如下typedef struct edge {//存放边的结构体最大可储存50条 int initial; int end; int weight; } edges; // qsort排序函数中使用使edges结构体中的边按照权值大小升序排序int cmpconst void *a, const void*b { return struct edge*a-weight - struct edge*b-weight; }void Kruskal_minTreegraphtype *g { int i, j,edges_index0; /*把边写入edges数组*/ edges edges[50], minTree[25];; for i 0; i g-vexNum; i { for j 0; j g-vexNum; j { printf%5d\t, g-edge[i][j]; if g-edge[i][j] ! INFINITYij { edges[edges_index].initial j; edges[edges_index].end i; edges[edges_index].weight g-edge[i][j]; } } printf\n; } qsortedges, g-edgNum, sizeofedges[0], cmp;//排序函数 使用c语言内置 /*判断是否形成回路 - 在初始状态下给每个顶点赋予不同的标记对于遍历过程的每条边 - 都有二个状态判断状态是否一致 - 如果一直说明标志在同一个链上 不能链接 - 如果不一致说明二个顶点不在同一个链上可以连接*/int flag[20];//顶点标志 最大20 for i 0; i g-vexNum; i flag[i] i;//初始化这个数组 int minnum 0; for i 0; i g-edgNum; i { int initial edges[i].initial; int end edges[i].end;if flag[initial] ! flag[end] { minTree[minnum] edges[i]; minnum; //将标志和end相同的全部更换成intial for j 0; j g-vexNum; j if flag[end] flag[j] flag[j] flag[initial]; flag[end] flag[initial]; } //如果边的最小生成树边的数量等于顶点的数量-1跳出循环 if minnum g-vexNum - 1 break; } //输出语句 printf\t德州学院地图最小生成树为\n; for i 0; i g-vexNum-1; i { printf\t\t\t\t %d.%s-%d.%s\n, minTree[i].initial1, g-vexs[minTree[i].initial].name, minTree[i].end1, g-vexs[minTree[i].end].name; } }5 调试与测试结果分析由于使用的编译环境不同输入时使用 scanf 报错 scanf 函数的 C4996 错误在网上查找后发现在 2 种解决办法1在项目-TestProject3 属性-预处理器-预处理器定义在它里面添加_CRT_SECURE_NO_WARNINGS2将项目属性中 SDL 检查关闭在调试过程中发现在将来访人员的个人信息写入到 CSV 文件时表头总是重复写入经过查询发现需要定义一个空的文件指针判断 CSV 文件时否存在如果不存在写入表头。如果存在则只需写入基本信息。又发现写入到 CSV 文件的信息总在同一个表格中最后经过查询CSV 文件为逗号分隔符在写入文件信息的时候不能以空格分隔应该使用逗号来进行分割。5.1 疫情防控信息采集界面当我们运行系统后首先出现访问信息登记界面。到访人员需要输入自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息如图 3 所示。图 3 疫情防控信息采集界面系统获取输入的信息系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和系统相同的路径下如图 4 所示。图 4 疫情防控信息文件界面5.2 德州学院校园导游主界面填写完信息后即可进入主界面。主界面包括六个选项景点信息查询两景点间最短路径查询两景点间所有路径查询多景点间访问路线查询德院最小生成树退出信息查询系统如图 5 所示。图 5 德州学院校园导游主界面5.3 景点信息查询查询界面景点信息查询。选择该项可进行各景点的信息查询景点信息查询界面会显示德州学院的具体地图通过选择要查询的景点系统返回该景点的信息。例如选择擢英园公寓如图 6 所示。图 6 景点信息查询界面5.4 两景点间最短路径查询界面两景点间最短路径查询选择该项可进行两个景点之间最短路径的查询根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的最短路程为多少以及两景点之间的具体路线。例如输入起始编号为 1 德州学院西大门终点编号为 7 紫藤长廊如图 7 所示。图 7 两景点间最短路径查询界面当输入编号有误时例如输入起始编号为 1 德州学院西大门终点编号为 15如图 8 所示。图 8 景点编号输入有误界面5.5 两景点间所有路径查询界面两景点间所有路径查询选择该项可显示两个景点之间的所有路经, 根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的所有路线。例如输入起始编号为 1 德州学院西大门终点编号为 8 厚德楼如图 9 所示。图 9 两景点间所有路径查询查询界面5.6 多景点间访问路线查询界面多景点间访问路线查询选择该项可进行从一个景点到多个景点的最短路径查询根据系统提示输入你要游览的第 1 个景点的编号再输入你要游览的第 2 个景点的编号依次进行直到你输入的编号为-1代表结束。系统会显示你输入所有顶点的最佳访问路径以及全程总长。例如输入游览的第 1 个景点的编号为 1 德州学院西大门输入游览的第 2 个景点的编号 3 擢英园公寓输入游览的第 3 个景点的编号为 8 厚德楼下一步输入-1 代表游览结束系统会显示最佳访问路径如图 10 所示。图 10 多景点间访问路线查询界面5.7 德院最小生成树查询界面德院最小生成树选择该选项可以看到本系统的邻接矩阵和最小生成树中的边如图 11 所示。图 11 德州学院最小生成树查询界面5.8 退出咨询系统退出咨询系统在主界面输入 6即出现欢迎您到访德州学院并出现德州学院的英文缩写如图 12 所示。图 12 退出咨询系统界面6 使用说明本系统为德州学院校园导游程序为来访的客人提供各种信息查询服务。系统运行后为防控新型冠状病毒首先出现访问信息登记界面。到访人员需要输入自己的姓名、手机号、最近 14 天是否到访过高风险地区、健康码是否为绿色等信息。系统将自动判断日期并以“年月日来访名单.csv”作为 CSV 文件的名字。这些信息将会写入 CSV 文件并保存和系统相同的路径下。填写完信息后即可进入主界面。主界面包括六个选项1选项 1景点信息查询。选择该项可进行各景点的信息查询景点信息查询界面会显示德州学院的具体地图通过选择要查询的景点系统返回该景点的信息。例如选择 3 擢英园公寓系统会显示景点名称 [擢英苑公寓]景点简介 擢英苑是位于德州学院内2020 级新生学生公寓德州学院男神聚集地。2选项 2两景点间最短路径查询选择该项可进行两个景点之间最短路径的查询根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的最短路程为多少以及两景点之间的具体路线。例如输入起始编号为 1 德州学院西大门终点编号为 7 紫藤长廊系统会显示德州学院西大门到紫藤长廊的最短距离是1180m这是最佳游览路线德州学院西大门- 日晞园- 体育楼- 紫藤长廊3选项 3两景点间所有路径查询选择该项可显示两个景点之间的所有路经, 根据系统提示首先输入起点编号再输入终点编号系统会给出两景点的所有路线。例如输入起始编号为 1 德州学院西大门终点编号为 5 体育楼系统会显示第 1 条路:德州学院西大门- 日晞园- 体育馆- 体育楼总长度是950m第 2 条路:德州学院西大门- 日晞园- 体育楼总长度是600m第 3 条路:德州学院西大门- 擢英园公寓- 日晞园- 体育馆- 体育楼总长度是1430m第 4 条路:德州学院西大门- 擢英园公寓- 日晞园- 体育楼总长度是1080m4选项 4多景点间访问路线查询选择该项可进行从一个景点到多个景点的最短路径查询根据系统提示输入你要游览的第 1 个景点的编号再输入你要游览的第 2 个景点的编号依次进行直到你输入的编号为-1代表结束。系统会显示你输入所有顶点的最佳访问路径以及全程总长。例如输入游览的第 1 个景点的编号为 1 德州学院西大门输入游览的第 2 个景点的编号 3 擢英园公寓输入游览的第 3 个景点的编号为 8 厚德楼下一步输入-1 代表游览结束系统会显示最佳访问路径德州学院西大门- 擢英园公寓- 日晞园- 体育楼- 紫藤长廊- 厚德楼全程总长为1760m。5选项 5德院最小生成树选择该选项可以看到本系统的邻接矩阵和最小生成树中的边。6选项 6退出景点程序选择该项将退出景点程序进入疫情防控输入界面。7 总结随着德州学院知名度的提高来访的客人逐渐增多因此开发了德州学院校园导游程序为来访的客人提供各种信息查询服务。具体功能有设计德州学院的校园平面图以图中顶点表示校内各景点存放景点名称、代号、简介等信息以边表示路径存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询即查询任意两相景点之间的一条最短的简单路径。提供图中任意景点问路查询即求任意两个景点之间的所有路径。提供校园图中多个景点的最佳访问路线查询即求途经这多个景点的最佳路径。本系统仍存在很多的不足例如疫情防控模块没有判断输入的手机号是否为 11 位数字。但是由于时间等原因没有继续完善系统。回想这次课程设计感触颇深从小组选题到不断完善系统。这次课程设计是我们小组一起合力完成的让我们深刻体会到团队的重要性。在设计过程中虽然遇到了一些问题但经过一次又一次的思考,一遍又一遍的检查终于找出了原因所在也暴露出了前期我们在这方面的知识欠缺和经验不足。此次设计也让我们明白了思路即出路有什么不懂不明白的地方要及时请教或上网查询只要认真钻研动脑思考动手实践就没有弄不懂的知识收获颇丰。最后在戎老师的指导下终于游逆而解。在今后社会的发展和学习实践过程中一定要不懈努力不能遇到问题就想到要退缩一定要不厌其烦的发现问题所在然后一一进行解决只有这样才能成功的做成想做的事。8 参考文献[1]曾海尚鲜连主编.数据结构[M].北京高等教育出版社.2019.[2]管纪文刘大有编.数据结构[M].北京高等教育出版社.1985.[3]许卓群编.数据结构[M].北京高等教育出版社.1987.[4]吴陈著.数据结构[M].北京科学出版社.2016.[5]陈锐于聚然主编.数据结构[M].合肥合肥工业大学出版社.2012.[6]廖滨华郭思培唐向阳编著.数据结构[M].武汉湖北科学技术出版社.2006.[7]齐景嘉主编陈炯张三群苗树红编.数据结构[M].南京东南大学出版社.2006.[8]唐策善黄刘生编著.数据结构[M].合肥中国科学技术大学出版社.1992.[9]叶乃文郑晓红编著.数据结构[M].北京人民邮电出版社.2001.[10]王忠义主编.数据结构[M].西安西安交通大学出版社.2003.[11]周娅主编.数据结构[M].重庆重庆大学出版社.2003.[12]冯建新主编.数据结构[M].沈阳东北财经大学出版社.2000.[13]陆松年等编著.数据结构[M].上海上海交通大学出版社.1995.♻️ 资源大小4.88MB➡️资源下载https://download.csdn.net/download/s1t16/87415922注更多内容可关注微信公众号【神仙别闹】如当前文章或代码侵犯了您的权益请私信作者删除
