链表——从0实现一个单向循环链表 & 并且实现约瑟夫问题

小鱼儿 2022-11-21 09:28 158阅读 0赞

# 目录 #

#### 一、什么是约瑟夫问题(Josephus Problem)? ####

#### 二、从0手写一个单向循环链表 ####

#### 三、实现约瑟夫问题 ####

--------------------

## 一、什么是约瑟夫问题(Josephus Problem)? ##

*  [百度百科-约瑟夫问题][-]
 *  以下图为例, 箭头从`1`开始循环数数, 具体数到几自己规定, 下图为例从`1`数到`3`, 然后`3`淘汰, 将箭头指向`被淘汰数`的下一个, 然后继续数, 淘汰`6`, 以此类推…  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]

> 上图淘汰顺序为: 3 6 1 5 2 8 4 7

## 二、从0手写一个单向循环链表 ##

*  该实现直接使用[单向循环链表][Link 1]的内容, 建议从**链表**开始看;  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]  
    **下面代码为`单向循环链表`的具体实现**

###### 1、自定义List接口实现 ######

package com.zy;
    
    /** * Description: 定义动态数组和链表的公共接口 * * @author guizy * @date 2020/3/19 21:50 */
    public interface List<E> { 
    
        /** * 找不到元素返回-1 */
        // 默认就是 public static final修饰
        int ELEMENT_NOT_FOUNT = -1;
    
        /** * 清除所有元素 */
        void clear();
    
        /** * 元素的数量 * * @return */
        int size();
    
        /** * 是否为空 * * @return */
        boolean inEmpty();
    
        /** * 是否包含某个元素 * * @param element * @return */
        boolean contains(E element);
    
        /** * 添加元素到尾部 * * @param element */
        void add(E element);
    
        /** * 获取index位置的元素 * * @param index * @return */
        E get(int index);
    
        /** * 设置index位置的元素 * * @param index * @param element * @return 原来的元素 */
        E set(int index, E element);
    
        /** * 在index位置插入一个元素 * * @param index * @param element */
        void add(int index, E element);
    
    
        /** * 删除index位置的元素 * * @param index * @return 被删除的元素 */
        E remove(int index);
    
        /** * 删除传入的元素 * * @param element */
        void remove(E element);
    
        /** * 查看元素的索引 * * @param element * @return */
        int indexOf(E element);
    }

###### 2、自定义AbstractList实现上面的List ######

package com.zy;
    
    /** * Description: 该类不对外公开,只是为了抽取一些公共的代码 * * @author guizy * @date 2020/3/19 22:13 */
    /* 抽象类是不能被实例化的，所以没有要求实现所有的方法。但是没写出的方法还是隐式的存在的。 当你在定义一个非abstract类继承那个类的话，就一定要全部实现了。 */
    public abstract class AbstractList<E> implements List<E> { 
    
        /** * 元素的数量 */
        protected int size;
    
        /** * 元素的数量 * * @return */
        public int size() { 
            return size;
        }
    
        /** * 是否为空 * * @return */
        public boolean inEmpty() { 
            return size == 0;
        }
    
        /** * 是否包含某个元素 * * @param element * @return */
        public boolean contains(E element) { 
            // 如果element元素可以找到
            return indexOf(element) != ELEMENT_NOT_FOUNT;
        }
    
        /** * 添加元素到尾部 * * @param element */
        public void add(E element) { 
            // elements[size++] = element;
            // 传入数组数量(相当于在最后插入元素)
            add(size, element);
        }
    
        /** * 封装数组越界异常 * * @param index */
        protected void indexOutOfBounds(int index) { 
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
    
        /** * 检查get,remove传入的index是否有效 * * @param index */
        protected void rangeCheck(int index) { 
            if (index < 0 || index >= size) { 
                indexOutOfBounds(index);
            }
        }
    
        /** * 根据index插入元素时,判断index是否有效 * * @param index */
        protected void rangeCheckForAdd(int index) { 
            if (index < 0 || index > size) { 
                indexOutOfBounds(index);
            }
        }
    }

###### 3、SingleCircleLinkedList继承AbstractList ######

package com.zy.single;
    
    import com.zy.AbstractList;
    
    /** * Description: 单向循环链表实现 * * @author guizy * @date 2020/3/19 21:22 */
    public class SingleCircleLinkedList<E> extends AbstractList<E> { 
    
        /* 单向循环链表, 相对于单链表; 我们只需要更高 add、remove方法即可! */
    
        /** * 指向第一个结点 */
        protected Node<E> first;
    
    
        /** * 结点类;为链表的内部类 * * @param <E> */
        protected static class Node<E> { 
    
            //存储元素的信息
            E element;
    
            //指向下一个结点
            Node<E> next;
    
            // 结点构造器
            public Node(E element, Node<E> next) { 
                this.element = element;
                this.next = next;
            }
    
            @Override
            public String toString() { 
                StringBuilder sb = new StringBuilder();
                sb.append(element).append("_").append(next.element);
                return sb.toString();
            }
        }
    
        @Override
        public void clear() { 
            size = 0;
            first = null;
        }
    
        @Override
        public E get(int index) { 
            // 通过node方法找到结点,通过结点的element来获取元素
            return node(index).element;
        }
    
        @Override
        public E set(int index, E element) { 
            // 获取index处的结点
            Node<E> node = node(index);
            E oldElement = node.element;
            node.element = element;
            // 返回的是没覆盖之前的结点元素信息
            return oldElement;
        }
    
        @Override
        public void add(int index, E element) { 
            rangeCheckForAdd(index);
    
            // 当index传0的时候,就会报异常,此时要特殊处理
            if (index == 0) { 
                Node<E> newFirst = new Node<>(element, first);
    
                // 拿到最后一个结点; 判断只有一个结点的情况
                Node<E> last = (size == 0) ? newFirst : node(size - 1);
                // 最后一个结点的next指向头结点
                last.next = newFirst;
                first = newFirst;
    
            } else { 
                // 在index处插入元素,首先要找到它前面的结点
                Node<E> preNode = node(index - 1);
                // 让前面的结点的next指向新创建的结点,新创建的结点指向index处的结点即可
                // 此时index处的结点,就是它前面的结点的next,就是指向index处的结点
                Node<E> newNode = new Node<>(element, preNode.next);
                // 前面的结点的next再指向新的结点
                preNode.next = newNode;
            }
            size++;
        }
    
        @Override
        /** * 返回的是被删除元素的element */
        public E remove(int index) { 
            // 假如被删除的结点为第一个结点
            Node<E> node = first;
            if (index == 0) { 
                if (size == 1) {  // 链表中只有一个元素的时候
                    first = null;
                } else { 
                    Node<E> last = node(size - 1);
                    // first已经指向了第一个结点,如果要删除第一个结点,此时要将first指向第一个结点的next结点
                    first = first.next;
                    last.next = first; // 最后一个结点指向新的第一个结点
                }
            } else { 
                Node<E> preNode = node(index - 1);
                node = preNode.next; // 这个node就是当前被删除的结点
                //preNode.next = preNode.next.next;
                preNode.next = node.next;
            }
            size--;
            return node.element;
        }
    
        @Override
        public void remove(E element) { 
            remove(indexOf(element));
        }
    
        @Override
        /** * element是保存在node里的,传入element,返回该结点的索引 */
        public int indexOf(E element) { 
            Node<E> node = first;
            if (element == null) { 
                // 因为element都在node中,所以通过next来遍历node
                for (int i = 0; i < size; i++) { 
                    if (node.element == null) return i;
                    node = node.next;
                }
            } else { 
                for (int i = 0; i < size; i++) { 
                    if (element.equals(node.element)) return i;
                    node = node.next;
                }
            }
            return ELEMENT_NOT_FOUNT;
        }
    
        /** * 传入一个index,返回该index位置的结点对象 * * @param index * @return */
        private Node<E> node(int index) { 
            // 当传入非法index就会报异常
            rangeCheck(index);
            /* 通过first去寻找结点,看需要next几次,找到该结点; 可以发现,next的次数和index有关系,index为几,就需要next几次 */
            Node<E> node = first;
            for (int i = 0; i < index; i++) { 
                node = node.next;
            }
            return node;
        }
    
        @Override
        public String toString() { 
            // 打印格式: size=3, [10, 20, 30]
            // 使用StringBuilder 效率高一些
            StringBuilder string = new StringBuilder();
            string.append("size=").append(size).append(", [");
            Node<E> node = first;
            for (int i = 0; i < size; i++) { 
                string.append(node.toString());
                if (i != size - 1) { 
                    string.append(", ");
                }
                node = node.next;
            }
            string.append("]");
            return string.toString();
        }
    }

## 三、实现约瑟夫问题 ##

在上面`单向循环链表`的实现基础上, 增加`1`个成员变量, `3`个方法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]  
**`核心实现:`**

/** * 指向某一节点 */
      private Node<E> current;
      
    
      /** * 让current节点重置到first节点 */
      public void reset() { 
          current = first;
      }
    
      /** * 移动current节点, 指向下一个节点 * @return */
      public E next() { 
          if (current == null) return null;
    
          current = current.next;
          return current.element;
      }
    
      /** * 删除current指向的节点, 删除成功后, 指向下一个节点 * @return 被删除节点的element */
      public E remove() { 
          // 当current没有指向first的时候, 初始化为null
          if (current == null) return null;
    
          // 删除之前要拿到其下一个节点; 如果只有一个节点的时候, current.next还是current本身
          Node<E> next = current.next;
          // 删除当前current所指向的节点
          E element = remove(indexOf(current.element));
          // 当只有一个节点的时候, current.next指向的还是它本身(因为是循环链表), 所以current一直被引用着, 没有被销毁
          if (size == 0) { 
              current = null;
          } else { 
              // 如果只有一个节点了, current指向的就是它自己, 它就不会被销毁, 所以上面做处理
              current = next; // 删除后, current指向它下一个
          }
          return element;
      }

**测试:**

static void testJosephusProblem() { 
         SingleCircleLinkedList<Integer> linkedList = new SingleCircleLinkedList<>();
         for (int i = 1; i <= 8; i++) { 
             linkedList.add(i);
         }
    
         //指向头结点
         linkedList.reset();
    
         while (!linkedList.inEmpty()) { 
             linkedList.next();
             linkedList.next();
             System.out.print(linkedList.remove() + " ");
         }
     }

**输出:**

和开篇图示顺序一致~

![在这里插入图片描述][20201030230720340.png_pic_center]

[-]: https://baike.baidu.com/item/%E7%BA%A6%E7%91%9F%E5%A4%AB%E9%97%AE%E9%A2%98/3857719?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b352680f3f3f465ca1953c2fdd47d535.png
[Link 1]: https://blog.csdn.net/m0_37989980/article/details/105263938
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/c70c545f9c024fe3af45819d96641bbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/0c058d97c6fd46918d50e9cfd1d07254.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/2280d9d7e9e54cc1ab71ae06100ecfa0.png
[20201030230720340.png_pic_center]: /images/20221120/ac85eb2e39894f2d82382d7ed2e5364b.png