交通咨询系统数据结构c语言

数 据 结 构 课 程 设 计

交通咨询系统设计

学 生 姓 名： 学 号： 指 导 教 师： 完 成 日 期：

目 录

1 设计任务书.................................................................................................................. 1

1.1 题目与要求....................................................................................................... 1 1.2 知识点............................................................................................................... 1 1.3 输入输出分析................................................................................................... 1 1.4 实现的功能....................................................................................................... 1 2 概要设计...................................................................................................................... 2

2.1 结构体类型及函数声明................................................................................... 2 2.2 主程序流程....................................................................................................... 2 3 详细设计...................................................................................................................... 3

3.1 数据类型实现................................................................................................... 3 3.2 程序代码........................................................................................................... 3 4 调试分析.................................................................................................................... 10

4.1 问题分析与回顾............................................................................................. 10 4.2 算法时空分析................................................................................................. 11 4.3 算法改进......................................................................................................... 11 4.4 经验和体会..................................................................................................... 11 5 测试结果.................................................................................................................... 12 参考文献.......................................................................................................................... 13

1 设计任务书

1.1 题目与要求

题目：编写程序实现交通咨询系统设计的模拟。 要求：（1）建立交通网络网的存储结构； （2）总体设计要画流程图； （3）提供程序测试方案；

（4）界面友好。

1.2 知识点

本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点。

1.3 输入输出分析

（1）普通输入

对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。

（2）对话式输入

在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。

（3）程序输出

对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()函数输出各个城市的代码城市名字对照表，用户可以更方便的使用。对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观。

1.4 实现的功能

在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。

1

2 概要设计

2.1 结构体类型及函数声明

（1）结构体

路径图结构体类型 MGraph 花费图结构体类型 HGraph （2）函数声明

void pri() //输出城市代号对照表函数。

void CreateMGraph(MGraph *G) //创建路径图函数，路径图存放于G中。 void CreateHGraph(HGraph *H) //创建花费图函数，花费图存放于H中。

void Dijkstra(MGraph *G, int v1,int n) //迪杰斯特拉算法求单源最短路径函数，v1为源点，n为城市个数，这个图存放于G中。

void Floyd(MGraph *G, int n) //弗洛伊德求两点间最短路径函数，n表示城市个数，这个图存放于G中。

void Floyd1(HGraph *H, int n) //弗洛伊德求两点间最小花费函数，n表示城市个数，这个图存放于H中。

2.2 主程序流程

（1）主程序调用模块图

主程序利用switch()语句实现各个模块的调用，主函数调用如图2-1所示。

主程序根据不同值主调函数 0退出 1求单源最短路径 2求两点间最短路径 3求两点间最小花费

图2-1 主程序调用模块图

2