Java数据结构与算法中环形链表与约瑟夫问题介绍

本篇内容介绍了“Java数据结构与算法中环形链表与约瑟夫问题介绍”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

 Josephu问题

设编号为1,2,....n的n个人围坐一圈,约定编号为k(1<<k<<n)的人开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,知道所有人出列为止,由此产生一个出队编号的序列.

循环链表处理Josephu问题

先构成一个有n个节点的单向循环链表,然后由k节点器从1开始计数,计到m时,对应节点从链表删除,然后再从被删除节点的下一个节点又从1开始计数,直到最后一个节点从链表中删除.

构建一个单向环形链表

1. 先创建第一个节点,让first指向该节点,并形成环.

2. 后面每创建一个新的节点,就把该节点,加入环形链表即可.

代码案例

package com.structures.linkedlist;  public class Josephu {     public static void main(String[] args) {         CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();         circleSingleLinkedList.addBoy(5);         circleSingleLinkedList.showBoys();         circleSingleLinkedList.countBoy(1,2,5);          /*         小孩的编号:1         小孩的编号:2         小孩的编号:3         小孩的编号:4         小孩的编号:5         小孩2出圈         小孩4出圈         小孩1出圈         小孩5出圈         最后留在圈中的小孩编号3         */     } }  //创建一个环形的单向链表 class CircleSingleLinkedList {     //创建一个first节点,当前没有编号     private Boy first = new Boy(-1);      //添加小孩节点,构建成一个环形链表     public void addBoy(int nums) {         if (nums < 1) {             System.out.println("nums 值不正确");             return;         }         Boy curBoy = null;         //for循环创建环形链表         for (int i = 1; i <= nums; i++) {             Boy boy = new Boy(i);             //如果是第一个小孩             if (i == 1) {                 first = boy;                 first.setNext(first);                 curBoy = first;//让curBoy指向第一个             } else {                 curBoy.setNext(boy);                 boy.setNext(first);                 curBoy = boy;             }         }     }      //遍历当前环形链表     public void showBoys() {         if (first.getNext() == null) {             System.out.println("没有任何小孩~~");             return;         }         Boy temp = first;         while (true) {             System.out.println("小孩的编号:" + temp.getNo());             if (temp.getNext() == first) {                 break;             }             temp = temp.getNext();         }     }      /**      * 根据用户输入,计算小孩出圈顺序      *      * @param startNo  表示从第几个小孩开始计数      * @param countNum 表示数几下      * @param nums     表示多少个小孩在圈中      */     public void countBoy(int startNo, int countNum, int nums) {         //先进行数据校验         if (first == null || startNo < 1 || startNo > nums) {             System.out.println("参数输入有误,请重新输入");             return;         }         //创建一个辅助指针,帮助完成小孩出圈         Boy helper = first;         //让helper指向环形链表的最后节点         while (helper.getNext() != first) {             helper = helper.getNext();         }         //报数前,先让helper和first移动,移动k-1次,这样first定位到开始节点,helper紧接着first         for (int i = 0; i < startNo - 1; i++) {             first = first.getNext();             helper = helper.getNext();         }         //报数时,让first和helper指针同时移动,然后出圈         while (true) {             //当圈中只有一个节点             if (helper == first) {                 break;             }             //让first和helper指针同时移动countNum - 1次             for (int i = 0; i < countNum - 1; i++) {                 first = first.getNext();                 helper = helper.getNext();             }             //此时first节点就是小孩要出圈的节点             System.out.printf("小孩%d出圈\n", first.getNo());             first = first.getNext();             helper.setNext(first);         }         System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());     } }  //创建一个Boy类,表示节点 class Boy {     private int no;//编号     private Boy next;//指向下一个节点,默认null      public Boy(int no) {         this.no = no;     }      public int getNo() {         return no;     }      public void setNo(int no) {         this.no = no;     }      public Boy getNext() {         return next;     }      public void setNext(Boy next) {         this.next = next;     } }

“Java数据结构与算法中环形链表与约瑟夫问题介绍”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！