目录

一.整体思路

1.JosephusProblem函数详细解析

1-1.JosephusProblem函数变量定义

1-2.JosephusProblem函数获取数据出列顺序代码讲解

1-3.JosephusProblem函数重构单链表代码讲解

完整代码

---

一.整体思路

约瑟夫环问题：编号为1~n个数据围成一圈，从编号1开始每到第m个数据，第m个数据出列，求这n个数据的出列顺序。本篇博客将采用循环链表存储这n个数据，每到第m个数据则将它的位置转存到一维数组中保存并删除循环链表中第m个数据，后续根据数据出列顺序重新构造单链表

1.JosephusProblem函数详细解析

1-1.JosephusProblem函数变量定义

注意：此处不直接将n作为待出列元素是为了防止后续对n的改变导致函数嵌套调用时传参不准确

int i=0,L_length=n,arr[n],j=0;//L_length代表待出列元素个数，arr[n]代表后续数据出列顺序
LinkList p=L->next;
LinkList q=L;

1-2.JosephusProblem函数获取数据出列顺序代码讲解

（1）定义p指针指向循环链表的首元结点，q指针指向头结点，便于防止后续删除结点时因待删除结点前驱不明导致链表断裂（虽然循环链表可以通过任一结点访问该链表所有结点，但这样做能有效降低时间复杂度）

（2）for循环是找出待出列元素，虽然循环链表L中有n个数据，但遍历所有结点个数是n+1，因为头结点不存储数据却会被遍历，故当遍历到头结点时跳过头结点（注意for循环遍历范围是1~m-1，因为最开始p是指向首元结点，故只需要m-1步就能删除结点，而后从第m个结点开始下一次循环）

（3）while循环终止条件是待出列元素为零，代表所有数据出列顺序已经确定。经过for循环找出待出列元素，通过arr数组存储该数据真实顺序，arr数组下表就是该元素出列顺序。若下一次寻找待出列元素的结点是头结点，则跳过头结点，指向下一个结点

LinkList p=L->next;
LinkList q=L;
while(L_length!=0)
{
	for(i=1;i<m;i++)
	{
		q=p;
		p=p->next;
		if(p==L)//若p遍历完一次整个循环链表又指向L,跳过L(头结点不存储数据) 
		{
			q=p;
			p=p->next; 
		}
	}
	arr[j]=p->data;
	j++;
	L_length--;
	q->next=p->next;
	LinkList temp=p;
	p=(p->next==L)?p->next->next:p->next;
	delete temp;
}

1-3.JosephusProblem函数重构单链表代码讲解

（1）首先尾指针归位，指向单链表最后一个结点（因为在前文已经删除循环单链表L中除了头结点外的所有的结点，故头结点是最后一个结点）

（2）采取头插法将arr数组中元素数据插入到单链表中（过程不做过多赘述）

（3）最后调用Traverse函数遍历输出该数据出列顺序

LinkList rear=L;
for(i=0;i<n;i++)
{
	p=new LNode;
	p->data=arr[i];
	p->next=NULL;
	rear->next=p;
	rear=p;
}
Traverse(L);

完整代码

仅设计单链表初始化、创建、初始化（不做过多赘述）

#include<iostream>
using namespace std;

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

void InitList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
}

void Creat(LinkList &L,int n,int m)
{
	LinkList rear=L;
	for(int i=1;i<=n;i++)
	{
		LinkList p=new LNode;
		p->data=i;
		p->next=NULL;
		rear->next=p;
		rear=p;
	}
	rear->next=L;
}

void Traverse(LinkList L)
{
	LinkList p=L->next;
	while(p)//此处循环链表已经在JosephusProblem函数中被重新构造成单链表，故循环结束条件也会改变 
	{
		cout << p->data << " ";
		p=p->next;
	}
}

void JosephusProblem(LinkList &L,int n,int m) 
{
	Creat(L,n,m);
	cout << 1 << endl;
	int i=0,L_length=n,arr[n],j=0;
	LinkList p=L->next;
	LinkList q=L;
	while(L_length!=0)
	{
		for(i=1;i<m;i++)
		{
			q=p;
			p=p->next;
			if(p==L)//若p遍历完一次整个循环链表又指向L,跳过L(头结点不存储数据) 
			{
				q=p;
				p=p->next; 
			}
		}
		arr[j]=p->data;
		j++;
		L_length--;
		q->next=p->next;
		LinkList temp=p;
		p=(p->next==L)?p->next->next:p->next;
		delete temp;
	}
	LinkList rear=L;
	for(i=0;i<n;i++)
	{
		p=new LNode;
		p->data=arr[i];
		p->next=NULL;
		rear->next=p;
		rear=p;
	}
	Traverse(L);
}

int main()
{
	int m,n;
	cin >> n >> m;
	LinkList L;
	InitList(L);
	JosephusProblem(L,n,m);
	return 0;
}