Loading... 推荐阅读 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://xn2001.com/archives/555.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://cdn.xn2001.com/2020/08/14/003341-dbcdddc2f03a11f5a66c29f4850a376c.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">单链表结构</p> <div class="inster-summary text-muted"> 链表(Linked List)介绍链表是有序的列表,但是它在内存中是存储如下链表是以节点的方式来存储,是链式存储。... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://xn2001.com/archives/558.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://imgcdn.xn2001.com/usr/themes/handsome/assets/img/sj/2.jpg!/fw/800/compress/true);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">双向链表</p> <div class="inster-summary text-muted"> 推荐阅读2. 双向链表应用实例2.1 双向链表的操作分析和实现使用带 head 头的双向链表实现 –水浒英雄排行榜... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 3. 单向环形链表应用场景 **Josephu(约瑟夫、约瑟夫环) 问题** Josephu 问题为:设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。 提示:用一个不带头结点的循环链表来处理 Josephu 问题:先构成一个有 n 个结点的单循环链表,然后由 k 结点起从 1 开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中删除算法结束。  创建环形链表:其实挺简单的,让最后一个对接上第一个即可。 小孩出圈:稍微麻烦一点点,两个指针(简称前后),前指针指向第一个,后指针指向最后一个,小孩们开始报数时,两个指针都移动下去,当某个小孩出圈了,前指针直接移动到下一个,后指针直接对接上前指针。**更通俗的说,他就是一个圆形蛋糕,分成四份的话,我们有两个指针,一个指向第一块,一个指向最后一块,然后他们一起移动,后指针永远在前指针的后面做好对接的准备。** 约瑟夫问题-创建环形链表的思路图解  约瑟夫问题-小孩出圈的思路分析图  我自己画了一个图  ## 代码 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-f0df8841917fe102ca9eb46d83ff59605" aria-expanded="true"><div class="accordion-toggle"><span>代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-f0df8841917fe102ca9eb46d83ff59605" class="collapse collapse-content"><p></p> ```java package com.xn2001.linkedlist; /** * @author 乐心湖 * @date 2020/8/17 15:10 **/ public class Josepfu { 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节点 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); curBoy = first; } else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } // 遍历当前的环形链表 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; // 将helper指针移到末尾 while (helper.getNext() != first) { helper = helper.getNext(); } // 定位到第startNo个孩子 for (int i = 0; i < startNo - 1; i++) { first = first.getNext(); helper = helper.getNext(); } // 小孩开始报数 while (helper != first) { for (int i = 0; i < countNum - 1; i++) { first = first.getNext(); helper = helper.getNext(); } System.out.printf("小孩%d 出圈\n", first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo()); } } class Boy { private int no;// 编号 private Boy next; // 指向下一个节点,默认 null 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; } } ``` <p></p></div></div></div> Last modification:August 17, 2020 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏