交通咨询系统设计—课程设计实验报告

1、数学与统计学院课程设计实验报告课程名称：算法与数据结构设计题目： 交通咨询系统设计 交通咨询系统设计 1.系统的设计要求1） 问题的描述根据不同目的的旅客对交通工具的不同要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市之间的模拟交通咨询的程序，为旅客提供两种或者三种最优决策的交通咨询。2） 需求分析1）提供对城市信息进行编辑（如：添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通

2、工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。2.系统概要为实现上述程序功能，要用到一种数据结构，图。根据输入的顶点和边，建立图，然后利用图的邻接表存储结构实现算法。ADT Graph 数据对象V：v是具有相同数据特性的元素的集合，称作顶点集。 数据关系R： R=VR VR=|v，w属于V且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息 基本操作P： Cre

3、ateGraph70405(&G , V , VR）; 初始条件：V是图的顶点集，VR是图的弧的集合。 操作结果：按V和VR的定义构造图G。Initgraph70405(G)；初始条件：图G存在。操作结果：各个变量初始化。 LocateVex70405G，u）； 初始条件：图G存在，u和G中顶点具有相同的性质。 操作结果：若图中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。Cityedit70405(G)；初始条件：图G存在。操作结果：对城市进行编辑。EnterVertex70405(G)；初始条件：图G存在。操作结果：增加城市。UserDemand70405(ALGraph G)；

4、初始条件：图G存在。操作结果：显示选择项目。MinExpenditure70405(arcs,expenditure,route)；初始条件：图G存在。操作结果：从一个顶点到另一个顶点的最少钱数。MinTime70405( arcs,time,route)；初始条件：图G存在。操作结果：从一个顶点到另一个顶点的最短时间。DeleteVex70405(&G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v以及相关的弧。ADT Graph系统模块图如下： 全国交通咨询系统退出显示交通系统用户咨询管理员模块管理员管理列车车次编辑飞机航班编辑城市编辑初始化交通系统用户咨询最少中转次

5、数最少旅行时间最少旅行费用显示交通系统显示城市显示飞机航班显示列车车次键盘输入初始化交通系统文档形式输入入飞机航班编辑删除航班新增航班火车列次编辑新增车次删除车次3 详细设计图的邻接表存储结构表示如下：#include MAX_VERTEX_NUM 20typedef struct ArcNode /弧的结构int adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一个弧的指针infoType *info;/该弧相关信息的指针ArcNode；typedef struct VNode/顶点结构vertextype data;/顶点信息Arcnode *

6、firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构AdjList vertices;int vexnum ,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;/队列的链式存储结构typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front;/对头指针。 QNode *rear;/队尾指针。LinkQueue; 主界面操作:int main() 界面初始化； 输入

7、操作命令； While（“命令” ！= “退出”） 接受命令（用户输入要实现功能）； 进入各个处理命令函数； 图的相关数据类型的定义/初始化图G 当i=1,执行如下：a.创建城市b.创建飞机航班c.创建列车车次d.创建图G 当i=2，执行创建图Gvoid initgraph70405 (ALGraph *G) switch(i) case 1:createcityfile70405(); createplanefile70405(); createtrainfile70405(); CreateGraph70405 (G); break;case 2:CreateGraph70405 (G)

8、; break; / 管理项目while(i!=5) 若i=1时，则执行初始化交通系统若i=2时，则执行城市编辑若i=3时，则执行飞机航班编辑若i=4时，则执行列车车次编辑void Administer(ALGraph *G)while(i!=5)switch(i) case 1:initgraph(G); break; case 2:cityedit(G); break; case 3:flightedit(G); break; case 4:trainedit(G); break;/对城市进行编辑，若i=1,则调用添加城市的函数；若i=2，则调用删除城市的函数。void cityedit7

9、0405(ALGraph *G) if(i=1) EnterVertex70405 (G); if(i=2) DeleteVertex70405 (G);/添加城市1. 定位v的位置，输入城市2. 若该城市存在，则返回否则，对城市进行确认，如果输入Y或者y，则把城市复制到图G的i位置void EnterVertex(ALGraph *G) i=LocateVertex (G,v); if(i=0&ivexnum) printf(n错误！此城市已存在n); return;else printf(n确认?(Y/N); c=getchar(); getchar(); if(c=Y|c=y) i=G-

10、vexnum; strcpy(G-verticesi.cityname,v); G-verticesi.planefirstarc=NULL; G-verticesi.trainfirstarc=NULL; G-vexnum=i+1; save(G); else return;/用户需求，while(i!=4)若i=1时，则调用最少旅行费用的函数；若i=2时，则调用最少旅行时间的函数；若i=3时，则调用最少旅行中转次数的函数。void UserDemand70405(ALGraph G) while(i!=4) switch(i) case 1:DemandDispose(1,G); brea

11、k; case 2:DemandDispose (2,G); break; case 3:DemandDispose (3,G); break; return ;/初始化队列头结点等于尾结点，并且头结点所指向的元素为空。void InitQueue(LinkQueue *Q) Q-front=(QNode *)malloc(sizeof(QNode); Q-rear=Q-front; Q-front-next=NULL;/入队 申请一个结点，然后给该结点放入x元素，并且该结点的下一个结点为空。尾结点的下一个结点指向该结点，然后把该结点给尾结点void EnterQueue70405(LinkQ

12、ueue *Q,int x) newnode=(QNode *)malloc(sizeof(QNode); newnode-adjvex=x; newnode-next=NULL; Q-rear-next=newnode; Q-rear=newnode;/出队 void DeleteQueue(LinkQueue *Q,int *x) p=Q-front-next; Q-front-next=p-next; if(Q-rear=p)Q-rear=Q-front;*x=p-adjvex; free(p);/判队列是否为空，如果头结点等于尾结点，则返回队列为空，否则队列不空。int IsEmpty

13、(LinkQueue *Q)if(Q-front=Q-rear) return(1);else return(0);/1.初始化一个邻接表 2.确定v1,v2在G中的位置，申请s,t两个结点，并且两条边所指向的位置分别为i,j 下一条边指向第一条依附该顶点的弧的指针 sG.verticesi.firstarct G.verticesj.firstarcStatus CreateUDN(ALGraph &G) /初始化邻接表 for( i = 0; i G.vexnum; i+) G.verticesi.firstarc = NULL; for(k = 0; k adjvex = j; /该边所

14、指向的顶点的位置为j s-nextarc = G.verticesi.firstarc; G.verticesi.firstarc =s; t-adjvex = i; /该边所指向的顶点的位置为i t-nextarc = G.verticesj.firstarc; G.verticesj.firstarc =t; return OK;/查找G里面有无v，若有，则返回v的位置。否则，返回-1int LocateVex(ALGraph G, char v) int i; for(i = 0; i G.vexnum; i+) if(v != G.verticesi.data) return i; r

15、eturn -1;/访问G中的v ，并且输出v int Visit(char v) printf(“%c ”,v); return OK;系统功能设计1） 系统功能分析系统提供操作的管理员还有用户两个主界面，并且通过系统主菜单为用户使用城市交通路线添加、删除、查找等基本功能，每一个功能设置计独立的模块实现，并且可以输出相对应的结果。交通咨询系统管理员用户添加城市删除城市查询最小耗费路线查询最短时间路线查询城市所有路线退出添加交通路线删除交通路线返回上一级菜单返回上一级菜单2） 系统子程序集功能设计主要功能有10个。l Main 主函数l SeekCity 查找城市l InsertCity 插入

16、城市l DelCity 删除城市l InsertTrain 插入火车l InsertFlight 插入航班l DelPath 删除交通路线l Dijkstra_Output 迪杰斯特拉l CalcMinCost 计算最小花费l CalcMinTime 计算最短时间1. 功能结构图2 功能结构调用关系图2. 系统设计思路交通咨询系统管理员用户添加城市删除城市查询最小耗费路线查询最短时间路线查询城市所有路线退出添加交通路线删除交通路线返回上一级菜单返回上一级菜单管理员界面包括添加城市、删除城市、添加交通路线、删除交通路线。用户界面包括出巡最小耗费路线、查询最短路线、查询城市所有路线。函数和过程的调

17、用关系图如下：Main()PrintGraphUserDemandAdministerAdministertraineditflighteditcityeditinitgraphUserDemandTimeDisposeTransferDisposeExpenditureDisposeDeleteQueueEnterQueueInitQueueTimeTreeDisposeMinTimeMinExpenditureinitgraphcreatetrainfilecreateGraphcreateplanefilecreatecityfilecityeditEnterVertexDeleteVe

18、rtex入flighteditDeleteplaneArEnterplaneArctraineditEntertrainArcDeletetrainArcInitQueueEnterQueueDeleteQueueCreateTimeTreeCopyTimeTreeTimeTreeDisposeVisitTimeTreeDestoryTimeTree功能模块具体简介如下：本系统进入时需要选择您的身份：管理员或用户。（1）管理员：要进入管理员界面，首先需要输入用户名和密码。为本系统方便使用，用户名和密码都默认为。输入正确的用户名和密码后，即可进入管理员界面，若输入错误，则退回主界面。管理员界面有

19、5个选项：添加城市、删除城市、添加交通路线、删除交通路线、返回上一级菜单。添加城市和删除城市只需输入城市名即可删除该城市，添加交通路线需要输入起始站城市名、终点站城市名、选择交通工具、火车（飞机）班次、起始时刻、到达时刻和票价，删除交通路线需输入班次。若添加信息成功，会显示“系统信息输入成功!”，若输入选择序号错误，会显示“选择序号错误！请重新选择！”。返回上一级菜单是返回主界面。输入的信息会分别写入city.txt，train,txt，flight,txt中，用户查询路线时会从文件中读入。（2）用户：用户界面有4个选项：查询最小耗费路线、查询最短时间路线、查询城市所有路线、返回上一级菜单。查

20、询最小耗费和最短时间是一个图的最短路径问题，因此用迪杰斯特拉（Dijkstra）算法按路径长度递增的顺序逐步产生最短路径的方法。最小耗费的编程思想如下：先设置一个二维数组，第一个下标放置城市编号，第二个下标为第一个下标城市中花费最小的终点站城市编号，数组放置的数据为所需要的花费。先判断初始城市和终点城市是否在交通路线中，再设置一个数组，将已找到的最小花费的城市放入这个数组。初始状态时，该数组只包含初始城市，然后不断的选取到该城市花费最小的路线加入数组中，直至找到终点城市。这就是迪杰斯特拉算法。最短时间的路线也是用此算法计算的。查询城市所有路线需要输入所要查询的城市名和选择交通工具，可显示该城市

21、中所选交通工具的所有路线。迪杰斯特拉（Dijkstra）算法的基本思想是：设置两个顶点的集合S和TVS，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。下面讨论基于邻接表的存储结构求两点间最短路径的方法： 根据迪杰斯特拉(D

22、ijkstra)算法所依据的原理：若按长度递增的次序生成从源点V0到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。四.系统的主要界面设计及运行说明：该图为主界面，选择序号即可进入所需界面。进入管理员界面需经过身份验证，输入用户名和密码，本程序用户名和密码均为。此图为管理员界面，这是添加交通路线的例子。此图为删除交通路线的例子。此图为已输入的火车路线的保存文件。第一个数字表示的是火车路线总数，城市文件和飞机路线文件同此文件类似。此图为查询火车最小耗费路线。这是两地之间无中转站的例子。此图为查询火

23、车最小耗费路线时两地之间有中转站的例子。飞机路线查询同此。此图为查询最短时间路线。此为两站中无中转站的例子。有中转站和飞机路线同最小耗费路线的图类似。此图为查询城市所有路线。此为查找北京所有火车的例子。程序中所用到的时刻表： 列车时刻表车 次出 发 地 到 达 地出发时间到达时间车 费27北京郑州西安郑州 郑州 西安郑州北京13：1521：2405：4113：4221：1205：1313：3021：39 78元 82元82元78元41 北京 郑州 上海 郑州 郑州上海郑州北京7：1115：2000：3509：4015：0800：1309：2817：37 90元 100元 100元90元59 上

24、海 广州 广州 上海08：2003：3903：1622：53 182元134 兰州 北京 北京 兰州03：5219：2418：5610：28 162元323 广州 昆明 昆明 广州06：1816：3116：1402：27 102元873 武汉 昆明 昆明 武汉07：1321：4221：1711：46134元116 武汉 长沙 长沙 武汉09：3618：5418：3203：4898元373 长沙 广州 广州 长沙13：1500：3500：1511：35116元747兰州武汉武汉兰州17：4115：1314：4712：19210元航班时刻表机 号 出 发 地 到 达 地出发时间到达时间费 用 63

25、20北京上海上海北京16：2018：00 17：2519：05680元201 北京 西安 西安 北京15：2512：3517：0014：15930元2323 西安广州 广州 西安7：1510：159：3511：351320元173 拉萨 昆明 昆明拉萨10：2012：3511：4514：00830元3304 拉萨 武汉 武汉拉萨14：1516：2515：4517：55890元4723 武汉广州 广州 武汉 7：0511：258：4513 ：05810元五.程序的主要代码：#include #include #define Dij_MAXN 33 #define MAX_VERTEX_NUM 3

26、1 #define MAX_STRING_NUM 10 #define MAX_TRAFFIC_NUM 10 typedef short int CityType; typedef struct TrafficNode char nameMAX_STRING_NUM; /班次 int StartTime,StopTime; /起止时间 int EndCity; /火车到达城市的编号 int Cost; /票价 TrafficNodeDat; typedef struct VNode CityType city; /城市编号 int TrainNum,FlightNum; /标记下面Train数

27、组和Flight数组里元素个数 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /数组成员为结构体，记录了到达城市、起止时间、票价和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM; VNodeDat; typedef struct PNode int City; int TraNo; PNodeDat; char CityNameMAX_VERTEX_NUMMAX_STRING_NUM; /城市名，采用第一下标为该城市在本程序中的编号 int CityNum; /城市数目 VNodeDat AdjListMAX_VERTEX_NUM;

28、/下标所在城市的线路PNodeDat PathMAX_VERTEX_NUM; /存储临时最小时间路径 PNodeDat MinPathMAX_VERTEX_NUM; /存储搜索到当前的最小时间路径 int MinTime,StartTime; int curPath; int SeekCity(char *name) /查找城市 int i; for(i=0;iCityNum;i+) if(strcmp(name,CityNamei)=0) return i; return -1;int SaveFile() /将火车飞机交通信息写入文件 FILE *fp; int i,j,total; if

29、(fp=fopen(city.txt,wb)=NULL) printf(nt无法打开文件!n); return -1; fprintf(fp,%dn,CityNum);/在city文件中输入城市总数 for(i=0;iCityNum;i+) fprintf(fp,%sn,CityNamei);/再输入城市名 fclose(fp); total=0; if(fp=fopen(train.txt,wb)=NULL) printf(nt无法打开文件!n); return -1; for(i=0;iCityNum;i+) total+=AdjListi.TrainNum; fprintf(fp,%dn

30、,total);/在train文件中输入火车总数 for(i=0;iCityNum;i+) for(j=0;jAdjListi.TrainNum;j+) fprintf(fp,%s %s %s ,AdjListi.T,CityNamei, CityNameAdjListi.Trainj.EndCity); /输入火车车次，始发站和终点站 fprintf(fp,%2d:%2d %2d:%2d %dn,AdjListi.Trainj.StartTime/60, AdjListi.Trainj.StartTime%60, AdjListi.Trainj.StopTime/60,

31、AdjListi.Trainj.StopTime%60, AdjListi.Trainj.Cost);/输入发车时间和到站时间和费用 fclose(fp); total=0; if(fp=fopen(flight.txt,wb)=NULL) printf(nt无法打开文件!n);return -1; for(i=0;iCityNum;i+) total+=AdjListi.FlightNum; fprintf(fp,%dn,total);/在flight文件中输入飞机总数 for(i=0;iCityNum;i+) for(j=0;jAdjListi.FlightNum;j+) fprintf(

32、fp,%s %s %s ,AdjListi.F,CityNamei, CityNameAdjListi.Flightj.EndCity); /输入飞机航班号，始发站和终点站 fprintf(fp,%2d:%2d %2d:%2d %dn,AdjListi.Flightj.StartTime/60, AdjListi.Flightj.StartTime%60, AdjListi.Flightj.StopTime/60, AdjListi.Flightj.StopTime%60, AdjListi.Flightj.Cost);/输入起飞时间，到达时间和费用 fclose(fp)

33、;return 1;int InsertCity(char *Name) /添加城市 strcpy(CityNameCityNum,Name); AdjListCityNum.city=CityNum;/设置城市编号 AdjListCityNum.FlightNum=0; AdjListCityNum.TrainNum=0;/新增城市火车数和飞机数初始为零 CityNum+;/城市总数加1 return 1;int DelCity(char *Name) /删除城市 int city,i,j; city=SeekCity(Name); for(i=city;iCityNum-1;i+) str

34、cpy(CityNamei,CityNamei+1); AdjListi.FlightNum=AdjListi+1.FlightNum;AdjListi.TrainNum=AdjListi+1.TrainNum; for(j=0;jAdjListi.FlightNum;j+) AdjListi.Flightj.Cost=AdjListi+1.Flightj.Cost; AdjListi.Flightj.EndCity=AdjListi+1.Flightj.EndCity; strcpy(AdjListi.F,AdjListi+1.F); AdjLis

35、ti.Flightj.StartTime=AdjListi+1.Flightj.StartTime; AdjListi.Flightj.StopTime=AdjListi+1.Flightj.StopTime; CityNum-;return 1;int InsertTrain(char *train,char *StartCity,char *EndCity,int StartTime,int EndTime,int cost) /添加火车路线 int i,j; i=SeekCity(StartCity);j=SeekCity(EndCity); AdjListi.TrainAdjListi

36、.TrainNum.Cost=cost;AdjListi.TrainAdjListi.TrainNum.EndCity=j; AdjListi.TrainAdjListi.TrainNum.StartTime=StartTime; AdjListi.TrainAdjListi.TrainNum.StopTime=EndTime; strcpy(AdjListi.TrainAdjListi.TrainN,train); AdjListi.TrainNum+;return 1;int InsertFlight(char *flight,char *StartCity,char *En

37、dCity,int StartTime,int EndTime,int cost) /添加飞机路线 int i,j; i=SeekCity(StartCity);j=SeekCity(EndCity); AdjListi.FlightAdjListi.FlightNum.Cost=cost;AdjListi.FlightAdjListi.FlightNum.EndCity=j; AdjListi.FlightAdjListi.FlightNum.StartTime=StartTime; AdjListi.FlightAdjListi.FlightNum.StopTime=EndTime; st

38、rcpy(AdjListi.FlightAdjListi.FlightN,flight); AdjListi.FlightNum+; return 1;int DelPath(char *name) /删除路线 int i,j,flag=0; for(i=0;iCityNum;i+) for(j=0;jAdjListi.FlightNum;j+) if(strcmp(AdjListi.F,name)=0) flag=1;break;/找到要删除的路线，找到跳出for循环 if(flag) for(;jAdjListi.FlightNum-1;j+) AdjL

39、isti.Flightj.Cost=AdjListi.Flightj+1.Cost; AdjListi.Flightj.EndCity=AdjListi.Flightj+1.EndCity; strcpy(AdjListi.F,AdjListi.Flightj+1.name); AdjListi.Flightj.StartTime=AdjListi.Flightj+1.StartTime; AdjListi.Flightj.StopTime=AdjListi.Flightj+1.StopTime; AdjListi.FlightNum-;break;/将要删除路线后面的路

40、线全部向前移，并将总数减1 for(j=0;jAdjListi.TrainNum;j+) if(strcmp(AdjListi.T,name)=0) flag=1;break; if(flag) for(;j=0) cost+=sPreCityjj;/循环后cost为总费用 j=PreCityj;tracki+=j; printf(nt您要查找的路线为:); printf(nt*n); printf(t车号 起始站 终点站 时间 花费n); if(!TravelType)/类型为火车 for(i-;i0;i-)/初始时i-后i为路线中的城市数目 end=tracki-1;m

41、in=32767; for(k=0;kAdjListtracki.Traink.Cost) min=AdjListtracki.Traink.Cost;/min为路径中的最小花费 tmp=k;/k为一条路径中花费最小的火车编号 printf(nt%s,AdjListtracki.T);/输出火车班次 printf(t%10s,CityNametracki);/输出起始城市名 printf(t%10s,CityNametracki-1);/输出终点城市名 printf(t%2d:%2d-%2d:%2d,AdjListtracki.Traintmp.StartTime/60

42、, AdjListtracki.Traintmp.StartTime%60, AdjListtracki.Traintmp.StopTime/60, AdjListtracki.Traintmp.StopTime%60);/输出起止时间 printf(t%dn,AdjListtracki.Traintmp.Cost);/输出花费 else/类型为飞机 for(i-;i0;i-) end=tracki-1;min=32767; for(k=0;kAdjListtracki.Flightk.Cost) min=AdjListtracki.Flightk.Cost;tmp=k; printf(nt%s,AdjListtracki.F);printf(t%10s,CityNametracki); printf(t%10s,CityNametracki-1); printf(t%2d:%2d-%2d:%2d,AdjListtracki.Flighttmp.StartTime/60, AdjListtracki.Flighttmp.StartTime%60, AdjListtracki.Flighttmp.StopTime/60, AdjListtracki.Flighttmp.StopTime%60); printf(t%dn,AdjListtracki.Fl