公交换乘算法代码,Java代码库,德仔网

代码语言
代码分类
【Java】公交换乘算法
作者: / 发布于2011/1/14/ 369
<div>公交换乘一站算法busTransfer
/**
* 公交换乘一站的算法思想：
* （注意：车次信息、站点信息、公交信息是等价的都是以HashMap的形式存储信息）
* 1.从数据库中获得所有公交信息存储到ArrayList，每个具体信息的元数据有三个：
* 公交车次、公交站点、该公交站点距离该公交车次的始发站点的站数，具体信息用HashMap保存
* 2.然后把公交信息数据进行结构化，把所有公交站点抽出，再把每一个站点对应的所有车次抽出
* 与其一一对应，单一的车次信息用HashMap存储，站点对应的所有车次信息用ArrayList存储，
* 所有的站点有经过站点的车次信息用HashMap存储
* 3.根据查询要求，分别从结构化以后的公交信息数据中找到，经过出发地的所有车次，经过目的地
* 的所有车次，然后在分别遍历每个车次，筛选出符合要求的中转站点，筛选规则是：每查询出一个
* 站点时，得到该站点距离该站点对应车次的始发站的站数，如果这个站数小于查询站点距离该车次的始
* 发站的站数，那么就符合规则，便把该站点信息保存到符合站点的ArrayList中，反之亦然
* 4.分别得到查询条件中出发地和目的地的中转站点信息（中转站点信息存储在ArrayList中），然
* 后遍历两个中转站点信息的集合，得到最终的具体中转信息（最终中转信息也是用ArrayList存储）
*/
package bustransfer;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.ResultSetMetaData;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.HashMap;
import java.util.Map;

public class BusTransfer {

 private String start = null;// 出发地

 private String whither = null;// 目标地

 private List schedule = null;// 用于缓存列车时刻表。

 private HashMap<String, ArrayList> stationsOfLine = null; // 所有公交线路，每个list存储该线路经过的所有车站。

 private HashMap<String, ArrayList> linesOfStation = null;// 所有车站，每个list中存储通过该车站的所有车次。

 // private ArrayList<String> startLine = new ArrayList<String>();//
 // 途经出发地的所有车次。

 // private ArrayList<String> whitherLine = new ArrayList<String>();//
 // 途经目的地的所有车次。

 private ArrayList<Map> firLineStaList = new ArrayList<Map>();

 private ArrayList<Map> secLineStaList = new ArrayList<Map>();

 public BusTransfer(String start, String whither) {
 this.start = start;
 this.whither = whither;

 try {
 this.schedule = this
 .executeQuery("select busLine,up,stationNo from bus_stations");
 } catch (Exception e) {
 // TODO Auto-generated catch block
 System.out.println("读取数据库出错");
 e.printStackTrace();
 }
 stationsOfLine = this.getStationsOfLine();
 linesOfStation = this.getLinesOfStation();
 }

 private HashMap<String, ArrayList> getStationsOfLine() {
 HashMap map = new HashMap();// 用于 临时存储从schedule中取出的HashMap.
 ArrayList<Map> line = null;// 每个list存储一个车次的相关车站信息。
 String buffer = "a";// 缓存站名。
 String temp = null;// 临时存储每次迭代取出的站名，用于与buffer站名比较。
 HashMap<String, ArrayList> stationsGroupByLine = new HashMap<String, ArrayList>();// 存储以车次分组後的车站的list

 Iterator it = schedule.iterator(); // 迭代器
 while (it.hasNext()) {
 map = (HashMap) it.next();

 temp = (String) map.get("busLine");
 if (stationsGroupByLine.containsKey(temp)) {
 line = stationsGroupByLine.get(temp);
 buffer = (String) ((Map) line.get(0)).get("busLine");
 }
 if (buffer.equals(temp)) {
 line.add(map);// 将同一车次的车站放入一个list中

 } else {
 if (line != null && !line.isEmpty()) {
 stationsGroupByLine.put(buffer, line);// 将由车次分组后的车站构成的list存入一个map
 }
 line = new ArrayList<Map>(); // line重新引用一个新构造的list，以供存储同一车站的车次。
 line.add(map);// 将同一车次的车站放入刚刚构造的空list中
 }
 buffer = temp;// 缓存当前操作的车次。
 }
 return stationsGroupByLine;
 }

 private HashMap getLinesOfStation() {
 HashMap map = new HashMap();// 用于 临时存储从schedule中取出的HashMap.
 ArrayList<Map> station = null;// 每个list存储一个经过该车站的相关车次信息。
 String buffer = "a";// 缓存车次。
 String temp = null;// 临时存储每次迭代取出的车次，用于与buffer车次比较。
 HashMap<String, ArrayList> linesGroupBystation = new HashMap<String, ArrayList>();// 存储以车站分组後的车次的list

 Iterator it = schedule.iterator(); // 迭代器
 while (it.hasNext()) {
 map = (HashMap) it.next();

 temp = (String) map.get("up");
 if (linesGroupBystation.containsKey(temp)) {
 // station存储temp车次对应的站点信息
 station = linesGroupBystation.get(temp);
 // 从station中取出已经放入linesGroupBystation车站信息，缓存改车站的名字
 // 与刚取出的Map中存储到车站信息进行比较
 buffer = (String) ((Map) station.get(0)).get("up");
 }
 if (buffer.equals(temp)) {
 // 如果station中几经存在该站点信息，那么，本站和station中存储到是同一站，所以
 // 将同一车次的车站放入一个list中
 station.add(map);

 } else {
 if (station != null && !station.isEmpty()) {
 // 将由车次分组后的车站构成的list存入一个map
 linesGroupBystation.put(buffer, station);
 }
 // line重新引用一个新构造的list，以供存储经过另一车站的所有车次
 station = new ArrayList<Map>();
 station.add(map);// 将同一车次的车站放入刚刚构造的空list中
 }
 buffer = temp;// 缓存当前操作的车次。
 }
 return linesGroupBystation;
 }
/**
 * 站点筛选规则：把符合规则的站点添分别放入
 * 
 * @param startSta
 * @param whitherSta
 */
 private void getStationsInLine(String startSta, String whitherSta) {
 // 获得经过初始站点的所有公交车次
 ArrayList firTrainLine = linesOfStation.get(startSta);
 // 获得经过所有目的站点的公交车次
 ArrayList secTrainLine = linesOfStation.get(whitherSta);

 ArrayList station;
 HashMap line = null;
 int transferStaNo = 0;
 // String stationName = null;
 String trainNo = "";

 if (firTrainLine != null) {
 Iterator firIt = firTrainLine.iterator();
 while (firIt.hasNext()) {
 // 取出一个存储车站信息HashMap
 line = (HashMap) firIt.next();
 // 取出车次信息
 trainNo = (String) line.get("busLine");
 transferStaNo = (Integer) line.get("stationNo");

 // 取出车次trainNo经过的所有站点信息
 station = stationsOfLine.get(trainNo);
 Iterator it = station.iterator();
 while (it.hasNext()) {

 Map map = (Map) it.next();// trainNo's map.
 int i = (Integer) map.get("stationNo");
 // 筛选站点规则：如果该站点距离初始站点距离比出发站点的距离初始站点的距离大，那么就把该站点存储到
 // firLineStaList,反之就做反车了，所以那些站点不必加入firLineStaList中
 if (i > transferStaNo) {
 //
 firLineStaList.add(map);
 }
 }
 }
 }

 if (secTrainLine != null) {
 Iterator secIt = secTrainLine.iterator();
 while (secIt.hasNext()) {
 line = (HashMap) secIt.next();
 trainNo = (String) line.get("busLine");
 transferStaNo = (Integer) line.get("stationNo");

 station = stationsOfLine.get(trainNo);
 Iterator it = station.iterator();
 while (it.hasNext()) {

 Map map = (Map) it.next();
 int i = (Integer) map.get("stationNo");

 if (i < transferStaNo) {

 secLineStaList.add(map);
 }
 }
 }
 }
 }

 /**
 * 
 * create date:2008-5-19 author:Administrator
 * 
 * @return
 */
 private ArrayList<Map> checkCrossLine() {

 ArrayList<Map> crossLineList = new ArrayList<Map>();// 相交线路的集合,即是所有的换乘方法的集合
 ArrayList<Map> lsStart = firLineStaList;// 经过起点站的所有车次的经停站站信息。
 ArrayList<Map> lsEnd = secLineStaList;// 经过目的站的所有车次的经停站站信息。

 if (lsStart != null && !lsStart.isEmpty() && lsEnd != null
 && !lsEnd.isEmpty()) {

 for (Map<String, String> mapStart : lsStart) {
 for (Map<String, String> mapEnd : lsEnd) {
 if (IsInTheSameCity(mapStart.get("up"), mapEnd.get("up"))) {

 // 将相交线路信息存入crossLine，存储某一个具体的换乘方法
 Map<String, String> crossLine = new HashMap<String, String>(
 4, 0.8f);

 // 把第一次要做到车次放如crossLine
 crossLine.put("firstLine", mapStart.get("busLine"));
 // 把要换乘的车次放入到crossLine
 crossLine.put("secondLine", mapEnd.get("busLine"));
 // 把中转站点放入到crossLine
 crossLine.put("transferSta", mapEnd.get("up"));

 // crossLine.put("transferSta",(String)startInf.get("up"));
 // 将包含相交线路信息的HashMap存入List
 // 也即是把具体某个换乘方法放入crossLineList
 crossLineList.add(crossLine);
 } else {
 continue;
 }
 }
 }

 } else {
 crossLineList = null;
 }

 return crossLineList;
 }

 private boolean IsInTheSameCity(String station1, String station2) {

 if (station1.contains(station2) || station2.contains(station1)) {
 // System.out.println(station1+"#########"+station2);
 return true;
 } else {
 return false;
 }

 }

 public ArrayList<Map> getSchemaOfTransfer() {
 this.getStationsInLine(this.start, this.whither);
 return this.checkCrossLine();
 }

 public static void main(String[] args) {
 BusTransfer tb = new BusTransfer("前门", "天安门西");
 // tb.getSchemaOfTransfer();
 for (Map map : tb.getSchemaOfTransfer()) {
 System.out.println(map);
 System.out.println("您好，您可以先乘坐 " + map.get("firstLine") + " 到 "
 + map.get("transferSta") + " 然后换乘 " + map.get("secondLine")
 + " 便可到达，不要错过站吆 ！");
 }

 // System.out.println(tb.secLineStaList.size());
 }

private Connection getConnection() {
 Connection con = null;
 String url = "jdbc:mysql://127.0.0.1:3306/souwhat?autoReconnect=true&useUnicode=true&characterEncoding=GBK&amp;mysqlEncoding=GBK";
 String user = "root";
 String psWord = "";
 try {
 Class.forName("com.mysql.jdbc.Driver");
 } catch (ClassNotFoundException e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 System.out.println("The Exception at load the Driver");
 }
 try {
 con = DriverManager.getConnection(url, user, psWord);
 } catch (SQLException e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 System.out.println("The Exception at creat the connection");
 }
 return con;
 }

 private void closeConnection(Connection conn) throws Exception {
 if (conn != null) {
 conn.close();
 }
 }

 private List executeQuery(String sql) throws Exception {
 // System.out.println("executeQuery(sql): " + sql);
 List list = new ArrayList();
 Connection conn = null;
 Statement stmt = null;
 ResultSet rs = null;
 try {
 conn = getConnection();
 stmt = conn.createStatement();

 System.out.println(sql);

 rs = stmt.executeQuery(sql);

 ResultSetMetaData rsmd = rs.getMetaData();
 while (rs.next()) {
 Map map = new HashMap();
 for (int i = 1; i <= rsmd.getColumnCount(); i++) {
 // 每一行所有列存入HashMap中
 map.put(rsmd.getColumnName(i), rs.getObject(i));
 }
 // 所有行存入List中
 list.add(map);
 }
 } catch (Exception e) {
 System.out.println("数据库查询出错!");
 e.printStackTrace();
 } finally {
 if (rs != null)
 rs.close();
 closeConnection(conn);
 }
 return list;
 }
}
试试其它关键字
　公交换乘　
同语言下
可能有用的
贡献的其它代码Label