2数据结构-全国交通咨询模拟系统实验报告

./全国交通咨询模拟一、设计目的掌握线性表、栈、图结构和对文件的操作,学习屏幕编辑和菜单技术,掌握用最短路径与其搜索算法编制较综合性的程序,能用图的邻接存储结构求解最优路线问题,解决有关实际问题。得到软件设计技能的训练。二、问题描述交通咨询模拟。根据旅客的不同需要,要考虑到旅客希望在旅途中的时间尽可能短、希望旅费尽可能省等的要求。三、基本要求1、对城市信息<城市名、城市间的里程>进行编辑：具备添加、修改、删除功能；2、对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；3、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具,可以不考虑回程；4、咨询以用户和计算机对话方式进行,要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具,输入起始站、终点站、出发时间,输出信息：最快需要多长时间才能到达与旅费,或者最少需要多少旅费才能到达与时间,并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。四、具体实现1、思路<1>数据存储。城市信息<城市名、代码>、交通信息<城市间的里程、各航班和列车时刻>存储于磁盘文件。在实验中本想用文本储存数据,但操作不熟悉,而是改用图的邻接矩阵储存原始信息,而后用数组进行添加删改<2>数据的逻辑结构。根据设计任务的描述,其城市之间的旅游交通问题是典型的图结构,可看作为无向图,图的顶点是城市,边是城市之间所耗费的时间〔要包括中转站的时间〕或旅费。<3>数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构,这里建议采用邻接矩阵作为数据的存储结构。<4>用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可,但要注意人机界面,具体实现由学生自行设计,也可参考有关程序<届时在网上提供>。这些工作有不小的工作量。<5>最优决策功能模块①读入城市信息和交通信息,用邻接表生成含权网络,表头数组中的元素存放城市名与对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市<代码、里程、列车车次>。②根据具体最优决策的要求,用floyd算法求出出发城市到其它各城市的最优值<最短时间或最小的费用>,搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。其相应的初始值可为∞,并在表头数组对应的城市元素中保存响应的信息。③主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行,要求在程序运行过程中可以反复操作。2、数据结构本程序运用了关于图这种数据结构。他的抽象数据类型定义如下：typedefstructunDiGraph{ intnumVerts;//结点 costAdjcost;//邻接矩阵}unDiGraph,*UNG;基本操作：unDiGraph*CreateCostG<>操作结果：构造带权<费用>图。unDiGraph*CreateTimeG<>操作结果：构造带权〔时间〕图。构造飞机带权<费用>图。PathMat*Floyed<unDiGraph*D>操作结果：Floyed函数求任意两点的最短路径。3、算法思想图1.火车路程表7047046513491579138523688125112553XXXXXXXXXXXX图城市之间火车行驶表并利用Floyed函数求带权图两点之间的最短路径。通过对带权费用图和带权时间图求最短路径,就可以最短道从一城市到另一城市之间最省时间和最省费用的走法。为了简洁直观,本设计对课本内的交通网进行了简化,原来的25个城市缩减为13个。但是基本实现了设计的目的。满足了基本要求。4、程序模块程序是用dos版做的界面。主界面包括1.选择火车最短时间路线2.选择火车最节约费用路线3.选择坐飞机4.管理员程序确5.退出本程序程序的模块为#include<windows.h>#include<stdio.h>#include<crtdbg.h>#include<string.h>#include<iostream.h>#include<malloc.h>#defineINF10000//定义一个最大数定为无穷值#defineMAX7staticintcnumber=7;staticintk=0;staticintv=0,z=0;//定义静态变量typedefstructzhu//定义结构体zhu{ intccost;//定义结构变量 intctime;}zhu;zhum[20],x[20],n[20];//定义数组为structzhu类型数组,且三个数组分别储存添加后的数据,且表示花费m,起点n,和终点xtypedefintcostAdj[MAX+1][MAX+1];//定义图的邻接矩阵,并从1开始intPath[MAX+1][MAX+1];//路程矩阵,表示经过存放的点ktypedefstructunDiGraph{ intnumV;//结点 costAdjcost;//邻接矩阵}unDiGraph,*UNG;typedefstructcedit{ chara[10];}cedit;ceditadd[10];costAdjB,L;//功能一输出相应的城市信息intpr<inti,intj>//pr函数表输出功能{ inth=0; if<j==0> { h=i; } elseif<j==1> { cin>>add[i].a; } switch<h>{ case<0>:cout<<""; break; case<1>:cout<<"XX"; break; case<2>:cout<<"XX";break;case<3>:cout<<"XX"; break;case<4>:cout<<"XX"; break;case<5>:cout<<"XX"; break;case<6>:cout<<"XX"; break;case<7>:cout<<""; break; } return1;}voidpri<>//声明pri函数,即利用pr函数输出代码为i的城市信息{ inti; cout<<"城市以与其代码"<<endl; cout<<"**************************************"<<endl; for<i=1;i<=cnumber;i++> { cout<<i<<"."; pr<i,0>; } cout<<"****************************************"<<endl;}//构造CostG图,表示其费用unDiGraph*CreateCostG<into>//火车的花费的存贮和编辑功能{ unDiGraph*G; inti; intj;//定义的i,j做循环变量 inta=0,b=0,f=1,h=1;//f变量初始为1,h初始值为1,a=0,b=0临时表示开始城市代码以与目的城市代码if<!<G=<unDiGraph*>malloc<sizeof<unDiGraph>>>>//为G图分配存储空间。 { return<NULL>; }for<i=1;i<=cnumber;i++> { for<j=1;j<=cnumber;j++> { G->cost[i][j]=INF;//初始化矩阵cost每一项,使其无穷大 } }G->numV=cnumber;G->cost[1][6]=G->cost[6][1]=90;G->cost[1][2]=G->cost[2][1]=84;G->cost[2][3]=G->cost[3][2]=51;G->cost[2][5]=G->cost[5][2]=67;G->cost[3][4]=G->cost[4][3]=53;G->cost[4][5]=G->cost[5][4]=40;G->cost[4][7]=G->cost[7][4]=88;G->cost[5][6]=G->cost[6][5]=90;G->cost[5][7]=G->cost[7][5]=67;G->cost[6][7]=G->cost[7][6]=60;if<o> { while<h==1>//h初始值为1 { v=v+1;//V为全局静态变量,初始值为0,v表示编辑的火车花费的组数,三个编辑数组中的存放代码 pri<>; cout<<"火车花费编辑"<<endl; cout<<"请输入开始城市的代码"<<endl; cin>>a; cout<<"请输入目的城市的代码"<<endl; cin>>b; cout<<"请输入你的两地花费"<<endl; cin>>m[v].ccost; n[v].ccost=a; x[v].ccost=b; cout<<"请选择"<<endl; cout<<"*********************************************************"<<endl; cout<<"1：继续更改城市费用"<<endl; cout<<"0:返回上一级菜单"<<endl; cout<<"*********************************************************"<<endl; cin>>h; switch<h>{ case1: h=1; break; case0: h=0; break; default:{ cout<<"选择出错"<<endl; } } } }f=v+1;//初始定义变量f为1,全局变量v为0,即1=0+1while<v++>//v++代表的意思 { G->cost[n[v].ccost][x[v].ccost]=m[v].ccost; }v=f;return<G>;}//构造TimeG图,表示其花费时间unDiGraph*CreateTimeG<into>//火车的时间的存贮和编辑功能{ unDiGraph*G; inti,j;//循环变量 inta=0,b=0,f,h=1;//a,b表增加城市的代码 if<!<G=<unDiGraph*>malloc<sizeof<unDiGraph>>>>//为G分配存储空间。 { return<NULL>; } for<i=1;i<=cnumber+1;i++> { for<j=1;j<=cnumber+1;j++> { G->cost[i][j]=INF;//初始化使G->cost[i][j]为无穷。 } } G->numV=cnumber;G->cost[1][6]=G->cost[6][1]=9; G->cost[1][2]=G->cost[2][1]=8; G->cost[2][3]=G->cost[3][2]=5; G->cost[2][5]=G->cost[5][2]=3; G->cost[3][4]=G->cost[4][3]=5; G->cost[4][5]=G->cost[5][4]=4; G->cost[4][7]=G->cost[7][5]=6; G->cost[5][6]=G->cost[6][5]=9; G->cost[5][7]=G->cost[7][5]=6; G->cost[6][7]=G->cost[7][6]=6;if<o> { while<h==1> { z=z+1;//全局静态变量,初始值为0.即1=0+1 pri<>; cout<<"火车时间编辑"<<endl; cout<<"请输入开始城市的代码"<<endl; cin>>a; cout<<"请输入结尾城市的代码"<<endl; cin>>b; cout<<"请输入你的两地时间"<<endl; cin>>m[z].ctime; n[z].ctime=a; x[z].ctime=b; cout<<"请选择"<<endl; cout<<"*********************************************************"<<endl; cout<<"1：继续更改城市时间"<<endl; cout<<"0:返回上一级菜单"<<endl; cout<<"*********************************************************"<<endl; cin>>h; switch<h>{ case1: h=1; break; case0: h=0; break; default:{ cout<<"选择出错"<<endl; } } }}f=z+1;//全局静态变量z,初始值为0 while<z++> { G->cost[n[z].ctime][x[z].ctime]=m[z].ctime; }z=f;return<G>;}//Floyed函数求任意两点的最短路径：voidFloyed<unDiGraph*D,unDiGraph*M>//图DM{ inti,j,k,n;//i,j为循环变量,k表中间节点的变量 costAdjA,C;//AC为图,临时表示两种最佳路线组成的矩阵,定义costAdjBL n=cnumber;for<i=1;i<=n;i++> { for<j=1;j<=n;j++> { A[i][j]=D->cost[i][j];//初始化矩阵A,C。 C[i][j]=M->cost[i][j]; Path[i][j]=-1; //初始化权矩阵p } } for<k=1;k<=n;k++>//k为逐步加入的中间结点 { for<i=1;i<=n;i++>//i代表矩阵A中行号 { for<j=1;j<=n;j++> { if<A[i][k]+A[k][j]<A[i][j]> { A[i][j]=A[i][k]+A[k][j]; C[i][j]=C[i][k]+C[k][j]; Path[i][j]=k;//若i经过k到j比i到j小,则选择经过K个中间点之后,i,j两点的最佳路径。 B[i][j]=A[i][j];//构造AC两个任意节点上的最优路径所建造的矩阵,并分别赋给BL代表时间与花费 L[i][j]=C[i][j];} else { B[i][j]=A[i][j]; L[i][j]=C[i][j]; } } } }//endfor循环 cout<<"\n最短路径为:"<<endl;}///end-Floyed//为了求从i到j的最短路径,只需要调用如下的过程：voidprn_pass<inti,intj>{ if<Path[i][j]!=-1> { prn_pass<i,Path[i][j]>;//输出最短路径经过的所有点个数k pr<Path[i][j],0>; }}//求最少时间路径。voidtime<>{ intBcity,Ecity;//起始成市和终点城市 intl,h=1;//定义变量lhdo{ pri<>;//输出城市列表与相应代码。 cout<<"请输入起始城市和目的城市的代码,中间以空格隔开"<<endl;cin>>Bcity; cin>>Ecity;//输入起始城市和终点城市的代码。 if<!<<0<Bcity&&Bcity<cnumber+1>&&<0<Ecity&&Ecity<cnumber+1>&&Bcity!=Ecity>> { cout<<"\n出错啦!!!输入城市请在1-7之间,且两城市代码不能相等!!"<<endl; } Floyed<CreateTimeG<0>,CreateCostG<0>>;//调用Floyed函数。pr<Bcity,0>;//显示起始城市。prn_pass<Bcity,Ecity>;//调用prn_pass函数,显示最短路径经过的城市。pr<Ecity,0>;//显示终点城市。if<B[Bcity][Ecity]>8000||L[Bcity][Ecity]>8000> { cout<<"两地间还没有线路通过"<<endl; } else { cout<<"火车花的时间是"<<B[Bcity][Ecity]<<"小时"<<endl; } cout<<"输入0.返回主菜单"<<endl;scanf<"%d",&l>;//h=l;}while<h==1>;}//求最少花费路径。voidmoney<>{ intBcity,Ecity;//起始成市和终点城市charl,h=1;do{ pri<>;//输出城市列表与相应代码。 cout<<"请输入起始城市和目的城市的代码,中间以空格隔开"<<endl;cin>>Bcity; cin>>Ecity;//输入起始城市和终点城市的代码。 if<!<<0<Bcity&&Bcity<cnumber+1>&&<0<Ecity&&Ecity<cnumber+1>&&Bcity!=Ecity>> { cout<<"\n出错啦!!!输入城市请在1-7之间,且两城市代码不能相等!!"<<endl;//输入出错 } Floyed<CreateCostG<0>,CreateTimeG<0>>;//调用Floyed函数。 pr<Bcity,0>;//显示起始城市。 prn_pass<Bcity,Ecity>;//调用prn_pass函数,显示最短路径经过的城市。 pr<Ecity,0>;//显示终点城市。 if<L[Bcity][Ecity]>8000||B[Bcity][Ecity]>8000> { cout<<"两地间还没有线路通过"<<endl; } else { cout<<"火车花的钱是"<<B[Bcity][Ecity]<<"元"<<endl;}cout<<"输入0.返回主菜单"<<endl;scanf<"%d",&l>;//h=l;}while<h==1>;}voidadd_city<>//对城市的增加{ staticinti=1; intj; cout<<"请输入你要增加的城市的个数"<<endl; cin>>j; for<i=1;i<=j;i++> { cout<<"请输入你要增加的城市名"<<endl; pr<i,1>;//将添加的内容放置于add数组中,并以i为代码 cnumber=cnumber+1; } cout<<"城市增加完毕"<<endl;}voidchose<>//选择最少时间或最小花费{ inth; cout<<"1:最小花费"<<endl; cout<<"2:最小时间"<<endl; cout<<"请选择："<<endl; cin>>h; if<h==1>{ money<>; } else { time<>; }}voidedit_line<>//增加编辑火车的费用{ CreateCostG<1>;}voidedit_hour<>//增加编辑火车的时间{ CreateTimeG<1>;}voidadministrator<>//管理员功能{ inth=1; while<h>{ cout<<"************************************************************"<<endl; cout<<"1:增加城市"<<endl; cout<<"2:添加或编辑火车费用"<<endl; cout<<"3:添加或编辑火车时间"<<endl; cout<<"0:返回主菜单"<<endl; cout<<"************************************************************"<<endl; cout<<"请选择"<<endl; cin>>h; switch<h>{case1:add_city<>; break;case2: edit_line<>; break;case3:edit_hour<>; break;case0: h=0; break;default: { cout<<"选择出错！"<<endl; }}}}//主函数voidmain<>{ charn; intx; while<x!=0> {cout<<endl; cout<<"输入你希望查询的种类代码,你将得到最佳方案!"<<endl; cout<<"******************全国交通咨询模拟系统******************"<<endl; cout<<"*主菜单*"<<endl; cout<<"*1.查看城市*"<<endl; cout<<"*2.选择最短时间路线*"<<endl; cout<<"*3.选择最节约费用路线*"<<endl; co