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

数据结构与算法设计课程设计任务书题目公交咨询程序学生姓名孙宝琳学号200701030124专业班级数学0701设计内容与要求【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1从文件中接收图和公交车信息；2可实现确定公交线路查询，即输出该车的所有站点；3可以对某一个站点进行查询输出该站点的所有下一站；4可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站）、图类（站点名，公交车类，现有路线条数，现有站点数）、DIJKSTRA算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用DIJKSTRA算法算出最优路线，并有最短路径的最后一个站点将路径上的所有站点入栈，出站时判断是否换车并输出方案；【提交成果】1“数据结构与算法设计课程设计任务书”一份，打印装袋；2“数据结构与算法设计课程设计报告”一份，打印装袋；3、上面两项内容的WORD文档，通过电子邮件交到指导教师。起止时间2009年6月8日至2009年6月19日指导教师签名年月日系（教研室）主任签名年月日学生签名孙宝琳2009年6月18日数据结构与算法设计课程设计专业数学与应用数学班级数学0701学号200701030124姓名孙宝琳完成日期618指导教师（签名）1、程序设计说明书【设计题目】公交咨询程序【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1从文件中接收图和公交车信息；2可实现确定公交线路查询，即输出该车的所有站点；3可以对某一个站点进行查询输出该站点的所有下一站；4可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站），图类（站点名，公交车类，现有路线条数，现有站点数），DIJKSTRA算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用DIJKSTRA算法算出最优路线并有最短路径的最后一个站点输出乘车方案；【类的设计】STRUCTBUS/公交车类INTNUMBER/公交车号INTLENGTH/总站数CHARBUS_STATEMAXSTATE20/站点CLASSGRAPH/建立无向图FRIENDCLASSDISTANCE/声明友元类PRIVATECHARSTATENAMEMAXSTATE20/站点INTBUSNUMBERMAXSTATEMAXSTATE/邻接矩阵，权值为这两个站点的公交车号INTCURRENTSTATE/当前站点数INTCURRENTBUS/当前公交车数BUSBUSESMAXBUS/公交车信息PUBLICGRAPH；/无参构造函数，对成员变量初始化VOIDINSERTSTATECHARSTATE；/插入一个站点VOIDINSERTBUSNUMBERCHARV1,CHARV2,INTBUSNUM；/插入权值VOIDSET_GRAPH；/图的建立BOOLISGRAPHFULL；/判断图是否已满VOIDSHOW_BUSMESSAGEINTNUMBER；/输出公交信息INTSEARCHBUSNUMBERCHARV0,CHARV1；/查找指定站点的公交车号码VOIDDIRECTIONCHARV0,CHARV1；/输出指定站点的公交车方向FRIENDVOIDBUSLINE/把外部函数定义为图的友元函数，以便使用图的私有成员变量FRIENDVOIDSEARCHSTATEFRIENDVOIDBESTPROJECTFRIENDVOIDMAINSURFACECLASSSTACKNODE/栈结点FRIENDCLASSSTACK/友元类PRIVATECHARDATE20/结点数据STACKNODELINK/结点链指针PUBLIC/构造函数结点赋值STACKNODECHARD0,STACKNODELNULL；CLASSSTACK/定义栈PRIVATESTACKNODETOP/栈顶指针PUBLICSTACKTOPNULL/构造函数STACK/析构VOIDPUSHCHARITEM/进栈INTPOPCHARX/退栈INTGETTOPCHARX/读取栈顶元素VOIDMAKEEMPTY/把栈置空INTISEMPTYCLASSDISTANCEPUBLICGRAPH/定义最短距离类PRIVATECHARPATH20/最短距离的前一站INTDISTANCEMAXSTATE/最短距离PUBLICVOIDBESTCHOOCECHARV0,CHARV1；/最优方案；【存储结构设计】使用邻接矩阵INTBUSNUMBERMAXSTATEMAXSTATE存储图的信息；公交车信息采用结构体数组BUSBUSESMAXBUS存储；栈使用链表来实现；【模块划分及调用关系】共有三个模块公交线路查询BUSLINE、站点查询SEARCHSTATE、最优方案BESTPROJECT【模块流程图】1BUSLINE存存在2SEARCHSTATEMAIN（）MAINSURFACEBUSLINESEARCHSTATEBESTPROJECT退出SET_GRAPH特定车号的路线查询所有路线浏览MAINSURFACE接收车号输出公交车信息SHOW_BUSMESSAGE存在否SET_GRAPH接收站点在图内查找站点名MAINSURFACE有循环输出当前车3BESTPROJECT无路径有路径栈为是车相同接收起始站BESTCHOOCESET_GRAPHDIJKSTRA算法MAINSURFACE对路径上的站入栈出栈判断是否是换车输出换车信息输出路径MAINSURFACE【界面设计】采用简单的人机会话，使操作简单明了；【用户手册】在程序所在文件夹下建立“公交查询TXT”，并输入以下内容30世家星城通讯学院石油公寓潘家庄明德门杨家村城南客运站西八里村医学院纬二街雁南路大雁塔赛格电脑城李家村和平门大差市五路口火车站603电视塔国展中心吴家坟八里村纬二街小寨长安立交省体育场草场坡南稍门南门钟楼北门火车站37城北客运站公交六公司方新村龙首村北关钟楼东门兴庆路建工路幸福路南口（每一个车的线路占一行）；编译运行程序，根据提示执行程序；要想有更为准确的方案，可以在“公交查询TXT”中加入公交车线路；2、程序上机调试报告【语法错误及其排除】1函数赋值时，将变量赋给了指针；使用指针传值；2在出栈时没有判断栈是否为空，导致TOP指空所到的车及方向在出栈前判断ISEMPTY（）；【算法错误及其排除】1在建立图中没有对A数组进行置空，导致数据混乱；在使用A之前对A数组赋空；2在输出最优结果时没有保留前一站使程序无法判断是否换车加入B数组保留前一站；3、程序测试结果【测试数据】30世家星城通讯学院石油公寓潘家庄明德门杨家村城南客运站西八里村医学院纬二街雁南路大雁塔赛格电脑城李家村和平门大差市五路口火车站603电视塔国展中心吴家坟八里村纬二街小寨长安立交省体育场草场坡南稍门南门钟楼北门火车站37城北客运站公交六公司方新村龙首村北关钟楼东门兴庆路建工路幸福路南口（每一个车的线路占一行）；【输出结果】1公交线路查询2站点查询3最优方案【程序性能评价】使用简单；结果正确、明了；【性能改进方向】1将邻接矩阵改为三维，即在相同两站间由多个公交可以到达；2在站点里加入方位，即在寻找最优结果的时候可以不必将所有站点进行操作，加快运行速度；3在公交车类中加入收费，在最优结果输出时计算收费有刷卡、投币、按站收费；【收获及体会】通过这个程序的编写使我对C中文件的操作、图的操作、栈的操作、查找等内容有了更深的理解，在编译的过程中也是我知道了自己的数据结构课程内容还很浅，还需要在努力；4、源程序代码INCLUDE/文件库INCLUDEINCLUDE/字符串函数库CONSTINTMAXBUS100/最大公交车数CONSTINTMAXSTATE200/最大站点数CONSTINTMAXVALUE999/最大值STRUCTBUS/公交车类INTNUMBER/公交车号INTLENGTH/总站数CHARBUS_STATEMAXSTATE20/站点CLASSGRAPH/建立无向图FRIENDCLASSDISTANCE/声明友元类PRIVATECHARSTATENAMEMAXSTATE20/站点INTBUSNUMBERMAXSTATEMAXSTATE/邻接矩阵，权值为这两个站点的公交车号INTCURRENTSTATE/当前站点数INTCURRENTBUS/当前公交车数BUSBUSESMAXBUS/公交车信息PUBLICGRAPH/无参构造函数，对成员变量初始化FORINTI0IBUSESCURRENTBUSNUMBER/接收车号码INFILEGETLINECH,700/在文件中读取一行FORINTI0CHIIIFCHI/把站点暂存在A中AJCHIELSESTRCPYBUSESCURRENTBUSBUS_STATEK,A/对公交车站点赋值INSERTSTATEA/插入站点FORJ0J“COUT“LINKDELETEP/释放栈顶结点VOIDSTACKMAKEEMPTY/把栈置空STACKNODEPWHILETOPNULL/逐结点回收PTOPTOPTOPLINKDELETEP/释放栈顶结点VOIDSTACKPUSHCHARITEM/进栈STACKNODEPNEWSTACKNODEITEM,TOP/新结点PLINKTOP/链入TOP之前TOPP/成为新栈顶INTSTACKPOPCHARX/退栈IFISEMPTYRETURN0STACKNODEPTOPTOPTOPLINK/修改栈顶指针STRCPYX,PDATE/送回退栈元素DELETEPRETURN1/释放INTSTACKGETTOPCHARX/读取栈顶元素IFISEMPTYRETURN0STRCPYX,TOPDATE/送回栈顶元素RETURN1/释放CLASSDISTANCEPUBLICGRAPH/定义最短距离类PRIVATECHARPATH20/最短距离的前一站INTDISTANCEMAXSTATE/最短距离PUBLICVOIDBESTCHOOCECHARV0,CHARV1/最优方案INTSMAXSTATE,V,I,J,W,START1,END1,NUMBER1,NUMBER