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

题号：5 题目:全国交通咨询模拟 1. 需求分析- 1.1 问题描述- 1.2 功能需求- 2. 设计- 2.1逻辑结构- 2.2 存储结构分析- 2.3 算法思想- 2.4 函数调用关系图- 2.5函数接口规格说明- 3. 调试分析 - 4. 用户手册 - 5. 测试数据与测试结果- 6. 源代码清单-1.需求分析1.1问题描述 出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。1.2功能需求 （1）提供对城市信息进行编辑（如添加或删除）的功能。 （2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增 设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。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)2创建图算法流程图：N开始iMAXVTXNUMG.FLAGI=0i+Y结束3打开图算法流程图：开始NY读出城市的号数cityNum，标志Flag，城市名称cityNamejvexNum读出图中顶点数vexNum,边数edgeNum打开文件j+iedgeNumN读出边上的各信息Y 结束i+4主菜单操作算法流程图：开始Switch(n)Case 2:Case 0:Case 1:Inquire_Menu(GT,GP)breakManage_Menu(GT,GP)5咨询菜单流程图Inquire_Menu(GT,GP)Switch(choice)Case 1:Case 2:Case 0:Inquire_Money(GT,GP)Inquire_Time(GT,GP)break6咨询钱最少模块图Inquire_Money(GT,GP)NWhile(True)Y输入 nYn=1NYinput_Money(GP,st, nd)n=2LeastMoneyPath (GP,st,nd,p)Ninput_Money(GT,st, nd)print_Money(GP,p)LeastMoneyPath(GT,st,nd,p)Yn=2结束Nprint_Money(GT,p)结束结束结束7input_Money(Graph G, int &st,int &sn)算法流程图While(True)输入起始城市名称YinputVex(G,st)=truebreakNWhile(True)输入终止城市名称inputVex(G,sn)=truebreakN8inputVex(G,st)算法流程图开始输入城市名字 nameYLocateVex(G,name,i)=trueReturn trueN输出城市不存在结束9LocateVex(G,name,i)算法流程图开始imaxvexnumYG.Flagi=1&strcmp(G.Adjlisti.cityName,name)=0i+YReturn falseReturn true结束10print_Money(GT,p)算法流程图开始i=0ip.len打印边p的信息Sum+=p.money i+Y结束输钱sumN11LeastMoneyPath(GT,st,nd,p)算法流程图结束初始化i=0inextEdgep-elem.Moneyelem.jvex重置每个顶点的最少钱的路径dijkstp-elem.jvex=p-elem.Money t=p-elemSetPath(pathp-elem.jvex,st,p-elem.jvex,t)Yp=qYNFound = false求从st 到nd 的最短路径算法并复制此路径copyPath(pathw,pathv)开始11ShortestTimePath(GT,st,nd,p)算法流程图开始每个点初始一个最大值初始每条路径置时间0置起点的时间为n置p为起点的第一条边检测依附每个顶点的边依据迪杰斯特求每个起点到终点的时间最少的路径结束12Manage_Menu(GT,GP)算法流程图开始Switch(choice)Case 1:Case 0:Case 3:Case 2:Plane_Edit(GT,GP)breakTrain_Edit(GT,GP)City_Edit(GT,GP)13City_Edit(GT,GP)算法流程图开始输入n进行选择Nn=1NYn =2添加城市及相关信息Y删除城市及相关信息结束输出错误输入n进行选择结束Nn =0Y结束14. Train_Edit(GT,GP)算法流程图开始NWhile(true)YBreak 输入n进行选择结束Yn=1NYn=2输入列车的信息breakN删除列车的信息重新输入n进行选择Nn=0breakYbreak注释：部分算法的设计思想相同，只是参数不同，故省略部分程序流程图。四、源程序#define MAXVTXNUM 30 /图中顶点数的最大值/*顶点、边和图类型*/typedef struct /定义各车次及航班的信息弧的信息int ivex; /起始点号int jvex; /终点号char Number10; / 车次号int Money; /费用int StartTime; /起始时间（秒）int EndTime; /终止时间（秒）int Time; /中途时间（秒）EdgeInfo; /边的信息typedef struct EdgeNode /边的信息 弧结点 EdgeInfo elem; EdgeNode *nextEdge;EdgeNode, *EdgePtr;/边的结点类型，指向边的指针typedef struct /城市信息 头结点char cityName10;int cityNumber;EdgePtr firstEdge; /指向的一条依附该顶点的边的指针Vnode; /顶点类型typedef struct /图的结构Vnode AdjlistMAXVTXNUM;/邻接表int vexNum, edgeNum; /图中的顶点数和边数int FlagMAXVTXNUM; /标志是否是图中的顶点,0表示不是,1表示是 Graph; /图类型/*图的基本操作*/* 路径类型 */typedef structint vx,vy; /vx为路径的起点,vy为路径的终点EdgeInfo p; /路径中边的信息Edge;typedef struct Edge edgesMAXVTXNUM; /路径中边的序列 : edgesi表示从起点到i的最短路径int len; /路径中边的数目Path;/*/void copyPath (Path &p1,Path &p2)/复制路径p1=p2int i;for(i=0;ip2.len;i+)p1.edgesi.vx=p2.edgesi.vx;p1.edgesi.vy=p2.edgesi.vy;p1.edgesi.p =p2.edgesi.p;p1.len=p2.len;void SetPath(Path &pa, int v, int w, EdgeInfo t)/设置pa从v到w的第一条边,边的信息为tpa.edges0.vx=v;pa.edges0.vy=w;pa.edges0.p=t;pa.len=1;#include int TimeChange(int hour,int minute) /把输入的小时和分钟树转换成分钟的形式，忽略天数if(minute60)hour=hour+minute/60;minute=minute%60;if(hour24)hour=hour%24;#include #include #include #include Graph.h#include Time.h#include Path.h#define NULL 0bool OpenGraph_T(Graph &G);bool OpenGraph_P(Graph &G);int Main_Menu(Graph >,Graph &GP);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 &pathA) /st：起点号，nd：终点号，结果存储在pathA中 /path包括路径的长度，起点，终点和路径信息/利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条/最短路径PathInfo,路径长度pathLength/设int dijkstMAXVTXNUM;Path pathMAXVTXNUM;int i;int dijkstMAXVTXNUM;bool finalMAXVTXNUM=false; Path pathMAXVTXNUM; /每个顶点都有路径 EdgeNode *p,*q; /边的信息 弧结点 EdgeInfo t; /边的信息bool found;int min=9999,min_i,v,w;for(i=0;inextEdge;if(p-elem.Moneyelem.jvex)dijkstp-elem.jvex=p-elem.Money;t=p-elem;SetPath(pathp-elem.jvex,st,p-elem.jvex,t);p=q;found= false;while(!found)/在所有未求得最短路径的顶点求使得dijksti取最小的ifor(i=0;iMAXVTXNUM;i+)if(finali=false & dijkstinextEdge;w=p-elem.jvex;if(finalw=false &(dijkstv+p-elem.Money)elem.Money;copyPath(pathw,pathv);InsertPath(pathw,v,w,p-elem);p=q; /while(p) /else/ while(!found)copyPath(pathA,pathnd);void ShortestTimePath(Graph G, int st, int nd, int n ,Path &pathA)/st：起点号，nd：终点号，n：当前时间（秒），结果存储在pathA中/利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条/最短路径PathInfo,路径长度pathLength/设int dijkstMAXVTXNUM;Path pathMAXVTXNUM;int i;int dijkstMAXVTXNUM;bool finalMAXVTXNUM=false; int nowMAXVTXNUM;Path pathMAXVTXNUM;EdgeNode *p,*q;EdgeInfo t;bool found;int min=99999,min_i,v,w,time;for(i=0;inextEdge;if(p-elem.StartTimeelem.EndTime=nowst)time= 1440-TimeSub(p-elem.EndTime,nowst);elsetime= TimeSub(p-elem.EndTime,nowst);if(timeelem.jvex)dijkstp-elem.jvex=time;t=p-elem;SetPath(pathp-elem.jvex,st,p-elem.jvex,t);nowp-elem.jvex=p-elem.EndTime;p=q;found= false;while(!found)/在所有未求得最短路径的顶点求使得dijksti取最小的ifor(i=0;iMAXVTXNUM;i+)if(finali=false & dijkstinextEdge;w=p-elem.jvex;if(finalw=false &(dijkstv+TimeSub(p-elem.EndTime,nowv)elem.EndTime,nowv);copyPath(pathw,pathv);InsertPath(pathw,v,w,p-elem);p=q; /while(p) /else/ while(!found)copyPath(pathA,pathnd);void Inquire_Money(Graph GT,Graph GP)Path p;int n=5;int st,nd;while(1)cout tt 1.查询飞机;cout t 2.查询火车;cout t 0.退出n;cout n;fflush(stdin);cout n;if(n=1)input_Money(GP,st, nd);LeastMoneyPath (GP,st,nd,p); /最少钱数print_Money(GP,p);break;else if(n=2)input_Money(GT,st, nd);LeastMoneyPath (GT,st,nd,p); /最少钱数print_Money(GT,p);break;else if (n=0)break;elsecout 输入有误，请重新输入！nn;/咨询系统菜单void Inquire_Menu(Graph GT,Graph GP)while(1)int choice=5;coutt*n;coutt*咨询系统菜单 *n;cout t* 1.最省钱咨询 *n;cout t* 2.最快到达咨询 *n;cout t* 0.退出系统 *n;cout t*n;cout choice;fflush(stdin);if(choice=0) break;switch(choice)case 1: Inquire_Money(GT,GP);break;case 2: Inquire_Time(GT,GP);break;default:cout 输入错误选项,请重试。nn;/城市编辑void City_Edit(Graph >,Graph &GP)int n,i;char name10;while(1)cout n;cout t 1.添加城市 ;cout t 2.删除城市 ;cout t 0.退出 ;cout n;fflush(stdin);if(n=1)cout name;fflush(stdin);InsertVex(GT,name);InsertVex(GP,name);cout n添加成功！n;break;else if(n=2)cout n请输入删除城市的名称：;if(input_Vex(GT,i)=true)DeleteVex(GT,i);DeleteVex(GP,i);cout 删除成功！n;break;else if(n=0)cout n;break;elsecout 输入有误，请重新输入！;/列车时刻表编辑 void Train_Edit(Graph >,Graph GP)int n,st,sn;int hour,minute;char number10;EdgeInfo q;while(1)cout n;cout t 1.添加列车 ;cout t 2.删除列车 ;cout t 0.退出 ;cout n;fflush(stdin);if(n=1)while(1)cout n请输入起始城市的名称：;if(input_Vex(GT,st)=true)break;while(1)cout n请输入终点城市的名称：;if(input_Vex(GT,sn)=true)break;cout number ;fflush(stdin);q.ivex=st;q.jvex=sn;strcpy(q.Number,number);cout q.Money;fflush(stdin);cout n请输入起始时间：;cout hour;fflush(stdin);cout minute;fflush(stdin);q.StartTime=TimeChange(hour,minute);cout n请输入到站时间：;cout hour;fflush(stdin);cout minute;fflush(stdin);q.EndTime=TimeChange(hour,minute);q.Time=TimeSub(q.EndTime,q.StartTime);cout n行车时间: q.Time/60 小时 q.Time%60 分钟;InsertEdge(GT,q);cout n添加成功！ n;break;else if(n=2)while(1)cout n请输入起始城市的名称：;if(input_Vex(GT,st)=true)break;while(1)cout n请输入终点城市的名称：;if(input_Vex(GT,sn)=true)break;cout n请输入车次：;if(input_Number(GT,st,sn,number)q.ivex=st;q.jvex=sn;strcpy(q.Number,number);DeleteEdge(GT,q);cout 删除成功！n;break;else if(n=0)cout (n);break;elsecout 输入有误，请重新输入！;void Manage_Menu(Graph >,Graph &GP)while(1)int choice=5;cout t* n;cout t* 管理系统菜单 *n;cout t* 1.城市编辑 *n;cout t* 2.列车时刻表编辑 *n;cout t* 3.航班时刻表编辑 *n;cout t* 0.退出系统 *n;cout t* n;cout choice;fflush(stdin);if(c