(交通运输)交通图咨询查询系统数据结构(C语言).

信息科学与工程学院《结构数据》

课程设计报告

课程设计名称：交通咨询系统

专业班级：计算机xxx

学生姓名：xxx

学号：2015xxxx

指导教师：xx

课程设计时间：2016.07.04 —2016.07.08

计算机应用技术专业课程设计任务书

说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页

填表说明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 运行结果................................................................ 4..1

8 心得体会................................................................ 4..6

9 参考文献................................................................ 4..7

1 需求分析

本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。本系统要实现的功能有：添加城市和城市间距离，删除城市及城市间距离，修改城市间距离，查询城市间的最短路径，查询某个城市到某个城市的最短路径。具体如下：

1.1 添加交通图信息

能录入新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15 个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。

1.2 查询单源最短路径

能够实现输入起点城市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。

1.3 查询多源最短路径

输入起点城市名和终点城市名，查询出两个城市的最短路径，并输出该最

短路径。

1.4 更新交通图信息

根据给定的城市名能够修改该城市的名字。或者输入两个城市，修改一条路径的距离。

1.5 删除交通图信息

根据输入的城市名，删除与该城市有关的所有路径。输入两个城市可以删除一条路径。

1.6 读取、保存信息

能够实现退出系统时把交通图中的信息保存在一个文件中，在程序瑕疵运行时能够读取出来。

2 概要设计

2.1 数据类型的定义

1. 定义交通图城市的元素类型

typedef struct _city{

char name[10]; 城市名

struct _path * firstpath ；// 第一个路径}AdjList[15],CityNode;

2. 定义交通图的路径元素类型

typedef struct _path{

int adjcity// 邻接点域

int distance ；// 距离

struct _path *nextpath ；// 下一个路径}PathNode,*PathPtr;

3. 定义交通图类型

typedef struct {

int cities;

int paths;

AdjList list ；

}Graph ;

4. 全局变量

PList head;

typedef int PathMatrix;

typedef int ShortPathTable;

PathMatrix P[MAX_CITIES][MAX_CITIES];

ShortPathTable D[MAX_CITIES];

2.2 功能模块结构图

根据需求分析，为了满足用户的功能需求，按照软件开发方法学中的模块划分原则，我将本系统主要划分为如下模块：操作交通图信息，和查询交通图路径两大模块。各模块之间的关系如图1 所示。

图 1 模块结构图为了实现上述功能模块，分别在顺序表和单链表物理结构上定义了多个函数，本系统定义的函数和功能如下：

1. 数据结构部分部分

void initalize_graph(Graph *G)

功能为：图初始化，即生成一个空图。

功能为：图的创建，用图存储数据。