全国交通咨询模拟分解.doc

《全国交通咨询模拟分解.doc》由会员分享，可在线阅读，更多相关《全国交通咨询模拟分解.doc（15页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计报告实验题目：5组+全国交通咨询模拟班级：191132-04姓名：薛福兴学号：20131000447指导老师：郭艳完成日期：2015年07月5组 + 全国交通模拟咨询系统31、需求分析31.1、解决问题：31.2、程序的功能：31.3、输入和输出的形式：32设计42.1 设计思想42.2 设计表示 52.3 详细设计53调试分析104用户手册105测试数据及测试结果106参考文献147总结148检查过后对程序的修改(07.25)155组 + 全国交通模拟咨询系统1、需求分析 1.1、解决问题： 城市之间有两种交通工具：火车和飞机。出于不同目的的旅客对交通工具有不同的要求。例如，

2、因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程序，为旅客提供两种最优决策的交通咨询。1.2、程序的功能： 读取城市信息文件并在程序运行时动态加载到内存；提供对城市信息进行编辑（如添加或删除）的功能。 读取列车时刻表和飞机航班表并在程序运行时动态加载到内存；提供对列车时刻表和飞机航班表进行编辑（增设或删除）的功能。 用户输入城市起点和终点，以及决策选项（最快到达或最省钱到达）后，系统针对用户所选的决策策略提供城市起点到城市终点间的所有不重复的可行方案（按照最优到最差的顺序排序输出）。全程只考虑一种交通工具。数据结构设计应尽可能快地实现查

3、询和排序。 旅途中耗费的总时间应该包括中转站的等候时间。 咨询以用户和计算机的对话方式进行。1.3、输入和输出的形式： 功能：模拟全国交通咨询系统对费用或运行时间的最佳方案进行排序。 数据流入：将站台、铁路线的信息通过读取文件的方式进行对图的建立。 数据流出：在退出程序时对修改过的文件进行保存。 程序流程图：资源管理器流程图如图2设计 2.1 设计思想 一、数据与操作的特性 数据特性分析在本项目共包含2大类。1.1.1)AdjLWGraph类AdjLWGraph类为图的邻接表，内含seqlist类的顶点Vertices私有数据成员，numOfEdges代表图中所含边数。1.1.2)Railro

4、adline类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)对站点和铁路线进行增加与删除。二、数据结构设计 逻辑结构设计： 在AdjLWGrap

5、h类中存放着站点，站点中含有每个站点的名称、简称、两点之间所属铁路线、站点的编号以及和此站点相连的站点的信息。 存储结构设计： 通过采取邻接表的格式，将站与站之间的联系进行构建。在数据读入时，将铁路线进行构建。三、算法设计 总体设计选择区间添加or删除城市增加or删除时刻表添加城市删除城市选择决策(省钱or快速）全国交通咨询模拟系统询问是否加入铁路线添加铁路删除铁路修改铁路修改两点间的费用 主要算法的基本思想 在读入读出中，对图的点与边进行构建，对铁路线所经过的点与铁路线的名称进行构建。 在找符合条件的所有路线时，采用递归。 在对所有符合条件的所有可能进行组合，并计算出时间、与费用，采用数组进

6、行存取。 对所有可能采用快速排序+插入排序，然后进行输出。2.2 设计表示 函数调用关系图 函数接口规格说明void ifile1(AdjLWGraph &g2) /将图进行读入，通过引用修改图。void GetEdgRoadline(const int v1,const int v2,SeqList &S_line)const; /将边间所有路线读出。读入引用数组S_line中。void InsertEdge(const int v1, const int v2, double Money); /在两个站点间插入边与权值。Railroadline(int num,string n); /将铁

7、路线的标号和铁路的名称进行初始化/查询两点间的所有线路(递归)void Circle1(int v0, int j, int k, SeqList m_vec, SeqList &m_total,Edg &w)/此函数传入所有边的信息、m_total用于存储所有符合条件的路线所经过的点。/查询两点间的所有线路的所有可能（装站or不转）和算时间和费用(递归)void Circle2(int vi,int vj,int i,int j,int v_end,SeqList &temp,SeqList &M_t,AdjLWGraph &G,SeqList &S_rrl)/此函数传入参数有：M_t所有符

8、合条件的路线、temp存放某条路线所经过点之间的线路、S_rrl存储对所有是否转站的可能进行存入。三、数据类型定义AdjLWGraph类AdjLWGraph类为图的邻接表，内含seqlist类的顶点Vertices私有数据成员，numOfEdges代表图中所含边数。Railroadline类Railroadline类为铁路线所含含的信息，number为铁路线编号、name为铁路线的名称、S_allv中存储的为铁路线所经过的站、S_rrl中存储火车到达每个站的时间、S_orrl中存储火车在该点的出发时间。2.3 详细设计 （6个主要功能） 构造数据类型AdjLWGraph类中：在对图进行构建的同

9、时，也要对每个站点与站点之间的联系进行构造；AdjLWGraph:AdjLWGraph(const int sz):Vertices(sz)numOfEdges = 0;Vertex(EdgeListNode * ptr =NULL):adjhead(ptr) Vertex(VT d,string n, EdgeListNode *ptr=NULL):b_name(d),name(n),number(G_number+),adjhead(ptr)Railroadline类中：在对铁路线进行构造对铁路线的编号、名字、通行标志进行赋值；railroadline:railroadline(int n

10、um, string n, string m) :number(num), name(n), mark(m) 文件读入铁路线读入 将铁路线的所属编号、名字、所经过的点、所经过的点的出发时间、到达时间进行读入While（文件未结束）读入铁路线的编号、名字While（a！=-1）将经过的点存储While（a！=-1）将经过的点的出发时间存储While（a！=-1）将经过的点的到达时间存储站台读入 将铁站台的名称、简称进行读入。 将站点与站点的距离进行读入。while (1)将站台的名称、编号、简称读入对图进行初始化（既将点添加入图中）将两点间的权值读入图中 增加站点输入站点名称与简称是否加入已有铁

11、路线YN输入需加入铁路线名称退出输入需插入的位置对该铁路线进行更新 删除站台Void Delete_city()输入要删除的城市for（所有线路）将铁路线中所含有该城市的点删除并修改该点后面站点的出发与到达时间；增加该城市在此条线路前后两个站点的权值；If（该城市位于此铁路线最后一个）If（该点与前一个站点只有一条铁路经过）删除边Else 删除该边储存的此条铁路线Else If（该城市位于此铁路线第一个）If（该点与后一个站点只有一条铁路经过）删除边Else 删除该边储存的此条铁路线ElseIf（该点与前一个站点只有一条铁路经过）删除边Else 删除该边储存的此条铁路线If（该点与后一个站点只

12、有一条铁路经过）删除边Else 删除该边储存的此条铁路线 两个站台之间的所有路线可能排序输入两个站台选择决策最快方式最省钱方式采用快速排序+插入排序进行排序采用递归将两个站台间所有路线找出采用递归将所有路线的可能进行组合存储并计算时间与费用（两点之间存在多条铁路线的情况）按升序将所有结果输出 排序功能void quickSort(Num (&r)100, int n, int k) qsort_improve(r,0,n,k);/先调用改进算法Qsort使之基本有序 长度大于k时递归, k为指定的数 并调用的Partition算法 Partition函数为将小于基准的数放基准数前，将大于基准的

13、数放基准数后 再用插入排序对基本有序序列排序 3调试分析 （1）调试过程中遇到的问题解决与分析； 开始最大的难点是如何将各点之间的信息进行建立。在对各铁路线增加时，通过不断调试和修改，将一些未考虑情况增加了一些判断和循环，从而使各站点之间的信息进行较好的建立。其次是对路线的查找，采用递归，通过不断地调试，将所有路线找出，在计算一条线路中所用到的时间时，由于使用过多的结构体，使得在写程序时过于复杂，为了解决这一问题，最终将所有点所包括的一些信息用有意义的英文字符表示，增加了程序的可读性，使得读写时更加通俗易懂。（2）算法的时间空间复杂度分析： 刚开始对费用和时间进行排序时使用的是冒泡排序，时间复

14、杂度为O(n2)使用效率并不高，后经过对比采用快速排序+插入排序，此排序既降低了时间复杂度，同时也避免了当原本序列为顺序时，时间复杂度降为冒泡排序。4用户手册 1) 在压缩包里含有测试数据.txt,将文本中的内容复制、粘贴到运行程序的控制台中，程序将会实现各个功能。2) Railroadline.txt文件中各数据的说明：3) Vertex.txt文件中各数据的说明：4) Edge.txt文件中各数据的说明：5测试数据及测试结果 1) 选择出行方式根据选择，系统对飞机或火车交通图进行构建2) 选择区间3) 添加城市4) 删除城市5) 增加列车6) 删除列车7) 修改列车8) 修改两点间的费用6

15、参考文献 数据结构（c+语言描述）（朱战力著）7总结 此次上机实验应用了图实现了全国交通咨询模拟系统，在此次编程中，我不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了图的重要性以及其应用的方便，并且对邻接表加深了印象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。 通过这次课程设计练习，使我更深刻地理解了图的使用。完成整个程序设计使我对图和邻接表的掌握的更加熟练，同时采用数组，对存储的内部更加了解。 同时通过计算最短用时和最少费用并对其采用快速排序+插入排序，使用递归实现一些的功能，加深了对数据结构的理解和认识。并在完成课程设计的过程主动查阅了相关资料，学到

16、了不少课本上没有的技术知识。 经过这次课程设计，我深刻认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。 编程是一件枯燥乏味工作，但是只要认真钻研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。8检查过后对程序的修改(07.25)在检查过程中，发现我对数据的排序写的不好，采用冒泡排序，大大增加了程序的时间和空间的复杂度，在经过对排序的对比，最后我采用了快速排序+插入排序。我采用的原因如下：快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。 在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低。