约瑟夫问题–循环链表实现
- 问题:设编号为1、2………..n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它(m)的下一位又从1开始报数,数到m的那个人又出列,直到所有人出列为止,由此产生一个出队的编号的顺序
- 设置:n是5,m是2,k是1,从第一个人开始报数。
单向环形链表实现
-
构建一个单向的环形链表思路:
- 先创建第一个节点,让first指向该节点,并形成环形,即
first.next=first
- 再每次创建一个新节点时就把该节点加入到已有的环形链表中即可
- 先创建第一个节点,让first指向该节点,并形成环形,即
-
遍历环形链表
-
先让一个辅助变量指针
curBoy
指向first节点 -
然后通过一个while循环遍历该环形链表即可
newBoyNodePre.next=newBoyNode;
newBoyNode.next=first;
curBoy=newBoyNodePre.next;
或者curBoy=newBoyNode;
- 当
curBoy.next=first;
则遍历结束
- 当
代码实现
- 创建指定个数的环形链表和展示环形链表
package com.guodaxia.josepfu; /** * @ author Guo daXia * @ create 2022/11/16 */ public class Josepfu { public static void main(String[] args) { CircleSingleLinkedList list = new CircleSingleLinkedList(); list.addBoy(5); list.showBoy(); } } /** * 创建一个单向循环链表 */ class CircleSingleLinkedList{ //创建一个first节点 private Boy first = null; //添加小孩节点,构建成一个环形的链表 public void addBoy(int nums){ if (nums<1){ System.out.println("nums不正确"); return; } //辅助指针,帮助遍历节点 Boy curBoy = null; for (int i = 1;i<=nums;i++){ //根据编号,创建小孩节点 Boy boy = new Boy(i); if (i==1){//如果是添加第一个小孩时,较为特殊 first=boy; first.setNext(first);//boy的next为first,构成环。 curBoy=first;//让curBoy指向第一个小孩 }else { curBoy.setNext(boy); boy.setNext(first); curBoy=boy; } } } //遍历当前环形链表 public void showBoy(){ if (first==null){ System.out.println("没有任何小孩~"); return; } //因为first不能动,所以我们任然使用一个辅助指针进行遍历 Boy curBoy = first; //从first第一个男孩开始遍历 while (true){ System.out.printf("小孩的编号%d\n",curBoy.getNo()); if (curBoy.getNext()==first){break;} curBoy= curBoy.getNext();//使辅助指针后移,达成循环迭代条件 } } } /** * 创建一个Boy类,表示一个节点 */ class Boy{ private int no;//编号 private Boy next;//指向下一个节点,默认位null public Boy(int no) {this.no = no;} public int getNo() {return no;} public Boy getNext() {return next;} public void setNo(int no) {this.no = no;} public void setNext(Boy next) {this.next = next;} }
- 实现逻辑,按用户指定从那个小孩开始报数,直到报到 几下数结束,并将最后一个报数小孩出圈。
/** * 根据用户输入,计算出小孩出圈的顺序 * @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; //1.先让helper指向环形链表的最后一个节点 while (true){ if (helper.getNext()==first){ break; } helper=helper.getNext(); } //2.小孩报数前,先把helper和first移动startNo-1次(startNo是从第几个小孩开始报数) for (int i=0;i<startNo-1;i++){ first=first.getNext(); helper=helper.getNext(); } while (true){ if (helper==first){//说明场上只剩一个小孩了 break; } //3.当小孩开始报数时,让helper和first指针同时移动countNum-1次(countNum是报几下) for (int j=0;j<countNum-1;j++){ first=first.getNext(); helper=helper.getNext(); } //4.这时就可以将first指针指向的小孩节点出圈,原来的first指向的节点就会被回收 System.out.printf("编号为%d的小孩出圈\n",first.getNo()); first=first.getNext();//first指针下移一位 helper.setNext(first);//将helper.next指向first } //跳出循环,可以把最后一个小孩节点打印出来、 System.out.printf("场上剩下的最后一个编号为%d \n",helper.getNo()); } }
-
原文地址:http://www.cnblogs.com/container-simple/p/16901268.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性