栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

环形链表实现约瑟夫问题

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

环形链表实现约瑟夫问题

看到网上很多示例编写的代码都不够精练简洁,现对“约瑟夫问题”用JAVA实现如下:

class RoundLinked{

    //头节点
    private Node head=new Node<>();
    //尾节点
    private Node tail=head;
    private int size=0;

    public RoundLinked(int nums){
        make(nums);
        this.size=nums;
    }

    public boolean empty(){
        return head==tail;
    }

    
    public void Josephus(int k,int count){

        if(empty()){
            return;
        }
        if(k>=size){
            System.out.println("k的值不合法");
            return;
        }


        //1.旋转到第k个节点
        int tmpIndex=1;
        do {
            if(k==tmpIndex){
                break;
            }
            head=head.next;
            tail=tail.next;
            tmpIndex++;
        }while (true);


        for (;;){
            if(empty()){
                break;
            }
            //2.开始丢手帕
            for (int i = 0; i < count; i++) {
                head=head.next;
                tail=tail.next;
            }
            System.out.println("死掉:"+head);
            //跳过当前节点
            head= head.next;
            //重连
            tail.next=head;
        }
        //3.留在队列当中的
        System.out.println("幸存:"+head);


    }
    private void make(int nums){
        if(nums<1){
            System.out.println("创建的节点不能为空!");
            return;
        }
        for (int i = 0; i < nums; i++) {
            Node node=new Node(i+1);
            tail.next=node;
            tail=tail.next;
        }
        //将空节点去掉
        head=head.next;
        //首尾相连
        tail.next=head;
    }

    public void ls(){
        if(empty()) return;
        Node cur=head;
        do {
            System.out.println(cur);
            cur=cur.next;
        }while (cur!=head);
    }


    static class Node{
        public T data;
        public Node next;

        public Node(){
            this(null);
        }
        public Node(T data,Node next){
            this.data=data;
            this.next=next;
        }

        public Node(T data){
            this(data,null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }
}

测试:

public class RoundLinkedDemo {
    public static void main(String[] args) {
        RoundLinked linked=new RoundLinked(10);
        linked.Josephus(1,1);
    }
}

结果:

死掉:Node{data=2}
死掉:Node{data=4}
死掉:Node{data=6}
死掉:Node{data=8}
死掉:Node{data=10}
死掉:Node{data=3}
死掉:Node{data=7}
死掉:Node{data=1}
死掉:Node{data=9}
幸存:Node{data=5}

发博客真好玩儿._.

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936778.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号