交通信息查询详细设计说明书.doc

交通咨询系统交通咨询系统 详详 细细 设设 计计 说说 明明 书书 设计成员设计成员 孙坤孙坤 13111196 叶嘉伟叶嘉伟 13111198 余富林余富林 13111197 原赫原赫 13111195 项目名称 详细设计说明书1 详细设计说明书详细设计说明书 1 引言引言 1 1 编写目的 在概要设计设定的大纲与数据结构上进一步完成每一个模块的功能 写出对应的算法 及其伪代码 为下一步细化到代码做准备 本说明书为程序实现提供细化的参考 1 2 背景背景 待开发系统名称 交通信息查询系统 本系统开发人员为本小组全体成员 13111195 原赫 13111196 孙坤 13111197 余富林 13111198 叶嘉伟 1 3 定义定义 迪杰斯特拉算法 本系统采用的求解最短路径的算法 1 4 参考资料参考资料 数据结构 c 语言版 严蔚敏 吴伟民 清华大学出版社 C 语言程序设计 第四版 谭浩强 清华大学出版社 项目名称 详细设计说明书2 2 系统结构系统结构 选择登陆类型 程序开始运行 显示欢迎界面 普通用户管理人员密码登陆 花费最短路线时间最短路线管理城市管理列车管理航班 判断是否退回主菜单 是 否 以上为本系统的主要结构组成 详细的结构说明参见交通信息查询系统概要设计说明 书 项目名称 详细设计说明书3 3 模块详细设计模块详细设计 3 1 模块列表 说明 以下模块详细设计均以航班一种交通工具为例 对于列车以此类推 模块名称 模块标示符 管理员添加城市 Model1 管理员删除城市 Model2 管理员添加航班 Model3 管理员删除航班 Model4 普通用户查询最少花费航班 Model5 普通用户查询最短时间航班 Model6 3 2 模块 1 model1 3 2 1 模块描述模块描述 该模块所要实现的功能为将一个新城市加入到交通信息库当中 适用对象为信息库管 理员 要求通过键盘输入所要添加的新城市 并将信息保存到对应的文件中去 同时要求 有一定判错功能 3 2 2 输入项输入项 要求输入一个城市名作为添加城市名 为了方便起见 这里运用 STRING 类作为变量 类型 项目名称 详细设计说明书4 3 2 3 输出项输出项 输出项为添加的 string 类城市名 要求输出到文件中去 并修改文件中的城市数 3 2 4 流程逻辑流程逻辑 输入城市名 判别城市是否存在 No Yes 修改文件中的信息 写 入城市名 增加城市数 初始化数据结构 End Start 3 2 5 接口接口 本模块与其他模块以及整个数据结构的接口为城市文件 通过本模块修改文件以及初始 化操作与数据结构关联起来 项目名称 详细设计说明书5 3 2 6 初步代码初步代码 int addcity graph char ch int k int p 0 string c fstream file printf n n n cout 这里是城市添加管理页面 n n n outputcities t cout 警告 您的操作将改变交通信息库 输入 1 继续操作 否则离开 ch getchar dd ch for ch n ch getchar if dd 1 return 2 cout n n cout c getchar for k 1 k t citynum k if c str k cout 抱歉 您所添加的城市已经存在 n Sleep 800 return 1 file open file txt file setw 6 t citynum 1 endl file seekg 0 ios end file endl file c file close initialcities t initialflights t initialtrains t cout 城市已成功添加了呢 Sleep 800 return 0 添加城市函数 运行完之后不必调用城市初始化 初始化已包含在函数中 3 2 7 测试计划测试计划 测试时通过各种不符合要求的输入来检验本模块的判错能力 同时注意文件中新生成的 信息是否与预想的吻合 项目名称 详细设计说明书6 3 3 模块 模块 2 model2 3 3 1 模块描述模块描述 该模块所要实现的功能为将一个已有城市从交通信息库当中删除 适用对象为信息库 管理员 要求通过键盘输入所要删除的城市 并将信息保存到对应的文件中去 同时要求 有一定判错功能 3 3 2 输入项输入项 要求输入一个城市名作为删除城市名 为了方便起见 这里运用 STRING 类作为变量类 型 3 3 3 输出项输出项 输出项为整个城市列表 要求输出到文件中去 并修改城市数 3 3 4 流程逻辑流程逻辑 输入城市名 判别城市是否存在 Yes No 将数据结构中的相关内 容全部删除 并重新将 数据结构的信息打入文 件中 End Start 项目名称 详细设计说明书7 3 3 5 初步代码初步代码 int deletecity graph unsigned int hour unsigned int minute int decreasef 0 删除城市后减少的航班数 int decreaset 0 删除城市后减少的列车数 int i j string c char ch int k int m fstream file 以上为变量声明 cout 这里是城市删除管理页面 n n n n cout c getchar cout n n for k 1 k t citynum k if c str k m k m 为想要删除城市的下标 break if k t citynum cout 抱歉 您想要删除的城市不存在 n Sleep 800 return 1 以上为判定城市是否存在 file open file txt fstream out ios trunc file setw 6 t citynum 1 endl for i 1 i t citynum i 现在的城市数还是未删之前的 if i m file str i endl else continue file close for i m j 1 j t citynum j decreasef t map i j flightnum decreaset t map i j trainnum for i 1 j m i t citynum i decreasef t map i j flightnum decreaset t map i j trainnum decreasef decreasef t map m m flightnum decreaset decreaset t map m m trainnum 以上已经将数据结构更新完毕 接下来将文件全数更新一下即可 3 3 6 测试计划测试计划 测试时通过各种不符合要求的输入来检验本模块的判错能力 同时注意文件中新生成的 信息是否与预想的吻合 项目名称 详细设计说明书8 3 4 模块 模块 3 model3 3 4 1 模块描述模块描述 该模块所要实现的功能为将一个新航班加入到交通信息库当中 适用对象为信息库管理员 要求通过键盘输入所要添加的新航班 并将信息保存到对应的文件中去 同时要求有一定 判错功能 3 4 2 输入项输入项 要求输入一连串信息作为航班信息 string 类型的出发地 目的地 航班号 以钟点形式 输入起止时间 以整型输入花费 3 4 3 输出项输出项 输出项为整个型航班信息 要求输出到文件中去 并修改相应量值 3 4 4 流程逻辑流程逻辑 Start 项目名称 详细设计说明书9 若航班已 存在 End 以同样的判别形式输 入目的地 若目的地与 出发地相同 输入航班信息并写入 文件 最后初始化文 件 3 4 5 初步代码初步代码 int addflight graph char ch int p 0 int k k1 k2 int j int i string c c1 c2 fstream file 以上为变量声明 file open flight txt cout 这里是航班添加管理页面 outputflights t for p 0 for k 1 k t citynum k if c str k k1 k p 1 break if k t citynum cout c getchar cout n n cout c1 getchar cout n n for p 0 p 0 for k 1 k t citynum k if c1 c cout c1 getchar cout n n break if c1 str k k2 k p 1 break if k t citynum cout c1 getchar cout n n cout c2 getchar for i 1 i t map k1 k2 flightnum i if t map k1 k2 flightinf i code c2 cout 您所要添加的航班已经存在 请核实后再进行添加 n Sleep 800 return 1 接下来将航班列表文件更新即可 3 4 6 测试计划测试计划 测试时通过各种不符合要求的输入来检验本模块的判错能力 同时注意文件中新生成的 信息是否与预想的吻合 3 5 模块 模块 4 model4 模块 4 与模块 2 的思想与流程基本一致这里只提供初步代码 int deleteflight graph char ch unsigned int hour unsigned int minute fstream file int m int i j int k1 k2 k1 k2 用来记录出发点与目的地 int p 0 string c c1 c2 int k 以上为变量声明 cout 这里是航班删除管理页面 outputflights t for p 0 for k 1 k t citynum k if c str k p 1 k1 k break if k t citynum cout c getchar cout n n cout c1 getchar cout n n for p 0 p 0 for k 1 k t citynum k 项目名称 详细设计说明书11 if c1 c cout c1 getchar cout n n break if c1 str k p 1 k2 k break if k t citynum cout c1 getchar cout n n cout c2 getchar cout n n for i 1 i t map k1 k2 flightnum i if c2 t map k1 k2 flightinf i code m i break if i t map k1 k2 flightnum cout 您所要删除的航班不存在 Sleep 800 return 1 nflight for i m i chu getchar cout dao getchar cout n n for i 1 i t citynum i if chu str i p i break else if i t citynum cout 对 不 起 您 输 入 的 出 发 城 市 尚 未 添 加 n Sleep 1000 return 1 项目名称 详细设计说明书13 for i 1 i t citynum i if dao str i q i break else if i t citynum cout 对 不 起 您 输 入 的 目 标 城 市 尚 未 添 加 n Sleep 1000 return 1 以上输入并匹配了出发点目的地 for i 1 i t citynum i for j 1 j t citynum j if t map i j flightnum 0 i j t map i j weight MAX else for k 1 mincost MAX k t map i j flightnum k if t map i j flightinf k cost mincost mincost t map i j flightinf k cost t map i j mincostflight k 当前最小花费的航班编号被记录下来 t map i j weight mincost 二维数组 map 的权值已经赋值完毕 for i 1 i t citynum i final i 0 weight i t map p i weight if t map p i weight MAX path i 1 p path i 2 i final p 1 以上为各个辅助数组的初始化 for N t citynum min MAX for i 1 i t citynum i if weight i min j i final j 1 N if j q N 1 break 以上程序段对当前已更新的辅助数组们进行处理 选出当前 weight 数组中的最小项 for i 1 iweight j t map j i weight weight i weight j t map j i weight for m 1 path j m j m path i m path j m path i m path j m m path i m i N 1 以上程序段作用为更新各辅助数组中的数据 每次对每个未结束求解顶点对应的数 据进行审查 接下来将 path 终点 的路径及其信息一一打出即可 项目名称 详细设计说明书14 3 5 5 测试计划测试计划 测试时通过各种情况的交通图来测试算法的正确性 特别是一些特殊情况一定要多多测 试 3 6 模块 5 model5 3 6 1 模块描述模块描述 在这个模块中 普通用户可以查询两座城市之间的最少时间路径 通过输入两城市名 程 序会列出一条时间最短路径以供参考 3 6 2 模块主要算法分析模块主要算法分析 这个模块用的也是迪杰斯特拉算法 但是由于路径时间与前一趟航班到达时间有关 所以 图的权值必须在运行过程中慢慢赋值 这是这一个算法与模块 4 最大的区别 3 6 3 流程逻辑流程逻辑 Start 项目名称 详细设计说明书15 将 j 的路径中最后一班航班的落地时间记录 将 j 到 i 的每趟 航班之间的等待时间加上航班飞行时间加上 path j 中的权值作 为起点 j i 的路径时间总长 将之与 weight i 进行比较 取 其中较小的作为 weight i 的新值 若两趟航班之间间隔不大于 20 分钟 则无法搭乘当日航班 权值需加上 24 小时 End 3 5 4 初步代码初步代码 int timeleast graph char ch int jian 1 int p int q string chu string dao unsigned int min MAX unsigned int mintime MAX unsigned int dtime int i int a b c d int k int j int m int n unsigned int minute unsigned int hour unsigned int h printf 请 输 入 您 的 出 发 城 市 cin chu getchar printf 请 输 入 您 的 目 标 城 市 cin dao getchar cout endl for i 1 i t citynum i if chu str i p i break else if i t citynum cout 对 不 起 您 输 入 的 出 发 城 市 尚 未 添 加 n Sleep 1000 return 1 for i 1 i t citynum i f dao str i q i break else if i t citynum cout 对 不 起 您 输 入 的 目 标 城 市 尚 未 添 加 n Sleep 800 return 1 输入并匹配出发点与目的地 初始化个辅助数组 选出当前 weight 最小的顶点 j 将其 final 值置为一 若 j 为终点 项目名称 详细设计说明书16 for i 1 i t citynum i for j 1 j t citynum j if t map i j flightnum 0 i j t map i j weight MAX else t map i j weight 0 对不连通的城市进行赋值 MAX 连通城市初始权值为 0 for i 1 i t citynum i mintime MAX final i 0 if i p weight i MAX else if t map p i flightnum 0 for j 1 j t map p i flightnum j dtime t map p i flightinf j time2 t map p i flightinf j time1 24 3600 24 3600 if dtime mintime mintime dtime t map p i mintimeflight j weight i mintime t map p i flightinf j realwaitingtime mintime else if t map p i flightnum 0 weight i MAX if weight i MAX path i 1 p path i 2 i final p 1 以上为各个辅助数组的初始化 for N t citynum for i 1 i t citynum i if weight i min j i final j 1 N if j q N 1 break 以上程序段对当前已更新的辅助数组们进行处理 选出当前 weight 数组中的最小项 if min MAX break for i 1 i t citynum i mintime MAX min MAX if final i 1 continue if t map j i flightnum 0 continue for k 1 path j k j k if path j k 1 j m path j k n t map m j mintimeflight n 为上一次选出的最短 weight 路径中最后一班航班的编号 从 m 到 j for k 1 min MAX kt map j i flightinf k time1 t map j i flightinf k realwaitingtime 24 3600 t map m j flightinf n time2 t map j i flightinf k time1 t map j i flightinf k time2 t map j i flightinf k time1 24 3600 24 3600 else if t map