公交换乘一站算法

小咪咪 2022-08-27 12:39 189阅读 0赞

公交换乘一站算法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&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;  
        \}  
\}