全国交通咨询模拟系统

1、全国交通咨询模拟系统目录一、 需求分析4二、 个人工作4三、概要设计51主程序流程图：52创建图算法流程图：6四、源程序14五、程序结果255.3设计和调试分析29六、程序设计体会30全国交通咨询模拟系统一、 需求分析旅客对由于出行目的的不同对交通工具的要求也有不同。例如，因公事出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。为了能满足广大旅客的需求，方便旅客出行，就此编制一个全国城市间的交通咨询程序，为旅客提供两种或者三种最优决策的交通咨询，达到如下的基本要求:：（1） 提供对城市信息进行编辑（如：添加和删除）的功能.（2） 城市之间有两

2、种交通工具：火车和飞机。提供对列车时刻表和飞机航班表进行编辑（增加或删除）的功能。（3） 提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。（4） 旅途中耗费的总时间应该包括中转站的等候时间。（5） 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘哪趟列车或哪一次班机到何地。（6） 通过对比以及用户操作基本达到旅客出行的便利。二、 个人工作 此次课程设计是对全国城市交通图列车时刻表及飞机航班表的编辑。此次课设是利用VC工具在dos环境下实现全国交通的咨询与管理

3、。通过此次程序可以对全国城市之间火车与飞机进行两方面的咨询，即最少的时间与最少的费用的咨询，从而方便旅客的出行。通过此次课程设计，我要学会怎样用在VC dos环境下编程，而且要通过此次课程设计加深对数据结构的理解，在设计中用邻接表作交通图的存储结构，表示边的结点中除含有邻接点的信息外，还包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等属性。图中顶点城市的信息，包括城市名称、城市编号和依附该顶点的边的指针。在程序中，利用迪杰斯特拉算法求花钱最少和花时间最少的交通方式。三、概要设计1主程序流程图：开始CreateGraph(GT)CreateGraph(GP)OpenGraph_T(GT

4、)OpenGraph_P(GP)Main_Menu(GT,GP)DestoryGraph(GT) DestoryGraph(GP)结束SaveGraph_T(GT)SaveGraph_P(GP)2创建图算法流程图：N开始i<MAXVTXNUMG.FLAGI=0i+Y结束3打开图算法流程图：开始NY读出城市的号数cityNum，标志Flag，城市名称cityNamej<vexNum读出图中顶点数vexNum,边数edgeNum打开文件j+i<edgeNumN读出边上的各信息Y 结束i+4主菜单操作算法流程图：开始Switch(n)Case 2:Case 0:Case 1:Inq

5、uire_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)LeastMoneyP

6、ath(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)算法流程图开始i<maxv

7、exnumYG.Flagi=1&&strcmp(G.Adjlisti.cityName,name)=0i+YReturn falseReturn true结束10print_Money(GT,p)算法流程图开始i=0i<p.len打印边p的信息Sum+=p.money i+Y结束输钱sumN11LeastMoneyPath(GT,st,nd,p)算法流程图结束初始化i=0i<MAXVTXNUM每个顶点的最短路径为一最大值dijskti=9999，初始化每条路径InitPath(pathi) i+Yp=G.Adjlistst.firstEdgeWhile(p)Nq为p

8、的下一条边q=p->nextEdgep->elem.Money<dijkstp->elem.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置起点的

9、时间为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)YBre

10、ak 输入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; /中途时间（

11、秒）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; /图中的顶点数和边数in

12、t 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;

13、for(i=0;i<p2.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 <iostream.h>int TimeChange(int hour,int minut

14、e) /把输入的小时和分钟树转换成分钟的形式，忽略天数if(minute>60)hour=hour+minute/60;minute=minute%60;if(hour>24)hour=hour%24;#include <stdio.h>#include <stdlib.h>#include <string.h>#include "Graph.h"#include "Time.h"#include "Path.h"#define NULL 0bool OpenGraph_T(Graph

15、&G);bool OpenGraph_P(Graph &G);int Main_Menu(Graph &GT,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

16、(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

17、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;i<MAXVTXNUM;i+) /初始化dijksti=9999;InitPath(pathi); /pathi.len=0;p=G.Adjlistst.firstEdge;while(p

18、) /初始化dijkst数组，检测依附于起始点的每一条边q=p->nextEdge;if(p->elem.Money<dijkstp->elem.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;i<MAXVTXNUM;i+)if(finali=false &&a

19、mp; dijksti<min)min_i=i;finalmin_i=true;if(min_i=nd) found=true;elsev=min_i;p=G.Adjlistv.firstEdge;while(p)q=p->nextEdge;w=p->elem.jvex;if(finalw=false &&(dijkstv+p->elem.Money)<dijkstw)dijkstw=dijkstv+p->elem.Money;copyPath(pathw,pathv);InsertPath(pathw,v,w,p->elem);p=q

20、; /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 finalMAXV

21、TXNUM=false; int nowMAXVTXNUM;Path pathMAXVTXNUM;EdgeNode *p,*q;EdgeInfo t;bool found;int min=99999,min_i,v,w,time;for(i=0;i<MAXVTXNUM;i+) /初始化dijksti=99999;InitPath(pathi);nowi=0;nowst=n;p=G.Adjlistst.firstEdge;while(p) /初始化dijkst数组，检测依附于起始点的每一条边q=p->nextEdge;if(p->elem.StartTime<nowst&

22、amp;&p->elem.EndTime>=nowst)time= 1440-TimeSub(p->elem.EndTime,nowst);elsetime= TimeSub(p->elem.EndTime,nowst);if(time<dijkstp->elem.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= f

23、alse;while(!found)/在所有未求得最短路径的顶点求使得dijksti取最小的ifor(i=0;i<MAXVTXNUM;i+)if(finali=false && dijksti<min)min_i=i;finalmin_i=true;if(min_i=nd) found=true;elsev=min_i;p=G.Adjlistv.firstEdge;while(p)q=p->nextEdge;w=p->elem.jvex;if(finalw=false &&(dijkstv+TimeSub(p->elem.EndTi

24、me,nowv)<dijkstw)dijkstw=dijkstv+TimeSub(p->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 <<

25、 "t 2.查询火车"cout << "t 0.退出n"cout << "t 请选择："cin >> 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); /最少钱数p

26、rint_Money(GT,p);break;else if (n=0)break;elsecout << "输入有误，请重新输入！nn"/咨询系统菜单void Inquire_Menu(Graph GT,Graph GP)while(1)int choice=5;cout<<"t*"<<"n"cout<<"t*咨询系统菜单 *"<<"n"cout << "t* 1.最省钱咨询 *"<<&qu

27、ot;n"cout << "t* 2.最快到达咨询 *"<<"n"cout << "t* 0.退出系统 *"<<"n"cout<< t*"<<"n"cout << " 请选择: "cin >> choice;fflush(stdin);if(choice=0) break;switch(choice)case 1: Inquire_Money(GT,GP);br

28、eak;case 2: Inquire_Time(GT,GP);break;default:cout << " 输入错误选项,请重试。nn"/城市编辑void City_Edit(Graph &GT,Graph &GP)int n,i;char name10;while(1)cout << "n"cout << "t 1.添加城市 "cout << "t 2.删除城市 "cout << "t 0.退出 "cout <

29、;< "tttt 请选择："cin >> n;fflush(stdin);if(n=1)cout << "n请输入添加城市的名称："cin >> name;fflush(stdin);InsertVex(GT,name);InsertVex(GP,name);cout << "n添加成功！"<<"n"break;else if(n=2)cout << "n请输入删除城市的名称："if(input_Vex(GT,i)=t

30、rue)DeleteVex(GT,i);DeleteVex(GP,i);cout << "删除成功！n"break;else if(n=0)cout << "n"break;elsecout << "输入有误，请重新输入！"/列车时刻表编辑 void Train_Edit(Graph &GT,Graph GP)int n,st,sn;int hour,minute;char number10;EdgeInfo q;while(1)cout << "n"cout

31、 << "t 1.添加列车 "cout << "t 2.删除列车 "cout << "t 0.退出 "cout << "ttt 请选择："cin>>n;fflush(stdin);if(n=1)while(1)cout << "n请输入起始城市的名称："if(input_Vex(GT,st)=true)break;while(1)cout << "n请输入终点城市的名称："if(input_V

32、ex(GT,sn)=true)break;cout << "n请输入车次："cin >> number ;fflush(stdin);q.ivex=st;q.jvex=sn;strcpy(q.Number,number);cout << "n请输入票价："cin >> q.Money;fflush(stdin);cout << "n请输入起始时间："cout << "n几点: "cin >> hour;fflush(stdin);c

33、out << "几分: "cin >> minute;fflush(stdin);q.StartTime=TimeChange(hour,minute);cout << "n请输入到站时间："cout << "n几点: "cin >> hour;fflush(stdin);cout << "几分: "cin >> minute;fflush(stdin);q.EndTime=TimeChange(hour,minute);q.Tim

34、e=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(

35、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")

36、;break;elsecout << "输入有误，请重新输入！"void Manage_Menu(Graph &GT,Graph &GP)while(1)int choice=5;cout << "t*"<< "n"cout << "t* 管理系统菜单 *"<<"n"cout << "t* 1.城市编辑 *"<<"n"cout << "

37、t* 2.列车时刻表编辑 *"<<"n"cout << "t* 3.航班时刻表编辑 *"<<"n"cout << "t* 0.退出系统 *"<<"n"cout<< "t*"<< "n"cout << " 请选择: "cin >> choice;fflush(stdin);if(choice=0) break;switch

38、(choice)case 1: City_Edit(GT,GP);break;case 2: Train_Edit(GT,GP);break;case 3: Plane_Edit(GT,GP);break;default:cout << " 输入错误选项,请重试。nn"int Main_Menu(Graph &GT,Graph &GP)while(1)int choicem=3;cout << ("n");cout << "t*"<< "n"cout&

39、lt;<"t*全国交通咨询系统主菜单 *"<<"n" cout << "t* 1.咨询系统 *"<<"n"cout << "t* 2.管理系统 *"<<"n"cout << "t* 0.退出系统 *"<<"n"cout<< "t*"<< "n"cout << "t

40、tt 请选择: "cin >> choicem;cout << "n"fflush(stdin);/清除输入流switch(choicem)case 1: Inquire_Menu(GT,GP);break;case 2: Manage_Menu(GT,GP);break;case 0: return choicem;default:cout << " 输入有误,请重试。nn"五、程序结果5.1操作流程1 本程序的运行环境为DOS操作系统，执行文件为源程序目录下的DeBug子目录下的：Traffic.exe;

41、双击了Traffic.exe后显示了文本方式的用户界面如下：选择1进入：选择2进入：在选择1进入咨询系统菜单后选择1：在选择1进入咨询系统菜单后选择1：在选择1进入咨询系统菜单后选择2：选择2进入管理系统后进行选择1进行城市编辑进入城市编辑后选择1进行添加城市进入城市编辑选择2清除城市进入管理菜单选择2进行列车时刻编辑进入列车时刻表编辑添加列车选择3进入航班编辑后选择1进行添加航班选择3进入航班编辑后选择2进行删除航班5.2数据测试测试1：长沙上海乘坐火车信息：最省钱：总共费用243元 T147 长沙南昌 63元 K445 南昌上海 180元 最快到达：（拟出发时间早上8：00）共需48小时30分钟 T147 长沙南昌 5:50-12:30 K445 南昌上海 16:208:40因为包