数据结构课程设计报告-全国交通咨询模拟.doc

计算机科学与技术学院数据结构课程设计指导教师二一八年一月十七日课程设计任务书及成绩评定课程设计题目全国交通咨询模拟课程设计的目的和内容设计目的：通过数据结构课程设计的训练，达到以下目的：(1)巩固和加深对数据结构知识的理解，熟练掌握几种重要的数据结构与算法，能够根据具体问题选择合适的数据结构并设计相应算法；(2)初步掌握软件开发过程的需求分析、系统设计、程序测试和编码风格等基本流程和规范；(3)提高综合运用所学的数据结构和算法知识独立分析和解决复杂工程问题的能力；(4)培养学生从事计算机相关专业工作所应具备的科学方法和基本素质。设计内容：(根据具体题目简要阐述系统的总体任务、所需实现的功能、相应的子任务和模块分解、数据结构的选择和算法的设计、数据库的设计和存储、系统的重点测试内容等。本部分表格不得超出本页范围，文档格式不得擅自改变。) 从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。程序所能达到的功能 a.该系统有供用户选择的菜单和交互性。可以对城市、列车车次和飞机航班进行编辑，添加或删除。 b.建立一个全国交通咨询系统，该系统具备自动查找任意两城市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。 c.初始化交通系统有两种方式，键盘和文档。 数据存储:城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面。 最优决策功能模块(fast or province)。课程设计的创新和特色(简要列举本设计的创新点和特色，比如应用了何种数据结构或算法使得排序或查找更为高效；使用了何种数据库设计使得数据存储和检索更为高效；区别于其他项目组的特色或亮点等等。)在设计程序中，用邻接表作交通图的存储结构，表示边的结点中除含有邻接点的信息外，还包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等属性。图中顶点城市的信息，包括城市名称、城市编号和依附该顶点的边的指针。利用迪杰斯特拉算法求花钱最少和花时间最少的交通方式。用BFS算法求从出发城市到终点城市所经最少中转站路径。用QT实现系统的可视化，系统不再是呈现在黑黑的控制台，增添了登陆界面，各种选项按钮，信息全部以表格的形式输出，用户更可直接在表格中进行信息的增添修改，实现人机了界面。之所以使用它，主要有这么几个原因：上手快，入门成本低；跨平台。一处编写，处处编译运行，比如我们在windows下写了一个小软件，比如记事本，那么我们完全可以拷贝源码到linux、mac下进行对应的编译，这样编译出来的软件可以同时运行在各个平台上。信号和槽可以说是Qt的一大亮点，使用其原对象系统扩充了我们的对象之间交互的方式，真的很棒。设计进度及完成情况日 期内 容2018/1/8-1/9需求分析，模块设计2018/1/10-1/12制作登录和系统主界面，实现用户管理模块的增，改，查功能。2018/1/13-1/14实现文件的读写，用QT实现系统的可视化2018/1/14优化系统界面，测试数据，撰写实训报告主要参考文献(参考文献的格式请严格遵守要求。本页表格打印不得超出本页范围。)1 严蔚敏,吴伟民.数据结构（C语言版）.北京:清华大学出版,1997.成绩评定团队成绩 评语： 指导老师： (签字) 年 月 日 目 录第1章 概述1第2章 系统分析2第3章 概要设计5第4章 详细设计10第5章 测试与运行23第6章 总结与心得28参考文献 29第1章 概述旅客对由于出行目的的不同对交通工具的要求也有不同。例如，因公事出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。为了能满足广大旅客的需求，方便旅客出行，就此编制一个全国城市间的交通咨询程序，为旅客提供两种或者三种最优决策的交通咨询。通过此次程序可以对全国城市之间火车与飞机进行两方面的咨询，即最少的时间与最少的费用的咨询，从而方便旅客的出行。以邻接表作交通图的存储结构表示边的结点内除含有邻接点的信息外包括交通工具、路程中消耗的时间，花费和中转站次数以及出发和到达的时间等多项属性。根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，用BFS算法求从出发城市到终点城市所经最少中转站路径。搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。输出结果，从目的城市出发，搜索到出发城市，所经过的城市均入栈(队列)，再逐一出栈栈(队列)中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长。用QT实现系统的可视化，增添了登陆界面，各种选项按钮，信息全部以表格的形式输出，用户更可直接在表格中进行信息的增添修改，实现人机界面。第2章 系统分析2.1系统需求从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。2.2课题实现在对全国重要交通枢纽城市及交通工具信息充分调查了解后，依据对交通信息数据流动特点的分析，现在可以进行系统的功能分析，根据软件工程的原理，需求分析的任务是确定系统必须完成的工作。经过详细的调研分析之后，可以得出全国交通咨询模拟系统必须具备的功能分为 8个模块：2.2.1用户登录 -全国交通咨询模拟系统！- * 1、填写帐号 * 2、填写密码 * 3、登录 * 4、退出 * *请输入您的选择：图2.2.1 登录界面设计图2.2.2添加城市 -城市信息添加- * 1、文件添加 * 2、手动添加 * 3、保存 * 4、退出 * *请输入您的选择：图2.2.2 添加城市设计图2.2.3显示全部信息-显示全部信息- * 1、显示全部信息 * 2、每次添加或更改后刷新 * * 3、退出 * *图2.2.3 登录界面设计图 2.2.4修改列车 -列车班次信息修改- * 1、输入列车班次 * 2、查询此列车 * 3、修改列车信息：班次，起始时 * 间，费用 * 4、退出 * *请输入您的选择：图2.2.4 列车信息修改设计图2.2.5修改航班-航班信息修改- * 1、输入飞机航班 * 2、查询此航班 * 3、修改航班信息：航班，起始时 * 间，费用 * 4、退出 * *请输入您的选择：图2.2.5 航班信息修改设计图2.2.6计算最少中转站路线并打印-计算最少中转站路径- * * 1、出发城市，到达城市 * 2、BFS算法求出最少中转站路经 * * 3、打印最少中转站路径 * *图2.2.6 计算最少中转站路线设计图2.2.7计算最快路线并打印 -计算最快路线- * 1、出发城市，到达城市 * 2、Dijkstra算法求出最短时间 * 路径 * * 3、打印最快路线及花费时间 * *请输入您的选择：图2.2.7 计算最快路线设计图2.2.8计算最少花费路线并打印 -计算最少花费路线- * 1、出发城市，到达城市 * 2、Dijkstra算法求出最少花费 * 路径 * * 3、打印最少花费路线及费用 * *请输入您的选择：图2.2.8 计算最少花费路线设计图第3章 概要设计3.1 主程序图3.1 主程序3.2 城市信息添加图3.2 添加城市信息3.3 用户咨询系统图3.3 用户咨询系统3.4 修改列车班次图3.4 修改列车车次3.5 修改飞机航班图3.5修改航班班次第4章 详细设计根据上面的流程图和逻辑拆分对这个问题有了一个比较直观详细地了解。并且从中也可得知路线的添加即数据的存储是这个系统进行运作的一个基础。而为了便于数据的存储、添加、修改等操作，我们选择了储存文件对这些数据进行了存储。将每个信息量放在不同的文件中可以更有效、直观地对这些数据进行处理。4.1登录系统void login:doProcesslogin(bool) if(ui-lineEdit_zhanghao-text()=|ui-lineEdit_pwd-text()=) QMessageBox:warning(this,tr(提示), tr(账号或密码未填写！), QMessageBox:Yes); else if(ui-lineEdit_zhanghao-text()=yanghounan|ui-lineEdit_zhanghao-text()=fushengming|ui-lineEdit_zhanghao-text()=zhuhongbin|ui-lineEdit_zhanghao-text()=yangshuo)&ui-lineEdit_pwd-text()=123456) this-hide(); mainf = new mainform(); QMessageBox:warning(this,tr(提示), tr(登录成功！), QMessageBox:Yes); mainf-show(); else QMessageBox:warning(this,tr(提示), tr(账号或密码错误！), QMessageBox:Yes); ui-lineEdit_zhanghao-clear(); ui-lineEdit_pwd-clear(); 4.2主函数#include mainform.h#include #includeaddform.h#include#include#include login.husing namespace std;struct trainmap int time12,money,time22,time2; int truetime; string times;struct planemap int time12,money,time22,time2; int truetime1; string times;struct city string name; int id;struct trainmap a3131;struct planemap b3131;struct city c31;int i=1;int main(int argc, char *argv) QApplication a(argc, argv); login w; /运行程序显示登录页面 w.show(); return a.exec();4.3邻接矩阵tranmap转换为邻接表Gint user:exchange()/邻接矩阵tranmap转换为邻接表G int num=0;/记录边数 int j,k,n=i;/n为节点数+1 ArcNode *p; g=(ALGraph *)malloc(sizeof(ALGraph); for(j=0; jadjlistj.firstarc=NULL; for(j=0; j=0; k-) if(ajk.money!=0&ajk.truetime!=0) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=k; p-trainmoney=ajk.money; p-traintime=ajk.truetime; num+; p-nextarc=g-adjlistj.firstarc; g-adjlistj.firstarc=p; g-n=n; g-e=i; return num;4.4 planemap转换为邻接表Gint user:exchangep()/planemap转换为邻接表G int num=0; int j,k,n=i; ArcNode *p; g=(ALGraph *)malloc(sizeof(ALGraph); for(j=0; jadjlistj.firstarc=NULL; for(j=0; j=0; k-) if(bjk.money!=0&bjk.truetime1!=0) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=k; p-planemoney=bjk.money; p-planetime=bjk.truetime1; num+; p-nextarc=g-adjlistj.firstarc; g-adjlistj.firstarc=p; g-n=n; g-e=i; return num;4.5 列车车次花费最少路径函数(Dijkstra算法)void user:Dijkstra1()/列车车次花费最少路径函数 /初始化 for(int j = 1; j adjlistu.firstarc; while(p) int tempv = p-adjvex;/当前节点编号 int tempw = p-trainmoney;/当前节点花费 if(!visitedtempv & disttempv.w distu.w+tempw)/判断最少花费路径 disttempv.w = distu.w+tempw; pathtempv = u;/更新当前节点的父亲节点 q.push(disttempv); p = p-nextarc; int j=ve,h31,k=1,l; /输出列车车次花费最少路径 h0=ve; while(pathj!=v0) hk+=pathj; j=pathj; hk=v0; QString lu; for(l=k;l0;l-) lu.append(.c_str().append(-); lu.append(.c_str(); ui-lu-setText(lu);4.6 列车班次用时最少路径函数(Dijkstra算法)void user:Dijkstra2()/列车班次用时最少路径函数 /初始化 for(int j = 1; j adjlistu.firstarc; while(p) int tempv = p-adjvex; int tempw = p-traintime; if(!visitedtempv & disttempv.w distu.w+tempw) disttempv.w = distu.w+tempw; pathtempv = u; q.push(disttempv); p = p-nextarc; int j=ve,h31,k=1,l; /列车车次用时最少路径 h0=ve; while(pathj!=v0) hk+=pathj; j=pathj; hk=v0; QString lu; for(l=k;l0;l-) lu.append(.c_str().append(-); lu.append(.c_str(); ui-lu-setText(lu);4.7 航班班次用时最少路径函数(Dijkstra算法)void user:Dijkstra4()/航班班次用时最少路径函数 /初始化 for(int j = 1; j adjlistu.firstarc; while(p) int tempv = p-adjvex; int tempw = p-planetime; if(!visitedtempv & disttempv.w distu.w+tempw) disttempv.w = distu.w+tempw; pathtempv = u; q.push(disttempv); p = p-nextarc; int j=ve,h31,k=1,l;/航班班次用时最少路径 h0=ve; while(pathj!=v0) hk+=pathj; j=pathj; hk=v0; QString lu; for(l=k;l0;l-) lu.append(.c_str().append(-); lu.append(.c_str(); ui-lu-setText(lu);4.8 列车最少花费咨询(Dijkstra算法)void user:doProcessspend1(bool) if(ui-start1-text()=|ui-end1-text()=) QMessageBox:warning(this,tr(错误), tr(请检查您的填写！), QMessageBox:Yes); else int x=exchange(); /顶点，边 m=x; n=i-1; int l=0,l1=0; for(int o=1; ostart1-text().toStdString() v0=o; l=1; break; for(int o=1; oend1-text().toStdString() ve=o; l1=1; break; if(l&l1) Dijkstra1(); if(distve.w != INF&ve!=v0) QString s; s.append(从).append(.c_str().append(乘列车到).append(.c_str().append(最少花费为：).append(QString:number(distve.w).append(RMB); ui-out-setText(s); else QMessageBox:warning(this,tr(提示), tr(没有该路径！), QMessageBox:Yes); else QMessageBox:warning(this,tr(提示), tr(未找到你输入的城市！), QMessageBox:Yes); 4.9 列车用时最少路径查询(Dijkstra算法)void user:doProcesstime1(bool) if(ui-start1-text()=|ui-end1-text()=) QMessageBox:warning(this,tr(错误), tr(请检查您的填写！), QMessageBox:Yes); else int x=exchange(); /顶点，边 m=x; n=i-1; int l=0,l1=0; for(int o=1; ostart1-text().toStdString() v0=o; l=1; break; for(int o=1; oend1-text().toStdString() ve=o; l1=1; break; if(l&l1) Dijkstra2(); if(distve.w != INF&ve!=v0) QString s; s.append(不包含中间下车等待时间！)从).append(.c_str().append(乘列车到).append(.c_str().append(最少用时为：).append(QString:number(distve.w/60).append(小时).append(QString:number(distve.w%60).append(分钟); ui-out-setText(s); else QMessageBox:warning(this,tr(提示), tr(没有该路径！), QMessageBox:Yes); else QMessageBox:warning(this,tr(提示), tr(未找到你输入的城市！), QMessageBox:Yes); 4.10查找列车最少中转次数（BFS算法）void user:doProcesscity1(bool) /查找列车最少中转次数 if(ui-start1-text()=|ui-end1-text()=) QMessageBox:warning(this,tr(错误), tr(请检查您的填写！), QMessageBox:Yes); else int kk; int jj; int x=exchange();/邻接矩阵转换为邻接表 int l=0,l1=0; for(jj=1; jjstart1-text().toStdString() v0=jj; l=1; break; for(kk=1; kkend1-text().toStdString() ve=kk; l1=1; break; if(l&l1) int e=BFS(); QString s; s.append(从).append(.c_str().append(到).append(.c_str().append(坐列车最少中转次数为).append(QString:number(e).append(次！); ui-out-setText(s); else QMessageBox:warning(this,tr(提示), tr(未找到输入的城市！), QMessageBox:Yes); 4.11查找航班最少中转次数（BFS算法）void user:doProcesscity2(bool) /查找航班最少中转