数据结构课程设计说明书--公交乘车

1《数据结构与算法设计》课程设计任务书题目公交咨询程序学生姓名孙宝琳学号0124专业班级数学0701设计内容与要求【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1．从文件中接收图和公交车信息；2．可实现确定公交线路查询，即输出该车的所有站点；3．可以对某一个站点进行查询输出该站点的所有下一站；4．可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站）、图类（站点名，公交车类，现有路线条数，现有站点数）、Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询——在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线，并有最短路径的最后一个站点将路径上的所有站点入栈，出站时判断是否换车并输出方案；【提交成果】1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋；2.“《数据结构与算法设计》课程设计报告”一份，打印装袋；3、上面两项内容的word文档，通过电子邮件交到指导教师。起止时间2009年6月8日至2009年6月19日指导教师签名年月日系（教研室）主任签名年月日学生签名孙宝琳2009年6月18日数据结构与算法设计课程设计2专业数学与应用数学班级数学0701学号0124姓名孙宝琳完成日期6.18指导教师（签名）1、程序设计说明书【设计题目】公交咨询程序【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1从文件中接收图和公交车信息；2可实现确定公交线路查询，即输出该车的所有站点；3可以对某一个站点进行查询输出该站点的所有下一站；4可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站），图类（站点名，公交车类，现有路线条数，现有站点数），Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询——在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线并有最短路径的最后一个站点输出乘车方案；【类的设计】structBus//公交车类{intnumber;//公交车号intlength;//总站数charbus_state[Maxstate][20];//站点};classGraph//建立无向图{friendclassDistance;//声明友元类private:charstatename[Maxstate][20];//站点intbusnumber[Maxstate][Maxstate];//邻接矩阵，权值为这两个站点的公交车号intcurrentstate;//当前站点数intcurrentbus;//当前公交车数Busbuses[Maxbus];//公交车信息public:Graph()；//无参构造函数，对成员变量初始化voidInsertstate(charstate[])；//插入一个站点voidInsertbusnumber(charV1[],charV2[],intbusnum)；//插入权值voidSet_graph()；//图的建立boolIsGraphFull()；//判断图是否已满voidshow_busmessage(intnumber)；//输出公交信息intsearchbusnumber(charv0[],charv1[])；//查找指定站点的公交车号码3voiddirection(charv0[],charv1[])；//输出指定站点的公交车方向friendvoidbusline();//把外部函数定义为图的友元函数，以便使用图的私有成员变量friendvoidsearchstate();friendvoidbestproject();friendvoidmainsurface();};classStackNode//栈结点{friendclassStack;//友元类private:chardate[20];//结点数据StackNode*link;//结点链指针public://构造函数：结点赋值StackNode(chard[]=0,StackNode*l=NULL)；};classStack//定义栈{private:StackNode*top;//栈顶指针public:Stack():top(NULL){}//构造函数~Stack();//析构voidPush(charitem[]);//进栈intPop(charx[]);//退栈intGetTop(charx[]);//读取栈顶元素voidMakeEmpty();//把栈置空intIsEmpty();};classDistance:publicGraph//定义最短距离类{private:charpath[20];//最短距离的前一站intdistance[Maxstate];//最短距离public:voidbestchooce(charv0[],charv1[])；//最优方案}；【存储结构设计】使用邻接矩阵intbusnumber[Maxstate][Maxstate];存储图的信息；公交车信息采用结构体数组Busbuses[Maxbus];存储；4栈使用链表来实现；【模块划分及调用关系】共有三个模块：公交线路查询Busline()、站点查询Searchstate()、最优方案Bestproject()【模块流程图】1.Busline():存存在2searchstate():Main（）Mainsurface()Busline()Searchstate()Bestproject()退出Set_graph()特定车号的路线查询所有路线浏览Mainsurface()接收车号输出公交车信息show_busmessage()存在否Set_graph()接收站点在图内查找站点名所到的车及方向Mainsurface()有循环输出当前车53bestproject():【界面设计】采用简单的人机会话，使操作简单明了；【用户手册】在程序所在文件夹下建立“公交查询.txt”，并输入以下内容：30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）；编译运行程序，根据提示执行程序；要想有更为准确的方案，可以在“公交查询.txt”中加入公交车线路；2、程序上机调试报告【语法错误及其排除】1函数赋值时，将变量赋给了指针；使用指针传值；2在出栈时没有判断栈是否为空，导致top指空在出栈前判断IsEmpty（）；无路径有路径栈为是车相同接收起始站Bestchooce()Set_graph()Dijkstra算法Mainsurface()对路径上的站入栈出栈判断是否是换车输出换车信息输出路径Mainsurface()6【算法错误及其排除】1在建立图中没有对a数组进行置空，导致数据混乱；在使用a之前对a数组赋空；2在输出最优结果时没有保留前一站使程序无法判断是否换车加入b数组保留前一站；3、程序测试结果【测试数据】30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）；【输出结果】1公交线路查询：2站点查询：73最优方案：【程序性能评价】使用简单；结果正确、明了；【性能改进方向】1.将邻接矩阵改为三维，即在相同两站间由多个公交可以到达；2.在站点里加入方位，即在寻找最优结果的时候可以不必将所有站点进行操作，加快运行速度；3.在公交车类中加入收费，在最优结果输出时计算收费(有刷卡、投币、按站收费)；【收获及体会】通过这个程序的编写使我对c++中文件的操作、图的操作、栈的操作、查找等内容有了更深的理解，在编译的过程中也是我知道了自己的数据结构课程内容还很浅，还需要在努力；4、源程序代码#includefstream.h//文件库#includestdlib.h#includestring.h//字符串函数库constintMaxbus=100;//最大公交车数8constintMaxstate=200;//最大站点数constintMaxValue=999;//最大值structBus//公交车类{intnumber;//公交车号intlength;//总站数charbus_state[Maxstate][20];//站点};classGraph//建立无向图{friendclassDistance;//声明友元类private:charstatename[Maxstate][20];//站点intbusnumber[Maxstate][Maxstate];//邻接矩阵，权值为这两个站点的公交车号intcurrentstate;//当前站点数intcurrentbus;//当前公交车数Busbuses[Maxbus];//公交车信息public:Graph()//无参构造函数，对成员变量初始化{for(inti=0;iMaxstate;i++)for(intj=0;jMaxstate;j++){if(i==j)busnumber[i][j]=-1;//自己到自己没有车elsebusnumber[i][j]=MaxValue;}currentstate=0;currentbus=0;for(i=0;iMaxbus;i++){buses[i].number=-1;buses[i].length=0;}}voidInsertstate(charstate[])//插入一个站点{if(!IsGraphFull())//如果图没满{for(inti=0;icurrentstate;i++)//查看该站是否已经存在if(strcmp(state,statename[i])==0)break;if(i==currentstate)//如果不存在，在站点数组后加入9{strcpy(statename[currentstate],state);for(i=0;icurrentstate;i++){busnumber[currentstate][i]=MaxValue;busnumber[i][currentstate]=MaxValue;}busnumber[currentstate][currentstate]=-1;currentstate++;//当前数组加一}}}voidInsertbusnumber(charV1[],charV2[],intbusnum)//插入权值{for(inti=0;icurrentstate;i++)//查找站点if(strcmp(V1,statename[i])==0)break;for(intj=0;jcurrentstate;j++)if(strcmp(V2,statename[j])==0)break;if(i!=currentstate&&j!=currentstate)//站点存在插入权值{busnumber[i][j]=busnum;bus