《交通咨询系统数据结构c语言》由会员分享，可在线阅读，更多相关《交通咨询系统数据结构c语言（17页珍藏版）》请在金锄头文库上搜索。
1、交通咨询系统数 据 结 构 课 程 设 计交通咨询系统设计学 生 姓 名： 学 号： 指 导 教 师： 完 成 日 期： 页脚内容14目 录1 设计任务书11.1 题目与要求11.2 知识点11.3 输入输出分析11.4 实现的功能12 概要设计22.1 结构体类型及函数声明22.2 主程序流程23 详细设计33.1 数据类型实现33.2 程序代码34 调试分析104.1 问题分析与回顾104.2 算法时空分析104.3 算法改进114.4 经验和体会115 测试结果11参考文献131 设计任务书1.1 题目与要求题目：编写程序实现交通咨询系统设计的模拟。要求：（1）建立交通网络网的存储结构；
2、 （2）总体设计要画流程图； （3）提供程序测试方案；（4）界面友好。1.2 知识点本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点。1.3 输入输出分析（1）普通输入对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。 （2）对话式输入在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。（3）程序输出对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()
3、函数输出各个城市的代码城市名字对照表，用户可以更方便的使用。对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观。1.4 实现的功能在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。2 概要设计2.1 结构体类型及函数声明（1）结构体路径图结构体类型 MGraph 花费图结构体类型 HGraph （2）函数声明void pri() /输出城市代号对照表函数。v
4、oid 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
5、 主程序流程（1）主程序调用模块图主程序利用switch()语句实现各个模块的调用，主函数调用如图2-1所示。 主程序根据不同值主调函数0退出1求单源最短路径2求两点间最短路径3求两点间最小花费图2-1 主程序调用模块图3 详细设计3.1 数据类型实现 （1）路径图结构体类型 Vertextype vexsMVNum; /顶点数组，顶点表示城市代号 Adjmatrix arcsMVNum MVNum; /邻接矩阵定义路径图 MGraph;（2）花费图结构体类型typedef struct Vertextype vexsMVNum; /顶点数组，顶点表示城市代号Adjmatrix arcsMVN
6、um MVNum; /邻接矩阵定义花费图 HGraph;3.2 程序代码 #include #include #define MVNum 100 /最大顶点数 #define Maxint 65535 /定义一个最大数，其意义为无穷大enum booleanFALSE,TRUE; typedef char Vertextype; typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /顶点数组 类型假定为char型 Adjmatrix arcsMVNum MVNum; / 邻接矩阵 假定为int型 MGraph; typedef
7、 struct Vertextype vexsMVNum; /顶点数组 类型假定为char型 Adjmatrix arcsMVNum MVNum; / 邻接矩阵 假定为int型 HGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum; void pr(int i)switch(i)case 1:printf(北京 );break;case 2:printf(天津 );break;case 3:printf(郑州 );break;case 4:printf(徐州 );break;case 5:printf(西安 );break;case
8、 6:printf(成都 );break; case 7:printf(武汉 );break;case 8:printf(上海 );break;case 9:printf(福州 );break; case 10:printf(南昌 );break;case 11:printf(株洲 );break;case 12:printf(贵阳 );break; case 13:printf(昆明 );break;case 14:printf(广州 );break;void pri()int i;printf(城市代号对照表n);printf(*);for(i=1;i=14;i+)printf(%d.,i
9、); pr(i); pr(i);printf(n); printf(*);void CreateMGraph(MGraph *G) /采用邻接矩阵表示法构造有向图G，此图为带权距离图 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) for(j=1;jarcsij=Maxint; / 初始化邻接矩阵 G-arcs12=G-arcs21=137; G-arcs24=G-arcs42=674; G-arcs13=G-arcs31=695; G-arcs34=G-arcs43=349;G-arcs35=G-arcs53=511; G-arcs56=G
10、-arcs65=842;G-arcs37=G-arcs73=534; G-arcs48=G-arcs84=651;G-arcs613=G-arcs136=1100; G-arcs612=G-arcs126=967;G-arcs711=G-arcs117=409; G-arcs810=G-arcs108=825;G-arcs910=G-arcs109=622; G-arcs1011=G-arcs1110=367;G-arcs1112=G-arcs1211=902;G-arcs1213=G-arcs1312=639; G-arcs1114=G-arcs1411=675; void CreateHG
11、raph(HGraph *H) /采用邻接矩阵表示法构造有向图H,此图为带权花费图 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) for(j=1;jarcsij=Maxint; / 初始化邻接矩阵 H-arcs12=H-arcs21=20; H-arcs24=H-arcs42=93; H-arcs13=H-arcs31=93; H-arcs34=H-arcs43=51;H-arcs35=H-arcs53=72; H-arcs56=H-arcs65=112;H-arcs37=H-arcs73=75; H-arcs48=H-arcs84=91;H-arcs613=H-arcs136=141; H-arcs612=H-arcs126=128;
