3.23 每日总结

今天完成了最优化的线路查询，应用了BFS算法，广度优先遍历使用了队列的算法，实现最短路径的算法。

下面是算法部分代码：

Rea.java

package Contrl;
import line.Tool;
import java.util.*;
import java.io.IOException;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import Model.*;
public class Read {

    private ArrayList<Station> station= new ArrayList<>();
    private ArrayList<Route> route= new ArrayList<>();
    
    public ArrayList<Station> getStation() {
        return station;
    }

    public ArrayList<Route> getRoute() {
        return route;
    }
    public Read() 
    {
        try {
            for(int k=1;k<3;k++) {
                Route r = new Route();
                String str="线路"+String.valueOf(k);
                r.setRname(str);//录入线路号
                find(k,r);//录入所在线路所有站点
                route.add(r);
            }
            //站点部分
            for(int i=0;i<route.size();i++) {
                String rname = route.get(i).getRname();
                ArrayList<String> l = route.get(i).getRoute();//临时保存当前线路内部站点
                //判断环线(若线路首尾相同则为环线)
                if(l.get(0).equals(l.get(l.size()-1))) {
                    int flag=0;
                    //优先处理首尾站点
                    for(int k=0;k<station.size();k++) {
                        //若该站点曾经录入过，则添加相关信息
                        //有环线的站点首尾相同且需添加两个相邻站
                        if(station.get(k).getSname().equals(l.get(0))) {
                            station.get(k).setBTR(rname);//更新所属线路
                            //更新邻站
                            station.get(k).setBs(l.get(1));
                            station.get(k).setBs(l.get(l.size()-2));
                            flag=1;
                            break;
                        }
                    }
                    //若该站点从未录入，则新建
                    if(flag==0) {
                        Station s = new Station();
                        s.setSname(l.get(0));//添加站点名称
                        s.setBTR(rname);//添加所属线路
                        //添加邻站
                        s.setBs(l.get(1));
                        s.setBs(l.get(l.size()-2));
                        station.add(s);
                    }
                }else {
                    int flag=0;
                    //优先处理首部站点
                    for(int k=0;k<station.size();k++) {
                        //若该站点曾经录入过，则添加相关信息
                        //未有环线首尾站点仅有一个相邻站
                        if(station.get(k).getSname().equals(l.get(0))) {
                            station.get(k).setBTR(rname);
                            station.get(k).setBs(l.get(1));
                            flag=1;
                            break;
                        }
                    }
                    //若该站点从未录入，则新建
                    if(flag==0) {
                        Station s = new Station();
                        s.setSname(l.get(0));
                        s.setBTR(rname);
                        s.setBs(l.get(1));
                        station.add(s);
                    }
                    flag=0;
                    //处理尾部站点
                    for(int k=0;k<station.size();k++) {
                        //若该站点曾经录入过，则添加相关信息
                        if(station.get(k).getSname().equals(l.get(l.size()-1))) {
                            station.get(k).setBTR(rname);
                            station.get(k).setBs(l.get(l.size()-2));
                            flag=1;
                            break;
                        }
                    }
                    //若该站点从未录入，则新建
                    if(flag==0) {
                        Station s = new Station();
                        s.setSname(l.get(l.size()-1));
                        s.setBTR(rname);
                        s.setBs(l.get(l.size()-2));
                        station.add(s);
                    }
                    
                }
                //遍历处理剩余站点
                for(int j=1;j<l.size()-1;j++) {
                    int flag=0;
                    for(int k=0;k<station.size();k++) {
                        if(station.get(k).getSname().equals(l.get(j))) {
                            station.get(k).setBTR(rname);
                            station.get(k).setBs(l.get(j-1));
                            station.get(k).setBs(l.get(j+1));
                            flag=1;
                            break;
                        }
                    }
                    if(flag==0) {
                        Station s = new Station();
                        s.setSname(l.get(j));
                        s.setBTR(rname);
                        //前后站点均为邻站
                        s.setBs(l.get(j-1));
                        s.setBs(l.get(j+1));
                        station.add(s);
                    }
                    
                    
                }
            }
        }catch(Exception e) {  
            e.printStackTrace();  
        }
    }
    public void find(int nol,Route r){
        //List<String> list=new ArrayList<>();
        Connection conn=Tool.getConnection();
        PreparedStatement pre=null;
        ResultSet res=null;
        String sql="SELECT *FROM line where nol=? ";
        try {
        pre=conn.prepareStatement(sql);
        pre.setInt(1, nol);
        res=pre.executeQuery();
        while(res.next()) {
            String num1=res.getString ("name");
            r.addRoute(num1);
        }
        }
    catch(SQLException e) {
            
            e.printStackTrace();
        }finally{
            Tool.release(conn, pre, res);
        }
    }
}

BFS.java

package Contrl;

import java.util.*;
import Model.*;

public class BFS {
    public ArrayList<Station> FindMin(String firstStation,ArrayList<Station> station) {
        ArrayList<Station> result = new ArrayList<>();//结果集
        //找到始发站
        int fsIndex=-1;
        for(int i=0;i<station.size();i++) {
            Station tmp = station.get(i);
            if(tmp.getSname().equals(firstStation)) {//名称相同即找到
                fsIndex=i;
                break;
            }
        }
        //若未找到则报错结束
        if(fsIndex==-1) {
            System.out.println("未找到该起始站点");
            System.exit(0);//未找到则退出
            return station;
        }
        
        //执行算法
        Queue<Station> queue = new LinkedList<>();//链表模拟队列
        station.get(fsIndex).setVisited(1);//标记访问
        queue.offer(station.get(fsIndex));//初始站点入队列
        
        int dist=0;//保存步数
        while(!queue.isEmpty()) {
            Station tmpS = queue.remove();//移出队列头部
            
            if(dist==0) {//判断是不是队头
                tmpS.setDist(dist);//存入步数
                dist++;
            }else {
                //判断是否换乘
                dist=tmpS.getPs().getDist();
                tmpS.setDist(dist+1);
                dist++;
            }
            result.add(tmpS);//结果集增加
            
            ArrayList<Station> tmpBs = tmpS.getBs(station);
            for(int i=0;i<tmpBs.size();i++) {
                if(tmpBs.get(i).getVisited()==0) {//判断是否访问过
                    tmpBs.get(i).setPs(tmpS);//保存前置站点为当前站点
                    tmpBs.get(i).setVisited(1);//标记访问
                    queue.offer(tmpBs.get(i));//若未访问过则直接存入队列
                }
            }
        }
        
        return result;//返回结果集
    }
    
    public ArrayList<String> shortPath(String endStation,ArrayList<Station> station,ArrayList<String> str) {
        //找到终点站
        int endIndex=-1;
        for(int i=0;i<station.size();i++) {
            Station tmp = station.get(i);
            if(tmp.getSname().equals(endStation)) {
                endIndex=i;
                break;
            }
        }
        //若未找到则报错结束
        if(endIndex==-1) {
            System.out.println("未找到该终点站");
            System.exit(0);
            return null;
        }
        
        Stack<Station> stack = new Stack<>();//建立栈以实现逆序输出
        Station tmp = station.get(endIndex);//栈底为终点站
        if(tmp.getDist()==0) {
            System.out.println("该站为始发站");
            return null;
        }
        int dist = tmp.getDist();//用于保存途经站点数
        int transNum = 0;//用于保存换乘数
        //逐步入栈
        while(tmp.getPs()!=null) {
            stack.push(tmp);
            tmp=tmp.getPs();//更新为前置站点入栈
        }
        
        //判断换乘
        ArrayList<String> r1 =tmp.getBTR();
        ArrayList<String> r2 = stack.peek().getBTR();
        String now="";//用于保存当前线路
        int flag=0;
        //寻找当前线路
        for(int i=0;i<r1.size();i++) {
            for(int j=0;j<r2.size();j++) {
                if(r1.get(i).equals(r2.get(j))) {
                    now=r1.get(i);
                    flag=1;
                    break;
                }
            }
            if(flag==1) {
                break;
            }
        }
        String s1="当前为："+now;
        str.add(s1);
        String s2=tmp.getSname();
        str.add(s2);
        System.out.println("当前为："+now);
        System.out.print(tmp.getSname());

        //逐步出栈
        while(!stack.isEmpty()) {
            //判断是否换乘
            r1 = tmp.getBTR();
            r2 = stack.peek().getBTR();
            flag=0;
            for(int i=0;i<r1.size();i++) {
                for(int j=0;j<r2.size();j++) {
                    //若两个站点所共有的线路与当前线路不同，则为换乘线路
                    if(r1.get(i).equals(r2.get(j))&&(!now.equals(r1.get(i)))) {
                        now=r1.get(i);
                        flag=1;
                        break;
                    }
                }
                if(flag==1) {
                    break;
                }
            }
            if(flag==1) {
                tmp=stack.peek();
                System.out.println();
                String s3="转至："+now;
                str.add(s3);
                System.out.println("转至："+now);
                String strs=stack.pop().getSname();
                str.add(strs);
                //System.out.print(stack.pop().getSname());
                System.out.print(str);
                transNum++;
            }else {
                tmp=stack.peek();
                //str+="-->"+stack.pop().getSname();
                String s=stack.pop().getSname();
                System.out.print("-->"+s);
                str.add("-->"+s);
            }
            
        }
        System.out.println();
        dist--;
        str.add("途径站数"+dist);
        str.add("换乘数"+transNum);
        System.out.println("途径站数"+dist);
        System.out.println("换乘数"+transNum);
        return str;
    }
}

Route.java

package Model;

import java.util.*;

public class Route {
    private String rname;
    private ArrayList<String> route = new ArrayList<>();
    
    public String getRname() {
        return rname;
    }
    public void setRname(String rname) {
        this.rname = rname;
    }

    public void addRoute(String sname) {
        this.route.add(sname);
    }

    public String allRoute() {
        String result="";
        
        for(int i=0;i<route.size();i++) {
            result+=route.get(i)+" ";
        }
        
        return result.trim();
    }
    public ArrayList<String> getRoute() {
        return this.route;
    }
}

Station.java

package Model;

import java.util.*;

public class Station {
    public final static int MaxDist = 65535;
    private String sname;//站名
    private ArrayList<String> bTR = new ArrayList<>();//线路名
    private ArrayList<String> bs = new ArrayList<>();//邻站（距离为1的站）

    
    //执行算法后更改
    private Station ps;//前一个站点
    private int dist;//距离（距起始站）
    private int transNum;//换乘数
    private int visited;//保存是否访问
    
    public Station() {
        this.dist=MaxDist;
        this.transNum=0;
        this.visited=0;
    }
    
    public String getSname() {
        return sname;
    }
    public void setSname(String sname) {
        this.sname = sname;
    }
    //站所属路线（可能有多个）
    public void setBTR(String belongToRname) {
        this.bTR.add(belongToRname);
    }
    //所属路线输出（用于算法）
    public ArrayList<String> getBTR() {
        return this.bTR;
    }
    //相邻站录入
    public void setBs(String sname) {
        for(int i=0;i<this.bs.size();i++) {
            if(this.bs.get(i).equals(sname)) {
                return;
            }
        }
        this.bs.add(sname);
    }
    //相邻站输出（用于算法）
    public ArrayList<Station> getBs(ArrayList<Station> station){
        ArrayList<Station> result = new ArrayList<>();
        for(int i=0;i<this.bs.size();i++) {
            String tmp = this.bs.get(i);
            for(int j=0;j<station.size();j++) {
                if(station.get(j).getSname().equals(tmp)) {
                    result.add(station.get(j));
                    break;
                }
            }
        }
        return result;
    }
    public int getVisited() {
        return visited;
    }

    public void setVisited(int visited) {
        this.visited = visited;
    }

    //执行算法后更改
    public Station getPs() {
        return ps;
    }
    public void setPs(Station ps) {
        this.ps = ps;
    }
    public int getDist() {
        return dist;
    }
    public void setDist(int dist) {
        this.dist = dist;
    }
    public int getTransNum() {
        return transNum;
    }
    public void setTransNum(int transNum) {
        this.transNum = transNum;
    }
}

Start.java:主程序代码，用于控制台输出

package Util;

import java.util.*;
import Contrl.*;
import Model.*;

public class Start {
    //public final static String FILEPATH = "D:\\data.txt";
    public static void main(String[] args) throws Exception{
        Scanner input = new Scanner(System.in);
        
        //读取文件
        //ReadDate file = new ReadDate(FILEPATH);
        //提取所保存的站点和线路信息
        Read re=new Read();
        ArrayList<Station> station= re.getStation();
        ArrayList<Route> route= re.getRoute();
        
        //输出所有线路名称
        for(int i=0;i<route.size();i++) {
            System.out.print(route.get(i).getRname()+" ");
        }
        System.out.println();
        //输出菜单
        System.out.println("请选择所需任务: 1.查询线路 2.规划路线");
        //输入
        int choose = input.nextInt();
        if(choose==1) {
            System.out.print("请输入所需查询的线路名: ");
            String name = input.next();
            int index=-1;
            for(int i=0;i<route.size();i++) {
                if(route.get(i).getRname().equals(name)) {
                    index=i;
                    break;
                }
            }
            if(index==-1) {
                System.out.println("该线路名错误");
            }else {
                System.out.println(route.get(index).getRname()+":"+route.get(index).allRoute());
            }
        }else if(choose==2) {
            BFS bfs = new BFS();
            System.out.print("请输入始发站: ");
            String start = input.next();
            station=bfs.FindMin(start,station);
            System.out.print("请输入终点站: ");
            String end = input.next();
            //String l="";
            ArrayList<String> l=new ArrayList<>();
            bfs.shortPath(end, station,l);
            //System.out.printf(l);
        }
        
    }
    

}

下面是演示结果：