【java数据结构与算法学习】约瑟夫问题

桃扇骨 2022-05-30 00:45 136阅读 0赞

约瑟夫问题：n个人围成一圈，从第一个人开始报数，数到m的人出局，然后从下一个人接着报数，直到最后一个人，求出局顺序

约瑟夫问题在数据结构中是一个循环链表。

循环链表是在单链表的基础上改进的，当单链表的尾节点指向头节点构成一个环，就成了一个循环链表。

下面就是约瑟夫问题在java中的代码实现方式。

public class CircleList<AnyType> {
        private static class Node<AnyType>{
            private AnyType data;
            public Node<AnyType> next;
    
            public Node(AnyType data, Node<AnyType> next){
                this.data = data;
                this.next = next;
            }
            public Node(){}
        }
        /**
         * @param n 参与游戏的人数
         * */
        public Node<AnyType> createList(int n){
            //创建链表头节点
            Node<AnyType> header = new Node();
    
            Node<AnyType> p = header;
            Node<AnyType> temp = null;
            //尾插法创建链表
            if (n > 0){
                for (int i = 1;i<=n;i++){
                    temp = new Node(i,null);
                    p.next = temp;
                    p = temp;
                }
                //表尾指向首节点，而不是头节点，这样才符合约瑟夫问题
                temp.next = header.next;
            }
            //返回首节点
            return header.next;
        }
        
        public static void main(String[] args) {
    
            int n = 41; //人数
            int m = 3;  //每第三个人出局
    
            //创建一个循环链表，一共41人参加游戏
            CircleList<Integer> list = new CircleList<>();
            Node L = list.createList(n);
            //list.printList(L);
    
    
            Node p = L;
            //如果不是空表（游戏中还有人）
            while(p.next != p){
                //走到要删除的前一个元素的位置。如当前是1，则走到了2的位置，3是我们要出局的元素
                for (int i = 1;i< (m-1);i++ ){
                    p = p.next;
                }
                //打印出局人的信息
                System.out.println(p.next.data);
                //删除出局的人第二个节点指向了第四个节点
                p.next = p.next.next;
                //将指针指向第四个元素，相当于刚开始指针在第一个元素的位置。重复执行以上操作。
                p = p.next;
            }
    
        }
    }