据数结构课程设计方案说明文本--公交乘车本科论文.doc

《数据结构与算法设计》 课程设计任务书 题 目 公交咨询程序 学生姓名 孙宝琳 学号 200701030124 专业班级 数学0701 设 计 内 容 与 要 求 【问题描述】 利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。 【软件功能】 从文件中接收图和公交车信息； 可实现确定公交线路查询，即输出该车的所有站点； 可以对某一个站点进行查询输出该站点的所有下一站； 可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点； 【算法思想】 设计公交车类（车号，路程长度，终点站）、图类（站点名，公交车类，现有路线条数，现有站点数）、Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询——在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线，并有最短路径的最后一个站点将路径上的所有站点入栈，出站时判断是否换车并输出方案； 【提交成果】 1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋； 2.“《数据结构与算法设计》课程设计报告”一份，打印装袋； 3、上面两项内容的word文档，通过电子邮件交到指导教师。 起止时间 2009 年 6 月 8 日 至 2009 年6月 19 日 指导教师签名 年 月 日 系（教研室）主任签名 年 月 日 学生签名 孙宝琳 2009年 6月18 日 数据结构与算法设计课程设计 专业 数学与应用数学 班级 数学0701 学号 200701030124 姓名 孙宝琳 完成日期 6.18 指导教师（签名） 程序设计说明书 【设计题目】公交咨询程序 【问题描述】 利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。 【软件功能】 1 从文件中接收图和公交车信息； 2 可实现确定公交线路查询，即输出该车的所有站点； 3 可以对某一个站点进行查询输出该站点的所有下一站； 可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点； 【算法思想】 设计公交车类（车号，路程长度，终点站），图类（站点名，公交车类，现有路线条数，现有站点数），Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询——在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线并有最短路径的最后一个站点输出乘车方案； 【类的设计】 struct Bus //公交车类 { int number; //公交车号 int length; //总站数 char bus_state[Maxstate][20]; //站点 }; class Graph //建立无向图 { friend class Distance; //声明友元类 private: char statename[Maxstate][20]; //站点 int busnumber[Maxstate][Maxstate]; //邻接矩阵，权值为这两个站点的公交车号 int currentstate; //当前站点数 int currentbus; //当前公交车数 Bus buses[Maxbus]; //公交车信息 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 vo