3-交通咨询系统设计-数据结构-课程设计任务书.doc

交通资讯系统 系统需求分析 1.1问题描述 在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。 1.2功能要求 1.交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二是 某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的问题。主 要目的是给用户提供路径咨询。 2.本系统规定： (1)在程序中输入城市名称时，需输入0到5的城市代号 (2)在选择功 能是，应输入与所选功能对应的一个整形数据。 (3)程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径，两城市之间最短路径 2.概要设计 2.1系统总体设计 图2.1系统总体设计 2.2各模块的功能 void main() 主函数 void Dijkstr() 采用狄克斯特拉算法求从顶点v到其余个顶点的最短路径 void DisPath() 由path计算最短路径 void Ppath() 输出各条最短路径 void Floyd() 采用弗洛伊德算法求所有顶点之间的最短路径 void DisPath2() 由path计算最短路径 void Ppath2() 输出各条最短路径 2.3相关数据结构设计 1.数据结构 typedef int InfoType; typedef struct {char cityname; int no; InfoType info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n,e; VertexType vxs[MAXV]; }MGraph; 数据库结构：下表构成该系统的基本数据库 城市代号 邻接矩阵边数组 城市个数 路径 城市名称 int int int int char 3.详细设计 3.1采用c语言定义相关的数据结构 本系统定义了整形int,字符型char,还有结构体定义，建立图的存储结构 首先定义交通图的存储结构，邻接矩阵是表示图形中顶点之间相邻关系的矩阵.设G=（V，E）是具有n(n0)个顶点的图，则邻接矩阵具有如下定义的n阶方阵 Wij 若vi≠vj 且vi,vj∈E(G) A[i][j]= ∞ 其他 一个图的邻接矩阵表示是唯一的,除了许用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息 3.2函数调用关系图 3.2.1主函数 void main() { int i,j,z,x; MGraph g; int A[][MAXV]={{INF,5,INF,7,INF,INF},{INF,INF,4,INF,INF,INF}, {8,INF,INF,INF,INF,9},{INF,INF,5,INF,INF,6},{INF,INF,INF,5,INF,INF}, {3,INF,INF,INF,1,INF}}; g.n=6; g.e=10; for(i=0;ig.n;i++) for(j=0;jg.n;j++) g.edges[i][j]=A[i][j]; printf(******************* 交通咨询系统 **********************\n); printf(************* 1-查看系统中的城市代号 **********\n); printf(************* 2-一个城市到所有城市的最短路径 **********\n); printf(************* 3-任意的两个城市之间的最短路径 **********\n); printf(************* 0-退出 **********\n); printf(\n); printf(请选择：);sca