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

全国交通咨询模拟 罗媛一、设计目的掌握线性表、栈、图结构和对文件的操作，学习屏幕编辑和菜单技术，掌握用最短路径及其搜索算法编制较综合性的程序，能用图的邻接存储结构求解最优路线问题，解决有关实际问题。得到软件设计技能的训练。二、问题描述交通咨询模拟。根据旅客的不同需要，要考虑到旅客希望在旅途中的时间尽可能短、希望旅费尽可能省等的要求。三、基本要求1、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；2、对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；3、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；4、咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。四、具体实现1、思路(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵储存原始信息，而后用数组进行添加删改(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费。(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用邻接矩阵作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。(5) 最优决策功能模块 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、列车车次)。 根据具体最优决策的要求，用floyd算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。其相应的初始值可为，并在表头数组对应的城市元素中保存响应的信息。 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2、数据结构本程序运用了关于图这种数据结构。他的抽象数据类型定义如下：typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作结果：构造带权(费用)图。unDiGraph* CreateTimeG()操作结果：构造带权（时间）图。构造飞机带权(费用)图。PathMat *Floyed(unDiGraph *D)操作结果：Floyed函数 求任意两点的最短路径。3、算法思想 图1.火车路程表7046513491579138523688125112553北京徐州西安成都郑州广州上海 图 城市之间火车行驶表并利用Floyed函数求带权图两点之间的最短路径。通过对带权费用图和带权时间图求最短路径，就可以最短道从一城市到另一城市之间最省时间和最省费用的走法。 为了简洁直观，本设计对课本内的交通网进行了简化，原来的25个城市缩减为13个。但是基本实现了设计的目的。满足了基本要求。4、程序模块1 程序是用dos 版做的界面。2 主界面包括1.选择火车最短时间路线 2.选择火车最节约费用路线3.选择坐飞机 4.管理员程序确 5.退出本程序3 程序的模块为#include <windows.h>#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>#define INF 10000 /定义一个最大数定为无穷值#define MAX 7static int cnumber=7;static int k=0;static int v=0,z=0;/定义静态变量typedef struct zhu/定义结构体zhuint ccost;/定义结构变量int ctime;zhu;zhu m20,x20,n20;/定义数组为struct zhu 类型数组，且三个数组分别储存添加后的数据，且表示花费m，起点n，和终点xtypedef int costAdjMAX+1MAX+1;/定义图的邻接矩阵，并从1开始int PathMAX+1MAX+1;/路程矩阵，表示经过存放的点ktypedef struct unDiGraphint numV;/结点costAdj cost;/邻接矩阵unDiGraph,*UNG;typedef struct ceditchar a10;cedit;cedit add10;costAdj B,L;/功能一 输出相应的城市信息int pr(int i,int j)/pr函数表输出功能int h=0;if (j=0)h=i;else if (j=1)cin>>addi.a;switch (h)case(0) : cout<<""break;case(1) : cout<<"成都 "break;case(2) : cout<<"广州 " break; case(3) : cout<<"上海 "break; case(4) : cout<<"徐州 "break; case(5) : cout<<"郑州 "break; case(6) : cout<<"西安 "break; case(7) : cout<<"北京 "break;return 1;void pri()/声明pri函数，即利用pr函数输出代码为i的城市信息int i;cout<<"城市以及其代码"<<endl;cout<<"*"<<endl;for(i=1;i<=cnumber;i+)cout<<i<<"."pr(i,0);cout<<"*"<<endl;/构造CostG图，表示其费用unDiGraph *CreateCostG(int o)/火车的花费的存贮和编辑功能unDiGraph *G;int i;int j;/定义的 i,j做循环变量int a=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->costij=INF;/初始化矩阵cost每一项，使其无穷大 G->numV=cnumber; G->cost16=G->cost61=90; G->cost12=G->cost21=84; G->cost23=G->cost32=51; G->cost25=G->cost52=67; G->cost34=G->cost43=53; G->cost45=G->cost54=40; G->cost47=G->cost74=88; G->cost56=G->cost65=90; G->cost57=G->cost75=67; G->cost67=G->cost76=60; if (o) while(h=1)/h初始值为1v=v+1;/V为全局静态变量，初始值为0 ,v表示编辑的火车花费的组数，三个编辑数组中的存放代码pri();cout<<"火车花费编辑"<<endl;cout<<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入目的城市的代码"<<endl;cin>>b;cout<<"请输入你的两地花费"<<endl;cin>>mv.ccost;nv.ccost=a;xv.ccost=b;cout<<"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市费用"<<endl;cout<<"0:返回上一级菜单"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<endl; f=v+1;/初始定义变量f为1,全局变量v为0，即1=0+1 while (v+) /v+代表的意思G->costnv.ccostxv.ccost=mv.ccost; v=f; return(G);/构造TimeG图，表示其花费时间unDiGraph *CreateTimeG(int o)/火车的时间的存贮和编辑功能unDiGraph *G;int i,j;/循环变量int a=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->costij=INF;/初始化使G->costij为无穷。G->numV=cnumber; G->cost16=G->cost61=9;G->cost12=G->cost21=8;G->cost23=G->cost32=5;G->cost25=G->cost52=3;G->cost34=G->cost43=5;G->cost45=G->cost54=4;G->cost47=G->cost75=6;G->cost56=G->cost65=9;G->cost57=G->cost75=6;G->cost67=G->cost76=6; if (o)while(h=1)z=z+1;/全局静态变量，初始值为0.即1=0+1pri();cout<<"火车时间编辑"<<endl;cout<<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市的代码"<<endl;cin>>b;cout<<"请输入你的两地时间"<<endl;cin>>mz.ctime;nz.ctime=a;xz.ctime=b;cout<<"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市时间"<<endl;cout<<"0:返回上一级菜单"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<endl; f=z+1;/全局静态变量z,初始值为0while (z+) G->costnz.ctimexz.ctime=mz.ctime; z=f; return(G); /Floyed函数 求任意两点的最短路径：void Floyed(unDiGraph *D,unDiGraph *M)/图D M int i,j,k,n;/i,j为循环变量,k表中间节点的变量costAdj A,C;/A C为图，临时表示两种最佳路线组成的矩阵，定义costAdj B Ln=cnumber; for(i=1;i<=n;i+) for(j=1;j<=n;j+)Aij=D->costij;/初始化矩阵A,C。Cij=M->costij; Pathij=-1; /初始化权矩阵pfor(k=1;k<=n;k+) /k为逐步加入的中间结点 for(i=1;i<=n;i+) /i代表矩阵A中行号for(j=1;j<=n;j+)if(Aik+Akj<Aij)Aij=Aik+Akj;Cij=Cik+Ckj;Pathij=k;/若i经过k到j比i到j小，则选择经过K个中间点之后，i,j两点的最佳路径。Bij=Aij;/构造A C 两个任意节点上的最优路径所建造的矩阵，并分别赋给B L代表时间与花费Lij=Cij; else Bij=Aij; Lij=Cij; /end for循环 cout<<"n最短路径为: "<<endl;/end-Floyed/为了求从i到j的最短路径，只需要调用如下的过程：void prn_pass(int i,int j) if(Pathij!=-1) prn_pass(i,Pathij);/输出最短路径经过的所有点个数k pr(Pathij,0);/求最少时间路径。void time()int Bcity,Ecity;/起始成市号码和终点城市号码int l,h=1;/定义变量l hdo 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 (BBcityEcity>8000|LBcityEcity>8000) cout<<"两地间还没有线路通过"<<endl;elsecout<<"火车花的时间是"<<BBcityEcity<<"小时"<<endl; cout<<" 输入0.返回主菜单 "<<endl; scanf("%d",&l); / h=l; while(h=1); /求最少花费路径。void money() int Bcity,Ecity;/起始成市号码和终点城市号码 char l,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 (LBcityEcity>8000|BBcityEcity>8000)cout<<"两地间还没有线路通过"<<endl;elsecout<<"火车花的钱是"<<BBcityEcity<<"元"<<endl; cout<<" 输入0.返回主菜单"<<endl; scanf("%d",&l); / h=l; while(h=1); void add_city()/对城市的增加static int i=1;int j;cout<<"请输入你要增加的城市的个数"<<endl;cin>>j;for (i=1;i<=j;i+)cout<<"请输入你要增加的城市名"<<endl;pr(i,1);/将添加的内容放置于add数组中，并以i为代码cnumber=cnumber+1;cout<<"城市增加完毕"<<endl;void chose()/选择最少时间或最小花费int h;cout<<"1:最小花费"<<endl;cout<<"2:最小时间"<<endl;cout<<"请选择："<<endl;cin>>h;if (h=1) money();elsetime();void edit_line()/增加编辑火车的费用CreateCostG(1);void edit_hour()/增加编辑火车的时间CreateTimeG(1);void administrator()/管理员功能int h=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) case 1 :add_city();break;case 2:edit_line();break;case 3:edit_hour();break;case 0:h=0;break;default:cout<<"选择出错！"<<endl;/主函数void main() char n;int x;while(x!=0) cout<<endl;cout<<"输入你希望查询的种类代码，你将得到最佳方案!"<<endl;cout<<" *全国交通咨询模拟系统*"<<endl;cout<<" * 主菜单 *"<<endl;cout<<" * 1.查看城市 *"<<endl;cout<<" * 2.选择最短时间路线 *"<<endl;cout<<" * 3.选择最节约费用路线 *"<<endl;cout<<" * 4.管理员程序 *"<<endl;cout<<" * 0.退出程序 *"<<endl; cout<<" *"<<endl; cout<<endl<<endl<<endl<<endl<<endl;cout<<"请选择（0-4）. "/输入选择菜单。 cin>>n ;switch(n)/当输入为0-4，则用switch语句进行选择。case '1': pri();/查看城市break;case '2' : time(); /当输入为2，则调用time函数。break;case '3' : money();/当输入为3，则调用money函数。break;case '4':administrator();break; case '0':/当输入为0。则确认退出。 x=0;break; default :cout<<endl<<"出错啦!请在0-4之间选择!"<<endl<<endl; /输入出错 /end-Switch六、测试数据开始界面1、 查看程序2、 最快到达咨询（举例） 当输入出错时，系统会提示出错信息，并返回输入窗口让用户重新输入。 七、 实验总结：1.时间复杂度1.构造带权图CreateFlyG CreateCostG和CreateTimeG：T(MAX)=O(MAX)2)2. Floyed函数 Floyed : T(n)=O(n2+n3)3.显示路径函数 prn_pass : T(n)=O(n)2.空间复杂度 本程序的空间复杂度均为S(n)=(n2); 即存放n2个节点数据辅助空间。3. 实验心得在本次实验中，对于图和最短路径的内容作了进一步加深，但是也发现了自己在“栈”的内容上不熟练，所以讲原本的最优路径的临时存放由原先设想的栈改换成加变量k进行每个节点的循环来找最优路径。本次实验之后，应当利用更多的时间来实践课本内容，以求能熟练上手。