交通咨询管理课程设计报告

课程设计报告 课程名称 课程名称 数据结构数据结构 题目名称 题目名称 全国交通咨询模拟全国交通咨询模拟 学生学院 学生学院 专业班级 专业班级 学学 号 号 学生姓名 学生姓名 指导老师 指导老师 2009 年 6 月 24 日 全国交通咨询模拟全国交通咨询模拟 一 设计目的一 设计目的 掌握线性表 栈 图结构和对文件的操作 学习屏幕编辑和菜单技术 掌握用最短路径及 其搜索算法编制较综合性的程序 能用图的邻接存储结构求解最优路线问题 解决有关实 际问题 得到软件设计技能的训练 二 问题描述二 问题描述 交通咨询模拟 根据旅客的不同需要 要考虑到旅客希望在旅途中的时间尽可能短 希望 旅费尽可能省等的要求 旅途用火车或飞机作为交通工具 用计算机编制程序 为旅客提 供两种最优决策的交通咨询系统 三 基本要求三 基本要求 1 对城市信息 城市名 城市间的里程 进行编辑 具备添加 修改 删除功能 2 对城市间的两种交通工具 飞机和火车 对飞机航班和列车时刻表进行编辑 里程 航 班和列车班次的添加 修改 删除 3 提供两种最优决策 最快到达或最省钱到达 全程只考虑一种交通工具 可以不考虑回程 4 旅途中的耗费的总时间应包括中转站的等候时间 其中飞机至少二小时 火车至少一小时 5 咨询以用户和计算机对话方式进行 要注意人机交互的屏幕界面 由用户选择最优决策 原则和交通工具 输入起始站 终点站 出发时间 输出信息 最快需要多长时间才能到 达及旅费 或者最少需要多少旅费才能到达及时间 并详细说明依次于何时何地乘坐哪一 趟班机或列车何时到达何地 四 实现提示四 实现提示 1 1 算法思路 算法思路 1 数据存储 城市信息 城市名 代码 交通信息 城市间的里程 各航班和列车时刻 存储于磁盘文件 建议把城市信息存于文件前面 交通信息存于文件的后面 用 fread 和 fwrite 函数操作 2 数据的逻辑结构 根据设计任务的描述 其城市之间的旅游交通问题是典型的图结构 可看作为有向图 图的顶点是城市 边是城市之间所耗费的时间 要包括中转站的等候时 间 或旅费 3 数据的存储结构 采用邻接表和邻接矩阵都可作为数据的存储结构 但当邻接边不多 时 宜采用邻接表 以提高空间的存储效率 这里建议采用邻接表作为数据的存储结构 4 用不同的功能模块对城市信息和交通信息进行编辑 添加 修改 删除功能可用菜单 方式或命令提示方式 只要能方便的对城市信息和交通信息进行管理即可 但要注意人机 界面 具体实现由学生自行设计 也可参考有关程序 届时在网上提供 这些工作有不小 的工作量 5 最优决策功能模块 fast or province 读入城市信息和交通信息 用邻接表生成含权网络 表头数组中的元素存放城市名及对 方城市到达该元素所代表城市的所有信息 表头数组中的元素所对应的单链表存放与该元 素所代表的城市有交通联系的城市 代码 里程 航班 列车车次 根据具体最优决策的要求 用 Dijkstra 算法求出出发城市到其它各城市的最优值 最短 时间或最小的费用 搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中 其目的城市所代表的元素中就保存了所需的最优决策结果 这过程中 要用队列或栈保存 局部最优决策值 局部最短的时间或最省的费用 变小的城市 其相应的初始值可为 并 在表头数组对应的城市元素中保存响应的信息 开始时 栈 队 中只有出发地城市 随着 对栈 队 顶 首 城市有交通联系的城市求得决策值 最短时间或最小的费用 若该值是局 部最优值且该城市不在栈 队 中 则进栈 队 直至栈 队 为空 输出结果 从目的城市出发 搜索到出发城市 所经过的城市均入栈 再逐一出栈栈中 的城市 输出保存在表头数组中对应城市的信息 对方城市的出发信息 里程 时间 费用 等 及最终结果 即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地 最终所需 的最快需要多长时间才能到达及旅费 或者最少需要多少旅费才能到达及时间 6 主程序可以有系统界面 菜单 也可用命令提示方式 选择功能模块执行 要求在程 序运行过程中可以反复操作 2 2 数据结构 数据结构 本程序运用了关于图这种数据结构 他的抽象数据类型定义如下 typedef struct unDiGraph int numVerts 结点 costAdj cost 邻接矩阵 unDiGraph UNG 基本操作 基本操作 unDiGraph CreateCostG 操作结果 操作结果 构造带权 费用 图 unDiGraph CreateTimeG 操作结果 操作结果 构造带权 时间 图 构造飞机带权 费用 图 PathMat Floyed unDiGraph D 操作结果 操作结果 Floyed 函数 求任意两点的最短路径 3 算法思想 算法思想 本程序运用了图的知识 构造了无向带权费用图和无向带权时间图 如图 1 图 2 所示 图 1 十三城市之间火车费用表 权值表示费用 图 2 十三城市之间火车行驶时间表 权值表示时间 并利用 Floyed 函数求带权图两点之间的最短路径 通过对带权费用图和带权时 间图求最短路径 就可以最短道从一城市到另一城市之间最省时间和最省费用 的走法 为了简洁直观 本设计对课本内的交通网进行了简化 原来的 25 个城市缩 减为 13 个 但是基本实现了设计的目的 满足了基本要求 4 程序模块 程序模块 1 程序是用 dos 版做的界面 2 主界面包括 1 选择火车最短时间路线 2 选择火车最节约费用路线 3 选择坐 飞机 4 管理员程序确 5 退出本程序 3 程序的模块为 include include include include include include 引用的文本件 define INF 65535 定义一个最大数定为无穷值 define MAX 13 typedef int costAdj MAX 1 MAX 1 图邻接矩阵从 1 开始记数 int Path MAX 1 MAX 1 图邻接矩阵从 1 开始记数 int o 13 h typedef struct unDiGraph int numVerts 结点 costAdj cost 邻接矩阵 unDiGraph UNG 图的定义 costAdj B L void pr int i 选择城市 void pri 输出城市 unDiGraph CreateCostG 构造带权 费用 图 返回首地址 G unDiGraph CreateTimeG 构造带权 时间 图 返回首地址 G unDiGraph CreateFlyG 飞机的相关信息 void Floyed unDiGraph D unDiGraph M Floyed 函数 求任意两点的最短路径 void prn pass int i int j 为了求从 i 到 j 的最短路径 只需要调用如下的过程 void time 求最少时间路径 void money 求最少花费路径 void administrator 管理员功能 void main main 函数 5 主程序主程序 include include include include include include define INF 65535 定义一个最大数定为无穷值定义一个最大数定为无穷值 define MAX 23 static int c number 13 static int k 0 staticint v 0 z 0 r 0 t 0 typedef struct zhu int c cost int c time int f cost int f time zhu zhu m 20 x 20 n 20 typedef int costAdj MAX 1 MAX 1 图邻接矩阵从图邻接矩阵从 1 开始记数开始记数 int Path MAX 1 MAX 1 图邻接矩阵从图邻接矩阵从 1 开始记数开始记数 typedef struct unDiGraph int numVerts 结点结点 costAdj cost 邻接矩阵邻接矩阵 unDiGraph UNG 图的定义图的定义 typedef struct c edit char a 10 c edit c edit add 10 costAdj B L int pr int i int j int h 0 if j 0 h i else if j 1 cin add i a switch h 运用运用 switch 语句 语句 case 0 cout break case 1 cout 成都成都 break case 2 cout 西安西安 break case 3 cout 郑州郑州 break case 4 cout 武汉武汉 break case 5 cout 株洲株洲 break case 6 cout 贵阳贵阳 break case 7 cout 柳州柳州 break case 8 cout 广州广州 break case 9 cout 南宁南宁 break case 10 cout 徐州徐州 break case 11 cout 北京北京 break case 12 cout 天津天津 break case 13 cout 上海上海 break default cout add i 13 a return 1 输出城市列表及相应代码输出城市列表及相应代码 void pri int i cout 城市及其代码城市及其代码 endl endl endl cout endl for i 1 i c number i cout i pr i 0 cout endl endl endl endl endl endl endl 构造带权构造带权 费用费用 图图 返回首地址返回首地址 G unDiGraph CreateCostG int o 火车的花费的存贮和编辑功能火车的花费的存贮和编辑功能 unDiGraph G int i j int a 0 b 0 f h 1 if G unDiGraph malloc sizeof unDiGraph 为为 G 分配存储空间 分配存储空间 return NULL for i 1 i c number 1 i for j 1 jcost i j INF 初始化使初始化使 G cost i j 为无穷 为无穷 G numVerts c number G cost 1 6 G cost 6 1 96 G cost 1 2 G cost 2 1 84 G cost 2 3 G cost 3 2 51 G cost 3 4 G cost 4 3 53 G cost 4 5 G cost 5 4 40 G cost 5 6 G cost 6 5 90 G cost 5 8 G cost 8 5 67 G cost 5 7 G cost 7 5 67 G cost 6 7 G cost 7 6 60 G cost 7 9 G cost 9 7 25 G cost 3 11 G cost 11 3 69 G cost 11 12 G cost 12 11 13 G cost 12 10 G cost 10 12 67 G cost 3 10 G cost 10 3 34 G cost 13 10 G cost 10 13 65 G cost 13 5 G cost 5 13 118 if o while h 1 v v 1 pri cout 火车花费编辑火车花费编辑 endl cout 请输入开始城市的代码请输入开始城市的代码 a cout 请输入结尾城市的代码请输入结尾城市的代码 b cout 请输入你的两地花费请输入你的两地花费 m v c cost n v c cost a x v c cost b cout 请选择请选择 endl cout endl cout 1 继续更改城市费用 继续更改城市费用 endl cout 0 返回上一级菜单返回上一级菜单 endl cout h switch h case 1 h 1 break case 0 h 0 break default cout 选择出错选择出错 cost n v c cost x v c cost m v c cost v f return G 构造带权构造带权 时间时间 图图 返回首地址返回首地址 G unDiGraph CreateTimeG int o 火车的时间的存贮和编辑功能火车的时间的存贮和编辑功能 unDiGraph G int i j int a 0 b 0 f h 1 if G unDiGraph malloc sizeof unDiGraph 为为 G 分配存储空间 分配存储空间 return NULL for i 1 i c number 1 i for j 1 jcost i j INF 初始化使初始化使 G cost i j 为无穷 为无穷 G numVerts c number G cost 1 6 G cost 6 1 9 G cost 1 2 G cost 2 1 8 G cost 2 3 G cost 3 2 5 G cost 3 4 G cost 4 3 5 G cost 4 5 G cost 5 4 4 G cost 5 6 G cost 6 5 9 G cost 5 7 G cost 7 5 6 G cost 5 8 G cost 8 5 6 G cost 6 7 G cost 7 6 6 G cost 7 9 G cost 9 7 2 G cost 3 11 G cost 11 3 6 G cost 11 12 G cost 12 11 1 G cost 12 10 G cost 10 12 6 G cost 3 10 G cost 10 3 3 G cost 13 10 G cost 10 13 6 G cost 13 5 G cost 5 13 11 if o while h 1 z z 1 pri cout 火车时间编辑火车时间编辑 endl cout 请输入开始城市的代码请输入开始城市的代码 a cout 请输入结尾城市的代码请输入结尾城市的代码 b cout 请输入你的两地时间请输入你的两地时间 m z c time n z c time a x z c time b cout 请选择请选择 endl cout endl cout 1 继续更改城市时间 继续更改城市时间 endl cout 0 返回上一级菜单返回上一级菜单 endl cout h switch h case 1 h 1 break case 0 h 0 break default cout 选择出错选择出错 cost n z c time x z c time m z c time z f return G unDiGraph CreateTimeF int o 飞机的时间的存贮和编辑功能飞机的时间的存贮和编辑功能 unDiGraph G int i j int a 0 b 0 f h 1 if G unDiGraph malloc sizeof unDiGraph 为为 G 分配存储空间 分配存储空间 return NULL for i 1 i c number 1 i for j 1 jcost i j INF 初始化使初始化使 G cost i j 为无穷 为无穷 G numVerts c number G cost 1 6 G cost 6 1 3 G cost 1 2 G cost 2 1 2 G cost 2 3 G cost 3 2 1 G cost 3 4 G cost 4 3 2 G cost 4 5 G cost 5 4 4 G cost 5 6 G cost 6 5 3 G cost 5 7 G cost 7 5 6 G cost 5 8 G cost 8 5 6 G cost 6 7 G cost 7 6 6 G cost 7 9 G cost 9 7 2 G cost 3 11 G cost 11 3 6 G cost 11 12 G cost 12 11 1 G cost 12 10 G cost 10 12 2 G cost 3 10 G cost 10 3 3 G cost 13 10 G cost 10 13 6 G cost 13 5 G cost 5 13 1 if o while h 1 t t 1 pri cout 飞机时间编辑飞机时间编辑 endl cout 请输入开始城市的代码请输入开始城市的代码 a cout 请输入结尾城市的代码请输入结尾城市的代码 b cout 请输入你的两地时间请输入你的两地时间 m t f time n t f time a x t f time b cout 请选择请选择 endl cout endl cout 1 继续更改城市时间 继续更改城市时间 endl cout 0 返回上一级菜单返回上一级菜单 endl cout h switch h case 1 h 1 break case 0 h 0 break default cout 选择出错选择出错 cost n t f time x t f time m t f time t f return G unDiGraph CreateCostF int o 飞机花费的存贮和编辑功能飞机花费的存贮和编辑功能 unDiGraph G int i j int a 0 b 0 f h 1 if G unDiGraph malloc sizeof unDiGraph 为为 G 分配存储空间 分配存储空间 return NULL for i 1 i c number 1 i for j 1 jcost i j INF 初始化使初始化使 G cost i j 为无穷 为无穷 G numVerts c number G cost 1 6 G cost 6 1 960 G cost 1 2 G cost 2 1 840 G cost 2 3 G cost 3 2 501 G cost 3 4 G cost 4 3 530 G cost 4 5 G cost 5 4 400 G cost 5 6 G cost 6 5 900 G cost 5 8 G cost 8 5 670 G cost 5 7 G cost 7 5 670 G cost 6 7 G cost 7 6 600 G cost 7 9 G cost 9 7 200 G cost 3 11 G cost 11 3 690 G cost 11 12 G cost 12 11 310 G cost 12 10 G cost 10 12 670 G cost 3 10 G cost 10 3 340 G cost 13 10 G cost 10 13 650 G cost 13 5 G cost 5 13 1180 if o while h 1 r r 1 pri cout 飞机花费编辑飞机花费编辑 endl cout 请输入开始城市的代码请输入开始城市的代码 a cout 请输入结尾城市的代码请输入结尾城市的代码 b cout 请输入你的两地花费请输入你的两地花费 m r f cost n r f cost a x r f cost b cout 请选择请选择 endl cout endl cout 1 继续更改城市费用 继续更改城市费用 endl cout 0 返回上一级菜单返回上一级菜单 endl cout h switch h case 1 h 1 break case 0 h 0 break default cout 选择出错选择出错 cost n r f cost x r f cost m r f cost r f return G Floyed 函数函数 求任意两点的最短路径 求任意两点的最短路径 void Floyed unDiGraph D unDiGraph M int i j k n costAdj A C n c number for i 1 i n i for j 1 jcost i j 初始化矩阵初始化矩阵 A C i j M cost i j Path i j 1 初始化矩阵初始化矩阵 p 置置 1 for k 1 k n k k 为逐步加入的中间结点为逐步加入的中间结点 for i 1 i n i i 为为 A 中行号中行号 for j 1 j n j if A i k A k j A i j A i j A i k A k j C i j C i k C k j Path i j k 若若 i 经过经过 k 到到 j 比比 i 到到 j 小 则令小 则令 A i j A i k A k j B i j A i j L i j C i j else B i j A i j L i j C i j end for cout n 最短路径为最短路径为 endl end Floyed 为了求从为了求从 i 到到 j 的最短路径 只需要调用如下的过程 的最短路径 只需要调用如下的过程 void prn pass int i int j if Path i j 1 prn pass i Path i j 输出最短路径经过的所有点输出最短路径经过的所有点 pr Path i j 0 求最少时间路径 求最少时间路径 void time int Bcity Ecity 起始成市号码和终点城市号码起始成市号码和终点城市号码 int l h 1 do pri 输出城市列表及相应代码 输出城市列表及相应代码 cout 请输入起始城市和目的城市的代码 中间以空格隔开 范围请输入起始城市和目的城市的代码 中间以空格隔开 范围 1 c number Bcity cin Ecity 输入起始城市和终点城市的代码 输入起始城市和终点城市的代码 if 0 Bcity else cout 火车花的钱是火车花的钱是 L Bcity Ecity 元元 endl cout 火车花的时间是火车花的时间是 B Bcity Ecity 小时小时 endl printf n n 1 继续最少花费查找继续最少花费查找 n 2 返回主菜单返回主菜单 n 清选择清选择 scanf d 输入输入 1 或或 2 选择是否继续 选择是否继续 h l while h 1 printf n void f time int Bcity Ecity 起始成市号码和终点城市号码起始成市号码和终点城市号码 int l h 1 do pri 输出城市列表及相应代码 输出城市列表及相应代码 cout 请输入起始城市和目的城市的代码 中间以空格隔开 范围请输入起始城市和目的城市的代码 中间以空格隔开 范围 1 c number Bcity cin Ecity 输入起始城市和终点城市的代码 输入起始城市和终点城市的代码 if 0 Bcity else cout 飞机花的钱是飞机花的钱是 L Bcity Ecity 元元 endl cout 飞机花的时间是飞机花的时间是 B Bcity Ecity 小时小时 endl printf n n 1 继续最少花费查找继续最少花费查找 n 2 返回主菜单返回主菜单 n 清选择清选择 scanf d 输入输入 1 或或 2 选择是否继续 选择是否继续 h l while h 1 printf n 求最少花费路径 求最少花费路径 void money int Bcity Ecity 起始成市号码和终点城市号码起始成市号码和终点城市号码 char l h 1 unDiGraph G do pri 输出城市列表及相应代码 输出城市列表及相应代码 cout 请输入起始城市和目的城市的代码 中间以空格隔开 范围请输入起始城市和目的城市的代码 中间以空格隔开 范围 1 c number Bcity cin Ecity 输入起始城市和终点城市的代码 输入起始城市和终点城市的代码 if 0 Bcity else cout 火车花的钱是火车花的钱是 B Bcity Ecity 元元 endl cout 火车花的时间火车花的时间 L Bcity Ecity 小时小时 endl printf n n 1 继续最少花费查找继续最少花费查找 n 2 返回主菜单返回主菜单 n 清选择清选择 scanf d 输入输入 1 或或 2 选择是否继续 选择是否继续 h l while h 1 printf n 求飞机的情况求飞机的情况 void f money cout 1 endl int Bcity Ecity 起始成市号码和终点城市号码起始成市号码和终点城市号码 char l h 1 unDiGraph G do cout 2 endl pri 输出城市列表及相应代码 输出城市列表及相应代码 cout 请输入起始城市和目的城市的代码 中间以空格隔开 范围请输入起始城市和目的城市的代码 中间以空格隔开 范围 1 c number Bcity cin Ecity 输入起始城市和终点城市的代码 输入起始城市和终点城市的代码 if 0 Bcity else cout 飞机花的钱是飞机花的钱是 B Bcity Ecity 元元 endl cout 飞机花的时间飞机花的时间 L Bcity Ecity 小时小时 endl printf n n 1 继续最少花费查找继续最少花费查找 n 2 返回主菜单返回主菜单 n 清选择清选择 scanf d 输入输入 1 或或 2 选择是否继续 选择是否继续 h l while h 1 printf n void add city 对城市的增加对城市的增加 static int i 1 int j cout 请输入你要增加的城市的个数请输入你要增加的城市的个数 j for i 1 i j i cout 请输入你要增加的城市名请输入你要增加的城市名 endl pr i 1 c number c number 1 cout 城市增加完毕城市增加完毕 endl void chose money 花最少钱的算法花最少钱的算法 int h cout 1 火车火车 endl cout 2 飞机飞机 endl cout 请选择 请选择 h if h 1 money else f money void chose time 花最少时间的算法花最少时间的算法 int h cout 1 火车火车 endl cout 2 飞机飞机 endl cout 请选择 请选择 h if h 1 time else f time void edit line 增加编辑火车的费用增加编辑火车的费用 CreateCostG 1 void edit hour 增加编辑火车的时间增加编辑火车的时间 CreateTimeG 1 void edit fline 增加编辑飞机的费用增加编辑飞机的费用 CreateCostF 1 void edit fhour 增加编辑飞机的时间增加编辑飞机的时间 CreateTimeF 1 void administrator 管理员功能管理员功能 int h 1 while h cout endl cout 1 增加城市增加城市 endl cout 2 添加或编辑火车费用添加或编辑火车费用 endl cout 3 添加或编辑火车时间添加或编辑火车时间 endl cout 4 添加或编辑飞机费用添加或编辑飞机费用 endl cout 5 添加或编辑飞机时间添加或编辑飞机时间 endl cout 0 返回主菜单返回主菜单 endl cout endl cout 请选择请选择 h switch h case 1 add city break case 2 edit line break case 3 edit hour break case 4 edit fline break case 5 edit fhour break case 0 h 0 break default cout 选择出错 选择出错 endl 主函数主函数 void main 人机对话界面设置