数据结构与算法-单向环形链表与约瑟夫问题（续思路与代码）

news/2024/11/14 19:32:47/

上一篇写的单向环形链表与约瑟夫问题简介和举例，这篇写思路和代码~

目录

3.思路

3.1创建环形链表：

3.2遍历环形链表：

3.3产生出圈序号：

4.代码

4.1在构建环形链表时添加节点：

4.2遍历环形链表：

4.3产生出圈序号：

4.4完整代码：

5.运行结果

3.思路

3.1创建环形链表：

先创建一个节点，有个first变量指向这个节点，这个节点的next也是指向自己。还有个curBoy变量

然后新加一个节点，还有个boy变量。boy变量指向新节点，第一个节点的next指向新节点

然后新节点的next指向第一个节点，curBoy变量指向新节点。成环形了。

再新增一个节点即第三个节点，boy指向这个节点

然后第二个节点的next指向第三个节点，然后curBoy节点指向第三个节点，第三个节点的next指向第一个节点

就形成环形链表了

简单来说就是先创建第一个节点，并使first指向该节点，并形成环形。后面每创建一个新节点，就把该节点加入已有的这个环形链表中。

3.2遍历环形链表：

先让辅助变量curBoy指向first节点，然后通过循环遍历该环形链表，当curBoy.next==first时就遍历完了。

3.3产生出圈序号：

根据用户输入，生成出圈顺序。先设置一个辅助变量helper初始时指向环形链表最后一个节点，小孩报数前先让first和helper移动k-1次也就是移到k所在编号节点。当小孩报数时，first和helper同时移动m-1次（总共移动m下，因为到自己要移动一下，所以除自己之外要移动m-1下），这时就可以将first指向的小孩节点出圈，做法是将first移到下一个（first=first.next），再使helper.next=first。那么原来first指向的节点就没有任何引用，就会被回收。

first后移示意图：

first=first.next示意图：

helper.next=first示意图：

4.代码

4.1在构建环形链表时添加节点：

//添加节点，构建环形链表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);//成环curBoy=first;//让curBoy指向第一个小孩}else{curBoy.setNext(boy);//构建原来的末尾节点指向新节点的线，就是原来指向first的线变成指向新节点boy.setNext(first);//构建新节点指向first的线curBoy=boy;//curBoy节点后移到这个新节点}}}

4.2遍历环形链表：

//遍历环形链表public void showBoy(){//判断链表是否为空if(first==null){System.out.println("没有小孩");return;}//同样用到辅助变量Boy curBoy=first;while(true){System.out.printf("小孩的编号 %d \n",curBoy.getNo());if(curBoy.getNext()==first){//已经遍历完break;}curBoy=curBoy.getNext();//后移}}

4.3产生出圈序号：

public void countBoy(int startNo, int countNum, int nums) {//先校验if (first == null || startNo < 1 || startNo > nums) {System.out.println("参数输入有误，请重新输入");return;}//辅助变量帮助出圈Boy helper = first;while (true) {if (helper.getNext() == first) {//说明helper指向最后小孩节点了，下一个就是first所在节点break;}helper = helper.getNext();//后移}//报数前first和helper移动k-1次for(int j=0;j<startNo-1;j++){first=first.getNext();helper=helper.getNext();}//报数时先移动m-1次然后出圈。直到圈中只有一个节点while(true){if(helper==first){//圈中只有一个节点break;}//first和helper同时移动countNum-1次for(int j=0;j<countNum-1;j++){first=first.getNext();helper=helper.getNext();}//此时first指向的节点是要出圈的节点System.out.printf("小孩 %d 出圈 \n",first.getNo());//将小孩节点出圈first=first.getNext();//first移到出圈的下一个节点helper.setNext(first);//helper的下一个指向first}System.out.printf("最后留在圈中的小孩编号 %d \n",helper.getNo());}

4.4完整代码：

package com.xjj.linkedlist;public class Josephu {public static void main(String[] args) {//测试构建环形链表与遍历CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();circleSingleLinkedList.addBoy(5);//加入5个circleSingleLinkedList.showBoy();//测试出圈顺序是否正确circleSingleLinkedList.countBoy(1,2,5);//出圈顺序为2-4-1-5-3}}//创建环形链表（单向）class CircleSingleLinkedList {//创建first节点，首先不知道谁是第一个小孩所以先没有编号，设为-1private Boy first = new Boy(-1);//添加节点，构建环形链表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);//成环curBoy = first;//让curBoy指向第一个小孩} else {curBoy.setNext(boy);//构建原来的末尾节点指向新节点的线，就是原来指向first的线变成指向新节点boy.setNext(first);//构建新节点指向first的线curBoy = boy;//curBoy节点后移到这个新节点}}}//遍历环形链表public void showBoy() {//判断链表是否为空if (first == null) {System.out.println("没有小孩");return;}//同样用到辅助变量Boy curBoy = first;while (true) {System.out.printf("小孩的编号 %d \n", curBoy.getNo());if (curBoy.getNext() == first) {//已经遍历完break;}curBoy = curBoy.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;while (true) {if (helper.getNext() == first) {//说明helper指向最后小孩节点了，下一个就是first所在节点break;}helper = helper.getNext();//后移}//报数前first和helper移动k-1次for(int j=0;j<startNo-1;j++){first=first.getNext();helper=helper.getNext();}//报数时先移动m-1次然后出圈。直到圈中只有一个节点while(true){if(helper==first){//圈中只有一个节点break;}//first和helper同时移动countNum-1次for(int j=0;j<countNum-1;j++){first=first.getNext();helper=helper.getNext();}//此时first指向的节点是要出圈的节点System.out.printf("小孩 %d 出圈 \n",first.getNo());//将小孩节点出圈first=first.getNext();//first移到出圈的下一个节点helper.setNext(first);//helper的下一个指向first}System.out.printf("最后留在圈中的小孩编号 %d \n",helper.getNo());}}//Boy类表示节点class Boy {private int no;//编号private Boy next;//指向下一个节点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;}}

5.运行结果

测试的是k=1，n=5，m=2的情况。理论出圈顺序为2-4-1-5-3。

成功实现

加油加油^_^


http://www.ppmy.cn/news/1453013.html

相关文章

c语言刷题——输出图案

c语言刷题——输出图案

1.输出用“*”组成的X形图案 题目&#xff1a;请打印用“*”组成的X形图案 描述&#xff1a; 多组输入&#xff0c;一个整数&#xff08;2~20&#xff09;&#xff0c;表示输出的行数&#xff0c;也表示组成“X”的反斜线和正斜线的长度。 输出描述&#xff1a; 针对每行输…
阅读更多...
eNSP-浮动静态路由配置

eNSP-浮动静态路由配置

ip route-static 192.168.1.0 24 192.168.3.2 preference 60 #设置路由 目标网络地址 和 下一跳地址 preference值越大 优先级越低 一、搭建拓扑结构 二、主机配置 pc1 pc2 三、配置路由器 1.AR1路由器配置 <Huawei>sys #进入系统视图 [Huawei]int g0/0/0 #进入接…
阅读更多...
Kafka的优点和缺点,以及适用场景

Kafka的优点和缺点,以及适用场景

Kafka作为一个开源的分布式流处理平台&#xff0c;在大数据和实时处理领域具有广泛的应用。以下是Kafka的优点、缺点以及适用场景&#xff1a; 一、Kafka的优点 高吞吐量和低延迟&#xff1a;Kafka能够处理每秒数百万条消息&#xff0c;具有极低的延迟&#xff0c;使得它非常…
阅读更多...
EPAI手绘建模APP颜色、贴图、材质、样式

EPAI手绘建模APP颜色、贴图、材质、样式

⑦ 颜色选择页面 1) 颜色环选色。 图 65 颜色选择器-颜色环 2) RGB选色。 图 66 颜色选择器-RGB 3) HSL选色。 图 67 颜色选择器-HSL 4) 国风颜色库选色。 图 68 颜色选择器-国风 5) CSS颜色库选色。 图 69 颜色选择器-CSS 6) 历史颜色&#xff1a;保存最近使用的多个颜色&…
阅读更多...
SpringBoot之Zuul服务

SpringBoot之Zuul服务

概述 Spring Cloud Netflix zuul组件是微服务架构中的网关组件,其核心功能是路由和过滤,目前公司业务就是基于Zuul搭建的网关服务,本文主要内容&#xff1a;Zuul的执行流程、Zuul过滤实现、Zuul安全配置 Zuul服务 Zuul执行流程 接收请求 客户端发送请求到Zuul服务器(前置经过…
阅读更多...
【云原生】Docker 的网络通信

【云原生】Docker 的网络通信

Docker 的网络通信 1.Docker 容器网络通信的基本原理1.1 查看 Docker 容器网络1.2 宿主机与 Docker 容器建立网络通信的过程 2.使用命令查看 Docker 的网络配置信息3.Docker 的 4 种网络通信模式3.1 bridge 模式3.2 host 模式3.3 container 模式3.4 none 模式 4.容器间的通信4.…
阅读更多...
线性数据结构-手写链表-LinkList

线性数据结构-手写链表-LinkList

为什么需要手写实现数据结构&#xff1f; 其实技术的本身就是基础的积累和搭建的过程&#xff0c;基础扎实 地基平稳 万丈高楼才会久战不衰&#xff0c;做技术能一通百&#xff0c;百通千就不怕有再难得技术了。 一&#xff1a;链表的分类 主要有单向&#xff0c;双向和循环链表…
阅读更多...
华纳云：ubuntu中fdisk找不到硬盘怎么解决？

华纳云：ubuntu中fdisk找不到硬盘怎么解决？

如果在 Ubuntu 中使用 fdisk 命令找不到硬盘&#xff0c;可能是由于以下几个原因导致的&#xff1a; 1.未正确识别硬盘&#xff1a;可能是因为硬盘未被正确识别或未被操作系统识别。这可能是由于硬件连接问题、硬盘故障、驱动问题等引起的。 2.需要管理员权限&#xff1a;在 Ub…
阅读更多...
最新文章

Copyright @ 2022~2023