公交线路优化路径的查询数据结构课程设计报告

课程设计报告


课程： 《数据结构》


题目： 公交线路优化路径的查询


学 院： 计算机与电子信息学院

专 业：

班 级：

学 号：

学生姓名： 空白小龙

指导教师：


二〇一一 年 一 月一、实验目的和要求

1、实验目的：

【问题描述】

对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市 的公交线路的输入格式为：

线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；……；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。车速。该线路平均经过多少时间来一辆。

例如：63：A(32,45)；B(76,45)；C(76,90)；……；N(100,100) 。1元。1/每分钟。5分钟。

假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。不考虑乘客上下车的时间。

对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径。

2、实验要求：

【设计要求】

① 根据上述公交线路的输入格式，定义并建立合适的图模型。

② 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x ：站名S，…，站名M1；换乘线路x ：站名M1，…，站M2；…；换乘线路x：站名MK，…，站名T。共花费x元。

③ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；…；换乘线路x：站名MK，…，站名T。共花费x时间。

④ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名 S，T 后，可以输出从 S 到T 的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名 S，…，站名 M1；换乘线路 x：站名M1，…，站名 M2；…；换乘线路x：站名 MK，…，站名T。共花费x 时间。

采用图形化界面显示操作结果，使用的编程工具：

Ecclipse：eclliipse-SDK-3.2-win32eclliipse-SDK-3.2-win32

实现图形化界面要安装的插件：emff-sdo-SDK-2..2..2、GEF--ALL--3..2、VE--runttimee-1.2.3_jeemJDK：jdk1..6..0


二、设计概要：

1、根据实验要求，与及所了解的数据类型相关知