一、设计目的
掌握线性表、栈、图结构和对文件的操作，学习屏幕编辑和菜单技术，掌握用最短路径及其搜索算法编制较综合性的程序，能用图的邻接存储结构求解最优路线问题，解决有关实际问题。得到软件设计技能的训练。
二、问题描述
交通咨询模拟。根据旅客的不同需要，要考虑到旅客希望在旅途中的时间尽可能短、希望旅费尽可能省等的要求。旅途用火车或飞机作为交通工具。用计算机编制程序，为旅客提供两种最优决策的交通咨询系统。
三、基本要求
1、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；
2、对城市间的两种交通工具：飞机和火车。对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除；
3、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，
可以不考虑回程；
4、旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，
火车至少一小时；
5、咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟班机或列车何时到达何地。
四、实现提示
1、算法思路
(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。
(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。
(5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。
② 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队)中，则进栈(队)，直至栈(队)为空。
③ 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
2、数据结构
本程序运用了关于图这种数据结构。
他的抽象数据类型定义如下：
typedef struct unDiGraph
{
int numVerts; //结点
costAdj cost; //邻接矩阵
}unDiGraph,*UNG;
基本操作：
unDiGraph* CreateCostG()
操作结果：构造带权(费用)图。
unDiGraph* CreateTimeG()
操作结果：构造带权（时间）图。
构造飞机带权(费用)图。
PathMat *Floyed(unDiGraph *D)
操作结果：Floyed函数 求任意两点的最短路径。
3、算法思想
本程序运用了图的知识，构造了无向带权费用图和无向带权时间图。（如图1，图2所示）
图1. 十三城市之间火车费用表（权值表示费用）
图2. 十三城市之间火车行驶时间表 （权值表示时间）
并利用Floyed函数求带权图两点之间的最短路径。通过对带权费用图和带权时间图求最短路径，就可以最短道从一城市到另一城市之间最省时间和最省费用的走法。
为了简洁直观，本设计对课本内的交通网进行了简化，原来的25个城市缩减为13个。但是基本实现了设计的目的。满足了基本要求。
4、程序模块
1．程序是用dos 版做的界面。
2．主界面包括1.选择火车最短时间路线 2.选择火车最节约费用路线3.选择坐飞机 4.管理员程序确 5.退出本程序
3．程序的模块为
#include #include #include #include #include #include #define INF 65535 //定义一个最大数定为无穷值 #define MAX 13 typedef int costAdj[MAX+1][MAX+1];//图邻接矩阵从1开始记数 int Path[MAX+1][MAX+1];//图邻接矩阵从1开始记数 int o[13],h; typedef struct unDiGraph { int numVerts; //结点 costAdj cost; //邻接矩阵 }unDiGraph,*UNG; //图的定义 costAdj B,L; void pr(int i)//选择城市 void pri()//输出城市 unDiGraph *CreateCostG()//构造带权(费用)图 返回首地址G： unDiGraph *CreateTimeG()//构造带权(时间)图 返回首地址G： unDiGraph *CreateFlyG()//飞机的相关信息 void Floyed(unDiGraph *D,unDiGraph *M) //Floyed函数 求任意两点的最短路径： ： void prn_pass(int i,int j) //为了求从i到j的最短路径，只需要调用如下的过程 void time()//求最少时间路径。 void money()//求最少花费路径 void administrator()//管理员功能 void main()//main函数 五、主程序 #include #include #include #include #include #include #define INF 65535 //定义一个最大数定为无穷值 #define MAX 23 static int c_number=13; static int k=0; static int v=0,z=0,r=0,t=0; typedef struct zhu { int c_cost; int c_time; int f_cost; int f_time; }zhu; zhu m[20],x[20],n[20]; typedef int costAdj[MAX+1][MAX+1];//图邻接矩阵从1开始记数 int Path[MAX+1][MAX+1];//图邻接矩阵从1开始记数 typedef struct unDiGraph { int numVerts; //结点 costAdj cost; //邻接矩阵 }unDiGraph,*UNG; //图的定义 typedef struct c_edit { char a[10]; }c_edit; c_edit add[10]; costAdj B,L; int pr(int i,int j) { int h=0; if (j==0) { h=i; } else if (j==1) { cin>>add[i].a; } switch(h)//运用switch语句。 { 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; case(8) : cout<<"广州 "; break; case(9) : cout<<"南宁 "; break; case(10) : cout<<"徐州 "; break; case(11) : cout<<"北京 "; break; case(12) : cout<<"天津 "; break; case(13) : cout<<"上海 "; break; default: cout< return 1; } //输出城市列表及相应代码 void pri() { int i; cout<<" 城市及其代码"< { cout< } cout< //构造带权(费用)图 返回首地址G： unDiGraph *CreateCostG(int o)//火车的花费的存贮和编辑功能 { unDiGraph *G; int i,j; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G分配存储空间。 { return(NULL); } for(i=1;i for(j=1;j G->cost[i][j]=INF; //初始化使G->cost[i][j]为无穷。 } } G->numVerts=c_number; G->cost[1][6]=G->cost[6][1]=96; G->cost[1][2]=G->cost[2][1]=84; G->cost[2][3]=G->cost[3][2]=51; G->cost[3][4]=G->cost[4][3]=53; G->cost[4][5]=G->cost[5][4]=40; G->cost[5][6]=G->cost[6][5]=90; G->cost[5][8]=G->cost[8][5]=67; G->cost[5][7]=G->cost[7][5]=67; G->cost[6][7]=G->cost[7][6]=60; G->cost[7][9]=G->cost[9][7]=25; G->cost[3][11]=G->cost[11][3]=69; G->cost[11][12]=G->cost[12][11]=13; G->cost[12][10]=G->cost[10][12]=67; G->cost[3][10]=G->cost[10][3]=34; G->cost[13][10]=G->cost[10][13]=65; G->cost[13][5]=G->cost[5][13]=118; if (o) { while(h==1) { v=v+1; pri(); cout<<"火车花费编辑"< cout<<"请输入结尾城市的代码"< cout<<"请输入你的两地花费"< n[v].c_cost=a; x[v].c_cost=b; cout<<"请选择"< switch(h) { case 1: h=1; break; case 0: h=0; break; default:{ cout<<"选择出错"< } } } f=v+1; while (v--) { G->cost[n[v].c_cost][x[v].c_cost]=m[v].c_cost; } v=f; return(G); } //构造带权(时间)图 返回首地址G： unDiGraph *CreateTimeG(int o)//火车的时间的存贮和编辑功能 { unDiGraph *G; int i,j; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G分配存储空间。 { return(NULL); } for(i=1;i for(j=1;j G->cost[i][j]=INF;//初始化使G->cost[i][j]为无穷。 } } G->numVerts=c_number; 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[3][4]=G->cost[4][3]=5; G->cost[4][5]=G->cost[5][4]=4; G->cost[5][6]=G->cost[6][5]=9; G->cost[5][7]=G->cost[7][5]=6; G->cost[5][8]=G->cost[8][5]=6; G->cost[6][7]=G->cost[7][6]=6; G->cost[7][9]=G->cost[9][7]=2; G->cost[3][11]=G->cost[11][3]=6; G->cost[11][12]=G->cost[12][11]=1; G->cost[12][10]=G->cost[10][12]=6; G->cost[3][10]=G->cost[10][3]=3; G->cost[13][10]=G->cost[10][13]=6; G->cost[13][5]=G->cost[5][13]=11; if (o) { while(h==1) { z=z+1; pri(); cout<<"火车时间编辑"< cout<<"请输入结尾城市的代码"< cout<<"请输入你的两地时间"< n[z].c_time=a; x[z].c_time=b; cout<<"请选择"< switch(h) { case 1: h=1; break; case 0: h=0; break; default:{ cout<<"选择出错"< } } } f=z+1; while (z--) { G->cost[n[z].c_time][x[z].c_time]=m[z].c_time; } z=f; return(G); } unDiGraph *CreateTimeF(int o)//飞机的时间的存贮和编辑功能 { unDiGraph *G; int i,j; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G分配存储空间。 { return(NULL); } for(i=1;i for(j=1;j G->cost[i][j]=INF;//初始化使G->cost[i][j]为无穷。 } } G->numVerts=c_number; G->cost[1][6]=G->cost[6][1]=3; G->cost[1][2]=G->cost[2][1]=2; G->cost[2][3]=G->cost[3][2]=1; G->cost[3][4]=G->cost[4][3]=2; G->cost[4][5]=G->cost[5][4]=4; G->cost[5][6]=G->cost[6][5]=3; G->cost[5][7]=G->cost[7][5]=6; G->cost[5][8]=G->cost[8][5]=6; G->cost[6][7]=G->cost[7][6]=6; G->cost[7][9]=G->cost[9][7]=2; G->cost[3][11]=G->cost[11][3]=6; G->cost[11][12]=G->cost[12][11]=1; G->cost[12][10]=G->cost[10][12]=2; G->cost[3][10]=G->cost[10][3]=3; G->cost[13][10]=G->cost[10][13]=6; G->cost[13][5]=G->cost[5][13]=1; if (o) { while(h==1) { t=t+1; pri(); cout<<"飞机时间编辑"< cout<<"请输入结尾城市的代码"< cout<<"请输入你的两地时间"< n[t].f_time=a; x[t].f_time=b; cout<<"请选择"< switch(h) { case 1: h=1; break; case 0: h=0; break; default:{ cout<<"选择出错"< } } } f=t+1; while (t--) { G->cost[n[t].f_time][x[t].f_time]=m[t].f_time; } t=f; return(G); } unDiGraph *CreateCostF(int o)//飞机花费的存贮和编辑功能 { unDiGraph *G; int i,j; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G分配存储空间。 { return(NULL); } for(i=1;i for(j=1;j G->cost[i][j]=INF; //初始化使G->cost[i][j]为无穷。 } } G->numVerts=c_number; G->cost[1][6]=G->cost[6][1]=960; G->cost[1][2]=G->cost[2][1]=840; G->cost[2][3]=G->cost[3][2]=501; G->cost[3][4]=G->cost[4][3]=530; G->cost[4][5]=G->cost[5][4]=400; G->cost[5][6]=G->cost[6][5]=900; G->cost[5][8]=G->cost[8][5]=670; G->cost[5][7]=G->cost[7][5]=670; G->cost[6][7]=G->cost[7][6]=600; G->cost[7][9]=G->cost[9][7]=200; G->cost[3][11]=G->cost[11][3]=690; G->cost[11][12]=G->cost[12][11]=310; G->cost[12][10]=G->cost[10][12]=670; G->cost[3][10]=G->cost[10][3]=340; G->cost[13][10]=G->cost[10][13]=650; G->cost[13][5]=G->cost[5][13]=1180; if (o) { while(h==1) { r=r+1; pri(); cout<<"飞机花费编辑"< cout<<"请输入结尾城市的代码"< cout<<"请输入你的两地花费"< n[r].f_cost=a; x[r].f_cost=b; cout<<"请选择"< switch(h) { case 1: h=1; break; case 0: h=0; break; default:{ cout<<"选择出错"< } } } f=r+1; while (r--) { G->cost[n[r].f_cost][x[r].f_cost]=m[r].f_cost; } r=f; return(G); } //Floyed函数 求任意两点的最短路径： void Floyed(unDiGraph *D,unDiGraph *M) { int i,j,k,n; costAdj A,C; n=c_number; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) {A[i][j]=D->cost[i][j];//初始化矩阵A。 C[i][j]=M->cost[i][j]; Path[i][j]=-1; //初始化矩阵p, 置-1. } } 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] C[i][j]=C[i][k]+C[k][j]; Path[i][j]=k;//若i经过k到j比i到j小，则令A[i][j]=A[i][k]+A[k][j]。 B[i][j]=A[i][j]; L[i][j]=C[i][j]; } else{ B[i][j]=A[i][j]; L[i][j]=C[i][j]; } } }//end-for cout<<"\\n最短路径为: "< //为了求从i到j的最短路径，只需要调用如下的过程： void prn_pass(int i,int j) { if(Path[i][j]!=-1) { prn_pass(i,Path[i][j]);//输出最短路径经过的所有点 pr(Path[i][j],0); } } //求最少时间路径。 void time() { int Bcity,Ecity;//起始成市号码和终点城市号码 int l,h=1; do { pri();//输出城市列表及相应代码。 cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1-- "< cin>>Ecity;//输入起始城市和终点城市的代码。 if (!((0 cout<<"\\n出错啦 输入城市号码请在1-"< Floyed(CreateTimeG(0),CreateCostG(0));//调用Floyed函数。 pr(Bcity,0);// 显示起始城市。 prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0);//显示终点城市。 if (B[Bcity][Ecity]>5000||L[Bcity][Ecity]>10000) { cout<<"两地间还没有线路通过"< else { cout<<"火车花的钱是"< printf("\\n\\n 1.继续最少花费查找\\n 2.返回主菜单\\n 清选择..."); scanf("%d",&l); //输入1或2选择是否继续。 h=l; } while(h==1); printf("\\n"); } void f_time() { int Bcity,Ecity;//起始成市号码和终点城市号码 int l,h=1; do { pri();//输出城市列表及相应代码。 cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1-- "< cin>>Ecity;//输入起始城市和终点城市的代码。 if (!((0 cout<<"\\n出错啦 "< Floyed(CreateTimeF(0),CreateCostF(0));//调用Floyed函数。 pr(Bcity,0);// 显示起始城市。 prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0);//显示终点城市。 if (B[Bcity][Ecity]>5000||L[Bcity][Ecity]>10000) { cout<<"两地间还没有线路通过"< else { cout<<"飞机花的钱是"< printf("\\n\\n 1.继续最少花费查找\\n 2.返回主菜单\\n 清选择..."); scanf("%d",&l); //输入1或2选择是否继续。 h=l; } while(h==1); printf("\\n"); } //求最少花费路径。 void money() { int Bcity,Ecity;//起始成市号码和终点城市号码 char l,h=1; /*unDiGraph *G;*/ do { pri();//输出城市列表及相应代码。 cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1-- "< cin>>Ecity;//输入起始城市和终点城市的代码。 if (!((0 cout<<"\\n出错啦 "< } Floyed(CreateCostG(0),CreateTimeG(0));//调用Floyed函数。 pr(Bcity,0);//显示起始城市。 prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0);//显示终点城市。 if (B[Bcity][Ecity]>5000||L[Bcity][Ecity]>10000) { cout<<"两地间还没有线路通过"< else { cout<<"火车花的钱是"< printf("\\n\\n 1.继续最少花费查找\\n 2.返回主菜单\\n 清选择..."); scanf("%d",&l); //输入1或2选择是否继续。 h=l; } while(h==1); printf("\\n"); } //求飞机的情况 void f_money() { cout<<"1"< char l,h=1; /*unDiGraph *G;*/ do { cout<<"2"< pri();//输出城市列表及相应代码。 cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1-- "< cin>>Ecity;//输入起始城市和终点城市的代码。 if (!((0 cout<<"\\n出错啦 "< } Floyed(CreateCostF(0),CreateTimeF(0));//调用Floyed函数。 pr(Bcity,0);//显示起始城市。 prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0);//显示终点城市。 if (B[Bcity][Ecity]>5000||L[Bcity][Ecity]>10000) { cout<<"两地间还没有线路通过"< else{ cout<<"飞机花的钱是"< printf("\\n\\n 1.继续最少花费查找\\n 2.返回主菜单\\n 清选择..."); scanf("%d",&l); //输入1或2选择是否继续。 h=l; } while(h==1); printf("\\n"); } void add_city()//对城市的增加 { static int i=1; int j; cout<<"请输入你要增加的城市的个数"< for (i=1;i<=j;i++) { cout<<"请输入你要增加的城市名"< c_number=c_number+1; } cout<<"城市增加完毕"< void chose_money()//花最少钱的算法 { int h; cout<<"1:火车"< if (h==1) { money(); } else { f_money(); } } void chose_time()//花最少时间的算法 { int h; cout<<"1:火车"< if (h==1) { time(); } else { f_time(); } } void edit_line()//增加编辑火车的费用 { CreateCostG(1); } void edit_hour()//增加编辑火车的时间 { CreateTimeG(1); } void edit_fline()//增加编辑飞机的费用 { CreateCostF(1); } void edit_fhour()//增加编辑飞机的时间 { CreateTimeF(1); } void administrator()//管理员功能 { int h=1; while (h) { cout<<"************************************************************"< switch(h) { case 1 :add_city(); break; case 2: edit_line(); break; case 3:edit_hour(); break; case 4:edit_fline(); break; case 5:edit_fhour(); break; case 0: h=0; break; default: { cout<<"选择出错！"< } } } //主函数 void main() { //人机对话界面设置，输入选项，再输入你的起始成市号码和终点城市号码 ，你将被给出你所要的 //最短时间或最消费用的最佳路径的城市号码 对照即可得出经过哪些城市 char n; int x; while(x!=0) { cout< cin>>n ; switch(n)//当输入为0-4，则用switch语句进行选择。 { case '1': pri();//查看城市 break; case '2' : chose_time(); //当输入为1，则调用time函数。 break; case '3' : chose_money();//当输入为2，则调用money函数。 break; case '4':administrator(); break; case '0'://当输入为3。则确认退出。 x=0; break; default : { cout< }//end-Switch } } 六、测试数据 开始界面 1、查看程序 2、最快到达咨询（举例） （1）火车最快到达咨询：成都到广州 （2）飞机最快到达咨询：成都到贵阳 3、最节省到达咨询 （1）火车最省钱到达咨询：郑州到南宁 （2）飞机最省钱到达咨询：株洲到天津 4、管理员程序 （1）增加城市 （2）添加或编辑火车费用 （3）添加或编辑火车花费时间 （4）添加或编制飞机费用 （5）添加或编辑飞机花费时间 测试数据及测试情况： 时间的最少花费和最短时间的铁路乘车路线。 例如：在最短时间路线选择时，如果输入11（北京）和8 (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个节点数据辅助空间。
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
