首页 > 其他分享 >每日双人总结

每日双人总结

时间：2023-03-17 22:45:05浏览次数：36  
标签：总结 end get int adj 每日 line 双人 public 

import java.util.LinkedList;

public class Graph {
    public int num;                     //结点总数
    /*
     * LinkedList<Integer> adj[]
     * 一个存放list的数组，其中list中存放的是对应节点的所有邻接点信息,
     * 如adj[1]存储的就是序列号为1的站点的所有邻接点信息,也可以理解为存储所有的边
     */
    public LinkedList<Integer> adj[];  
    /*
     * 图的构造方法，传入结点总数v
     * 将数组实例化，并将每个数组中的每个list都实例化
     */
    public Graph(int v){               
        num = v;
        adj = new LinkedList[v];
        for(int i=0; i<v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }
    /*
     * 图的加边方法，传入参数，s和t，二者都是结点的序列号
     *因为是无向图，所以二者的邻接点list都要存储对方的信息
     */
    public void addEdge(int s,int t) {
        adj[s].add(t);
        adj[t].add(s);
    }
    public int getV() {
        return num;
    }
    public void setV(int v) {
        this.num = v;
    }
    public LinkedList<Integer>[] getAdj() {
        return adj;
    }
    public void setAdj(LinkedList<Integer>[] adj) {
        this.adj = adj;
    }
}

Copy 22:37:49
public void calc(int start,int end,Graph graph){
        if(start<0||end<0) {
            return;
        }
        if(start==end) {
            System.out.println("两站点相同");
            return;
        }
        int v=graph.getV();  //得到结点总数
        LinkedList<Integer>[] adj=graph.getAdj();  //得到所有边的信息
        boolean[] visited = new boolean[v];        //创建访问数组
        visited[start] = true;         //设置初始站点已被访问过
        Queue<Integer> queue = new LinkedList<>();     //创建辅助队列
        queue.add(start);     
        int[] prev = new int[v];   //路径数组，记录站点的前一个站点，如prev[q]=w,就表示想要到达q，就必须先经过w
        for(int i=0; i<v;i++) {    //初始化为-1
            prev[i] = -1;
        }
        while(queue.size() != 0) {
            int w =queue.poll();
            for(int i=0; i<adj[w].size();++i) {   //遍历站点 w 的所有邻接站点
                int q = adj[w].get(i);     //取出 w 的邻接站点
                if(!visited[q]) {      //判断是否访问过
                    prev[q] = w;         //加入路径数组
                    if(q == end) {       //如果是终点就结束，调用print方法打印路径
                        print(prev,start,end);  
                        return;
                    }
                    visited[q] = true;  //如果不是目的地，就设置为已访问过， 
                    queue.add(q);      //邻接站点入队
                }
            }
        }
    }

Copy 22:37:56
private void print(int[] prev, int start,int end) {
        int end2=end;    //将end赋值给end2，之后会用到
        int num=1;       //用于记录经过的站数，初值为1
        Stack<Integer> stack=new Stack<Integer>(); //创建辅助栈
        /*
         * 依次将路径数组中的值入栈，利用栈后进先出的特性
         * 循环条件1：prev[end]!=-1 表示已经找到了正确路线，
         * 循环条件2：start!=end，表示已经全部压栈完毕
         */
        while(prev[end]!=-1&&start!=end){  
            stack.push(prev[end]);  //目的地的前一个站点入栈
            end=prev[end];          //将目的地设为目的地的前一个站点，这样循环下去，最终end=start 结束循环
        }
        List<String> line = new ArrayList<String>();  //创建辅助list line
        /*
         * 将栈里的数据依次出栈，并将序列号转换成站名，放进list
         */
        while(!stack.empty()){     //只要栈不空
            int e=stack.pop();     //出栈
            String name=new CDSubway().station_name.get(e); //调用CDSubway的静态变量station_name，根据序列号获取站名
            line.add(name);  //将站名加入list
        }
        String name=new CDSubway().station_name.get(end2); //通过之前保存的end2，获取目的地站名，因为end会变化
        line.add(name); //加入list
        System.out.print(line.get(0));
        //对线路上每一个站点进行遍历（从第二个站点开始，倒数第二个站点结束），判断与前后两个站点是否发生了换乘
        for(int i=1;i<line.size()-1;i++) {
            /*
             * 之所以3个站点要一前一后一共四次调用transfer方法是因为一条路线有两个方向
             * 如顺着走就是高新，火车南站，三瓦窑，逆着走就是三瓦窑，火车南站，高新
             * 注，地铁并没有顺逆的方向，这里的顺逆是指的我的station_data文件中标注的顺序
             */
            int x=transfer(line.get(i-1),line.get(i)); 
            int y=transfer(line.get(i),line.get(i-1)); 
            int x1=transfer(line.get(i),line.get(i+1));
            int y1=transfer(line.get(i+1),line.get(i));
            if(x<=0) {    //说明逆着走  
                x=y;
            }
            if(x1<=0) {   //说明逆着走
                x1=y1;
            }
            if(x==x1) {      //表示没换乘
                System.out.print("->"+line.get(i));
                num++;
            }
            else {           //表示换乘
                System.out.print("->"+line.get(i)+"(换乘"+num(x1)+")");
                num++;
            }
        }
        System.out.println("->"+line.get(line.size()-1));
        System.out.println("共"+num+"站");
    }

BFS算法实现最短路径

Copy 22:37:29
import java.util.LinkedList;

public class Graph {
public int num;                     //结点总数
/*
 * LinkedList<Integer> adj[]
 * 一个存放list的数组，其中list中存放的是对应节点的所有邻接点信息,
 * 如adj[1]存储的就是序列号为1的站点的所有邻接点信息,也可以理解为存储所有的边
 */
public LinkedList<Integer> adj[];  
/*
 * 图的构造方法，传入结点总数v
 * 将数组实例化，并将每个数组中的每个list都实例化
 */
public Graph(int v){               
num = v;
adj = new LinkedList[v];
for(int i=0; i<v; ++i) {
adj[i] = new LinkedList<>();
}
}
/*
 * 图的加边方法，传入参数，s和t，二者都是结点的序列号
 *因为是无向图，所以二者的邻接点list都要存储对方的信息
 */
public void addEdge(int s,int t) {
adj[s].add(t);
adj[t].add(s);
}
public int getV() {
return num;
}
public void setV(int v) {
this.num = v;
}
public LinkedList<Integer>[] getAdj() {
return adj;
}
public void setAdj(LinkedList<Integer>[] adj) {
this.adj = adj;
}
}

Copy 22:37:49
public void calc(int start,int end,Graph graph){
if(start<0||end<0) {
return;
}
if(start==end) {
System.out.println("两站点相同");
return;
}
int v=graph.getV();  //得到结点总数
LinkedList<Integer>[] adj=graph.getAdj();  //得到所有边的信息
boolean[] visited = new boolean[v];        //创建访问数组
visited[start] = true;         //设置初始站点已被访问过
Queue<Integer> queue = new LinkedList<>();     //创建辅助队列
queue.add(start);     
int[] prev = new int[v];   //路径数组，记录站点的前一个站点，如prev[q]=w,就表示想要到达q，就必须先经过w
for(int i=0; i<v;i++) {    //初始化为-1
prev[i] = -1;
}
while(queue.size() != 0) {
int w =queue.poll();
for(int i=0; i<adj[w].size();++i) {   //遍历站点 w 的所有邻接站点
int q = adj[w].get(i);     //取出 w 的邻接站点
if(!visited[q]) {      //判断是否访问过
prev[q] = w;         //加入路径数组
if(q == end) {       //如果是终点就结束，调用print方法打印路径
print(prev,start,end);  
return;
}
visited[q] = true;  //如果不是目的地，就设置为已访问过， 
queue.add(q);      //邻接站点入队
}
}
}
}

Copy 22:37:56
private void print(int[] prev, int start,int end) {
int end2=end;    //将end赋值给end2，之后会用到
int num=1;       //用于记录经过的站数，初值为1
Stack<Integer> stack=new Stack<Integer>(); //创建辅助栈
/*
 * 依次将路径数组中的值入栈，利用栈后进先出的特性
 * 循环条件1：prev[end]!=-1 表示已经找到了正确路线，
 * 循环条件2：start!=end，表示已经全部压栈完毕
 */
while(prev[end]!=-1&&start!=end){  
stack.push(prev[end]);  //目的地的前一个站点入栈
end=prev[end];          //将目的地设为目的地的前一个站点，这样循环下去，最终end=start 结束循环
}
List<String> line = new ArrayList<String>();  //创建辅助list line
/*
 * 将栈里的数据依次出栈，并将序列号转换成站名，放进list
 */
while(!stack.empty()){     //只要栈不空
int e=stack.pop();     //出栈
String name=new CDSubway().station_name.get(e); //调用CDSubway的静态变量station_name，根据序列号获取站名
line.add(name);  //将站名加入list
}
String name=new CDSubway().station_name.get(end2); //通过之前保存的end2，获取目的地站名，因为end会变化
line.add(name); //加入list
System.out.print(line.get(0));
//对线路上每一个站点进行遍历（从第二个站点开始，倒数第二个站点结束），判断与前后两个站点是否发生了换乘
for(int i=1;i<line.size()-1;i++) {
/*
 * 之所以3个站点要一前一后一共四次调用transfer方法是因为一条路线有两个方向
 * 如顺着走就是高新，火车南站，三瓦窑，逆着走就是三瓦窑，火车南站，高新
 * 注，地铁并没有顺逆的方向，这里的顺逆是指的我的station_data文件中标注的顺序
 */
int x=transfer(line.get(i-1),line.get(i)); 
int y=transfer(line.get(i),line.get(i-1)); 
int x1=transfer(line.get(i),line.get(i+1));
int y1=transfer(line.get(i+1),line.get(i));
if(x<=0) {    //说明逆着走  
x=y;
}
if(x1<=0) {   //说明逆着走
x1=y1;
}
if(x==x1) {      //表示没换乘
System.out.print("->"+line.get(i));
num++;
}
else {           //表示换乘
System.out.print("->"+line.get(i)+"(换乘"+num(x1)+")");
num++;
}
}
System.out.println("->"+line.get(line.size()-1));
System.out.println("共"+num+"站");
}

标签：总结,end,get,int,adj,每日,line,双人,public
From： https://www.cnblogs.com/copyjames/p/17228493.html

相关文章

  • C++指针总结
    在程序运行时分配的内存空间是需要在运行中释放的，这部分内存称之为堆。智能指针不用自己释放内存，只要没有指针指向内存了，就会自动释放。下面是两种智能指针：shared_ptr允......
  • 2023/3/17 做题技巧总结
    T1对于一道题目，如果描述有类似于“对于\(\forallx,y\in\mathbb{S}\)都有\(x\oplusy\in\mathbb{S}\)（其中\(\oplus\)为任意满足交换律的运算）”的描述时，我......
  • 3.17学习总结
    今天将地铁查询系统写完了，所有功能都可实现，我们参考了网上的表结构，将算法优化了一下，所有功能都可使用。     ......
  • 每日总结-23.3.17
    今天写了打卡关于记录和检测连续打卡时长的代码packagecom.example.daka1;importandroidx.appcompat.app.AppCompatActivity;importandroid.content.Intent;impo......
  • 个人所最偏爱的“游戏的表达”的思考和总结
    思维导图，个人比较喜欢用MindMaster这个思维导图软件，所以会使用这个软件，来整理思绪。《游戏改变世界》中一些个人最为关注的观点个人的话，还是更喜欢，童话，卡通，童真类型的，......
  • 每日总结 3.17
    今天完成了web课程的实验报告一后，继续对查询线路的显示进行了优化处理。页面不会在查询之前显示null，使用foreach进行集合遍历。<%@pagelanguage="java"contentType="......
  • 今日总结
    今天我们讨论了该如何快速遍历地铁的所有车站，由于地铁图过于复杂，再加上今天课很多，因此我们目前还没有商量出结果，根据网上内容，我推测出要使用欧拉回路算法，这部分算法对我们......
  • 3.17学习总结
    今天上web课上机实验学会了网页html的制作实验代码如下<!DOCTYPE html><html>    <head>        <title>信2105-3尹亚博个人主页</title>      ......
  • 3.17 总结
    前言：废掉了T1.线性代数考场时想到了线性基，但是思路仅从基底入手，没想到如何维护这个基的最大值小于\(n\)。题解：容易想到线性代数，相当于就是求任意元素小于\(n\)的......
  • 2023/3/16每日随笔
    今天主要完成了AndroidStudio开发的项目首尾工作，将记事本的添加删除修改的操作进行了完善，加入了闹钟功能，可设置闹铃来提示，同时也进行了打卡功能的完成，但是对于切换角色进......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99