交通图咨询查询系统数据结构c语言.doc

信息科学与工程学院
《结构数据》
课程设计报告
课程设计名称: 交通咨询系统
专业班级: 计算机xxx
学生姓名: xxx
学号: 2015xxxx
指导教师: xx
课程设计时间: —
计算机应用技术专业课程设计任务书
学生姓名
Xxx
专业班级
学号
题目
交通咨询系统
课题性质
A
课题来源
D
指导教师
白浩
同组姓名
无
主要内容
建立交通网络图的存储结构。
某个城市到达其余各城市的最短路径。
实现两个城市之间最短路径的问题。
主要目的是给用户提供路径咨询
任务要求
根据需求分析给出概要设计,本系统包括以下功能模块:添加信息、查询信息、删除信息、修改信息、退出和保存信息;
结合课题利用数据结构相关知识,利用C语言实现该系统的所有上述功能,要求界面友善,程序运行正常;
提交课程设计报告1份(具体写作要求参考样例),可运行的系统和源代码电子版一套。
参考文献
严蔚敏.《数据结构(C语言版)》.北京:清华大学出版社
谭浩强.《C语言程序设计》.(第三版)北京:清华大学出版社
审查意见
指导教师签字:xx
教研室主任签字:xx
2016 年 06 月 27 日
说明:本表由指导教师填写,由教研室主任审核后下达给选题学生,装订在设计(论文)首页
填表说明
1.“课题性质”一栏:
;
;
(如CAI课题等);
;
。
2.“课题来源”一栏:
、省、市级以上科研课题;
、事业单位委托课题;
、院(系、部)级基金课题;
。
目录
1 需求分析 1
添加交通图信息 1
查询单源最短路径 1
查询多源最短路径 1
更新交通图信息 2
读取、保存信息 2
2 概要设计 3
数据类型的定义 3
功能模块结构图 4
3 运行环境 6
4 开发工具和编程语言 6
5 详细设计 7
图结构的基本操作 7
8
8
8
8
迪杰斯特拉算法的实现 8
迪杰斯特拉算法函数 8
提取迪杰斯特拉函数信息 8
求多源最短路径 8
6 程序编码 9
7 运行结果 41
8 心得体会 46
9参考文献 47
需求分析
本系统中的数据来源于标准输入设备(如键盘)和文件,可以实现对交通图城市、城市到其余城市的距离的操作,根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离,各个城市到各个城市的最短距离,以及路径。本系统要实现的功能有:添加城市和城市间距离,删除城市及城市间距离,修改城市间距离,查询城市间的最短路径,查询某个城市到某个城市的最短路径。具体如下:
添加交通图信息
能录入新数据(城市和路径)。当录入了重复的城市和路径时,则提示数据录入重复并取消录入;当交通图中超过15个城市时,存储空间已满,不能再录入新数据;录入的新数据能按递增的顺序自动进行条目编号。
查询单源最短路径
能够实现输入起点城市名后,查询出其到各个城市的最短路径,输出该城市到的其他所有的城市的最短路径。
查询多源最短路径
输入起点城市名和终点城市名,查询出两个城市的最短路径,并输出该最短路径。
更新交通图信息
根据给定的城市名能够修改该城市的名字。或者输入两个城市,修改一条路径的距离。
删除交通图信息
根据输入的城市名,删除与该城市有关的所有路径。输入两个城市可以删除一条路径。
读取、保存信息
能够实现退出系统时把交通图中的信息保存在一个文件中,在程序瑕疵运行时能够读取出来。
概要设计
数据类型的定义
定义交通图城市的元素类型
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;