Java数据结构之环形链表和约瑟夫问题详解
作者:小黎的培培笔录 发布时间:2023-07-19 11:02:32
一、环形链表
1、创建结点
环形链表其实也很好理解,就是将单链表的头和尾连接起来,就形成了环形链表。
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
2、添加小结点
写一个方法用来添加结点,这个方法我们直接传入需要创建结点的个数,然后再方法中直接创建出一个简单的循环链表。代码解析:
//创建一个first结点,当前没有编号
public Node first = new Node(-1);
public void add(int n){
//其实循环链表,一个结点也可以循环,但这里为了方便后面介绍约瑟夫问题
//我们循环的结点不能少于两个所以做了这个判断。
if (n < 2){
System.out.println("n的值不正确");
return;
}
//辅助结点
Node end = null;
//使用for循环来创建链表
for (int i = 1; i <= n; i++) {
//根据编号创建结点
Node node = new Node(i);
//如果是第一个结点,first头指向第一个结点,end表示尾,回过头来指向first,形成循环
if(i == 1){
first = node;
end = first;
}else{
//先将尾部end的next指向新的结点node,然后end后移指向新的结点,
//再将end的next指向第一个结点first,这样就形成了循环
end.next = node;
end = end.next;
end.next = first;
}
}
}
3、显示循环链表
显示循环链表的方式和单链表的显示方式差不多,关键点在于如何判断循环链表的结束,我们的尾部是指向头部的,所以当尾部的next指向的结点等于头部,就是最后一个结点,此时就退出循环。
public void show(Node first){
//判断循环链表是否为空
if (first.next == first){
System.out.println("列表为空!");
return;
}
//辅助结点
Node temp = first;
//循环打印
while (true){
System.out.println(temp);
//最后一个结点的next等于first,就退出
if (temp.next == first){
break;
}
temp = temp.next;
}
}
二、约瑟夫问题
1、问题描述
约瑟夫(Joseph)问题的一种描述是:编号为1,2,...n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。开始选任一个正整数作为报数上限值m, 从第一个人开始按顺时针方向自1开始顺序报数, 报到m时停止报数。 报m的人出列, 将它的密码作为新的m值。 试设计一个程序求出出列顺序。
2、首先确定圈大小及开始位置
▶ 写一个方法
start :表示从哪一个位置开始
m : 报多少个数,报到m个数的人出列
n :圈总的大小
public void goOutCircle(int start,int m, int n){
}
▶ 确定圈的大小
传入的n要多余两个人才能玩,然后传入的开始位置start不能在总人数之外,符合条件,我们调用前面我们介绍的方法add()进行循环链表的创建。
if (n >= 2 && start <= n){
add(n);
}else {
System.out.println("输入异常!");
return;
}
▶ 确定开始位置
first是指向链表的第一个的,但我们开始的位置可以是任何一个结点,所以先声明辅助结点temp,遍历循环链表,如果结点的data和传入的start的值相等,就找到了开始位置,将first 指向开始位置temp,然后循环就结束了。
Node temp = first;
while (true){
if (temp.data == start){
first = temp;
break;
}
temp = temp.next;
}
3、出圈操作
首先,我们需要一个辅助的结点end,然后假设开始位置在数据2的地方,first和end都指向数据2,数的次数为m = 2。
开始数数,数据3的位置是数数m = 2 的时候,这时数据3应该出圈。
first继续指向要出圈数据的下一个结点,end所在的结点指向first指向的结点,就让数据3出圈了。
结点出圈后,first和end又同时指向一个结点,m 又开始重新计数 ,如此循环下去即可。
Node end = first;
while (true) {
//当总数只有一个的时候,循环结束。
if (n == 1) {
System.out.println("胜利者为" + first + "号");
break;
}
//用for循环,循环次数为 m - 1,因为本身要数一个数
for (int i = 1; i <= m - 1; i++) {
//first指向下一个结点
first = first.next;
//如果找到了要出圈的结点,first是正好指向它的
if (i == m - 1) {
//first指向的这个结点出圈
System.out.println(first + "号出圈");
//每出圈一个,总数减一
n--;
//first继续指向下一个结点
first = first.next;
//此时end还在出圈结点的前一个位置,end的next指向first
end.next = first;
//end也同样指向first指向的结点
end = first;
break;
}
//如果没有到要出圈的结点,end继续跟着first指向同一个结点
end = first;
}
}
4、出圈方法完整代码
public void goOutCircle(int start,int m, int n){
//首先确定圈的大小
if (n >= 2 && start <= n){
add(n);
}else {
System.out.println("输入异常!");
return;
}
//确定数数的位置
Node temp = first;
while (true){
if (temp.data == start){
first = temp;
break;
}
temp = temp.next;
}
//进行遍历
Node end = first;
while (true) {
if (n == 1) {
System.out.println("胜利者为" + first + "号");
break;
}
for (int i = 1; i <= m - 1; i++) {
first = first.next;
if (i == m - 1) {
System.out.println(first + "号出圈");
n--;
first = first.next;
end.next = first;
end = first;
break;
}
end = first;
}
}
}
运行结果:
来源:https://blog.csdn.net/yzh2776680982/article/details/125829711
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 一、添加pom.xml依赖<parent> <groupId>org.springfram
- Feign调用中的两种Header传参方式在Spring Cloud Netflix栈中,各个微服务都是以HTTP接口的形式暴露自身服务的,
- 修改整理的一个通用类,用来操作oracle数据库 十分的方便,支持直接操作sql语句和Hash表操作.现在修补MIS我都用这个类,节约了大
- 创建新的项目的时候,文件名一直追加,不分层对于刚用idea的小白,这个问题困扰了我好几天了,幸好现在还不怎么敲代码,下面给一个详细的解决方案
- 场景我们团队现在面临着多端数据接口对接的问题,为了解决这个问题我们定义了接口对接的规范,前端(安卓,Ios,web前端)和后端进行了数据的格
- 一、Shiro简介:Apache Shiro是一个Java的安全(权限)框架。Shiro 可以非常容易的开发出足够好的应用,其不仅可以用在J
- Comparator是个接口,可重写compare()及equals()这两个方法,用于比价功能;如果是null的话,就是使用元素的默认顺序
- 1.前提已经配置Sleuth,可参考2.什么是Zipkin?官网:https://zipkin.io/大规模分布式系统的APM工具( App
- 在使用NavigationPage导航的时候, 我们可以给里面添加一些功能按钮, 如下所示:<ContentPage.ToolbarI
- 完整代码已上传到GitHub。Web端体验地址:http://47.116.72.33/(只剩一个月有效期)apk下载地址:https://
- 这篇文章主要介绍了Spring如何使用注解的方式创建bean,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 一、String与Date(java.util.Date)互转 1.1 String -&g
- 前言前一篇文章我们熟悉了HikariCP连接池,也了解到它的性能很高,今天我们讲一下另一款比较受欢迎的连接池:Druid,这是阿里开源的一款
- 本文实例讲述了C#基于HttpWebRequest实现发送HTTP请求的方法。分享给大家供大家参考,具体如下:调用第三方API的时候要用到H
- 前几篇主要集中在注册中心eureka的使用上,接下来可以创建服务提供者provider来注册到eureka。demo源码见: https:/
- 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来
- 什么是通用Mapper通用Mapper就是为了解决单表增删改查,基于Mybatis的插件。开发人员不需要编写SQL,不需要在DAO中增加方法
- 在Java中创建一个线程有两种方法:继承Thread类和实现Runnable接口。下面通过两个例子来分析两者的区别:1)继承Thread类p
- 第一次是接触Lambda表达式是在TypeScript中(JavaScript的超集中),当时是为了让TypeScript的this方法外而
- 解决办法:1.VCS--->Enable Version Control Integration2.选择要关联的版本工具补充:git