约瑟夫问题 （Java） |
您所在的位置：网站首页 › java约瑟夫环循环链表 › 约瑟夫问题 （Java） |
|
一、问题描述
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。 问题即，给定人数、起点、要跳过的数字，选择初始圆圈中的位置以避免被处决。 二、思路及实现常见的做法是使用循环链表来解决约瑟夫问题。 首先需要找到第一个报数的结点。 跳过指定的人数后，找到要处决的人的前一个结点（删除操作只能通过前一个结点进行），删除要删除的人。 循环链表中只剩一个人时，此人就被释放。 循环链表实现 Node.java /** * @author liyanan * @date 2020/1/2 13:44 */ /** * 模拟结点 */ public class Node { /** * 存储数据 */ public int data; /** * 指向下一个节点 */ public Node next; public Node() { } public Node(int data) { this.data = data; } } 复制代码CircleLinkedList.java /** * 循环链表的实现（特殊的单链表） * * @author liyanan * @date 2020/1/2 13:16 */ public class CircleLinkedList { /** * 指向循环链表的第一个结点 */ private Node head; /** * 循环链表的长度 */ private int length; public CircleLinkedList() { head = null; length = 0; } public Node getHead() { return head; } public int getLength() { return length; } /** * 尾部插入 * * @param newNode */ public void insert(Node newNode) { if (head == null) { // 循环链表为空时，head 指向新的节点 head = newNode; } else { Node temp = head; // 找到循环链表最后一个节点 while (temp.next != head) { temp = temp.next; } // 插入新的节点 temp.next = newNode; } // 循环链表新的结点指向 NULL newNode.next = head; // 循环链表长度加 1 length++; } /** * 将新的结点插入到指定结点后 * * @param preNode 指定节点 * @param newNode 新的节点 */ public void insert(Node preNode, Node newNode) { newNode.next = preNode.next; preNode.next = newNode; length++; } /** * 删除数据域为指定值的元素 * * @param e */ public void del(int e) { Node temp = head; while (length >= 0) { // 找到数据域为 e 的结点 if (temp.data == e) { if (temp.next == head) { // 第一个节点 head = null; } else { // 最后一个节点 temp.next = temp.next.next; } // 循环链表长度减 1 length--; return; } // 找到下一个结点 temp = temp.next; } } /** * 给定被删除元素的前一个结点，删除指定元素 * * @param preNode */ public Node del(Node preNode) { Node delNode = preNode.next; if (delNode == head) { // 维护 head 的指向 head = head.next; } // 删除 preNode.next = preNode.next.next; length--; return delNode; } /** * 随机访问第 k 个结点 * * @param k * @return */ public Node find(int k) { if (k |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |