交通咨询系统设计报告

重庆科技学院重庆科技学院 数据结构数据结构 课程设计课程设计 报告报告 学 院 电气与信息工程学院 专业班级 计科 2 学生姓名 学 号 设计地点 单位 计算机基础自主学习中心 设计题目 交通咨询系统设计 完成日期 2012 年 7 月 6 日 指导教师评语 成绩 五级记分制 指导教师 签字 重庆科技学院重庆科技学院 课程设计任务书课程设计任务书 设计题目 交通咨询系统的设计 学生姓名 课程名称数据结构课程设计专业班级计 地 点计算机基础自主学习中心起止时间 2012 6 25 2012 7 6 设 计 内 容 及 要 求 人们在出差 旅游出行时 往往关心节省交通费用或节省所需要的时间等问题 可以用一个图结构来表示交通网络 图中顶点表示城市 边表示城市之间的交通情况 其权值可代表里程 交通费用或时间 设计一个交通咨询系统 能让旅客咨询从任一 个城市到另一个城市之间的最短路径 里程 最少交通费用或最少时间等问题 该设计的内容主要分两部分 一是建立交通网络图的存储结构 二是实现求两个 城市顶点之间的最短路径算法 要求表示城市之间的交通关系的边的信息中包括里程 费用 时间三个值 程序 可实现求任两个城市之间的最短里程 最少时间或最少费用的路线 建立图的存储结 构时要求从文本文件中读入顶点和边的信息 设 计 参 数 测试数据要求 交通图中顶点数不少于 16 个 边数不少于 20 每条边有三个权值 里程 交通 费用 时间 进 度 要 求 2012 6 25 完成任务的讲解 并接受课程设计任务 选定课程设计的题目 2012 6 26 了解任务的算法 并画出算法的程序流程图 对任务的关键技术进行验 证 并确定解决办法 2012 6 27 2012 6 29 程序设计及编码 上机调试 2012 7 02 对程序进行调试 设计测试用例进行测试 2012 7 03 整理课程设计的过程 并进行总结 完善程序功能 2012 7 04 编写课程设计报告初稿 2012 7 05 完善课程设计报告 并准备答辨 2012 7 06 提交课程设计报告和程序 进行答辨 参 考 资 料 1 严蔚敏 吴伟民 数据结构 清华大学出版社 2007 3 2 程杰 大话数据结构 清华大学出版社 2011 6 3 美 Stephen Prata C Primer Plus 中文版 第五版 人民邮电出版社 2005 2 其 它 说 明 1 本表应在每次实施前一周由负责教师填写二份 学院审批后交学院教务办备案 一 份由负责教师留用 2 若填写内容较多可另纸附后 3 一题多名学生共用的 在设计 内容 参数 要求等方面应有所区别 系主任 雷亮 指导教师 黄永文 王双明 熊茜 彭军 王成敏 2012 年 6 月 20 日 摘要摘要 在交通网络非常发达 人们在出差 旅游出行时 往往关心节省交通费用或节省 所需要的时间等问题 对于这样一个人们关心的问题 可以用一个图结构来表示交通 网络 利用计算机建立一个交通咨询系统 图中顶点表示城市 边表示城市之间的交 通情况 其权值可代表里程 交通费用或时间 比如任意一个城市到其他城市的最短 路径 任意两个城市之间的最短路径问题 本次设计的交通咨询系统主要是运用 C 语言的数据结构来完成交通图的存储 图 中顶点的单源最短路径和任意一对顶点间的最短路径问题 关键词 关键词 数字结构 C 语言 交通咨询 最短路径 目录目录 1 1 设计内容和要求设计内容和要求 1 1 11 1 问题描述问题描述 1 1 21 2 需求分析需求分析 1 2 2 课程需求分析课程需求分析 2 2 12 1 算法思路算法思路 2 2 22 2 数据结构体数据结构体 2 2 32 3 基本操作基本操作 3 2 42 4 算法应用算法应用 3 2 52 5 程序设计流程图程序设计流程图 4 3 3 功能模块详细设计功能模块详细设计 5 3 13 1 测试数据测试数据 5 3 23 2 程序调试程序调试 5 4 4 课程总结与体会课程总结与体会 19 5 5参考文献参考文献 20 6 6 致谢致谢 21 重庆科技学院 数据结构 课程设计报告 1 1 1 设计内容和要求设计内容和要求 1 11 1 问题描述 问题描述 设计 实现一个全国大城市间的交通咨询程序 为旅客提供三种最优决策方 案 1 时间最短 2 费用最小 3 里程最少 1 21 2 需求分析 需求分析 该程序所做的工作的是模拟全国交通咨询 为旅客提供三种最优决策的交 通咨询 此程序规定 1 在程序中输入城市名称时 需输入 20 个字符以内的字符串 输入费用时需 输入一个实型数据 输入时间时需输入一个整型数据 在选择功能时 应输入与所选 功能对应的一个整型数据 2 程序的输出信息主要是 最快需要多少时间才能到达 或最少需要多少 旅费才能到达 或两城市间需要走过的最短路程 并详细说明如何坐车才能最省 3 程序的功能包括 提供对城市信息的编辑 对两城市间时间 花费 还有 路程的编辑 提供三种最优决策 最快到达 最省钱到达 最少路程到达 重庆科技学院 数据结构 课程设计报告 2 2 2 课程需求分析课程需求分析 2 12 1 算法思路算法思路 1 数据存储 城市信息 交通信息 城市间的里程 旅费和时间 存储于磁盘文 件 建议把城市信息 交通信息还有城市和交通信息数目分开存于三个文件中 用 fread 和 fwrite 函数操作 2 数据的逻辑结构 根据设计任务的描述 其城市之间的旅游交通问题是典型 的图结构 可看作为有向图 图的顶点是城市 边是城市之间所耗费的时间 旅费 里程 3 数据的存储结构 采用邻接矩阵作为数据的存储结构 提高空间的存储效率 4 用不同的功能模块对城市信息和交通信息进行编辑 可用菜单方式或命令提 示方式 只要能方便的对城市信息和交通信息进行管理即可 6 主程序可以有系统界面 菜单 也可用命令提示方式 选择功能模块执行 要求在程序运行过程中可以反复操作 2 22 2 数据结构数据结构体体 typedef struct lu 交通信息数据类型 int distance 城市间里程 int cost 城市间旅费 int time 城市间时间 lu lujin max max typedef struct city 城市数据类型 char name 20 城市名称 citys max typedef struct 网络图的数据类型 citys clist 城市信息 lujin arcs 边的信息 int c n l n 边和顶点数目 Graph typedef struct 最短路径 重庆科技学院 数据结构 课程设计报告 3 char adjvex int mincost 最少旅费 int mindistance 最短里程 int mintime 最少时间 closedge 2 32 3 基本操作基本操作 void zairu Graph G 导入文件中的信息 能否是程序运行 void Administer Graph G 管理员操作界面 由主函数调用 void show Graph G 显示系统中的全部城市信息和交通信息 int insertcity Graph G 增加城市信息 int insertlu Graph G 增加交通信息 int Located Graph G char p 返回邻接矩阵的位置下标 系统中的关键 void baocun Graph G 将城市信息 交通信息保存在文件中 int serchlu Graph G 搜索交通信息 void mindistance Graph G int v0 int v1 最少里程计算 迪杰斯特拉算 法 void mincost Graph G int v0 int v1 最少旅费计算 迪杰斯特拉算法 void mintime Graph G int v0 int v1 最少时间计算 迪杰斯特拉算法 2 42 4 算法应用算法应用 在判断源点到其余各点的最短路径时运用迪杰斯特拉算法 一般情况下 假设 S 为以求得最短路径的终点的集合 则可证明 下一条最短路 径 设其终点为 x 或者是弧 v k 或者是中奖只经过 S 中的顶点而最后到达顶点 x 的路径 这可用反证法来证明 假设此路径上有一个顶点不在 S 中 则说明存在一条 终点不在 S 而长度比此路径短的路径 但是 这是不可能的 因为我们是按照路径长 度递增的次序来产生各最短路径的 故长度比此路径段的所有路径均已产生 它们的 终点必定在 S 中 即假设不成立 因此 在一般情况下 下一条长度次短的最短路径的长度必是 i viDMinj D SV 其中 D i 或者是弧上的权值 或者是 D k 和弧上的权值 i vv Svk ik vv 重庆科技学院 数据结构 课程设计报告 4 之和 1 假设用带权的邻接矩阵 arcs 来表示带权有向图 arcs i j 表示弧 上的权值 若存在 则置 arcs i j 为 在计算机上可用允许的v 最大值代替 S 为已找到从 v 出发的最短路径的终点的集合 他的初始状态为空集 那么 从 v 出发到图上其余个顶点 终点 vi 可能达到的最短路径长度的初值为 VvivGVexLocatearciD i 2 选择 使得 j v S D VviMiniD i 就是当前求得的一条从 v 出发的最短路径的终点 令 j v jSS 3 修改从 v 出发到集合 V S 上任一顶点可达的最短路径长度 如果 k v kDkjarcsiD 则修改为 kD kjarcsjDkD 4 重复操作 2 3 共 n 1 次 由此求得从 v 到图上其余各点的最短路径是依路 径长度递增的序列 2 52 5 程序设计流程图 程序设计流程图 交通咨询系统交通咨询系统 管理员管理员 用户用户 添加城市添加城市 查询最少查询最少 花费路线花费路线 查询最短查询最短 时间路线时间路线 查询最短查询最短 里程路线里程路线 退出退出 添加交通添加交通 路线路线 返回上一返回上一 级菜单级菜单 返回上一返回上一 级菜单级菜单 显示所有交通路线显示所有交通路线 重庆科技学院 数据结构 课程设计报告 5 图 2 1 程序设计流程图 3 3 功能模块详细设计功能模块详细设计 3 13 1 测试数据测试数据 表 3 1 城市信息 北京天津石家庄济南 重庆成都郑州徐州 九江武汉广安无锡 表 3 2 交通信息表 起始目的旅费 元 时间 小时 里程 公里 重庆广安 501300 重庆成都 1002500 广安成都 601100 北京天津 1001250 济南天津 2002300 成都南京 50020700 浙江郑州 300301000 九江武汉 20010500 南京无锡 1005200 石家庄北京 1005300 浙江徐州 300241500 重庆南京 500232000 成都郑州 400302400 无锡北京 700403500 徐州上海 20015895 上海温州 1008300 重庆科技学院 数据结构 课程设计报告 6 济南重庆 15015500 天津武汉 530282593 广安济南 300231842 上海重庆 534281434 3 23 2 程序调试程序调试 1 主界面包括四个选项 选项一 管理员管理界面 选择该项可进行城市交通系 统的管理 选项 二 用户咨询界面 选择该项可进行最少费用 最少时间 最短里程 的决策咨询 选项三 显示城市交通系统 选择该项可显示城市交通系统的所有信息 包括城市 交通路线信息 选项四 退出程序 选择该项将退出程序 图 3 1 程序主界面 在该系统运行的开始会从文件读取交通信息 如果文件不存在会导致程序运行错 误 出现下图情况 重庆科技学院 数据结构 课程设计报告 7 图 3 2 文件不存在 该函数代码如下 void zairu Graph G 读取文本中的信息 FILE fpout fpin int cnum lnum char Fromc 20 Toc 20 int t i j for i 0 i max i for j 0 j arcs i j distance G arcs j i distance zuida G arcs i j cost G arcs j i cost zuida G arcs i j time G arcs j i time zuida fpout fopen number txt r assert fpout if fscanf fpout d d G l n lnum fclose fpout 读取城市顶点信息 fpout fopen city txt r for t 0 t c n t fscanf fpout s G clist t name fclose fpout 重庆科技学院 数据结构 课程设计报告 8 读取边的信息 起点 终点 距离 千米 花费 元 时间 分钟 fpout fopen lu txt r for t 0 t l n t fscanf fpout s s Fromc Toc i Located G Fromc j Located G Toc fscanf fpout d d d G arcs j i distance G arcs i j distance G arcs j i cost G arcs i j cost G arcs j i time G arcs i j time fclose fpout else fpin fopen number txt w assert fpin fprintf fpin 0 0 G l n 0 G c n 0 fclose fpin 2 管理员管理 界面首先出现登陆界面 采用加密技术 初始密码为 admin 菜单项包括 5 个选 项 选项一 增加城市信息 选项 二 增加交通路线信息 选项三 保存新增信息 返回上一级菜单 可返回主界面 重庆科技学院 数据结构 课程设计报告 9 图 3 3 管理员界面 在该界面中调用了三个重要函数 对城市 交通信息进行编辑和保存 int insertcity Graph G 增加城市 char name 20 printf 输入要增加的城市 scanf s name getchar if G c n 0 strcpy G clist 0 name name G c n 重庆科技学院 数据结构 课程设计报告 10 else for int i 0 i c n i if strcmp G clist i name name 0 return 1 else strcpy G clist G c n name name G c n return 1 图 3 4 增加城市 int insertlu Graph G 增加城市交通信息 char Fromc 20 Toc 20 int i j int d c t 重庆科技学院 数据结构 课程设计报告 11 printf 输入增加路径的出发城市 目的城市 距离 公里 花费 元 时间 小时 n scanf s s d d d Fromc Toc getchar i Located G Fromc j Located G Toc if i 1 j 1 return 1 else G arcs i j distance G arcs j i distance d G arcs i j cost G arcs j i cost c G arcs i j time G arcs j i time t G l n return 1 图 3 5 增加交通信息 重庆科技学院 数据结构 课程设计报告 12 void baocun Graph G 保存新增信息于文件中 FILE fpin int i m k 边和顶点的个数 fpin fopen number txt w assert fpin fprintf fpin d d G c n G l n fclose fpin 顶点信息 fpin fopen city txt w assert fpin for i 0 i G c n i fprintf fpin s G clist i name m i 10 if m 0 printf n fclose fpin 边的信息 fpin fopen lu txt w assert fpin for i 0 i G c n i for k i 1 k c n sizeof int 判断顶点是否已求出最 短路径 d int malloc G c n sizeof int 储存起始点到各点的最短路径 pred int malloc G c n sizeof int 最后用于输出最短路径 for v 0 v c n v finald v 0 d v G arcs v0 v cost if d v zuida pred v v0 else pred v 1 d v0 0 到起始点无路径 finald v0 1 v0 放入到 final 数组里 for i 1 ic n i 从 1 开始 因为起始点已经在 final 里面 剩下 n 1 个顶点 循环 n 1 次 mind zuida for w 0 wc n w if finald w 没有放进 final 里面的终点进行选择最短路径出来 if d w vexs v finald vd 1 放入 final 中 for w 0 w c n w if finald w pred w vd if pred v1 1 printf s 到 s G clist v0 name G clist v1 name printf 最短路程为 公里 d t t d v1 printf s G clist v0 name j pred v1 while j v0 printf s G clist j name j pred j printf s n G clist v1 name else printf s 到 s 没有信息 n G clist v0 name G clist v1 name 重庆科技学院 数据结构 课程设计报告 16 该代码在系统中是核心算法 图 3 7 最短路径 4 显示所有交通信息 图 3 8 交通信息 该函数代码如下 void show Graph G 重庆科技学院 数据结构 课程设计报告 17 int i k system cls printf n n 目前交通系统中含有 d 个城市 d 条旅游路径 n n n G c n G l n printf 各大城市 n for i 0 i G c n i printf s G clist i name if i 1 10 0 printf n printf n n n n printf 城市 t t 城市 t t 距离 公里 t 花费 元 t 时间 小 时 n for i 0 i G c n i for k i 1 k G c n k if G arcs i k distance zuida printf s t t s t t d t t d t t d n G clist i name G clist k name G arcs i k distance G arcs i k cost G arcs i k time system pause 该短代码中主要是读取三个文件 然后分别将信息输出在屏幕上 5 在该系统中还有一段代码 是该程序的核心内容 用于返回网络图结构中位 置下标 代码如下 重庆科技学院 数据结构 课程设计报告 18 int Located Graph G char p 返回数据位置 int i for i 0 i c n i if strcmp G clist i name p 0 return i