您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
本篇内容介绍了“Java数据结构与算法中环形链表与约瑟夫问题介绍”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
设编号为1,2,....n的n个人围坐一圈,约定编号为k(1<<k<<n)的人开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,知道所有人出列为止,由此产生一个出队编号的序列.
先构成一个有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数据结构与算法中环形链表与约瑟夫问题介绍”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。