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

《交通咨询系统设计实验报告》由会员分享，可在线阅读，更多相关《交通咨询系统设计实验报告（45页珍藏版）》请在金锄头文库上搜索。

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

2、时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。2.系统概要系统概要为实现上述程序功能，要用到一种数据结构，图。根据输入的顶点和边，建立图，然后利用图的邻接表存储结构 实现算法。ADT Graph数据对象 V：v 是具有相同数据特性的元素的集合，称作顶点集。数据关系 R：R

3、=VRVR=|v，w 属于 V 且 P（v，w） ，表示从 v 到 w 的弧，谓词 P（v，w）定义了弧的意义或信息 基本操作 P：CreateGraph70405(初始条件：V 是图的顶点集，VR 是图的弧的集合。操作结果：按 V 和 VR 的定义构造图 G。Initgraph70405(G)；初始条件：图 G 存在。操作结果：各个变量初始化。LocateVex70405G，u） ；初始条件：图 G 存在，u 和 G 中顶点具有相同的性质。操作结果：若图中存在顶点 u，则返回该顶点在图中的位置；否则返回其他信息。Cityedit70405(G)；初始条件：图 G 存在。操作结果：对城市进行编

4、辑。EnterVertex70405(G)；初始条件：图 G 存在。操作结果：增加城市。UserDemand70405(ALGraph G)；初始条件：图 G 存在。操作结果：显示选择项目。MinExpenditure70405(arcs,expenditure,route)；初始条件：图 G 存在。操作结果：从一个顶点到另一个顶点的最少钱数。MinTime70405( arcs,time,route)；初始条件：图 G 存在。操作结果：从一个顶点到另一个顶点的最短时间。DeleteVex70405(/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一个弧的指针

5、 infoType *info;/该弧相关信息的指针 ArcNode；typedef struct VNode/顶点结构 vertextype data;/顶点信息 Arcnode *firstarc;/指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构 AdjList vertices; int vexnum ,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph; /队列的链式存储结构 typedef struct QNode 飞机航班编辑新增航班删除航班火车列次编辑新增车次删除

6、车次int adjvex;struct QNode *next; QNode;typedef struct QNode *front;/对头指针。QNode *rear;/队尾指针。 LinkQueue;主界面操作主界面操作:int main()界面初始化；输入操作命令；While（“命令” ！= “退出” ） 接受命令（用户输入要实现功能） ； 进入各个处理命令函数； 图的相关数据类型的定义图的相关数据类型的定义 /初始化图 G当 i=1,执行如下：a.创建城市 b.创建飞机航班 c.创建列车车次 d. 创建图 G当 i=2，执行创建图 Gvoid initgraph70405 (ALGra

7、ph *G) switch(i) case 1:createcityfile70405();createplanefile70405();createtrainfile70405();CreateGraph70405 (G);break;case 2:CreateGraph70405 (G) ;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

8、); break;case 2:cityedit(G); break;case 3:flightedit(G); break; case 4:trainedit(G); break;/对城市进行编辑，若 i=1,则调用添加城市的函数；若 i=2，则调用删除城市的函数。void cityedit70405(ALGraph *G)if(i=1)EnterVertex70405 (G);if(i=2)DeleteVertex70405 (G);/添加城市1. 定位 v 的位置，输入城市2. 若该城市存在，则返回否则，对城市进行确认，如果输入 Y 或者 y，则把城市复制到图 G 的 i 位置void

9、EnterVertex(ALGraph *G)i=LocateVertex (G,v);if(i=0return;elseprintf(“n 确认?(Y/N)“);c=getchar();getchar();if(c=Y|c=y)i=G-vexnum;strcpy(G-verticesi.cityname,v);G-verticesi.planefirstarc=NULL;G-verticesi.trainfirstarc=NULL;G-vexnum=i+1;save(G);elsereturn;/用户需求，while(i!=4)若 i=1时，则调用最少旅行费用的函数；若 i=2时，则调用最少

10、旅行时间的函数；若 i=3时，则调用最少旅行中转次数的函数。void UserDemand70405(ALGraph G)while(i!=4)switch(i)case 1:DemandDispose(1,G);break; 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;

11、Q-front-next=NULL;/入队 申请一个结点，然后给该结点放入 x 元素，并且该结点的下一个结点为空。尾结点的下一个结点指向该结点，然后把该结点给尾结点void EnterQueue70405(LinkQueue *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

12、-next;if(Q-rear=p)Q-rear=Q-front;*x=p-adjvex;free(p);/判队列是否为空，如果头结点等于尾结点，则返回队列为空，否则队列不空。int IsEmpty(LinkQueue *Q)if(Q-front=Q-rear)return(1);elsereturn(0);/1.初始化一个邻接表2.确定 v1,v2在 G 中的位置，申请 s,t 两个结点，并且两条边所指向的位置分别为 i,j 下一条边指向第一条依附该顶点的弧的指针 sG.verticesi.firstarct G.verticesj.firstarcStatus CreateUDN(ALGr

13、aph i adjvex = j; /该边所指向的顶点的位置为 js-nextarc = G.verticesi.firstarc;G.verticesi.firstarc =s;t-adjvex = i; /该边所指向的顶点的位置为 it-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 #include #define Dij_MAXN 33

14、 #define MAX_VERTEX_NUM 31 #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

15、,FlightNum; /标记下面 Train 数组和 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; /下标所在城市的线路 PNodeDat PathMAX_VERTEX_NUM; /存储临时最小时间路径 PNodeDat MinPathMAX_VERTEX_NUM; /存储搜索到当前的最小时间路径 int MinTime,StartTime;