全国交通咨询模拟系统.doc

1题号：题号：5 题目题目:全国交通咨询模拟全国交通咨询模拟1. 需求分析需求分析---------------------------------------------------------1.1 问题描述问题描述----------------------------------------------------1.2 功能需求功能需求----------------------------------------------------2. 设计设计----------------------------------------------------------------2.1 逻辑结构逻辑结构-----------------------------------------------------2.2 存储结构分析存储结构分析-----------------------------------------------2.3 算法思想算法思想-----------------------------------------------------2.4 函数调用关系图函数调用关系图--------------------------------------------2.5 函数接口规格说明函数接口规格说明------------------------------------------3. 调试分析调试分析 ----------------------------------------------------------4. 用户手册用户手册 ----------------------------------------------------------5. 测试数据与测试结果测试数据与测试结果---------------------------------------------6. 源代码清单源代码清单---------------------------------------------------------1.1.需求分析需求分析1.11.1 问题描述问题描述出于不同目的的旅客对交通工具有不同的要求。

例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少 编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询21.21.2 功能需求功能需求（1）提供对城市信息进行编辑（如添加或删除）的功能2）城市之间有两种交通工具：火车和飞机提供对列车时刻表和飞机航班进行编辑 （增 设或删除）的功能3）提供两种最优决策：最快到达或最省钱到达全程只考虑一种交通工具4）旅途中耗费的总时间应该包括中转站的等候时间5）咨询以用户和计算机的对话方式进行32.2.设计设计1．．主程序流程图：主程序流程图：开始CreateGraph(GT) CreateGraph(GP)OpenGraph_T(GT) OpenGraph_P(GP)Main_Menu(GT,GP)DestoryGraph(GT) DestoryGraph(GP)结束SaveGraph_T(GT) SaveGraph_P(GP)42．．创建图算法流程图：创建图算法流程图：开始inextEdgep->elem.Moneyelem.jvex]重置每个顶点的最少钱的路径 dijkst [p->elem.jvex]=p->elem.Money t=p->elem SetPath(path[p->elem.jvex],st,p->elem.jvex,t)Yp=qYNFound = false求从 st 到 nd 的最短路径算法 并复制此路径 copyPath(path[w],path[v])开始11．．ShortestTimePath(GT,st,nd,p)算法流程图算法流程图10开始每个点初始一个最大值 初始每条路径 置时间＝0置起点的时间为 n 置 p 为起点的第一条边检测依附每个顶点的边依据迪杰斯特求每个起点到 终点的时间最少的路径结束12．．Manage_Menu(GT,GP)算法流程图算法流程图13．．City_Edit(GT,GP)算法流程图算法流程图开始Switch(choice)Case 1:Case 2:Case 3:Case 0:City_Edit(GT,GP)Train_Edit(GT,GP )Plane_Edit(GT,GP )break开始输入 n 进行选择n==1N1114. Train_Edit(GT,GP)算法流程图算法流程图注释：部分算法的设计思想相同，只是参数不同，故省略部分程序流程图。

N添加城市及相关信息Y结束n ==2删除城市及相关信息Y结束Nn ==0结束YN输出错误输入 n 进行选择开始While(true)输入 n 进行选择n==1NY输入列车的信息breakn==2删除列车的信息breakYNn==0breakYN重新输入 n 进行选 择Y Break 结束12四、四、源程序源程序#define MAXVTXNUM 30 //图中顶点数的最大值 /************顶点、边和图类型**********************************/ typedef struct //定义各车次及航班的信息 弧的信息 { int ivex; //起始点号 int jvex; //终点号 char Number[10]; // 车次号 int Money; //费用 int StartTime; //起始时间（秒） int EndTime; //终止时间（秒） int Time; //中途时间（秒） }EdgeInfo; //边的信息 typedef struct EdgeNode //边的信息 弧结点 { EdgeInfo elem; EdgeNode *nextEdge; }EdgeNode, *EdgePtr;//边的结点类型，指向边的指针typedef struct //城市信息 头结点 { char cityName[10]; int cityNumber; EdgePtr firstEdge; //指向的一条依附该顶点的边的指针 }Vnode; //顶点类型 typedef struct //图的结构 { Vnode Adjlist[MAXVTXNUM];//邻接表 int vexNum, edgeNum; //图中的顶点数和边数 int Flag[MAXVTXNUM]; //标志是否是图中的顶点,0 表示不是,1 表示是 }Graph; //图类型 /*****************图的基本操作**********************/ /************ 路径类型 *************************/ typedef struct { int vx,vy; //vx 为路径的起点,vy 为路径的终点 EdgeInfo p; //路径中边的信息 }Edge; typedef struct { Edge edges[MAXVTXNUM]; //路径中边的序列 : edges[i]表示从起点到 i 的最短路径13int len; //路径中边的数目 }Path; /**********************************/ void copyPath (Path for(i=0;i int TimeChange(int hour,int minute) { //把输入的小时和分钟树转换成分钟的形式，忽略天数 if(minute>60) { hour=hour+minute/60; minute=minute%60; } if(hour>24) { hour=hour%24; } #include #include #include #include “Graph.h“ #include “Time.h“ #include “Path.h“ #define NULL 0 bool OpenGraph_T(Graph bool OpenGraph_P(Graph 14int Main_Menu(Graph bool SaveGraph_T(Graph G); bool SaveGraph_P(Graph G); void main() { Graph GT; //火车交通图 Graph GP; //飞机交通图 CreateGraph(GT); //建立空的火车交通图 CreateGraph(GP); //建立空的飞机交通图 OpenGraph_T(GT); //打开已经存在火车的数据 OpenGraph_P(GP); //打开已经存在飞机的数据 Main_Menu(GT,GP); SaveGraph_T(GT); //保存火车数据 SaveGraph_P(GP); //保存飞机数据 DestoryGraph(GT); DestoryGraph(GP); } /*************/ void LeastMoneyPath(Graph G, int st, int nd, Path Path path[MAXVTXNUM]; int i; int dijkst[MAXVTXNUM]; bool final[MAXVTXNUM]={false}; Path path[MAXVTXNUM]; //每个顶点都有路径 EdgeNode *p,*q; //边的信息 弧结点 EdgeInfo t; //边的信息 bool found; int min=9999,min_i,v,w; for(i=0;inextEdge; if(p->elem.Moneyelem.jvex])15{ dijkst[p->elem.jvex]=p->elem.Money; t=p->elem; SetPath(path[p->elem.jvex],st,p->elem.jvex,t); } p=q; } found= false; while(!found) { //在所有未求得最短路径的顶点求使得 dijkst[i]取最小的 i for(i=0;inextEdge; w=p->elem.jvex; if(final[w]==false copyPath(path[w],path[v]); InsertPath(path[w],v,w,p->elem); } p=q; } //while(p) } //else }// while(!found) copyPath(pathA,path[nd]); } void ShortestTimePath(Graph G, int st, int nd, int n ,Path Path path[MAXVTXNUM]; int i; int dijkst[MAXVTXNUM]; bool final[MAXVTXNUM]={false}; int now[MAXVTXNUM]; Path path[MAXVTXNUM]; EdgeNode *p,*q; EdgeInfo t; bool found; int min=99999。