2024年3月12日发(作者：)

约瑟夫环

一.实验目的：

理解线性表的基本逻辑结构，完成链表及循环链表的实现

通过实验进一步理解线性表的逻辑结构和存储结构，提高使用理

论知识指导解决实际问题的能力，熟练掌握链表的实际应用。

二.实验内容：

题目：Josephus环问题

问题描述：

约瑟夫(Joseph)问题的一种描述是：编号为1,2,…，n的n个人

按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选

一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开

始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新

的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下

去，直到所有人全部出列为止。试设计一个程序求出出列顺序。

基本要求：

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各

人的编号。

测试数据：

m的初值为20;n=7,7个人的密码依次为：3,1,7,2,4,8,4，首先

m值为6（正确的出列顺序应为6,1,4,7,2,3,5）。

三. 实验方案（程序设计说明）

（一）算法设计思路：

1.利用单循环链表实现该程序的目的；

2.实现过程：创建单循环链表--信息从尾部插入--遍历链表找

出目标—删除操作杀害;

（二）算法流程图：

1