交通图咨询查询系统数据结构(C语言)讲述.doc

信息科学与工程学院 《结构数据》 课 程 设 计 报 告 课程设计名称： 交通咨询系统 专 业 班 级 ： 计算机xxx 学 生 姓 名 ： xxx 学 号 ： 2015xxxx 指 导 教 师 ： xx 课程设计时间： 2016.07.04—2016.07.08  计算机应用技术 专业课程设计任务书 学生姓名 Xxx 专业班级 学号 题 目 交通咨询系统 课题性质 A 课题来源 D 指导教师 白浩 同组姓名 无 主要内容 建立交通网络图的存储结构。 某个城市到达其余各城市的最短路径。 实现两个城市之间最短路径的问题。 主要目的是给用户提供路径咨询 任务要求 根据需求分析给出概要设计，本系统包括以下功能模块：添加信息、查询信息、删除信息、修改信息、退出和保存信息； 结合课题利用数据结构相关知识，利用C语言实现该系统的所有上述功能，要求界面友善，程序运行正常； 提交课程设计报告1份（具体写作要求参考样例），可运行的系统和源代码电子版一套。 参考文献 严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社 谭浩强.《C语言程序设计》.（第三版）北京：清华大学出版社 审查意见 指导教师签字：xx 教研室主任签字：xx 2016 年 06 月 27 日  填 表 说 明 1．“课题性质”一栏： A．工程设计； B．工程技术研究； C．软件工程（如CAI课题等）； D．文献型综述； E．其它。 2．“课题来源”一栏： A．自然科学基金与部、省、市级以上科研课题； B．企、事业单位委托课题； C．校、院（系、部）级基金课题； D．自拟课题。 目录 1 需求分析 1 1.1 添加交通图信息 1 1.2 查询单源最短路径 1 1.3 查询多源最短路径 1 1.4 更新交通图信息 2 1.6 读取、保存信息 2 2 概要设计 3 2.1 数据类型的定义 3 2.2 功能模块结构图 4 3 运行环境 6 4 开发工具和编程语言 6 5 详细设计 7 5.1 图结构的基本操作 7 5.1.1添加城市结点和路径结点 8 5.1.2修改城市结点和路径结点 8 5.1.3删除城市结点和路径结点 8 5.1.4退出保存 8 5.2 迪杰斯特拉算法的实现 8 5.2.1 迪杰斯特拉算法函数 8 5.2.2 提取迪杰斯特拉函数信息 8 5.2.3 求多源最短路径 8 6 程序编码 9 7 运行结果 41 8 心得体会 46 9参考文献 47  需求分析 本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。本系统要实现的功能有：添加城市和城市间距离，删除城市及城市间距离，修改城市间距离，查询城市间的最短路径，查询某个城市到某个城市的最短路径。具体如下： 添加交通图信息 能录入新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。 查询单源最短路径 能够实现输入起点城市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。 查询多源最短路径 输入起点城市名和终点城市名，查询出两个城市的最短路径，并输出该最短路径。 更新交通图信息 根据给定的城市名能够修改该城市的名字。或者输入两个城市，修改一条路径的距离。 1.5 删除交通图信息 根据输入的城市名 ，删除与该城市有关的所有路径。输入两个城市可以删除一条路径。 1.6 读取、保存信息 能够实现退出系统时把交通图中的信息保存在一个文件中，在程序瑕疵运行时能够读取出来。 概要设计 数据类型的定义 定义交通图城市的元素类型 typedef struct _city{ char name[10];城市名 struct _path * firstpath；//第一个路径 }AdjList[15],CityNode; 定义交通图的路径元素类型 typedef struct _path{ int adjcity//邻接点域 int distance；//距离 struct _path *nextpath；//下一个路径 }PathNode,*PathPtr; 定义交通图类型 typedef struct { int cities; int paths; AdjL