数据结构+算法--环形链表的创建和遍历 与 约瑟夫问题的解决
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构+算法--环形链表的创建和遍历 与 约瑟夫问题的解决,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3060字,纯文字阅读大概需要5分钟。
内容图文
单向环形链表&约瑟夫问题
什么是单向环形链表
单向环形链表的创建和遍历
约瑟夫问题
约瑟夫问题解题思路
以下代码约瑟夫问题解决思路与上图解决思路有一点点区别,区别:1步骤应该改为“需要创建一个辅助指针(变量)helper,事先应该让helper指向序号为 startNo的小孩节点 的 前一个节点;再让first指向序号为 startNo的小孩节点。”
代码实现
import java.util.Scanner;
public class Josephu {
public static void main(String[] args) {
//测试一把看看构建环形链表和遍历是否ok
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5); //加入5个小孩节点
circleSingleLinkedList.showBoy();
circleSingleLinkedList.countBoy(1,2,5);
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
//创建一个first节点,当前没有编号
private Boy first = null;
//添加小孩节点,构成一个环形链表
public void addBoy(int nums){
//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;
curBoy = first;
curBoy.next = first; //构成环
}else{
curBoy.next = boy;
curBoy = boy;
boy.next = first;
}
}
}
//遍历当前的环形链表
public void showBoy(){
//先判断链表是否为空
if(first == null){
System.out.println("当前环形链表中没有任何小孩");
return;
}
//因为first不能动,因此我们需要使用一个 辅助指针curBoy 来完成遍历
Boy curBoy = first;
while(true){
System.out.printf("小孩的编号 %d \n",curBoy.no);
if(curBoy.next == first){ //说明已经遍历完毕
break;
}
curBoy = curBoy.next; //curBoy后移
}
System.out.println("---------------------------");
}
//根据用户的输入,计算出小孩出圈的顺序
/**
*
* @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,事先应该指向序号为 startNo的小孩节点 的 前一个节点
while(true){
if(helper.next.no == startNo){ //说明helper已经指向序号为 startNo的小孩节点 的 前一个节点
break;
}
helper = helper.next;
}
first = helper.next; //让first指向序号为 startNo的小孩节点
//当小孩报数时,让first 和 helper 同时移动 countNum - 1 次,然后让此时first指向的小孩节点出圈
//这里是一个循环操作,直到圈中只有一个节点
while(true){
if(first == helper){ //说明圈中只有一个节点
break;
}
//让first 和 helper 同时移动 countNum - 1 次
for (int i = 1; i <= countNum - 1 ; i++) {
first = first.next;
helper = helper.next;
}
//这时first指向的节点,就是要出圈的小孩节点
System.out.printf("小孩 %d 出圈\n",first.no);
//这是将first指向的小孩节点出圈
first = first.next;
helper.next = first;
}
System.out.printf("最后留在圈中的小孩编号为 %d \n",first.no);
}
}
//创建一个boy类,表示一个节点
class Boy{
public int no; //编号
public Boy next; //指向下一个节点,默认null
public Boy(int no){
this.no = no;
}
}
结果截图:
内容总结
以上是互联网集市为您收集整理的数据结构+算法--环形链表的创建和遍历 与 约瑟夫问题的解决全部内容,希望文章能够帮你解决数据结构+算法--环形链表的创建和遍历 与 约瑟夫问题的解决所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。