校园导航系统

1 题号 第七题题号 第七题 题目 校园导航问题题目 校园导航问题 1 需求分析 需求分析 设计你的学校的平面图 至少包括 10 个以上的景点 场所 每两个景点间可以有不 同的路 且路长也可能不同 找出从任意景点到达另一景点的最佳路径 最短路径 要求 要求 1 以图中顶点表示校园内各景点 存放景点名称 代号 简介等信息 以边表示路 径 存放路径长度等有关信息 2 为来访客人提供图中任意景点相关信息的查询 3 为来访客人提供任意景点的问路查询 即查询任意两个景点之间的一条最短路径 4 修改景点信息 实现提示 一般情况下 校园的道路是双向通行的 可设计校园平面图是一个无向网 顶点和边 均含有相关信息 选做内容 1 提供图的编辑功能 增 删景点 增 删道路 修改已有信息等 2 校园导游图的仿真界面 2 设计 设计 2 1 设计思想 设计思想 数据结构设计 数据结构设计 1 图 采用邻接矩阵存储 其中图所用到的结构体为 typedef struct SeqList vertices 表示图中的顶点 int Edge MaxVertices MaxVertices 表示图中的边 int numOfEdge 表示图中边的数目 AdjMGraph 2 景点 用顺序表存储 所用到的结构体为 typedef struct char name 20 顶点名称 int code 顶点代号 char introduction 50 顶点信息简介 DataType 2 3 景点之间的连接描述 所用到的结构体为 typedef struct int row int col int weight RowColWeight 用图来存放所提供的所有景点 然后用线性表来存放每一个景点的信息 其中包括景点的名称 代号 信息简介 以及其它的一些信息 这样就将对景 点的操作 变成对图中各顶点的操作 算法设计 算法设计 关于本课题的算法 很大部分来源于这学期数据结构课程的学习 其中包括 图的创建 线性表的一些操作 对于具体的问题实现 都有不同的算法 在下面的分析中 我将详细说明 2 2 设计表示 设计表示 函数调用关系及函数说明函数调用关系及函数说明 首先 main 函数调用 Creat 函数 用来创建图 然后调用 menu 函数来选择用户所 要进行的操作 其中 menu 函数就是一个菜单供使用者来选择他所要进行的相关操作 比 如信息的查询 最短路径查询之类 对于要求 1 以图中顶点表示校园内各景点 存放景点名称 代号 简介等信 息 以边表示路径 存放路径长度等有关信息 图的创建设计流程图为 Creat 函数原型为 函数原型为 void Creat AdjMGraph G DataType v RowColWeight E int n int e 其中 G 为所创建的图结构体对象 v 为所有顶点的集合 它是 DataType 型 这个类型前面已经介绍过 E 存放着各顶点之间的连接关系 它是 RowColWeight 型 前面也介绍过 n 表示顶点的个数 e 表示边数 Creat 函数的功能就是实现图的创建 将已知的景点的一些信息 转换成图 的 信息 并进行存储 对于要求 2 为来访客人提供图中任意景点相关信息的查询 流程图为 main Creat menu main Creat menu Information1 Information 3 menu 函数的原型为 函数的原型为 void menu 他就是一个菜单 供用户选择他们所要进行的操作 Information1 函数原型为 函数原型为 void Information1 它的功能就是输入查询景点的信息 并调用 Information Information 函数原型为 函数原型为 void Information AdjMGraph G char scenery G 依然是所创建的图的结构 体对象 后面所有的 G 都是表示这个意思 scenery 是在 Information1 中输入的景点的 名称 此函数的功能就是根据输入的景点的名称来查询其相关的信息 对于要求 3 为来访客人提供任意景点的问路查询 即查询任意两个景点之间的一 条 最短路径 流程图为 Path1 函数原型为 函数原型为 void Path1 它的功能就是输入查询景点的名称 并调用 Path Path 函数原型为 函数原型为 void Path AdjMGraph G char sceneryname char sceneryname1 其中 sceneryname sceneryname1 就是在 Path1 函数中所输入的景点的名称 这 个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置 然后调用 Floyd 函数 查找出它们的最短路径 并输出所要的信息 Floyd 函数原型为 函数原型为 void Floyd int cost MaxVertices int n int weight MaxVertices int path MaxVertices 其中参数 cost MaxVertices 即是图中边的邻接存储矩阵 weight MaxVertices 用来存放 经 此算法后的各顶点间的最短路径的值 path MaxVertices 就是每两个顶点之间最短路径中 到达目的顶点的前一个顶点的位置 Path 函数中的输出信息就是据此而来 对于要求 4 修改景点信息 流程图为 Modify 函数原型为 函数原型为 void Modify 它不带任何参数 功能是通过手动输入景点名称 然后找到景点的 存储空间 然后在修改相应的信息 对于选做要求 增加景点 其工作流程图为 AddVertic 函数原型为 函数原型为 void AddVertic 他不带任何参数 该函数的功能是在这个函数里面输入景点的信 息 然后调用 ListInsert 函数 将所要增加的顶点信息插入到线性表中 ListInsert 函数原型为 函数原型为 void ListInsert SeqList L int i DataType x 参数 L 表示顶点存储的线性表 i 表示 menu Path1 Path menu Modify menu AddVertic Floyd ListInsert 4 要插入的位置 x 表示要插入的景点的信息 同时我在插入顶点时也将他与其他顶点之间的 距离设置为 MaxWeight 这样做主要是为了方便在 Floyd 函数里面求最短路径 对于选做要求 删除景点 其工作流程图为 DeleteVertic 函数原型为 函数原型为 void DeleteVertic 他不带任何参数 该函数的功能就是在函数体里面输入要删除的 景点的名称 然后根据名称找到该景点在线性表中的存储位置 然后调用线性表中的 ListDelete 函数进行相应顶点的删除 ListDelete 函数原型为 函数原型为 ListDelete SeqList L int i DataType x 其中参数 L 为存放顶点信息的线性表 i 表 示要删除顶点在线性表中的存放位置 x 就是要删除的那一个景点 它的功能就是从线性 表中删除指定的顶点 对于选做要求 增 删道路 流程图为 AddRoad 和和 DeleteRoad 两函数原型为 两函数原型为 void AddRoad 和 void DeleteRoad 这两个函数都不带参数 它们的功能就是在这 两个函数里面输入要删除要增加或者的边连接的两个景点的名称 然后在线性表中找到这 两个景点的相对存储空间 最后调用 InsertEdge 或者 DeleteEdge 函数 InsertEdge 和和 DeleteEdge 两函数原型为 两函数原型为 void InsertEdge AdjMGraph G int v1 int v2 int weight void DeleteEdge AdjMGraph G int v1 int v2 这两个函数中同名参数所代表的意义 是相同的 其中 v1 v2 是所输入景点在线性表中的相对位置 weight 就是增加的边的权值 函数接口说明函数接口说明 我所设计整个程序就是一些子函数的集合 每个功能都对应一个或者几个子函数 他们之间可以没有任何限制 只要能保证程序正确运行就可以调用 特别是 AdjMGraph h AdjMGraph h 和 SeqList h 头文件之中的函数 他们被很多函数调用过 这其中都没有任 何特殊类型的函数 2 3 详细设计 详细设计 根据题目分析 对于信息查询与修改功能 设计如下 1 输入景点名称 2 从线性表头扫描到表尾 if 找到该景点 输出景点结构体信息 else 输出提示信息找不到该顶点 实现查找最短路径 设计如下 1 景点名称 2 根据输入的信息找到它们所在的线性表中的位置 3 调用 Floyd 算法找出最短路径 4 输出信息 实现增删景点功能 设计如下 menu DeleteVertic ListDelete menu AddRoad DeleteRoad InsertEdge DeleteEdge 5 1 增加或者删除景点的名称 2 if 输入景点 将景点信息保存在相应的结构体中 并插入到线性表尾 if 删除景点 找到景点在线性表中所在的位置 然后将景点信息从线性表中删 除 实现增删道路功能 设计如下 1 入增加或删除道路连接的两个景点的名称 2 找到它们的相对位置 3 if 删除道路 将连接它们的边置为 MaxWeight if 增加道路 将输入的边值赋给相应的邻接矩阵表 3 3 调试分析 调试分析 调试过程中遇到的问题与解决方案 调试过程中遇到的问题与解决方案 1 关于最短路径的输出问题 在进行最短路径输出时 我刚开始时只能正序输出 具体的描述为 比如 我要查寻从东区到东湖的最短路径 那么它能正确输出结果 他的 形式为 东区 主楼 西体育馆 隧道 北大门 东湖 但是 当 我逆向输出时 得到的结果却有点问题 经过分析调试后 找到了错误的所在 在找最短 路径的时候我用的是 Floyd 算法 在这个算法中有三重循环 形式均为 for k 0 k食堂 东湖 经过分析调试后 其原因也是出在 Floyd 算法 那 在 Floyd 算法中 有这么一个判断if weight i j weight i k weight k j 由于我在输入新景点信息时并没有建立它与其它景点之间的连接信息 所以在图中 该新 景点与其它景点之间的边得连接信息是空的 也就是说在邻接矩阵中 它的边得信息是空 的 那么在进行 if weight i j weight i k weight k j 判断时 weight 新增景 点序号 其它景点序号 的值将是一个很大的负数 所以最短路径将会出错 解决这个问题 的方法就是在增加新景点时就将它与其它景点之间的边 距离 设置为 MaxWeight 这时 如果再用 Floyd 函数进行最短路径的求解时就不会再出现问题了 另外 在做这个题时也还出现过一些其他的小问题 不过都比较容易解决 这里我 就不再列出了 算法的时空复杂度分析算法的时空复杂度分析 对应题目的要求 我总共提供了八个选项操作对于每一个操作的分析如下 1 相关信息的查询 在这个操作中允许使用者输入一个景点名称 然后再根据景点名 称来或取其相关的信息 这个操作要扫描线性表 其时间复杂度为 o n 空间复杂度为 o n 2 最短路径查询 实现这个功能用到了 Floyd 算法 他用到了一个三重的 for 循环 故其时间复杂度为 o n 3 空间复杂度为 o 1 3 修改景点信息 要修改信息 必须首先找到景点所在的存储位置 那么就需要扫 描线性表 其时间复杂度为 o n 空间复杂度为 o 1 4 增加景点 增加景点信息时 直接将此景点结构体信息插入到线性表表尾 而不 需要进行遍历 其时间复杂度与空间复杂度均为 o 1 6 5 删除景点 删除景点时必须找到所要删除景点所在的位置 这样就必须遍历线性表 除此之外 删除后线性表还要进行移动操作 其时间复杂度为 o n 空间复杂度为 o n1 6 增加道路 增加道路也要扫描线性表 找到要增加路的两景点的存储位置 然后再 根据找到的存储位置去改变邻接矩阵的边的值 改变邻接矩阵的时间复杂度为 o 1 其总时 间消耗在线性表的扫描上 故最终其时间复杂度为 o n 空间复杂度为 o 1 7 删除道路 删除道路和增加道路类似 都是先找到存储位置 然后再改变邻接矩阵 它的时空复杂度分别为 o n o 1 8 浏览所有景点 浏览所有景点的实质就是从头到尾遍历线性表 然后输出遍历到的 节点的信息 其时间复杂度为 o n 空间复杂度为 o 1 4 用户手册 用户手册 使用说明 当用户将程序经过编译 连接后 点击运行 在 DOS 环境里面将看到一 个选项菜单 菜单里面提供了 8 种操作 同时输出了一行提示信息 请选择您想进行的操 作 然后用户可以输入一个 1 8 之间的数字进行选择性的操作 例如 您想进行信息的 查询操作 您可以从键盘输入数字 1 当然 一般而言先应该进行 浏览所有景点名称 操作 如果您选择了浏览所有景点名称操作 在屏幕上将会显示出 10 个景点的名称 这些 景点是事先加进去的 用户可以对这些景点进行任何程序所提供的操作 下面 我将详细介绍本程序的使用方法 在浏览景点后 菜单将会继续显示出来 为 您提供操作选择 如果如果您想进行 相关信息的查询 操作 输入数字 1 然后程序将会提醒您输入查 询景点的名称 在您输入景点名称后回车即可 如果如果您想进行 最短路径查询 操作 首先输入数字 2 然后程序将会提醒您输入 查询的景点的名称 您输入按要求输入所提供的两个景点名称即可 要注意的是景点名称 间以空格隔开 最后程序就会告诉您最短的路径 以及最短路的长度 如果如果您想修改景点的信息 同样先输入数字 3 然后程序就会提醒您输入所要修改 景点的名称 您可以根据要求输入一个景点的名称 然后回车 之后屏幕上就会显示您所 输入的景点的所有信息 同时会有三个修改选项供用户选择 然后您可以输入 1 3 之间 的一个数字进行选择性的修改 比如 您可以输入 1 对景点名称进行修改 修改完后又 会返回到菜单项继续选择 如果如果您想进行 增加景点 操作 可以输入数字 4 然后程序就会提示您输入新增 加的景点的名称 代号 信息简介 各种输入之间以空格隔开 当输入完毕后回车 景点 也就成功加入了 然后用户可以再次选择第八项操作浏览所有景点名称 检测新输入的景 点是否已经成功添加 如果如果您想进行 删除景点 操作 可以输入数字 5 回车后系统将会提示您输入要 删除的景点的名称 您可以输入您想要删除的景点的名称 然后回车 这样删除景点的操 作就已经完成 您同样可以选择第八项操作 检测是否成功删除了景点 如果如果您想进行 增加道路 操作 您可以输入数字 6 然后回车 系统将会提示您 输入增加道路所连接的两个景点的名称 输入两景点名称后回车 然后系统又会提示输入 增加道路的长度 输入后回车 这时增加道路操作也就完了 用户如果想要检查道路是否 增加成功可以进行 最短路径查询 操作 如果如果您想进行 删除道路 操作 您可以输入数字 7 然后系统就会提示您输入删 7 除道路所连接的两景点的名称 输入名称后回车即可 当然 如果您想检测删除是否成功 您可以选择 最短路径查询 操作 备注 经过测试 本程序的所有操作都能正常执行 您可以选择性的对他进行操作 同时也可以混合着操作 混合操作是检测错误的最好的一个方法 5 测试数据及测试结果 测试数据及测试结果 菜单显示为 菜单显示为 菜单 1 相关信息查询 2 最短路径查询 3 修改景点信息 4 增加景点 5 删除景点 6 增加道路 7 删除道路 8 浏览所有景点名称 请选择您想进行的操作 8 东区 博物馆 主楼 图书馆 西体育馆 隧道 北综 北体育馆 北大门 东湖 请选择您想进行的操作 1 请输入您所想要查询的景点的名称 博物馆 您输入的景点的名称是 博物馆 您输入的景点的代码为 11 您输入的景点的相关信息有 有各种化石 请选择您想进行的操作 2 请输入你要查询的两景点的名称 东区 东湖 最短路径为 108 从 东区 点到 东湖 景点的最短路径为 东区 主楼 西体育馆 隧道 北大门 东湖 请选择您想进行的操作 3 您想修改的景点的名称为 隧道 您输入的景点的名称是 隧道 您输入的景点的代码为 15 您输入的景点的相关信息有 自主修建 8 您想修改什么信息 1 名称 2 代号 3 信息简介 1 请输入要修改的的景点的新名称 地大隧道 请选择您想进行的操作 8 东区 博物馆 主楼 图书馆 西体育馆 地大隧道 北综 北 体育馆 北大门 东湖 请选择您想进行的操作 4 请输入增加节点的 名称 代号 信息简介 北一楼 34 教师办公室 请选择您想进行的操作 1 请输入您所想要查询的景点的名称 北一楼 您输入的景点的名称是 北一楼 您输入的景点的代码为 34 您输入的景点的相关信息有 教师办公室 请选择您想进行的操作 5 请输入您要删除景点的名称 北一楼 请选择您想进行的操作 8 东区 博物馆 主楼 图书馆 西体育馆 地大隧道 北综 北 体育馆 北大门 东湖 请选择您想进行的操作 6 输入您要增加的道路链接的两个景点名称 东区 北综 输入您要增加的道路的长度 50 请选择您想进行的操作 2 请输入你要查询的两景点的名称 东区 北综 最短路径为 50 从 东区 点到 北综 景点的最短路径为 东区 北综 请选择您想进行的操作 7 输入您要删除的道路链接的两个景点名称 东区 北综 请选择您想进行的操作 2 请输入你要查询的两景点的名称 东区 北综 最短路径为 103 从 东区 点到 北综 景点的最短路径为 东区 主楼 西体育馆 地大隧道 北大门 北综 9 6 源程序清单 源程序清单 school cpp 程序源文件 AdjMGraph h 图的相关操作头文件 AdjMGraphCreat h 创建图的头文件 SeqList h 线性表操作头文件 Floyd h Floyd 算法头文件 Operation h 自己所定义的一些操作的头文件 Inquiry h 查询信息包含的头文件 详细 school cpp 程序源文件 include include include define MaxSize 20 线性表的最大数组空间 define MaxVertices 20 景点个数所允许的最大值 define MaxWeight 1000 无穷边权值 include Floyd h include AdjMGraphCreat h include Inquiry h AdjMGraph G include Operation h void main 初始景点信息 DataType a 东区 10 研究生院 博物馆 11 有各种化石 主楼 12 学 校的标志建筑 图书馆 13 藏书 50 万册 西体育馆 14 主要供西区学 生使用 隧道 15 自主修建 北综 16 北区标志楼 北体育馆 17 主要供北区学生使用 北大门 18 外出通道 东湖 19 武汉最美的湖 邻接矩阵的表示 10 RowColWeightrcw 0 1 20 0 2 30 0 3 35 1 0 20 1 3 20 2 0 30 2 3 15 2 4 30 3 0 35 3 1 20 3 2 15 3 4 30 4 2 30 4 3 30 4 5 10 5 4 10 5 6 35 5 8 8 6 5 35 6 7 20 6 8 25 6 9 5 7 6 20 7 8 10 8 5 8 8 6 25 8 7 10 9 6 5 int n 10 e 28 景点数与边数 Creat 构造图 menu 详细 Floyd h 头文件 void Floyd int cost MaxVertices int n int weight MaxVertices int path MaxVertices 初始化 int i j k for i 0 i n i for j 0 j n j weight i j cost i j path i j 1 n 次递推 for k 0 k n k for i 0 i n i for j 0 jweight i k weight k j weight i j weight i k weight k j path i j k 详细 Inquiry h 头文件 void Information AdjMGraph G char scenery int i for i 0 i G vertices size i 11 if strcmp G vertices list i name scenery 0 printf 您输入的景点的名称是 s n G vertices list i name printf 您输入的景点的代码为 d n G vertices list i code printf 您输入的景点的相关信息有 s n n G vertices list i introduction break if i G vertices size printf 您所查询的景点不在我们所提供的范围内 n n void Path AdjMGraph G char sceneryname char sceneryname1 int i j k n m count 0 n G vertices size int weight MaxVertices MaxVertices path MaxVertices MaxVertices int value MaxVertices for i 0 i s n sceneryname sceneryname1 else while m 1 12 value count m if j sceneryname if j 0 i printf s G vertices list value i name printf s n sceneryname1 else for i 0 i G vertices list value i name printf s n sceneryname1 详细 Operation h 头文件 void menu 查询景点信息的函数 void Information1 char sceneryname 20 printf 请输入您所想要查询的景点的名称 scanf s sceneryname Information G sceneryname menu 查询最短路径的函数 void Path1 13 char sceneryname 20 sceneryname1 20 printf 请输入你要查询的两景点的名称 scanf s s sceneryname sceneryname1 Path G sceneryname sceneryname1 menu printf n 修改景点信息的函数 void Modify char sceneryname 20 int i x printf 您想修改的景点的名称为 scanf s sceneryname Information G sceneryname for i 0 i G vertices size i if strcmp G vertices list i name sceneryname 0 printf 您想修改什么信息 1 名称 2 代号 3 信息简介 scanf d if x 1 printf 请输入要修改的的景点的新名称 scanf s G vertices list i name break if x 2 printf 请输入要修改的的景点的新代号 scanf d break if x 3 printf 请输入要修改的的景点的新信息简介 scanf s G vertices list i introduction break menu 14 增加景点的函数 void AddVertic int i k DataType ver printf 请输入增加节点的 名称 代号 信息简介 n scanf s d s ver name ListInsert k G vertices size 1 for i 0 i G vertices size i if k i G Edge k i MaxWeight G Edge i k MaxWeight else G Edge k i 0 menu void DeleteVertic DataType x char name 20 int i k printf 请输入您要删除景点的名称 scanf s name for i 0 i G vertices size i if strcmp G vertices list i name name 0 k i ListDelete for i 0 i G vertices size i if k i G Edge k i MaxWeight G Edge i k MaxWeight else G Edge k i 0 15 menu 删除景点的函数 void AddRoad char name 20