资源预览内容
第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
第9页 / 共34页
第10页 / 共34页
亲,该文档总共34页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
. . . . .数据结构与算法设计课程设计任务书题 目公交咨询程序学生姓名孙宝琳学号200701030124专业班级数学0701设计内容与要求【问题描述】 利用图实现公交咨询系统,包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1 从文件中接收图和公交车信息;2 可实现确定公交线路查询,即输出该车的所有站点;3 可以对某一个站点进行查询输出该站点的所有下一站;4 可以对乘车方案进行查询,即输出确定起点,终点的最优乘车方案,换车输出换车次数及换车站点;【算法思想】设计公交车类(车号,路程长度,终点站)、图类(站点名,公交车类,现有路线条数,现有站点数)、Dijkstra算法类(最短路径上的最后一个站点,最短路径的站点数);从文件中接收内容并对图和公交车进行初始化,公交线路查询在图中找到起点站,按顺序输出所有公交车号相同的站点;乘车方案中利用Dijkstra算法算出最优路线,并有最短路径的最后一个站点将路径上的所有站点入栈,出站时判断是否换车并输出方案;【提交成果】1.“数据结构与算法设计课程设计任务书”一份,打印装袋;2.“数据结构与算法设计课程设计报告”一份,打印装袋;3、上面两项内容的word文档,通过电子邮件交到指导教师。起止时间2009 年 6 月 8 日 至 2009 年6月 19 日指导教师签名年 月 日系(教研室)主任签名年 月 日学生签名孙宝琳 2009年 6月18 日数据结构与算法设计课程设计专业 数学与应用数学 班级 数学0701 学号 200701030124 姓名 孙宝琳 完成日期 6.18 指导教师(签名)1、 程序设计说明书【设计题目】公交咨询程序【问题描述】利用图实现公交咨询系统,包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1 从文件中接收图和公交车信息;2 可实现确定公交线路查询,即输出该车的所有站点;3 可以对某一个站点进行查询输出该站点的所有下一站;4 可以对乘车方案进行查询,即输出确定起点,终点的最优乘车方案,换车输出换车次数及换车站点;【算法思想】 设计公交车类(车号,路程长度,终点站),图类(站点名,公交车类,现有路线条数,现有站点数),Dijkstra算法类(最短路径上的最后一个站点,最短路径的站点数);从文件中接收内容并对图和公交车进行初始化,公交线路查询在图中找到起点站,按顺序输出所有公交车号相同的站点;乘车方案中利用Dijkstra算法算出最优路线并有最短路径的最后一个站点输出乘车方案;【类的设计】 struct Bus /公交车类int number; /公交车号int length; /总站数char bus_stateMaxstate20; /站点;class Graph /建立无向图friend class Distance; /声明友元类private:char statenameMaxstate20; /站点int busnumberMaxstateMaxstate; /邻接矩阵,权值为这两个站点的公交车号int currentstate; /当前站点数int currentbus; /当前公交车数Bus busesMaxbus; /公交车信息public:Graph() ; /无参构造函数,对成员变量初始化 void Insertstate(char state);/插入一个站点void Insertbusnumber(char V1,char V2,int busnum) ;/插入权值void Set_graph() ; /图的建立bool IsGraphFull() ; /判断图是否已满void show_busmessage(int number); /输出公交信息int searchbusnumber(char v0,char v1) ; /查找指定站点的公交车号码void direction(char v0,char v1) ; /输出指定站点的公交车方向friend void busline(); /把外部函数定义为图的友元函数,以便使用图的私有成员变量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode /栈结点friend class Stack; /友元类private: char date20; /结点数据StackNode *link; /结点链指针public:/构造函数:结点赋值StackNode (char d =0,StackNode *l =NULL);;class Stack /定义栈private:StackNode *top; /栈顶指针public:Stack ( ) :top(NULL) /构造函数Stack ( ); /析构void Push(char item); /进栈int Pop(char x);/退栈int GetTop(char x); /读取栈顶元素void MakeEmpty (); /把栈置空int IsEmpty() ;class Distance:public Graph /定义最短距离类private:char path20; /最短距离的前一站int distanceMaxstate; /最短距离public:void bestchooce(char v0,char v1); /最优方案;【存储结构设计】 使用邻接矩阵int busnumberMaxstateMaxstate;存储图的信息;公交车信息采用结构体数组Bus busesMaxbus;存储;栈使用链表来实现;【模块划分及调用关系】Main() Mainsurface()退出Bestproject()Searchstate()Busline()共有三个模块:公交线路查询Busline()、站点查询Searchstate()、最优方案Bestproject()【模块流程图】1. Busline(): Set_graph()Mainsurface()特定车号的路线查询所有路线浏览循环输出当前车接收车号 存在 存 存在 输出公交车信息show_busmessage()2 searchstate():Set_graph() 否 接收站点Mainsurface()在图内查找有站点名所到的车及方向3 bestproject(): 无路径 有路径 栈为空 是 车相同接收起始站Bestchooce()Set_graph()Dijkstra算法Mainsurface()对路径上的站入栈出栈判断是否是换车输出换车信息输出路径Mainsurface()【界面设计】 采用简单的人机会话,使操作简单明了;【用户手册】 在程序所在文件夹下建立“公交查询.txt”,并输入以下内容: 30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;(每一个车的线路占一行); 编译运行程序,根据提示执行程序;要想有更为准确的方案,可以在“公交查询.txt”中加入公交车线路;2、 程序上机调试报告【语法错误及其排除】1 函数赋值时,将变量赋给了指针; 使用指针传值;2 在出栈时没有判断栈是否为空,导致top指空 在出栈前判断IsEmpty();【算法错误及其排除】1 在建立图中没有对a数组进行置空,导致数据混乱;在使用a之前对a数组赋空;2 在输出最优结果时 没有保留前一站使程序无法判断是否换车加入b数组保留前一站;3、 程序测试结果【测试数据】30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号