人机交互的北京公交线路查询系统结构设计.doc

人机交互的北京公交线路查询系统结构设计一、问题描述随着经济和科技的高速发展，城市的公共交通建设进程加快。北京作为一个国际化大都市，其公共交通网络已日趋完善。但随着一条条交通线路的开始运行，调整路线，或被其它路线取代而停用，城市复杂的公共交通网络有时也给市民出行造成了不小的困扰。一个用户从甲地到乙地，有多种交通方式及多种交通路线。而由于对速度，距离，交通方式，及费用等方面的不同需要，用户需要有多种满足不同需求的方案以备选择。常见的交通方式有公交车和地铁。本次专题就为人机交互的北京公交线路查询系统。用户只需输入起始站、终点站，系统即可为用户提供三种或以上决策的交通咨询。二、具体要求a. 提供对交通线路进行编辑功能。要求可添加或删除线路。b. 提供两种交通工具，公交车和地铁，设定路程所需要的时间、距离及费用等参数。c. 提供多种决策：最短距离、最快到达、最少费用、最少换乘次数等。d. 中途不考虑等候、拥堵等消耗时间。e. 该系统以人机对话方式进行。用户输入起始站、终点站及需求原则，系统输出乘车方案：乘什么车、乘几路车、距离、时间、费用换乘方法等相关信息。三、数据结构与算法分析1）可以以邻接表作交通图的存储结构，表示边的结构内除包含有邻接点的信息外，还应包括交通工具、路程时间和费用等多种属性。2） 使用图的基本算法：插入、删除、排序、深度优先级搜索和广度优先搜索等算法。四、算法设计与实现1、流程图由于算法较为明朗，这里只对其中较为复杂的部分通过全链表的线路结构建立邻接链表这一过程给出流程图。2、算法设计思路及特点1）迪克斯特拉（Dijkstra）算法按路径长度递增逐步产生最短路径2）线路结构在线路存储处理上，我们小组采用了链表结构进行存储线路：站点链结点结构 StationData 线路链结点结构 RouteData 3）图结构我们有四种搜索路径方式：最短距离、最短时间、最少换乘、最少花费。 a.用来搜索最短距离和最短时间的路径时是只考虑相邻的两个站点，所以在整个图结构中边数较小。为了节省空间资源，我们采用了邻接链表的方式来存储图。 b.用来搜索最少换乘与最少花费的路径时需要考虑到一个站点所有可能0换乘到达的站点，所以整个图结构中边数较多，所以采用了邻接矩阵的结构。3、程序代码（有备注，见附录）五、测试与结论1、采用VC进行编译调试（代码界面）2、主界面（用户体验界面）按照提示输入1.管理员 （管理权限系统权限，增加、删除、查询路线站点） 2.普通用户（查询路线站点）3、管理员权限测试1）登录需输入正确密码2）管理员功能选择界面 3）管理员增加路线界面 通过输入站点、时间间隔和距离间隔新建一条9号地铁线，保存。此时，显示全部线路的界面中新建的线路subway9已存在。4）管理员删除线路界面通过输入线路的名称，确定是否删除此线路。4、用户权限测试1） 用户功能选择界面2） 查询站点测试 输入要查询的站点 ，系统会显示出经过此站点的全部路线。如此用例中，输入“西直门”，西直门为换乘站，系统给出了经过此站的2条线路的详细情况。3） 用户搜索路线（最核心的功能） 首先先展示我们测试使用的路径图片。首先是最短距离的测试。最少时间的测试。最少换乘最短距离模式。最少换乘最短时间模式。最少花费最短距离模式。最少花费最短时间模式。 4）、输入两个报错用例a.以管理员身份登录以管理员身份登录系统时需要输入密码，若输入错误，则系统提示“密码错误，返回主界面”。b.用户查询报错用户站点查询时，输入站点名错误，系统提示“无此站点，重新输入。”六、小组分工邵青：编写了最短时间、最短距离部分的搜索函数 杨梓艺：编写了建立邻接链表部分的函数 赵欣：编写了最少换乘、最少花费部分的搜索函数 李哲：负责编写了建立邻接矩阵的函数，并编写了路线链表与该部分相关的函数 彭少龙：编写了路线链表的全部函数 宁立跃：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用， 张俭伟：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用 七、总结与思考通过大家的共同努力，完成了最后一次的专题程序设计。小组的各位成员都在本次设计中学习到了很多。1） 专业方面。我们对图和链表的结构从书面了解，逐步熟悉到能够掌握结构用法并运用到本次的图专题程序设计中。小组成员的基于C+编程的能力又得到了进一步的提升。2） 本次专题的主题为“北京公交查询系统”。题目与生活联系非常紧密，这就要求我们的程序设计一定要理论与实践相结合，同时考虑到交通网络中各种复杂的重叠，交叉及往返等情况，统筹兼顾。让小组成员都学会把专业中的编程更深入有效地运用到实际生活中去。3） 完成专题设计中组内合作是非常重要的。组内成员不断的进行思考与沟通，完善分工，提升了协作能力。附录：#include #include #include using namespace std;#define MAX 200#define Infinity 65535#define PASSWORD 123string password();/*存储格式*线路名 线路类型 线路费用站名1 距下一站时间 距下一站距离 站名2 。#（表示该线路结束）*/*线路链表部分*/class StationDatapublic: string sn; /站点名 int distance,time,number;/距下一站的距离和时间 StationData *next; StationData *former; StationData() distance = time = number = 0; next = former = NULL; ;class RouteDatapublic: string rn; /公交路线名 int type; /类型 float fee; /费用 StationData *link; RouteData *next; RouteData() link = NULL; next = NULL; ;class Routepublic: RouteData *head; int num; Route() head = NULL; num = 0; void Creat(); RouteData * Find(string s); void Add(); void Dele(); void Save(); void ShowOneRoute(RouteData * p); void Showall(); RouteData * FindRoute(string one,string two); double MinWay(string one,string two,int way); double MinWayMoney(string one,string two,int way); RouteData * MinWayReturnRouteData(string one,string two,int way); int TwoStationDistantAndShowRoute(RouteData *point,string one,string two,int &t); void CheckRoute(); void CheckStation();void Route:CheckRoute() string rr;point2: cout 请输入您需要查询的线路名，然后将会显示该线路的相关信息。n; cout rr; cout rn = rr) tf = 1; ShowOneRoute(p); break; p = p-next; if(tf = 0) cout 没有找到该线路！请重新输入n; system(pause); goto point2; cout endl; system(pause);void Route:CheckStation() string ss;point3: cout 请输入您需要查询的站点名，然后将会显示通过该站点的所有线路的相关信息。n; cout ss; cout link; while(q!=NULL) if(q-sn = ss) tf = 1; ShowOneRoute(p); cout next; p = p-next; if(tf = 0) cout link; while(p-next != NULL & p-sn != one & p-sn != two) p = p-next; if(p-next = NULL) min0 = Infinity; else if(p-sn = one) while(p-sn != two&p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != two) min0 = Infinity; if(min min0) min = min0;m = f; else if(p-sn = two) while(p-sn != one & p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != one) min0 = Infinity; if(min min0) min = min0;m = f; f = f-next; double d; if(min = Infinity) d = (double)min; else d = m-fee + (float)min)/1000; return d;int Route:TwoStationDistantAndShowRoute(RouteData *point,string one,string two,int &t) RouteData *n = point; int distant = 0; StationData *p = n-link; StationData *start; int tf = 0; while(p != NULL) if(p-sn = one) start = p;break; p = p-next; p = start; while(p!=NULL) if(p-sn = two) tf = 1;break; p = p-next; p = start; while(p != NULL) if(p-sn = two) tf = 2;break; p = p-former; if(tf = 1) p = start; distant = distant + p-distance; t = t + p-time; p = p-next; while(p-sn != two) cout 经 sn distance; t = t + p-time; p = p-next; else if(tf = 2) p = start; distant = distant + p-former-distance; t = t + p-former-time; p = p-former; while(p-sn != two) cout 经 sn former-distance; t = t + p-former-time; p = p-former; return distant;double Route:MinWay(string one,string two,int way) RouteData * f = head; RouteData * m = NULL; int min,min0,mark; min = Infinity; while(f != NULL) min0 = 0; StationData * p = f-link; while(p-next != NULL & p-sn != one & p-sn != two) p = p-next; if(p-next = NULL) min0 = Infinity; else if(p-sn = one) while(p-sn != two&p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != two) min0 = Infinity; if(min min0) min = min0;m = f; else if(p-sn = two) while(p-sn != one & p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != one) min0 = Infinity; if(min min0) min = min0;m = f; f = f-next; double d; if(min = Infinity) d = (double)min; else d = 1 + (float)min)/1000; return d;RouteData * Route:MinWayReturnRouteData(string one,string two,int way) RouteData * f = head; RouteData * m = NULL; int min,min0,mark; min = Infinity; while(f != NULL) min0 = 0; StationData * p = f-link; while(p-next != NULL & p-sn != one & p-sn != two) p = p-next; if(p-next = NULL) min0 = Infinity; else if(p-sn = one) while(p-sn != two&p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != two) min0 = Infinity; if(min min0) min = min0;m = f; else if(p-sn = two) while(p-sn != one & p-next!=NULL) if(way = 1) mark = p-distance; else if(way = 2) mark = p-time; min0 = min0 + mark; p = p-next; if(p-sn != one) min0 = Infinity; if(min min0) min = min0;m = f; f = f-next; return m;RouteData * Route:FindRoute(string one,string two) RouteData * f = head; while(f != NULL) StationData * p = f-link; while(p-next != NULL) if(p-sn = one & p-next-sn = two) return f; else if(p-sn = two & p-next-sn = one) return f; p = p-next; f = f-next; RouteData * Route:Find(string s) RouteData * n = head; while(n != NULL) if(n-rn = s) return n; n = n-next; return n;void Route:Dele() Showall(); string s; RouteData * n; point3: cout s; n = Find(s); if(n = NULL) point4: cout i; if(i = 1) goto point3; else if(i = 2); else goto point4; else ShowOneRoute(n); point5: cout ch; if(ch = Y | ch = y) RouteData * p = head; while(p-next != n) p = p-next; p-next = n-next; Save(); else if(ch = N | ch = n); else goto point5; void Route:Showall() RouteData * n = head; while(n != NULL) ShowOneRoute(n); cout next; void Route:ShowOneRoute(RouteData * p) if(p-type = 0) cout 地铁; else cout 公交; cout rn link; while(n != NULL) if(n-next != NULL) cout sn - ( time min, distance km)-; else cout sn; n = n-next; cout ssss; while(ssss != end) num+; RouteData * n = new RouteData; StationData * w = n-link; n-rn = ssss; f n-type n-fee; if(head = NULL) head = n;p = head; else p-next = n; p = n; string s; f s; while(s != #) StationData * pp = new StationData; pp-sn = s; f pp-time pp-distance; if(n-link = NULL) n-link = pp;w = n-link;pp-former = NULL; else w-next = pp; pp-former = w; w = pp; f s; f ssss; void Route:Add() RouteData *nr = new RouteData; cout 您将要建立一条新的公交线路。请按照指示输入新路线！n; cout nr-rn; point1: cout nr-type; if(nr-type = 0) cout fee = 2; else if(nr-type = 1) cout nr-fee; else cout link; cout 下面请依照提示，按顺序输入站点信息。n; cout s; while(s != #) StationData * pp = new StationData; pp-sn = s; cout pp-time; cout pp-distance; if(nr-link = NULL) nr-link = pp;w = nr-link; else w-next = pp; w = pp; cout s; ShowOneRoute(nr); point2: cout ch; if(ch = Y | ch = y) RouteData * k = head; if(head = NULL) head = nr;k = nr; else while(k-next != NULL) k = k-next; k-next = nr; num+; else if(ch = N | ch = y); else goto point2;void Route:Save() fstream f(.data.txt,ios:out); if(!f) return; RouteData * r = head; while(r != NULL) StationData * s = r-link; f rn type fee n; while(s != NULL) f sn time distance next; f next; f end; f.close();/*图部分*/class lineroutepublic: string sn; RouteData *r; lineroute *next; lineroute() r = NULL; next = NULL; ;class Linepublic: string sn; string rn; int type; float fee; Line *next; Line() next = NULL; ;/边尾节点信息结构体struct edgeNode int no; /尾接点序号 int dtime,dlong; /边权值 RouteData *r; edgeNode *next; /其下一条邻接边尾节点指针;/节点信息结构体struct vexNode string sn; /节点名称 edgeNode *link; /与其相连的边的尾节点链表指针;struct Queue int no; /队列中节点序号 int cost; /以此为尾节点的边的权值;class Graphpublic: /优先队列 Queue priQueMAX; /节点数组 vexNode adjlistMAX; /指定源点到节点i的最短路径花费 int lowcostMAX; /指定源点到节点i路径中，节点i的前驱节点序号 int parentMAX; int vexNumber; Line *s; void CreatGraph(Route &R); void keep_min_heap(int &num,const int k); void heap_insert(int &num,int no,int cost); Queue heap_extract_min(int &num); void print_it(Route &R,int v); void DijkstraDistance(Route &R,string start,string end); void DijkstraTime(Route &R,string start,string end); int FindNumber(string sn); void CreatLine(int v); void MinMoney(Route &R,string start,string end,int way); void MinChange(Route &R,string start,string end,int way);/*最大值：Infinity*/void Graph:MinMoney(Route &R,string start,string end,int way) int v0,v1,n,w; n = vexNumber; v0 = FindNumber(start); v1 = FindNumber(end); double shortestMAX; double EDGEnn; int finalMAX=0; int pathMAXMAX=0; /*建立邻接矩阵*/ int i,j; for(i = 0;i n;i+) for(j = 0;j n;j+) if(i = j) EDGEij = Infinity; continue; string one = adjlisti.sn; string two = adjlistj.sn; EDGEij = R.MinWayMoney(one,two,way); /*初始化数组*/ int order = 1; int step = 1; int min_i; double min_shortest; for(i = 0;i n;i+) shortesti = EDGEv0i; for(j = 0;j n;j+) pathij = 0; if(EDGEv0iInfinity-1) pathiv0 = step; shortestv0 = 0; finalv0 = order; pathv0v0 = step; /*算法部分*/ for(i = 1;i n;i+) min_shortest = Infinity; for(j = 0;j n;j+) if(!finalj & shortestj min_shortest) min_i = j; min_shortest =