约瑟夫环（循环列表实现）

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，令其出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。

    实验要求

利用无头结点的单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。

测试数据：

    m的初值为20；n=7,7个人的密码依次为：3，1，7，2，4，8，4，首先m值为8（正确的出列顺序应为6，1，4，7，2，3，5）

 实验提示：

    程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码，可设n<=30，此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

#include<iostream>//用链表实现约瑟夫环问题 （循环链表）
using namespace std;
typedef struct node  
{
	int num;
	int pwd;
	struct node* next;
}Node ,*list;
list Createlist(int n)//创建循环列表
{
	list head = NULL,rear=NULL, temp = NULL;
	head = rear;
	for (int i = 1; i <= n; i++)
	{
		temp = new node;
		temp->num = i;
		cin >> temp->pwd;
		if (head == NULL)//若为空则赋给头指针
		{
			head = temp;
		}
		else
		{
			rear->next = temp;//接在尾指针后
		}
		rear = temp;
	}
	rear->next = head;//尾指针指向头指针
	return head;
}
//void Printlist(list l)//打印输出
//{
	//list p = l;
	//for (int i = 0; i < 14; i++)
	//{
		//cout << p->num << p->pwd << " ";
		//p = p->next ;
	//}
	//cout << endl;
//}
void Getlist(list l,int n,int m)//约瑟夫环
{
	list p = l, q = NULL;
	while (p->next != p)//循环直到只剩一个 头尾相指
	{
		for (int i = 1; i < m; i++)
		{
			q = p;//保留离开点的上一个节点
			p = p->next;
		}
		cout << p->num<<" ";
		m = p->pwd;
		q->next = p->next;//剔除该点
		p = p->next;//从下一节点重新计数
	}
	cout << p->num;
}
int main()
{
	list l;
	int n, m;
	cin >> n >> m;
	l = Createlist(n);
	//Printlist(l);
	Getlist(l, n, m);
}

文章来源地址https://uudwc.com/A/8d6zv