全国交通资讯模拟数据结构课程设计报告

1、精品文档全国交通咨询模拟系统的设计与实现1. 问题描述出于不同目的的旅客对交通工具有不同的要求。 例如 , 因公出差的旅客希望在旅途中的时间尽可能短 , 出门旅游的游客则期望旅费尽可能省 , 而老年旅客则要求中转次数最少。 编制一个全国城市间的交通咨询程序 , 为旅客提供两种或三种最优决策的交通咨询。2. 需求分析(1) 提供对城市信息进行编辑 ( 如 : 添加或删除 ) 的功能。(2) 城市之间有两种交通工具：火车和飞机。(3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具。(4) 旅途中耗费的总时间应该包括中转站的等候时间。(5) 咨询以用户和计算机的对话方式进行。由

2、用户输入起始站、终点站、最优决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达 , 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。3. 概要设计因为全国交通咨询模拟中有众多城市之间的连接关系，为实现全国交通咨询系统的开发，采用图类型与邻接表类型来存储城市之间的信息。下面给出他们的 ADT的定义。3.1抽象数据类型定义如下：typedef struct unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作结果： 构造带权

3、 ( 费用 ) 图。unDiGraph* CreateTimeG()操作结果： 构造带权（时间）图。构造飞机带权 ( 费用 ) 图。PathMat *Floyed(unDiGraph *D)操作结果： Floyed 函数 求任意两点的最短路径。3.2系统功能模块设计全国交通咨询模拟系统由 4 个功能模块组成： 添加城市、删除程序、 采用火车出行、 采用飞机出行。1欢迎下载精品文档下面给出功能模块图，如图3-1 所示。图 3-1 全国交通咨询模拟功能模块图3.3 主要函数调用关系图（给出 ADT内基本操作的那些函数之间的函数调用关系图）如图 3-2 所示。2欢迎下载精品文档图 3-2系统函数调用

4、关系图3.4 主界面设计为了实现全国交通咨询模拟系统， 需要设计一个含有多菜单项的主控菜单子程序， 以链接系统中各个子项目的调用，为了方便用户使用本系统，本系统主控菜单的运行界面如图3-3 所示。4. 详细设计实现全国交通咨询模拟系统的开发， 采用图结构类型存储城市的信息。 其中，各城市间的邻接关系用图的邻接矩阵类型存储； 城市信息用结构体数组存储， 其中每个数组元素是一个结构体变量， 包含时间和费用三个分量； 图的顶点的个数和边的个数由变量费用、时间大小表示，它们是整型数据。3欢迎下载精品文档4.1数据类型定义数据存储：有向图、邻接表函数调用：#include <windows.h&g

5、t;#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h>#include <malloc.h>/引用的文本件#define INF 65535/定义一个最大数定为无穷值#define MAX 13typedef int costAdjMAX+1MAX+1;/图邻接矩阵从 1 开始记数int PathMAX+1MAX+1;/图邻接矩阵从 1 开始记数int o13,h;typedef struct unDiGraphint numVert

6、s; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG; /图的定义costAdj B,L;void pr(int i)/选择城市void pri()/输出城市unDiGraph *CreateCostG()/构造带权 (费用)图返回首地址 G：unDiGraph *CreateTimeG()/构造带权 (时间)图返回首地址 G：unDiGraph*CreateFlyG()/飞机的相关信息void Floyed(unDiGraph *D,unDiGraph *M) /Floyed函数 求任意两点的最短路径：void prn_pass(int i,int j) /为了求从

7、 i 到 j 的最短路径，只需要调用如下的过程void time()/求最少时间路径。void money()/求最少花费路径void administrator()/管理员功能void main()/main函数4.2系统子程序详细设计4.2.1求最小路径Void ShortPath_DIJ(AMGraph G, int v0,PathMatrix &P, ShortpathTable &D)For(v = 0;v <G.vexnum;+v)Finalv = FALSE;Dv = G.arcev0v;For( w = 0; w < G.vexnum; +w )。4

8、欢迎下载精品文档Pvw = FALSE;If ( Dv < INFINITY ) /如果有直接互通的两个顶点，直接将这个路径赋值到数组PV.Pvv0 = TRUE;Pvv = TRUE;Dv0 = 0; finalv = TRUE;/*下面开始主循环，每次求得v0 到某个 v 顶点的最短路径， 同时刷新之前的最短路径。 */对于除了v0 之外的顶点（这个循环仅仅限制次数，i 的值不用。Min = INFINITY; /假定初始的 ”最小值 ”为无穷大。For ( w = 0; w < G.vexnum; +w )If ( !finalw) /w定点在 V-S 中，及还未确定的顶点。

9、If ( Dw < min)v = w;min = Dw; /随着循环进行，依与v0 的距离大小，从小到达取的顶点v，并标记进 final。Finalv = TRUE; /标记已经找到For ( w = 0; w < G.vexnum; w+ )/ 更新路径If ( !finalw && ( min + G.arcsvw)Dw = min + G.arcsvw;Pw = Pw;/把一行都给赋值Pww = TRUE;4.2.2利用邻接表输出结果/ 邻接表中表对应的链表的特点。Typedef struct ENodeInt ivex ; /该边所指向的顶点的位置。5欢迎下载精品文档Struct ENode*next_edge; /指向下一条弧的指针。ENode,*PENode;/邻接表中表的顶点Typedef struct VNodeChar data; /顶点信息ENode *first_edge; /指向第一条依附该顶点的弧VNode;/邻接表Typedef st