全国交通咨询模拟

中国地质大学（武汉）·数据结构课程设计第1页数据结构课程设计报告实验题目：5组+全国交通咨询模拟班级：191132-04姓名：薛福兴学号：20131000447指导老师：郭艳完成日期：2015年07月中国地质大学（武汉）·数据结构课程设计第2页5组+全国交通模拟咨询系统.............................................................31、需求分析.....................................................................................31.1、解决问题：.........................................................................31.2、程序的功能：.....................................................................31.3、输入和输出的形式：.........................................................32．设计.............................................................................................42.1设计思想..............................................................................42.2设计表示............................................................................52.3详细设计..............................................................................53．调试分析...................................................................................104．用户手册...................................................................................105．测试数据及测试结果................................................................106．参考文献...................................................................................147．总结...........................................................................................148．检查过后对程序的修改(07.25).................................................15中国地质大学（武汉）·数据结构课程设计第3页共15页5组+全国交通模拟咨询系统1、需求分析1.1、解决问题：城市之间有两种交通工具：火车和飞机。出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程序，为旅客提供两种最优决策的交通咨询。1.2、程序的功能：①读取城市信息文件并在程序运行时动态加载到内存；提供对城市信息进行编辑（如添加或删除）的功能。②读取列车时刻表和飞机航班表并在程序运行时动态加载到内存；提供对列车时刻表和飞机航班表进行编辑（增设或删除）的功能。③用户输入城市起点和终点，以及决策选项（最快到达或最省钱到达）后，系统针对用户所选的决策策略提供城市起点到城市终点间的所有不重复的可行方案（按照最优到最差的顺序排序输出）。全程只考虑一种交通工具。数据结构设计应尽可能快地实现查询和排序。④旅途中耗费的总时间应该包括中转站的等候时间。⑤咨询以用户和计算机的对话方式进行。1.3、输入和输出的形式：①功能：模拟全国交通咨询系统对费用或运行时间的最佳方案进行排序。②数据流入：将站台、铁路线的信息通过读取文件的方式进行对图的建立。③数据流出：在退出程序时对修改过的文件进行保存。④程序流程图：资源管理器流程图如图中国地质大学（武汉）·数据结构课程设计第4页共15页2．设计2.1设计思想一、数据与操作的特性①数据特性分析在本项目共包含2大类。1.1.1)AdjLWGraph类AdjLWGraph类为图的邻接表，内含seqlist类的顶点Vertices私有数据成员，numOfEdges代表图中所含边数。1.1.2)Railroadline类Railroadline类为铁路线所含含的信息，number为铁路线编号、name为铁路线的名称、S_allv中存储的为铁路线所经过的站、S_rrl中存储火车到达每个站的时间、S_orrl中存储火车在该点的出发时间。②操作特性分析1.2.1)构造两个类，分别用于存储站点（站点之间的联系）、铁路线。1.2.2)通过读取文件的格式将数据读入项目中。1.2.3)通过在已创建好的图中，对站点、铁路线进行增加。1.2.4)通过输入两个站点并选择最快方式or最省钱方式，并对所有结果按升序进行排序。1.2.5)对站点和铁路线进行增加与删除。二、数据结构设计①逻辑结构设计：在AdjLWGraph类中存放着站点，站点中含有每个站点的名称、简称、两点之间所属铁路线、站点的编号以及和此站点相连的站点的信息。②存储结构设计：通过采取邻接表的格式，将站与站之间的联系进行构建。在数据读入时，将铁路线进行构建。三、算法设计①总体设计②主要算法的基本思想选择区间添加or删除城市增加or删除时刻表添加城市删除城市选择决策(省钱or快速）全国交通咨询模拟系统询问是否加入铁路线添加铁路删除铁路修改铁路修改两点间的费用中国地质大学（武汉）·数据结构课程设计第5页共15页在读入读出中，对图的点与边进行构建，对铁路线所经过的点与铁路线的名称进行构建。在找符合条件的所有路线时，采用递归。在对所有符合条件的所有可能进行组合，并计算出时间、与费用，采用数组进行存取。对所有可能采用快速排序+插入排序，然后进行输出。2.2设计表示①函数调用关系图②函数接口规格说明voidifile1(AdjLWGraph&g2)//将图进行读入，通过引用修改图。voidGetEdgRoadline(constintv1,constintv2,SeqListint&S_line)const;//将边间所有路线读出。读入引用数组S_line中。voidInsertEdge(constintv1,constintv2,doubleMoney);//在两个站点间插入边与权值。Railroadline(intnum,stringn);//将铁路线的标号和铁路的名称进行初始化//查询两点间的所有线路(递归)voidCircle1(intv0,intj,intk,SeqListMessagem_vec,SeqListEdg&m_total,Edg&w)//此函数传入所有边的信息、m_total用于存储所有符合条件的路线所经过的点。//查询两点间的所有线路的所有可能（装站or不转）和算时间和费用(递归)voidCircle2(intvi,intvj,inti,intj,intv_end,SeqListint&temp,SeqListEdg&M_t,AdjLWGraph&G,SeqListRailroadline&S_rrl)//此函数传入参数有：M_t所有符合条件的路线、temp存放某条路线所经过点之间的线路、S_rrl存储对所有是否转站的可能进行存入。三、数据类型定义AdjLWGraph类AdjLWGraph类为图的邻接表，内含seqlist类的顶点Vertices私有数据成员，numOfEdges代表图中所含边数。Railroadline类Railroadline类为铁路线所含含的信息，number为铁路线编号、name为铁路线的名称、S_allv中存储的为铁路线所经过的站、S_rrl中存储火车到达每个站的时间、S_orrl中存储火车在该点的出发时间。2.3详细设计（6个主要功能）①构造数据类型AdjLWGraph类中：在对图进行构建的同时，也要对每个站点与站点之间的联系进行构造；中国地质大学（武汉）·数据结构课程设计第6页共15页AdjLWGraph::AdjLWGraph(constintsz):Vertices(sz){numOfEdges=0;}Vertex(EdgeListNode*ptr=NULL):adjhead(ptr){}Vertex(VTd,stringn,EdgeListNode*ptr=NULL):b_name(d),name(n),number(G_number++),adjhead(ptr){}Railroadline类中：在对铁路线进行构造对铁路线的编号、名字、通行标志进行赋值；railroadline::railroadline(intnum,stringn,stringm):number(num),name(n),mark(m){}②文件读入铁路线读入将铁路线的所属编号、名字、所经过的点、所经过的点的出发时间、到达时间进行读入While（文件未结束）{读入铁路线的编号、名字While（a！=-1）{将经过的点存储}While（a！=-1）{将经过的点的出发时间存储}While（a！=-1）{将经过的点的到达时间存储}}站台读入将铁站台的名称、简称进行读入。将站点与站点的距离进行读入。while(1){将站台的名称、编号、简称读入对图进行初始化（既将点添加入图中）将两点间的权值读入图中}中国地质大学（武汉）·数据结构课程设计第7页共15页③增加站点④删除站台VoidDelete_city(){输入要删除的城市for（所有线路）{将铁路线中所含有该城市的点删除并修改该点后面站点的出发与到达时间；增加该城市在此条线路前后两个站点的权值；If（该城市位于此铁路线最后一个）{If（该点与前一个站点只有一条铁路经过）删除边Else删除该边储存的此条铁路线}输入站点名称与简称是否加入已有铁路线YN输入需加入铁路线名称退出输入需插入的位置对该铁路线进行更新中国地质大学（武汉）·数据结构课程设计第8页共15页ElseIf（该城市位于此铁路线第一个）{If（该点与后一个站点只有一条铁路经过）删除边Else删除该边储存的此条铁路线}Else{If（该点与前一个站点只有一条铁路经过）删除边Else删除该边储存的此条铁路线If（该点与后一个站点只有一条铁路经过）删除边Else删除该边储存的此条铁路线}}}中国地质大学（武汉）·数据结构课程设计第9页共15页⑤两个站台之间的所有路线可能排序⑥排序功能voidquickSort(Num(&r)[100],intn,intk){qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序输入两个站台选择决策最快方式最省钱方式采用快速排序+插入排序进行排序采用递归将两个站台间所有路线找出采用递归将所有路线的可能进行组合存储并计算时间与费用（两点之间存在多条铁路线的情况）按升序将所有结果输出中国地质大学（武汉）·数据结构课程设计第10页共15页长度大于k时递归,k为指定的数并调用的Partition算法Partition函数为将小于基准的数放基准数前，将大于基准的数放基准数后再用插入排序对基本有序序列排序}3．调试分析（