Java数据结构之环形链表和约瑟夫问题详解

目录
  • 一、环形链表
    • 1、创建结点
    • 2、添加小结点
    • 3、显示循环链表
  • 二、约瑟夫问题
    • 1、问题描述
    • 2、首先确定圈大小及开始位置
    • 3、出圈操作
    • 4、出圈方法完整代码
  • 总结

一、环形链表

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;
            }
        }
    }

运行结果:

总结

到此这篇关于Java数据结构之环形链表和约瑟夫问题详解的文章就介绍到这了,更多相关Java环形链表和约瑟夫问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java用单向环形链表来解决约瑟夫环Josepfu问题

    简单介绍 如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是让尾节点指向头结点. 单向环形链表应用场景:Josephu(约瑟夫.约瑟夫环)问题: 设编号为1, 2, - n的n个人围坐一圈,约定编号为k (1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列. 代码实现 节点类 //节点类 class JNode { private

  • java使用链表实现约瑟夫环

    约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列:他的下一个人又从1开始报数,数到m的那个人又出列:依此规律重复下去,直到圆桌周围的人全部出列.求出出队序列. 采用链表实现,结点数据就是编号. package com.dm.test; public class Test2 { public static void main(String[] args) { //头结点 Node root = new Nod

  • Java数据结构与算法之双向链表、环形链表及约瑟夫问题深入理解

    目录 一.双向链表 二.环形链表及其应用:约瑟夫问题 环形链表图示 构建一个单向的环形链表思路 遍历环形链表 约瑟夫问题 一.双向链表 使用带head头的双向链表实现 - 水浒英雄排行榜管理单向链表的缺点分析: 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找. 单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除节点时,总是找到temp,temp时待删除节点的前一个节点(认真体会). 分析双向链表的遍历,添加,修改,删除的操作思路 1.遍历

  • java 实现约瑟夫环的实例代码

    复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus {    private static class Node{        int No;        Node next;        public Node(int No){            this

  • java基于双向环形链表解决丢手帕问题的方法示例

    本文实例讲述了java基于双向环形链表解决丢手帕问题的方法.分享给大家供大家参考,具体如下: 问题:设编号为1.2--n的几个小孩围坐一圈,约定编号为k(1=<k<=n)的小孩从1开始报数,数到m的那个出列,他的下一位又从1开始报数,数到m的那个人又出列,直到所有人出列为止,由此产生一个出队编号的序列. 我们现在用一个双向环形链表来解这一问题.先来看看下面这幅图: 圆圈代表一个结点,红色的指针指向下一个元素,紫色的指针指向上一个元素.first指针指向第一个元素,表明第一个元素的位置,curs

  • Java 数据结构与算法系列精讲之环形链表

    目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li

  • Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • Java解决约瑟夫问题代码实例

    复制代码 代码如下: package list; import java.util.ArrayList; /** * Java约瑟夫问题: n个人(不同id)围成一个圈,从startId(任意数)个开始报数m(任意数)个数,数m的人出列排成新队列,m清零, * 然后又从下一个人开始数m个数开始,数到m就出列接在新队列尾部,如此重复,知道所有人都出列为止. * 打印 出列后的新队列 * * eg * int n = 10;//总人数 * int m = 3;   //报数个数 * int star

  • Java数据结构之环形链表和约瑟夫问题详解

    目录 一.环形链表 1.创建结点 2.添加小结点 3.显示循环链表 二.约瑟夫问题 1.问题描述 2.首先确定圈大小及开始位置 3.出圈操作 4.出圈方法完整代码 总结 一.环形链表 1.创建结点 环形链表其实也很好理解,就是将单链表的头和尾连接起来,就形成了环形链表. public class Node { public int data; public Node next; public Node(int data) { this.data = data; } @Override publi

  • Java数据结构之图的两种搜索算法详解

    目录 前言 深度优先搜索算法 API设计 代码实现 广度优先搜素算法 API设计 代码实现 案例应用 前言 在很多情况下,我们需要遍历图,得到图的一些性质,例如,找出图中与指定的顶点相连的所有顶点,或者判定某个顶点与指定顶点是否相通,是非常常见的需求. 有关图的搜索,最经典的算法有深度优先搜索和广度优先搜索,接下来我们分别讲解这两种搜索算法. 学习本文前请先阅读这篇文章 [数据结构与算法]图的基础概念和数据模型. 深度优先搜索算法 所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,

  • Java数据结构之图的领接矩阵详解

    目录 1.图的领接矩阵(Adjacency Matrix)存储结构 2.图的接口类 3.图的类型,用枚举类表示 4.图的领接矩阵描述 测试类 结果 1.图的领接矩阵(Adjacency Matrix)存储结构 图的领接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图.一个一位数组存储图中顶点信息,一个二维数组(称为领接矩阵)存储图中的边或弧的信息. 举例 无向图 无向图的领接矩阵的第i行或第i列的非零元素个数正好是第i个顶点的度. 有向图 有向图的领接矩阵的第i行的非零元素个

  • Java数据结构之线段树中的懒操作详解

    目录 一.问题提出 二.区间更新 三.区间查询 四.实战 1.问题描述 2.输入 3.代码 4.测试 一.问题提出 对于线段树,若要求对区间中的所有点都进行更新,可以引入懒操作. 懒操作包括区间更新和区间查询操作. 二.区间更新 对 [l,r] 区间进行更新,例如将 [l,r] 区间所有元素都更新为 v,步骤如下. 1.若当前节点区间被查询区间[l,r]覆盖,则仅对该节点进行更新并做懒标记,表示该节点已被更新,对该节点的子节点暂不更新. 2.判断是在左子树中查询还是在右子树中查询.在查询过程中,

  • Java数据结构之图的路径查找算法详解

    目录 前言 算法详解 实现 API设计 代码实现 前言 在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地 城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市.这类问题翻译成专业问题就是: 从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径. 例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4. 如果对图的前置知识不了解,请查看系列文章: [数据结构与算法]图的基础概念和数据

  • java数据结构与算法数组模拟队列示例详解

    目录 一.什么是队列 二.用数组来模拟队列 一.什么是队列 队列是一个有序列表,可以用数组或者链表来实现. 遵循先入先出的原则,即:先存入队列的数据,要先取出.后存入的的数据,后取出. 看一张队列的模拟图,1,2,3表示同一个队列Queue.在队列中有2个指针,front表示队首,rear表示队尾. 图1中表示队列里还没有数据,所以front跟rear初始化都是-1. 当图2中有数据进行存入的时候,front没变,而rear则随着数据的增多而改变.存入了4个数据,于是rear=3. 再看图3,f

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • java数据结构与算法之简单选择排序详解

    本文实例讲述了java数据结构与算法之简单选择排序.分享给大家供大家参考,具体如下: 在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想: 选择排序的基本算法思想: 每一趟在 n-i+1 (i=1,2,3,--,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 简单选择排序: 设所排序序列的记录个数为n.i取1,2,-,n-1,从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小的记录,与第i个记录交换.执行n-

  • python环形单链表的约瑟夫问题详解

    题目: 一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点. 这个问题就是著名的约瑟夫问题. 代码: 首先给出环形单链表的数据结构: class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedL

随机推荐