滁州学院
课程设计报告
课程名称： 数据结构课程设计 设计题目： 交通咨询模拟 系 别： 计算机与信息工程学院
专 业： 网络工程（无线传感器网络方向） 组 别：
起止日期: 2012年6月11号-2012年6月24号 指导教师： 胡成祥
计算机技术与科学系二〇一二年制
1 / 17
课程设计任务书
课程设计题目 组长 系别 组员 指导教师 葛秋婷 计算机与信息工程学院 交通咨询模拟 学号 专业 2011211366 班级 网工114 网络工程（无线传感器网络方向） 鲁猛(2011211396) 贾发展(2011211378) 李保磊(2011211385) 王礼辉(2011211415) 黄二辉(2011211377) 胡成祥 1.巩固和加深学生对数据结构课程基本知识的理解，综合该课程中所学的理论知识，独立或联合完成一个数据结构应用课题的设计； 课程设计目的 2.根据选题需要，通过查阅手册和文献资料，培养分析和解决实际问题的能力； 3.熟练掌握图基本数据结构的定义、存储结构和相应的算法，并可熟练利用c语言进行实现。 Windows xp + VC++ 6.0 1.选择合适的数据存储结构；2.输入两个城市的代码，系统统计出两地之间的所有可达的路径及最短路径；3.输入一个城市的代码，系统输出一个城市到其余城市的最短路径。 课程设计工作进度计划 课程设计所需环境 课程设计任务要求 序号 起止日期 1 2 3 4 5 6 2012.6.11~2012.6.12 2012.6.12~2012.6.13 2012.6.14~2012.6.16 2012.6.17~2012.6.20 2012.6.21~2012.6.22 2012.6.22~2012.6.24 工 作 内 容 分析设计内容和查找资料 构思算法思想及所需子函数 编写主函数及子函数 调试运行函数及修改程序 课题答辩及撰写课程设计报告 总结经验并各自字写总结体会与心得 分工情况 葛秋婷、鲁猛、贾发展、王礼辉分析设计内容；黄二辉、李保磊查找资料 葛秋婷、鲁猛、贾发展、李保磊、王礼辉、黄二辉一起讨论 葛秋婷编写主函数，鲁猛、王礼辉，贾发展各编写部分子函数 李保磊调试运行程序，鲁猛、葛秋婷、贾发展、王礼辉、黄二辉修改程序代码 李保磊、黄二辉编写课程设计报告 各人总结经验，写课程设计心得 教研室审核意见： 教研室主任签字： 年 月 日 2 / 17
目 录
1引言 ................................................................................................. - 1 -资料个人收集整理，勿做商业用途 2需求分析 ....................................................................................... - 1 -资料个人收集整理，勿做商业用途 2.1问题描述 .............................................................................. - 1 -资料个人收集整理，勿做商业用途 2.1.1课程设计题目 ............................................................ - 1 -资料个人收集整理，勿做商业用途 2.1.2课程设计任务及要求 .............................................. - 1 -资料个人收集整理，勿做商业用途 2.1.3软硬件运行环境级开发工具 ............................... - 1 -资料个人收集整理，勿做商业用途 2.2解题思路 .............................................................................. - 1 -资料个人收集整理，勿做商业用途 2.3数据结构 .............................................................................. - 2 -资料个人收集整理，勿做商业用途 2.4算法思想 .............................................................................. - 2 -资料个人收集整理，勿做商业用途 3概要设计 ....................................................................................... - 3 -资料个人收集整理，勿做商业用途 4详细设计 ....................................................................................... - 3 -资料个人收集整理，勿做商业用途 5系统测试 ....................................................................................... - 7 -资料个人收集整理，勿做商业用途 5.1十城市信息录入和菜单界面 ........................................ - 7 -资料个人收集整理，勿做商业用途 5.2查询一个城市到所有城市的最短路径 ..................... - 8 -资料个人收集整理，勿做商业用途 5.3查询两城市之间最短路径 ............................................. - 8 -资料个人收集整理，勿做商业用途 5.4查询两城市间所有路径 .................................................. - 9 -资料个人收集整理，勿做商业用途 6课程设计总结与体会 ............................................................... - 9 -资料个人收集整理，勿做商业用途 致谢 .................................................................................................. - 10 -资料个人收集整理，勿做商业用途 参考文献 ......................................................................................... - 10 -资料个人收集整理，勿做商业用途 附录 .................................................................................................. - 10 -资料个人收集整理，勿做商业用途
3 / 17
1引言
如今，各城市发展迅速，道路越来越多，对出行的人来说，这是一种压力，种种地不方便，让人们焦头烂额，为此我们小组设计了交通咨询模拟，帮人们解决这些问题。资料个人收集整理，勿做商业用途 交通咨询模拟的主要功能是可以列出从一个城市到另一个城市的所有路径，供所需要的人选择。有时候最短路径并不一定是人们所需要的，最适合的才是最好的，为了这个思想，我们小组经过讨论，决定把所有路径都列出来，供使用者选择，因为我们编写的程序是面向所有使用者。在这里，你可以找到你所需要的任何路径，这是我们小组设计这个程序的初衷，也是对社会的一点贡献。资料个人收集整理，勿做商业用途 2需求分析
2.1问题描述
2.1.1课程设计题目
交通咨询模拟
2.1.2课程设计任务及要求
设计内容：
设计一个包含不少于10个城市的交通网，输出从A城市到B城市的所有可达的路径及里程。
设计要求：
(1) 选择合适的数据存储结构；（注：数据的输入可以是键盘输入或文件输入两种方式） (2) 输入两个城市的名称，系统统计出两地之间的所有可达的路径及里程。
2.1.3软硬件运行环境级开发工具
硬件：电脑
软件：Windows XP 系统；创天中文VC++6.0 开发工具：创天中文VC++6.0
2.2解题思路
（1）数据存储。城市信息（城市的代码）、交通信息（城市间的里程）都由键盘输入。 （2）数据的逻辑结构。根据设计任务的描述，其城市之间的交通问题是典型的图型结构，可看做有向图，图的顶点为城市，边为城市之间的里程耗费。资料个人收集整理，勿做商业用途 （3）数据的存储结构。采用邻接矩阵作为数据的存储结构。但是当邻接边不多时适合用邻接表，以傲储存空间的利用效率。资料个人收集整理，勿做商业用途 （4）用不同的功能模块对城市信息和交通信息进行编辑。对于旅客是希望输出两个城市之间的所有路径还是直接输出最短路径或者是一个城市到所有城市的最短路径可用菜单
- 1 - / 17
方式提示，同时要注意人机界面，便于管理和操作。资料个人收集整理，勿做商业用途 （5）最优决策功能模块。
○1输入城市信息和交通信息，用邻接矩阵生成带全网络，矩阵中对应处存放城市之间的里程。资料个人收集整理，勿做商业用途 ○2根据最优决策的要求，用Dijkstra算法求出一个城市到其余城市的最优值（最短路径），搜索过程中到每个城市的最优信息都保存在S集中。用Floyd算法求两个城市之间的最短路径和里程。其次利用深度优先遍历输出一个城市到另一个城市的所有路径，这一过程中，要用到栈保存信息，将经过的路径放到栈中，然后一一出栈。资料个人收集整理，勿做商业用途 ○3输出结果。从出发城市，搜索到目的城市，所经过的城市一一输入，并将其里程相加。
资料个人收集整理，勿做商业用途 （6）主程序可以有系统界面、菜单，并要求在运行过程中可以反复操做。
2.3数据结构
本程序运用了关于图的这种数据结构。 其抽象数据类型定义如下：
typedef struct
{
VertexType vexs[MVNum];//顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为int型 }MGraph;
2.4算法思想
本程序运用了图的知识，构造了有向带权里程图。（如图2-1所示 ）
- 2 - / 17