C++环形链表实现约瑟夫(Josephu)问题

约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为48521376。

存储结构：带头结点的双向环形链表

//Josephu.h
#pragma once
typedef int nodetype;
typedef struct circlenode
{nodetype data;struct circlenode* front;struct circlenode* next;
}CLListNode;CLListNode*  CirclenodeInit();void CilcleListPush(CLListNode*& node,nodetype new_data);CLListNode* FindTail(CLListNode* L);void CLListPrint(CLListNode* L);bool CLListIsNull(CLListNode* L);CLListNode* JosephuCLList(CLListNode*& L,int m, int n);

简单的环形链表创建过程。front和next指针，便于链表的插入和删除。
JosephuCLList函数实现约瑟夫环问题。

//Josephu.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"Josephu.h"//结点初始化
CLListNode* CirclenodeInit()
{CLListNode* node = (CLListNode*)malloc(sizeof(CLListNode));node->front = NULL;node->next = NULL;return node;}void CilcleListPush(CLListNode*& node,nodetype new_data)
{//开始只有一个结点if (node->next==NULL){CLListNode* new_node= CirclenodeInit();new_node->data = new_data;node->next = new_node;new_node->front = node;node->front = new_node;new_node->next = node;}//大于等于2个结点else{CLListNode* tail = FindTail(node);CLListNode* new_node= CirclenodeInit();new_node->data = new_data;//尾结点尾指针指向新节点，新结点指针指向尾节点tail->next = new_node;new_node->front = tail;//新结点尾指针指向头节点，头结点指针指向新节点node->front = new_node;new_node->next = node;}}CLListNode* FindTail(CLListNode* L)
{CLListNode* tail = L->next;int i = 0;//找尾结点，个数大于1的情况while (tail->next != L&&tail->next != NULL){tail = tail->next;i++;}return tail;}bool CLListIsNull(CLListNode* L)
{//只有头结点和有头结点和第一个元素if ((L->front == L->next)){if (L->next != NULL)return false;elsereturn true;}//其余情况elsereturn false;
}void CLListPrint(CLListNode* L)
{if (CLListIsNull(L)){cout << "the list is empty" << endl;}else{CLListNode* p = L->next;int i = 0;while (p != L){cout << p->data<<"\t";p = p->next;}cout << endl;}
}
CLListNode* JosephuCLList(CLListNode*& L,int m,int n)
{CLListNode* Josephu = L->next;//out指针出列CLListNode* out = L;while (!CLListIsNull(L)){//报m次数，第m个出列//因为每次报完后指针都后移一位，所以只用循环m-1次for (int i = 0; i < m-1; i++){//如果下一个是头结点就跳过头结点Josephu = Josephu->next;if (Josephu == L)Josephu = L->next;}out = Josephu;Josephu = Josephu->next;//跳过头结点if (Josephu == L)Josephu = L->next;cout << out->data << "\t";//1到m-1次去除结点if (out->front != out->next){out->front->next = out->next;out->next->front = out->front;}//只剩最后一个元素清除if(out->front == out->next){break;	}free(out);}Josephu = L->front;return Josephu;
}

//main.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"Josephu.h"
void text()
{CLListNode* L = CirclenodeInit();nodetype i = 1;int n = 8, m = 4;for (i = 1; i <= n; i++){CilcleListPush(L,i);}CLListPrint(L);CLListNode* Josephu=JosephuCLList(L, m, n);cout << endl;cout << "Josephu:"<<Josephu->data << endl;free(Josephu);free(L);}int main()
{text();return 0;
}