本文共 6812 字，大约阅读时间需要 22 分钟。

单项环形链表——约瑟夫问题

约瑟夫问题：设编号为1、2、3、…n的n个人围成一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的哪个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依次类推，直到所有人都出列为止，由此产生一个出队列的编号；

• 分析：使用不带头结点的环形单链表的数据结构；

单向环形链表的初始化

环形链表加节点的分析

下面代码的init()方法就是环形链表添加节点，说多无用，这种东西越说越难理解，画个图就思路清奇了，如下图解：

打印环形链表的分析

下面代码的show()方法就是环形链表的打印，需要知道，此过程中FIRST始终指向的是链表的第一个节点，那么FIRST的前一个结点一定是环的最后一个结点，这里我们使用一个currentNode来表示当前打印的结点，并在每次在打印完后将currentNode后移，直到currentNode.next == FIRST时(即此时currentNode为环的最后一个节点)，结束遍历，如下图解：

约瑟夫游戏进行的分析

下面代码的play()方法就是约瑟夫游戏的进行，如下分析：

1. 首先我们应该保证将FIRST在环的开始节点，再定义一个lastNode，保证其在FIRST的前一个节点(即在环的最后一个节点)
2. 在小孩数数之前，先将FIRST 和 lastNode 同时移动 fromChild - 1个位置(fromChild指的就是从第几个孩子开始数数)，即保证FIRST 指向 进行数数节点的节点，lastNode 指向 FIRST指向节点的前一个节点；
3. 进行数数，将FIRST 和 lastNode 同时移动 count - 1 个位置(count指的是从一开始数到几)，即将FIRST指向 要出圈的节点，将lastNode 指向 FIRST指向节点的前一个节点；
4. 进行出圈，即将 FIRST = FIRST.next；并且为了保证lastNode指向FIRST指向节点的前一个节点，应该将 lastNode.next = FIRST；

如下图解：

代码

直接先把所有的代码展示出来，并进行一一解读，如下代码：

package edu.hebeu.circle;/** * 环形单链表的节点(约瑟夫问题中的小孩) * @author 13651 * */public class Node {
   		private Person child;		public Node next;		public Node(Person child) {
   		this.child = child;	}	public Person getChild() {
   		return child;	}	public void setChild(Person child) {
   		this.child = child;	}	}

节点类Node的创建，代码如下所示：

package edu.hebeu.circle;/** * 环形单链表的节点(约瑟夫问题中的小孩) * @author 13651 * */public class Node {
   		private Person child;		public Node next;		public Node(Person child) {
   		this.child = child;	}	public Person getChild() {
   		return child;	}	public void setChild(Person child) {
   		this.child = child;	}	}

*单向环形链表类CircleLinkedList的创建，如下代码所示：

package edu.hebeu.circle;public class CircleLinkedList {
   	/**	 * 表示first节点，该节点始终指向单向环形链表的第一个节点，默认值为null	 */	private static Node FIRST = null;		/**	 * 参加游戏的小孩个数	 */	private int childNum = 0;		/**	 * 私有化构造器	 */	private CircleLinkedList() {
   }		/**	 * 这个方法用来初始化环形链表(决定有几个小孩
   <链表的节点>
    )，基本思路：	 * 	1、先创建第一个节点，并让FIRST指向该节点，然后让FIRST形成自环(即让链表构成环)	 *  2、当添加后面的节点(即不是第一个节点)，就将该节点添加到上次添加的节点后面，然后在将该节点的next域指向 FIRST(即将该节点加入到环形链表)	 *  3、新建一个currentNode节点，并指向当前新添加的节点(即在下次添加新节点时，currentNode就是在其前面)，那么	 *  可以理解为：每次添加新节点后，将currentNode指向新添加的节点，下次添加新节点时可以使用currentNode来决定新节点添加到何处；	 * @param childNum 表示有几个小孩参与游戏
    <链表的节点>
     	 * 	 */	public static CircleLinkedList init(int childNum) {
   		if(childNum < 1) {
   			System.err.println("请保证有小孩参加此游戏！");			return null;		}		Node currentNode = null;		for(int i = 1; i <= childNum; i++) {
   			Node newNode = new Node(new Person(i, "child" + i)); // 创建一个孩子对象			if(i == 1) {
    // 如果i等于1，即是该节点是环形链表第一次创建的节点				FIRST = newNode; // 让FIRST指向第一个创建的节点(小孩)				newNode.next = FIRST; // 将新添加的节点的next域 指向 FIRST，即形成自环(让链表构成环)				currentNode = newNode; // 让currentNode 指向 新添加节点newNode(小孩)				continue; // 结束本次循环			}			currentNode.next = newNode; // 将未添加时的currentNode的next域 指向 新添加的节点newNode(小孩)			newNode.next = FIRST; // 将新添加的节点的next域 指向 FIRST，即将链表构成环			currentNode = newNode; // 让currentNode 指向 新添加的节点newNode(小孩)		}				CircleLinkedList circleLinkedList = new CircleLinkedList();		circleLinkedList.childNum = childNum;		return circleLinkedList;	}		/**	 * 这个方法表示开始游戏的方法，思路分析：	 *  1、定义一个 lastNode节点，并保证该节点指向链表的最后一个节点(即在FIRST之前)	 *  2、在小孩数数之前，先将FIRST 和 lastNode 同时移动 fromChild - 1个位置(fromChild指的就是从第几个孩子开始数数)，	 *  即保证FIRST 指向 开始数数的节点，lastNode 指向 FIRST指向节点的前一个节点；	 *  3、进行数数，将FIRST 和 lastNode 同时移动 count - 1 个位置(count指的是从一开始数到几)，	 *  即将FIRST 指向 要出圈的节点，将lastNode 指向 FIRST指向节点的前一个节点；	 *  4、进行出圈，即将 FIRST = FIRST.next；并且为了保证lastNode指向FIRST指向节点的前一个节点，应该将 lastNode.next = FIRST	 * @param count 表示从一开始数几个数	 * @param fromChild 表示首次从第几个小孩开始计数	 */	public void play(int count, int fromChild) {
   		if(FIRST == null) {
   			System.err.println("没有小孩参与该游戏！");			return;		}		if(count < 1) {
   			System.err.println("请保证数数的个数大于0！");			return;		}		if(fromChild > childNum) {
   			System.err.println("共有" + childNum + "个孩子参与游戏，找不到第" + fromChild + "个孩子！");			return;		}		Node lastNode = FIRST; // 链表的最后一个节点，默认为FIRST节点		/*		 * 该循环用来计算到当前环形链表的最后一个节点lastNode		 */		while(true) {
   			if(lastNode.next == FIRST) {
    // 如果lastNode的next域 为FIRST，表示此时该节点为最后一个节点				break;			}			lastNode = lastNode.next; // lastNode节点后移		}				/*		 * 在数数之前，先进行 fromChild -1 次循环，即将FIRST和lastNode移动了 fromChild - 1 次，保证FIRST位于开始数数的节点；lastNode位于FIRST节点的后一个节点		 */		for(int i = 0; i < fromChild - 1; i++) {
   			FIRST = FIRST.next; // FIRST节点后移			lastNode = lastNode.next; // lastNode节点后移		}				/*		 * 此循环用来进行出圈节点的操作，此循环结束的条件是链表内只有1个人了		 */		while(true) {
   			if(lastNode == FIRST) {
    // 当lastNode == FIRST时，说明圈中只有1人，结束掉循环				break;			}			/*			 * 该循环计算到要出圈的节点，循环 count - 1 次，即将FIRST和lastNode移动了 count - 1 次，			 * 此时FIRST就是位于 要出圈的节点，lastNode就是位于 FIRST节点的后一个节点			 */			for(int i = 0; i < count - 1; i++) {
    // 				FIRST = FIRST.next; // FIRST节点后移				lastNode = lastNode.next; // lastNode节点后移			}			/*此时FIRST指向的节点就是要出圈的节点*/			System.out.println(FIRST.getChild() + "出圈");			FIRST = FIRST.next; // 将FIRST后移			lastNode.next = FIRST; // 将lastNode的next域 指向 FIRST		}		System.out.println(FIRST.getChild() + "最后留下！");		childNum = 1; // 将 标识圈中孩子数量的变量 修改为1	}		/**	 * 这个方法用来遍历环形链表，基本思路：	 *  1、先定义一个currentBoy指针，并指向FIRST节点；	 *  2、然后进行遍历环形链表，如果currentBoy.next == FIRST时表示遍历结束	 */	public void show() {
   		if(FIRST == null) {
   			System.err.println("没有小孩参与该游戏！");			return;		}		Node currentNode = FIRST;		while(true) {
   			System.out.println(currentNode.getChild());			if(currentNode.next == FIRST) {
    // 如果当前节点currentNode的next域 等于 first，即当前遍历的是最后一个节点				break;			}			currentNode = currentNode.next; // 节点后移		}	}	}
    
   

测试类JosepfuTest的代码编写：

package edu.hebeu.circle;import java.util.Scanner;public class JosepfuTest {
   		private static final Scanner SCANNER = new Scanner(System.in);	private static CircleLinkedList CIRCLE_LINKED_LIST;		public static void main(String[] args) {
   		menu();	}		private static void menu() {
   		boolean isWhile = true;		while(isWhile) {
   			System.out.println();System.out.println();			System.out.println("初始化游戏人员i(init)");			System.out.println("遍历游戏人员s(show)");			System.out.println("开始游戏p(play)");			System.out.print("请输入："); char keyword = SCANNER.next().charAt(0);						switch(keyword) {
   				case 'i':					System.out.println("请输入游戏的人数："); Integer num = SCANNER.nextInt();					CIRCLE_LINKED_LIST = CircleLinkedList.init(num);					break;				case 's':					if(CIRCLE_LINKED_LIST == null) {
   						System.err.println("请先初始化游戏人员！");						break;					}					CIRCLE_LINKED_LIST.show();					break;				case 'p':					if(CIRCLE_LINKED_LIST == null) {
   						System.err.println("请先初始化游戏人员！");						break;					}					System.out.print("从一到几数："); Integer count = SCANNER.nextInt();					System.out.print("从第几个孩子开始数数："); Integer fromChild = SCANNER.nextInt();					CIRCLE_LINKED_LIST.play(count, fromChild);					break;				default:					isWhile = false;					break;			}		}	}}

测试

先来初始化游戏，保证游戏有5个人参与，如下：

转载地址：https://blog.csdn.net/m0_49039508/article/details/116768287 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！