交通咨询系统
一. 问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
描述
我们的任务是设计一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求,如最快路线、最少费用路线,可以给出相应的结果。
二. 基本要求
1)对城市信息(城市名、城市间的里程)进行编辑:具备添加、修改、删除功能;
2)对城市间的两种交通工具:飞机和火车。对飞机航班和列车时刻
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
进行编辑:里程、航班和列车班次的添加、修改、删除;
3)提供两种最优决策:最快到达或最省钱到达。全程只考虑一种交通工具,
可以不考虑回程;
4)旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时,
火车至少一小时;
5)咨询以用户和计算机对话方式进行,要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具,输入起始站、终点站、出发时间,输出信息:最快需要多长时间才能到达及旅费,或者最少需要多少旅费才能到达及时间,并详细说明依次于何时何地乘坐哪一趟班机或列车何时到达何地。
三.题目
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1)是建立交通网络图的存储结构
2)文件的写入和读出功能的实现
3)对城市信息(城市名、城市间的里程)进行编辑:具备添加、修改、删除功
能;
4)对城市间的两种交通工具:飞机和火车。对飞机航班和列车时刻表进行编
辑:航班和列车班次的添加、修改、删除;
5)实现两个城市顶点之间的最短路径问题
6)实现一个城市到另一个城市的最少的费用的计算
7)实现一个城市到另一个城市的最少的时间的计算。
四.逻辑结构
有向图的逻辑结构
数据关系:{R={VR}
VR={
|v,w∈V且P(v,m),表示从v到w的弧,谓词P(v,m)定义了弧的意义或信息}
五.存储结构
采用了数组表示法对有向图的信息进行存储
六.算法设计
(一)结构体的设计
结构体中包括了VNodeDat、TrafficnodeDat两个结构体。VNodeDat是城市结构体,包括了城市中的火车数、飞机数、飞机航班信息、列车车次信息。TrafficnodeDat结构体中包括了交通工具的有关信息,有飞机航班班次、列车车次、始发时间、终止时间、终点城市、飞机票价和火车票价。
(二)文档的读出和写出
由于层序需要输入的信息较多,所以我们采用文档的方式对城市、火车、飞机的相关信息进行记录。由于文档的读出和写入在C言语的学习中没有涉及,所以我们对这一块的空白的知识进行了补充。程序可以自动生成三个文档,分别是city文档、flight文档、train文档,分别对城市、航班、火车信息进行了存储。
(三)城市的添加
城市的添加是程序需要实现的一个基本的功能。这部分我们采用了一个函数InsertCity来实现。这个函数主要的功能是添加一个城市,并将城市里的信息初始化,方便对城市的信息进行添加。
(四)城市的删除
城市的删除是一个数组中的元素删除的过程,由一个DelCity 函数实现功能。主要的过程是选定要删除的城市后,将数组中的相关的信息(票价、终点城市、飞机火车班次、始发时间、到达时间)进行删除,删除的过程是数组后面的元素对前面元素的覆盖的操作。
(五)路线的添加
路线的添加主要是由两个InsertTrain、InsertFlight函数实现的功能,实现了火车和飞机的路线的添加。添加的信息是列车飞机的票价、班次、始发时间、到达时间、终点城市。主要思路是首先利用文档读出函数将相关的数据读出,然后利用一个循环将列车飞机的相关信息放入数组中,然后再调用文档读出写入函数将信息写入文档中。
(六)路线的删除
路线的删除是路线添加的相反的操作,过程是路线添加的逆过程。将火车和飞机的路线的相关信息进行删除。主要思路是首先将数据从文档中读出,利用一个循环实现数组中的后一个元素对前一个元素的覆盖,最终将文档写入函数将更改的情况写入文档中。
(七)最少费用的计算
这个算法用来构造所有城市的带权值的有向网络。正如一般的情况而言,每两个城市之间存在不止不条路径,要找到某两个城市之间最小花费的路径,于是对整个已建立的交通网络进行遍历,在遍历的过程中很容易就能实现这个目的。依次类推,能够得到任意两个城市之间的最小花费,以这个花费作为两个城市之间的权值,这样,最后得到的网络,正是专门用来算花费最小的网络(没有考虑时间上可能存在的冲突性:比如花费时间长,转车过程中存在下一趟车比上一趟车早的现象),再在这个基础上调用Dijkstra算法得到路径一定是最小花费路径。
(八)最少时间的计算
整个最短时间路线包括以下三个部分:一是文件的建立和保存;二是起始地点、目的地的输入和方式的选择;三是CalcMinTime(startcity,endcity,traveltype) 这个函数,这一部分是整个算法的主体,是计算出最短时间路线的关键。
在函数CalcMinTime(startcity,endcity,traveltype) 中,可以分为等价的两个计算部分,一个报错的第三部分和输出计算结果的第四部分。其中,第一部分为火车方式的计算,另一部分是航班方式的计算。两部分算法思想完全一致,都是先将用于记录最短时间的变量MinTime赋为最大值,然后选择起始地点,通过依次计算以该地点为起点的路线时间,比较其大小,更改MinTime 的具体值,从而保存下来最短时间路线,求得所需。在该算法中,具体最短时间路线的查找主要调用函数int SearchMinTime (CityType City, CityType EndCity, int CurTime,int curPathNo,int TravelType) 来完成。
函数int SearchMinTime (CityType City, CityType EndCity, int CurTime,int curPathNo,int TravelType) 可以分为两部分,从整体上看是采用递归算法实现的。第一部分是递归调用的结束条件,即当前路线的终止地点就是所要查找的目的地的时候,对已查找到的最短时间路线的处理。第二部分则是再引入中间点,通过中间点的连接,分别查找中间点到目的地的最短时间路线和起始点的最短时间路线,最终求得从起始点到目的地的最短时间路线的过程。这个部分也是分成火车方式和航班方式的等价两部分进行操作的,值得特别说明的是,在各自的部分中,所查找的时间是包括中途转站的等待时间的,其中包括对隔天情况的讨论。因此在返回的时间中,所查找的最终路线的最短时间就是总时间。
在这个问题的计算方面,也可以用迪杰斯特拉算法实现。
主程序代码:
#include
#include
#include
#define ERR 0
#define OK 1
#define Dij_MAXN 100
#define MAX_VERTEX_NUM 100
#define MAX_STRING_NUM 100
#define MAX_TRAFFIC_NUM 100
const char CityFile[] ="city.txt";
const char TrainFile[] ="train.txt";
const char FlightFile[] ="flight.txt";
typedef short int CityType;//CityType 定义短整形的变量
typedef struct TrafficNode
{
char name[MAX_STRING_NUM]; //班次 //MAX_STRING_NUM最为10
int StartTime,StopTime; //起止时间
int EndCity; //该有向边指向的顶点在数组中的位置,即该城市编号
int Cost; //票价
} TrafficNodeDat;
typedef struct VNode
{
CityType city;
int TrainNum,FlightNum; //标记下面Train数组和Flight数组里元素个数
TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体,记录了到达城市、起止时间、票价和班次
TrafficNodeDat Flight[MAX_TRAFFIC_NUM];
// int Cost; //遍历时到达该城市的耗费(时间或者费用)
} VNodeDat;
typedef struct PNode
{
int City;
int TraNo;
} PNodeDat;
VNodeDat AdjList[MAX_VERTEX_NUM]; //System Info
char CityName[MAX_VERTEX_NUM][MAX_STRING_NUM]; //城市名,采用第一下标为该城市在本程序中的编号
int CityNum; //城市数目
PNodeDat Path[MAX_VERTEX_NUM]; //存储临时最小时间路径
PNodeDat MinPath[MAX_VERTEX_NUM]; //存储搜索到当前的最小时间路径
int MinTime,StartTime;
int curPath;
//==================================================================================
int ShowMenu()
{ //printf(" 交通咨询系统 ");
printf("\n************MENU************\n");
printf("1: 添加城市\n2: 删除城市\n3: 添加交通路线\n4: 删除交通路线\n5: 查询最小费用路线\n6: 查询最快路线\n7: 清除屏幕\n0: 退出");
printf("\n****************************\n");
printf("\n请输入你的选择:");
return 1;
}
void CopyRight()
{
printf("o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...\n\n");
printf("\t欢迎使用交通咨询系统\n");
printf("\n设计者:余定坤 胡浩 陈周文 马蕾 王晓娟\n 张学思 陈妍伶 李维 陈俊霖 杨毅");
printf("\no(∩_∩)o...o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...");
}
int SeekCity (char *name) //寻找城市
{
int i;
for (i=0;i=0)
{
cost+=matx[PreCity[j]][j];
track[i++]=j=PreCity[j];
}
printf("\nTrack Way:");
if (!TravelType)
{
for(i--;i>0;i--)
{
printf("\n%s:",CityName[track[i]]);
end=track[i-1];min=32767;
for (k=0;kAdjList[track[i]].Train[k].Cost)
{
min=AdjList[track[i]].Train[k].Cost;
tmp=k;
}
printf("%s",AdjList[track[i]].Train[tmp].name);
printf("%2d:%2d-%2d:%2d",AdjList[track[i]].Train[tmp].StartTime/60,AdjList[track[i]].Train[tmp].StartTime%60,AdjList[track[i]].Train[tmp].StopTime/60,AdjList[track[i]].Train[tmp].StopTime%60);
}
}
else
{
for(i--;i>0;i--)
{
printf("\n%s:",CityName[track[i]]);
end=track[i-1];min=32767;
for (k=0;kAdjList[track[i]].Flight[k].Cost)
{
min=AdjList[track[i]].Flight[k].Cost;
tmp=k;
}
printf("%s",AdjList[track[i]].Flight[tmp].name);
printf("%2d:%2d-%2d:%2d",AdjList[track[i]].Flight[tmp].StartTime/60,AdjList[track[i]].Flight[tmp].StartTime%60,AdjList[track[i]].Flight[tmp].StopTime/60,AdjList[track[i]].Flight[tmp].StopTime%60);
}
}
printf("\n%s: DESTINATION!",CityName[track[0]]);
printf("\nMin Cost : %d\n",cost);
}
void Dijkstra(int matx[Dij_MAXN][Dij_MAXN],int p_start,int p_end,int TravelType)
{
int PreCity[Dij_MAXN]; //PreCity[i]==-1,never used;
//PreCity>0,the precity of City i
int i,j,min,pre,pos;
for (i=0;i0&&(min<0||matx[i][j]CurTime-StartTime)
{
for (i=0;i<=curPathNo;i++)
{
MinPath[i].City=Path[i].City;
MinPath[i].TraNo=Path[i].TraNo;
curPath=curPathNo;
}
MinTime=CurTime-StartTime;
}
}
else
{
curPathNo++;
Path[curPathNo].City=City;
if (!TravelType)
{
for (i=0;i=(CurTime%1440))&&(AdjList[City].Train[i].StopTime+(CurTime/1440)*1440-StartTime=CurTime)&&(AdjList[City].Flight[i].StopTime+(CurTime/1440)*1440-StartTime
本文档为【交通咨询系统】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。