交通咨询.doc

数据结构课程设计题目：交通咨询姓名：邵文学号：030807日期：2012年11月3日一实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二问题描述设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。三需求分析 该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1） 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。（2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。（3） 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。 （4） 设计良好的图形用户界面四概要设计 系统用到的抽象数据类型定义：1ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R=VR VR=|P(x,y)(x,y属于V) 基本操作：（1） initgraph(&G)；（2） CreateGraph(&G)；（3） EnterVertex(&G)；（4） DeleteVertex(&G)；（5） EnterplaneArc(&G)；（6） DeleteplanArc(&G)；（7） EntertrainArc(&G)；（8） DeletetrainArc(&G)；ADT Graph 2ADT LinkQueue 数据元素：可以是任意类型的数据，但必须属于同一个数据对象 关系：队列中数据元素之间是线性关系。 基本操作：（1） InitQueue(&Q)；（2） IsEmpty(&Q)；（3） EnterQueue(&Q,x)；（4） DeleteQueue(&Q,&y)； ADT LinkQueue 3ADT TimeTree 数据对象D：一个集合，该集合中的所有元素具有相同的特性 数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则R=H，H为如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H中没有前驱（2） 除root以外，D中每个结点在关系H下有且仅有一个前驱。 基本操作：（1） CreateTimeTree(p,i,j,&Q,infolist arcs)；（2） CopyTimeTree(p,q)；（3） VisitTimeTree(p)；ADT TimeTree 系统中子程序及功能要求：1Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程序。2initgraph(ALGraph *G)：初始化交通系统的子程序3createcityfile( )：创建城市文件的子程序4createplanefile( )：创建航班文件的子程序5createtrainfile( )：创建列车时刻表文件的子程序6LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编号7CreateGraph(ALGraph *G)：创建城市交通系统8cityedit(ALGraph *G)：提供城市编辑功能9EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能10DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功 能11flightedit(ALGraph *G)：提供航班编辑功能12EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功 能13DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的 功能14：trainedit(ALGraph *G):提供列车车次的编辑功能15EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次 的功能16DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车 次的功能17UserDemand(ALGraph G)：提供用户咨询的界面18DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序19InitQueue(LinkQueue *Q)：初始化队列20EnterQueue(LinkQueue *Q,int x)：入队操作21DeleteQueue(LinkQueue *Q,int *x)：出队操作22IsEmpty(LinkQueue *Q)：队列判空操作23TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,(*arcs)MAX_VERTEX_NUM ,ALGraph G,ALGraph G,int v0,int v1)：提供最少中转次数决策的功能 24MinExpenditure(infolist arcs,float *expenditure,float *route)：提供两个城市之间最少费用的功能 25ExpenditureDispose(int k, infolist (*arcs)MAX_VERTEX_NUM,ALGraph G, int v0,int v1,float *D,int *final)：提供最少费用决策的功能 26MinTime(infolist arcs,float *time,float *route) ：提供两个城市之间最短时间的功能 27TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM)：提供两个之间相隔一个以上城市的城市间的最短时间的功能 28CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist(*arcs)MAX_VERTEX_NUM)：创建时间树 29CopyTimeTree(TimeTree p,TimeTree q)：复制时间树 30VisitTimeTree(TimeTree p)：访问时间树 31DestoryTimeTree(TimeTree p)：销毁时间树 32TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraphG,int v0,int v1,float *D,int *final) ：提供最少时间决策的功能 33：PrintGraph(ALGraph *G)：显示整个城市交通系统 各程序模块之间的调用关系（子程序编号见上）： 主函数可调用子程序1，17，33 子程序1可调用子程序2，8，11，14 子程序2可调用子程序3，4，5，7 子程序7，12，13，15，16可调用子程序6 子程序8可调用子程序9，10 子程序11可调用子程序12，13 子程序14可调用子程序15，16 子程序17可调用子程序18 子程序18可调用子程序23，25，32 子程序23可调用子程序19，29，21，22 子程序25可调用子程序24 子程序32可调用子程序26，27 子程序27可调用子程序28，30，31 子程序28可调用子程序29五详细设计 创建交通图算法的伪码描述如下： int LocateVertex(ALGaph *G,char *v)/*找出城市名在图中对应结 点位置*/ for(k=0;kvexnum;k+) if(第k个结点中的城市名与传过来的城市名相同) j=k;/*记录位置*/ break; 返回k 的数值；int CreatGraph(ALGraph *G) if(打开城市文件，文件指针返回值为空） 输出错误文件信息； 程序返回值为0； while(文件不为空） 将文件指针所指的字符串读到城市名数组 cityi中； i+; 关闭文件； j=0; while(jvexnum=i; 打开航班信息文件plane.txt; 将文件中的内容以块为单位读到缓冲区数组a中； 关闭文件； a的计数变量k=0; 弧的计数变量 arc_num=0; while(kverticesi.planfirstarc; m=0; while(q!=NULL) if( 弧 q中的邻接顶点与j相等） 将数组ai 中的内容都复制到弧q中； m=1; break; q=q-nextarc; if(m=0); 开辟一个弧结点； 将数组ai中的内容都复制到新的弧结点中； 将弧结点连接到适当的位置中去； arc_num+; k+; G-planarcnum=arc_num; 打开列车信息文件plane.txt; 将文件中的内容以块为单位读到缓冲区数组a中； 关闭文件； a的计数变量k=0; 弧的计数变量 arc_num=0; while(kverticesi.trainfirstarc; m=0; while(q!=NULL) if( 弧 q中的邻接顶点与j相等） 将数组ai 中的内容都复制到弧q中； m=1; break; q=q-nextarc; if(m=0); 开辟一个弧结点； 将数组ai中的内容都复制到新的弧结点中； 将弧结点连接到适当的位置中去； arc_num+; k+; G-trainarcnum=arc_num;返回； 创建航班算法的伪码描述如下： creatplanefile() while(flag) /*flag为标志位,初值为1*/ 提示“输入航班信息”；输入航班code; 输入航班的出发城市vt; 输入航班的到达城市vh; 输入机票价格money;输入航班的出发时间bt;输入航班的到达时间at;a.count.co=code; /* a 为程序头部定义的结构体*/ strcpy(a.count.vt,vt);strcpy(a.count.vh,vh);a.count.bt=bt;a.count.at=at;a.count.mo=money;计数值count+1;提示“是否要继续输入航班信息：”；scanf(“%d”,&flag);if(航班文件不能以读写形式打开)提示“无法打开文件”；将计数值count写入航班车文件；for(i=0;icount;i+) if(无法将ai写入航班文件) 提示“文件无法写入”；关闭航班文件； 删除城市结点算法的伪码描述如下： DeleteVertex(ALGraph *G) /* G是程序头部定义的结构体*/ 提示“输入删除城市名”； gets(城市名：v); 提示“是否确定要删除（Y/N）“； c=getchar(); if(c=Y|c=y) n=0; /*0是记数标志，控制循环次数*/while(n图G表头接点总个数&图G的存储城市名与v不同) /*G表头结点总个数比实际大1*/ 记数值n+1; if(n = =图G表头结点总个数) 提示“无法找到此城市“；else i=LocateVertex(G,v);/*利用G函数找到此城市名所处在G中位置*/删除从此结点出发的所有航班弧；删除从此结点出发的所有列车弧；for(j=i;j图G表头结点总个数-1；j+)将G第j个结点的信息依前移1位；将G第j个结点的信息制空；/*以下是删除所有指向此结点的航班弧*/for(k=0;kadjvex ）i） 将该弧指向顶点位置-1； q=p； p指向下一条飞机弧； else if（该弧指向的顶点位置（p-adjvex ）= = i） if（p指向图G中k结点的第一条飞机弧） m=p； 将图G中k结点的第二条飞机弧改为第一弧； p指向下一条飞机弧； 释放（m）； else 将p的下一条弧赋给q的下一条弧； m=p； p指向下一条飞机弧； 释放（q）； else q=p； p指向下一条飞机弧； /*以下是删除所有指向此结点的列车弧*/for(k=0;kadjvex ）i） 将该弧指向顶点位置-1； q=p； p指向下一条列车弧； else if（该弧指向的顶点位置（p-adjvex ）=i） if（p指向图G中k结点的第一条列车弧） m=p； 将图G中k结点的第二条列车弧改为第一弧； p指向下一条列车弧； 释放（m）； else 将p的下一条弧赋给q的下一条弧； m=p； p指向下一条列车弧； 释放（q）； else q=p； p指向下一条列车弧； 图G表头结点总个数-1；else return； 求城市v0，v1之间的最少费用算法的伪码描述如下： ExpenditureDispose( )for(v=0；v城市个数；v+) 城市v还未求得最少费用； *(D+v)=城市v0到v的最少费用； 将城市v的路径设置为空； if(*(D+v)INFINITY) 将城市v0和v加入到城市v的路径中； 城市v0到城市v0的最少费用为0； 城市v0设为已求得最少费用； for(i=1；i城市个数；v+) m=INFINITY; for(w=0；w城市个数；w+) if(城市w未求得最少费用) if(*(D+w)m) v=w; m=*(D+w); if(v等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少费用*(D+v1)； 返回；else将城市v设为已求得最少费用； for(w=0；m+城市v到w的最少费用) *(D+w)=m+城市v到w的最少费用； 将城市w的路径改成城市v的路径并在最后加入城市w； 输出没有列车或飞机从城市v0到v1； 最少中转次数算法的伪码描述如下：求城市v0到城市v1的最少中转次数TransferDispose( )for(v=0；vG.vexnum；v+) 城市v设为未访问； 城市v的路径设为空； 将城市v0设为已访问； 将城市v0入队； while(队列不空) 队首城市v出队； w为与城市v相连的第一个城市； while(w存在) if(城市w未访问)将城市w设为已访问； 将城市w的路径改为城市v的路径并在最后加入城市w； if(w等于v1) 根据城市w的路径输出从城市v0到城市v1所需经过的城市及路线； 返回； 将城市w入队； w等于城市v相连的下一个城市； 输出没有列车或飞机从城市v0到v1； 求城市v0，v1之间的最少时间算法的伪码描述如下： TimeDispose( )for(v=0；v城市个数；v+) 城市v还未求得最少时间； *(D+v)=城市v0到v的最少时间； 将城市v的路径设置为空； if(*(D+v)INFINITY) 将城市v0和v加入到城市v的路径中； 城市v0到城市v0的最少时间为0； 城市v0设为已求得最少时间； for(i=1；i城市个数；v+) m=INFINITY; for(w=0；w城市个数；w+) if(城市w未求得最少时间) if(*(D+w)m) v=w; m=*(D+w); if(v等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少时间v1； 返回；else将城市v设为已求得最少时间； for(w=0；从城市v0到城市w的最少时间) *(D+w)=从城市v0到城市w的最少时间； else 将城市w的路径还原； 输出没有列车或飞机从城市v0到v1； 六测试分析 按照附录中的测试数据，得出如下测试、分析结果：1. 操作员管理功能.1. 当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息.2. 我们事先建立了有关图的3 个文本文件(包括city.txt,plan.txt,train.txt),在交通系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息.3. 当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或列车弧,以上各功能都正确.2. 交通咨询功能. 1. 火车情况. 1.1.最少费用.a. 两地间无中转且有多辆火车.北京-郑州输出结果为:旅行路线是: 乘坐NO.27列车车次在13：15 从 Beijing 到zhengzhou.最少旅行费用是78元. 而若选择NO.41 则花费为80 元. 结果正确.b. 两地之间无中转达且只有一辆火车.西安-武汉输出结果为:旅行路线是: 乘坐NO.218列车车次在1：34从xian到wuhan. 最少旅行费用是178.00 元. 结果正确.c. 两地之间有中转.昆明-北京输出结果为:旅行路线是: 乘坐NO.323列车车次在16.：31从kunming到Guangzhou. 乘坐NO.59列车车次在3：39从Guangzhou 到shanghai.乘坐NO.41列车车次在0：35从shanghai 到zhengzhou.乘坐NO.27列车车次在13：42 从zhengzhou 到Beijing.最少旅行费用是462 元. 而若选择 昆明-武汉-兰州-北京 则花费为506 元. 若选择 昆明-武汉-西安-郑州-北京 则花费为472 元.结果正确. 1.2最短时间. a. 两地间无中转且有多辆火车.北京-郑州输出结果为:旅行路线是: 乘坐NO.41列车车次在13：15从Beijing 到zhengzhou.最少旅行时间是7：57. 结果正确.b.两地之间无中转达且只有一辆火车.乌鲁木齐-兰州 输出结果为:旅行路线是: 乘坐No.371列车车次在0：35从wulumuqi 到lanzhou. 最少旅行时间是10：48. 结果正确.c. 两地之间有中转.广州-兰州 输出结果为:旅行路线是: 乘坐NO.59列车车次在3：39从guangzhou到shanghai. 乘坐NO.41列车车次在0：35从shanghai到zhengzhou.乘坐NO.41列车车次在9.40从zhengzhou到Beijing.乘坐NO.134列车车次在19.24从Beijing到lanzhou.最少旅行时间是54：49.结果正确. 1.3.最短周转次数.a. 两地可直达且有中转.昆明-广州 输出结果为:旅行路线是: 乘坐NO.323列车车次在16：31从kunming到guangzhou.最少旅行中转次数是0次 .而若选择 昆明-武汉-长沙-兰州 则 结果为3.结果正确.b.两地间有多条中转路径.昆明-上海输出结果为:旅行路线是: 乘坐NO.323列车车次在16：31从kunming 到guangzhou.乘坐NO.59列车车次在3：39从guangzhou 到shanghai.最少旅行总转次数是1次 .而若选择 昆明-武汉-西安-郑州-上海 则 结果为4.结果正确.2.飞机情况.2.1.两地无直达. 兰州-武汉输出结果为: 不存在飞机航班从lanzhou到wuhan.2.2.两地无直达.拉萨-昆明a.最少费用: 输出结果为:乘坐NO.173飞机航班在10：20 从lasa 到kunming.最少旅行费用是830 元.结果正确.b.最短时间:输出结果为:乘坐NO.173 飞机航班在10：20 从lasa 到kunming.最少旅行时间是1：25.结果正确.c.最短中转次数.输出结果为:乘坐NO.173 飞机航班在10：20 从lasa 到kunming.最少旅行中转次数是0次.结果正确.2.3两地可中转.广州-北京a.最少费用:输出结果为:乘坐NO.2323飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35 从xian 到beijing.最少旅行费用是2250 元.结果正确.b.最短时间:输出结果为: 乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35 从xian 到beijing.最少旅行时间是4：00.结果正确.c.最短中转次数.输出结果为:乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35从xian 到beijing.最少旅行中转次数是1次.结果正确.3.打印 打印结果正确;4.退出能正确退出七使用说明 1运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出程序。 2管理员管理界面包括5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的增加和删除，具体使用见说明4；选项三：航班编辑界面，可进行航班的增加和删除，具体使用见说明5；选项四：列车车次编辑界面，可进行列车车次的增加和删除，具体使用见说明6；选项五：返回上一级菜单，可返回主界面。 3初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城 市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间，则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下，且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。 4城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出错。 5航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间 新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达城市及费用、时间等信息；选项二，删除航班，可删除两个城市间的一条航班，选择该项后用户需输入要删除航班的编号，起始城市，到达城市的信息，若航班不存在或编号、城市输入有误，程序将提示错误。 6列车车次编辑界面包括两个选项：选项一：增加列车车次，可在两个城市之间新增列车车次，选择该项后用户需输入新增列车的编号，起始城市，到达城市及费用、时间等信息；选项二，删除列车车次，可删除两个城市间的一条列车车次，选择该项后用户需输入要删除车次的编号，起始城市，到达城市的信息，若列车车次不存在或编号、城市输入有误，程序将提示错误。 7用户咨询界面包括四个选项：选项一：最少费用咨询；选项二：最少时间咨询；选项三：最少中转次数咨询；选项三：返回上级菜单，可返回主界面。选择选项一、二、三都要求用户输入咨询信息，包括起始城市，到达城市和交通工具。输入完毕后城市提示用户是否确认，若不确认则要求用户重新输入咨询信息，若确认则给出用户所需的最优决策信息。 八附录：测试数据 航班时刻表 机 号 出 发 地 到 达 地出发时间到达时间费 用 6320北京上海上海北京16：2018：00 17：2519：05680元2104北京乌鲁木齐乌鲁木齐 北京8：0010：459：5511：401150元201 北京 西安 西安 北京15：2512：3517：0014：15930元2323 西安广州 广州 西安7：1510：159：3511：351320元173 拉萨 昆明 昆明拉萨10：2012：3511：4514：00830元3304 拉萨 武汉 武汉拉萨14：1516：2515：4517：55890元82 乌鲁木齐 昆明 昆明乌鲁木齐 9：3013：0512：1515：501480元4723 武汉广州 广州 武汉 7：0511：258：4513 ：05810元 列车时刻表车 次出 发 地 到 达 地出发时间到达时间车 费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 上海广州 广州 上海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 武汉 长沙 长沙 武汉9：3618：5418：3203：4898元373 长沙 广州 广州 长沙13：1500：3500：1511：35116元747兰州武汉武汉兰州17：4115：1314：4712：19210元371 兰州乌鲁木齐 乌鲁木齐 兰州11：4200：3523：5411：23114元218武汉西安 西安 武汉18：5001：3411：5118：35178元九附C语言实现源码#define MAX_VERTEX_NUM 18#define NULL 0#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5#include#include#include#include#define False 0#define True 1#define INFINITY 10000typedef structint number;float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar cityname10;ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct Node *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; QNode *rear;LinkQueue;typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree; struct arcint co; char vt10; char vh10; int bt2; int at2; float mo;aMAX_ARC_SIZE;char cityMAX_VERTEX_NUM10;int TTime2;int time2;int time12;int time22;int cMAX_VERTEX_NUM;int dMAX_VERTEX_NUM;void Administer(ALGraph *G);void cityedit(ALGraph *G);void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void Des