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

页脚下载后可删除，如有侵权请告知删除！
数 据 结 构 课 程 设 计
交通咨询系统设计
学 生 姓 名：
学 号：
指 导 教 师：
完 成 日 期：
页脚下载后可删除，如有侵权请告知删除！
目 录
1 设计任务书 1
题目与要求 1
知识点 1
输入输出分析 1
实现的功能 1
2 概要设计 2
构造体类型及函数声明 2
主程序流程 2
3 详细设计 3
数据类型实现 3
程序代码 3
4 调试分析 10
问题分析与回忆 10
算法时空分析 11
算法改良 11
经历和体会 11
5 测试结果 12
参考文献 14
页脚下载后可删除，如有侵权请告知删除！
1 设计任务书
题目与要求
题目：编写程序实现交通咨询系统设计的模拟。
要求：〔1〕建立交通网络网的存储构造；
〔2〕总体设计要画流程图；
〔3〕提供程序测试方案；
〔4〕界面友好。
知识点
本次课程设计应用到了图的创立、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、构造体、宏定义、自定义类型、函数的声明与调用等知识点。
输入输出分析
〔1〕普通输入
对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。
〔2〕对话式输入
在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。
〔3〕程序输出
对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()函数输出各个城市的代码城市名字对照表，用户可以更方便的使用。对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进展显示，使界面更美观。
实现的功能
在交通网络越来越兴旺的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。
页脚下载后可删除，如有侵权请告知删除！
2 概要设计
构造体类型及函数声明
〔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中。
主程序流程
〔1〕主程序调用模块图
主程序利用switch()语句实现各个模块的调用，主函数调用如图2-1所示。
　　　　　 主程序根据不同值主调函数
0退出
1求单源最短路径
2求两点间最短路径
3求两点间最小花费
图2-1 主程序调用模块图
页脚下载后可删除，如有侵权请告知删除！
3 详细设计
数据类型实现
〔1〕路径图构造体类型
{
Vertextype vexs[MVNum]; //顶点数组，顶点表示城市代号
Adjmatrix arcs[MVNum] [MVNum]; //邻接矩阵定义路径图
}MGraph;
〔2〕花费图构造体类型
typedef struct
{
Vertextype vexs[MVNum]; //顶点数组，顶点表示城市代号
Adjmatrix arcs[MVNu