Java两种方式实现约瑟夫环完整版

学校作业，顺便分享

 

单向循环链表：

package test1;

/**
 * 约瑟夫环(单向链表)
 * 
 * @author xu yiqing
 *
 */
public class josephcircle1 {

    private mylinkedlist linkedlist;
    private integer size;

    /**
     * 由单向链表生成单向循环链表
     * 
     * @param linkedlist 单项链表
     * @return 生成的约瑟夫环的第一个node
     */
    public node<integer> getjosephcircle(mylinkedlist linkedlist) {
        try {
            this.linkedlist = linkedlist;
            this.size = this.linkedlist.getlinkedlistsize();
            
            node<integer> head = linkedlist.getheadnode();
            node<integer> tail = linkedlist.getlastnode();
            tail.setnext(head);
            
            this.linkedlist.beginnode = null;
            
            return head;
        } catch (exception e) {
            e.printstacktrace();
            return null;
        }
    }

    /**
     * 删除约瑟夫环的一个node
     * 
     * @param node 想要删除的node
     * @return 返回删除node的前一个node
     */
    @suppresswarnings({ "rawtypes", "unchecked" })
    public node deletefromcircle(node node) {
        
        node flag = node.next;
        
        for (int i = 0; i < this.size - 2; i++) {
            flag = flag.next;
        }
        flag.next = flag.next.next;
        
        node = flag;
        
        this.size--;
        return node;
    }

    /**
     * 自定义链表类
     * 
     * @author xu yiqing
     *
     */
    static class mylinkedlist {
        private integer size;
        @suppresswarnings("rawtypes")
        private node beginnode;

        /**
         * 构造方法
         */
        public mylinkedlist() {
            doclear();
            
            this.beginnode = new josephcircle1().new node<integer>(null, null);
        }

        /**
         * 获取第一个node
         * 
         * @return 第一个node
         */
        @suppresswarnings("unchecked")
        public node<integer> getheadnode() {
            return beginnode.next;
        }

        /**
         * 在尾部添加一个新node
         * 
         * @param value node的值
         */
        @suppresswarnings({ "rawtypes", "unchecked" })
        public void addattail(integer value) {
            node newnode = new josephcircle1().new node<integer>(value, null);
            if (this.size == 0) {
                beginnode.next = newnode;
            } else {
                getnode(this.size - 1).next = newnode;
            }
            this.size++;
        }

        /**
         * 获取指定的node
         * 
         * @param index node索引
         * @return 获取到的node
         */
        @suppresswarnings({ "finally", "unchecked" })
        public node<integer> getnode(integer index) {
            if (index < 0 || index >= size) {
                try {
                    throw new exception("越界");
                } catch (exception e) {
                    e.printstacktrace();
                } finally {
                    return null;
                }
            } else {
                @suppresswarnings("rawtypes")
                node flag = beginnode;
                for (int i = 0; i <= index; i++) {
                    flag = flag.getnext();
                }
                return flag;
            }

        }

        /**
         * 删除指定的node
         * 
         * @param index 删除的node的索引
         */
        @suppresswarnings({ "rawtypes", "finally", "unchecked" })
        public void deletenode(integer index) {
            if (index < 0 || index >= size) {
                try {
                    throw new exception("越界");
                } catch (exception e) {
                    e.printstacktrace();
                } finally {
                    return;
                }
            } else {
                if (this.beginnode != null) {
                    node flag = beginnode;
                    for (int i = 0; i <= index; i++) {
                        flag = flag.getnext();
                    }
                    flag.next = flag.getnext().getnext();
                }
            }
            this.size--;
        }

        /**
         * 清空链表
         */
        private void doclear() {
            this.size = 0;
            this.beginnode = null;
        }

        /**
         * 获取最后一个node
         * 
         * @return 最后一个node
         */
        public node<integer> getlastnode() {
            return getnode(this.size - 1);

        }

        /**
         * 获取链表的大小
         * 
         * @return 大小
         */
        @suppresswarnings("unchecked")
        public integer getlinkedlistsize() {
            integer size = 0;
            node<integer> flag = beginnode;
            while ((flag = flag.getnext()) != null) {
                size++;
            }
            return size;
        }
    }

    /**
     * 自定义链表节点
     * 
     * @author xu yiqing
     *
     * @param <type> 泛型
     */
    class node<type> {

        private type value;
        private node<type> next;

        public node(type value, node<type> next) {
            super();
            this.value = value;
            this.next = next;
        }

        public type getvalue() {
            return value;
        }

        public void setvalue(type value) {
            this.value = value;
        }

        public node<type> getnext() {
            return next;
        }

        public void setnext(node<type> next) {
            this.next = next;
        }

    }

}

 

单向循环链表测试类：

package test1;

import java.util.scanner;

import test1.josephcircle1.mylinkedlist;
import test1.josephcircle1.node;
/**
 * 测试类
 * @author xu yiqing
 *
 */
public class test1 {
    @suppresswarnings("rawtypes")
    public static void main(string[] args) {
        josephcircle1 circle = new josephcircle1();
        mylinkedlist linkedlist = new mylinkedlist();
        scanner sc = new scanner(system.in);
        int m = sc.nextint();
        int num = sc.nextint();
        for (int i = 0; i < num; i++) {
            linkedlist.addattail(i + 1);
        }
        node node = circle.getjosephcircle(linkedlist);

        for(int i=0;i<num;i++) {
            for (int j = 0; j < (m-1); j++) {
                node = node.getnext();
            }
            //由于要删除，需要先显示出来
            system.out.print(node.getvalue());
            
            node=circle.deletefromcircle(node);
            node=node.getnext();

        }
        sc.close();
    }
    
}

 

 

顺序表：

package test1;

/**
 * 顺序表实现约瑟夫环
 * 
 * @author xu yiqing
 *
 */
public class josephcircle2 {

    /**
     * 约瑟夫环构造方法
     * 
     * @param number   将数据添加到顺序表
     * @param start    约瑟夫环开始索引
     * @param distance 删除元素间隔
     */
    public josephcircle2(int number[], int start, int distance) {
        mylinearlist list = new mylinearlist(number.length);
        for (int i = 0; i < number.length; i++) {
            list.append(number[i]);
        }
        int i = start;
        while (list.length() > 1) {
            i = (i + distance - 1) % list.length();
            system.out.print(list.get(i));
            list.remove(i);
        }
        system.out.print(list.get(0));
    }

    /**
     * 自定义顺序表
     * 
     * @author xu yiqing
     *
     */
    class mylinearlist {
        private integer[] elements;
        private integer len;

        /**
         * 构造方法
         * 
         * @param 拷贝顺序表
         */
        public mylinearlist(mylinearlist list) {
            this.len = list.len;
            this.elements = new integer[list.elements.length];
            for (int i = 0; i < list.elements.length; i++) {
                this.elements[i] = list.elements[i];
            }

        }

        /**
         * 构造方法
         * 
         * @param size 大小
         */
        public mylinearlist(int size) {
            this.elements = new integer[size];
            this.len = 0;
        }

        /**
         * 判空
         * 
         * @return
         */
        public boolean isempty() {
            return this.len == 0;
        }

        /**
         * 大小
         * 
         * @return 大小
         */
        public int length() {
            return this.len;
        }

        /**
         * 获取某个元素
         * 
         * @param index 所有
         * @return 元素
         */
        public integer get(int index) {
            if (index >= 0 && index < this.len) {
                return this.elements[index];
            } else {
                return null;
            }
        }

        /**
         * 设置某个元素
         * 
         * @param i     索引
         * @param value 值
         */
        public void set(int i, integer value) {
            if (i >= 0 && i < this.len)
                this.elements[i] = value;
            else
                try {
                    throw new exception("无法设置");
                } catch (exception e) {
                    e.printstacktrace();
                }

        }

        /**
         * 插入某个元素
         * 
         * @param i     索引
         * @param value 值
         */
        public void insert(int i, integer value) {
            if (i < 0) {
                i = 0;
            }
            if (i > this.len) {
                i = this.len;
            }
            if (this.len == this.elements.length) {
                integer[] temp = this.elements;
                this.elements = new integer[this.elements.length + 1];
                for (int j = 0; j < temp.length; j++) {
                    this.elements[j] = temp[j];
                }
            }

            for (int j = this.len - 1; j >= i; j--) {
                this.elements[j + 1] = this.elements[j];
            }
            this.elements[i] = value;
            this.len++;
        }

        /**
         * 在尾部添加
         * 
         * @param value 值
         */
        public void append(integer value) {
            this.insert(this.len, value);
        }

        /**
         * 删除某个元素
         * 
         * @param i 索引
         * @return 删除是否成功
         */
        public boolean remove(int i) {
            if (this.len == 0 || i < 0 || i >= this.len) {
                return false;
            }
            for (int j = i; j < this.len - 1; j++) {
                this.elements[j] = this.elements[j + 1];
            }
            this.elements[this.len - 1] = null;
            this.len--;
            return true;
        }

        /**
         * 清除
         * 
         * @return
         */
        public boolean removeall() {
            this.len = 0;
            return true;
        }

        /**
         * 销毁
         * 
         * @return
         */
        public boolean destroy() {
            this.removeall();
            this.elements = null;
            return true;
        }

        /**
         * 搜寻某个元素是否存在
         * 
         * @param value 值
         * @return 找不到返回-1
         */
        public integer search(integer value) {
            int index = this.indexof(value);
            return index == -1 ? null : this.elements[index];
        }

        /**
         * 根据值定位第一个索引
         * 
         * @param value 值
         * @return 第一个索引
         */
        private int indexof(integer value) {

            for (int i = 0; i < this.len; i++) {
                if (this.elements[i].equals(value)) {
                    return i;
                }
            }
            return -1;

        }

        /**
         * 是否包含
         * 
         * @param value 值
         * @return 第一个值的索引
         */
        public boolean contain(integer value) {
            return this.indexof(value) >= 0;
        }

        /**
         * 判断某个对象是否和该顺序表一致
         */
        public boolean equals(object object) {
            if (this == object)
                return true;
            if (object instanceof mylinearlist) {
                mylinearlist list = (mylinearlist) object;
                if (list.length() == this.length()) {
                    for (int i = 0; i < list.length(); i++) {
                        if (!this.get(i).equals(list.get(i)))
                            return false;
                    }
                    return true;
                }
            }
            return false;
        }
    }

}

 

 

测试类：

package test1;

import java.util.scanner;
/**
 * 测试类
 * @author xu yiqing
 *
 */
public class test2 {
    public static void main(string[] args) {
        
        scanner sc = new scanner(system.in);
        int m = sc.nextint();
        int n=sc.nextint();
        
        int[] arr=new int[n];
        for(int i=0;i<arr.length;i++) {
            arr[i]=i+1;
        }
        new josephcircle2(arr, 0, m);
        sc.close();

    }
}