#include<iostream>
using namespace std;
struct Node//定义节点的结构类型
{
int data;
Node* next;
};
class CircularLinkedList//循环链表类
{
public:
CircularLinkedList(){first=new Node;first->next=NULL;}
CircularLinkedList(int n);//构建一个附有值的循环链表
~CircularLinkedList();
int Josephus(int num);//约瑟夫函数
private:
Node* first;
};
CircularLinkedList::CircularLinkedList(int n)
{
first=new Node;
Node * r=first;
for(int i=1;i<=n;i++)
{
Node* s=new Node;
s->data=i;
s->next=NULL;
r->next=s;
r=s;
} //头插法初始化链表
r->next=first; //最后一个元素的next志指向头结点}
CircularLinkedList::~CircularLinkedList()
{
Node* p=first,*q;
while(p->next!=first)//p指向最后一个结点时结束循环
{
q=p;
p=p->next;
delete q;
}
delete p;//删除头结点
}
int CircularLinkedList::Josephus(int num)
{
Node* p=first,*q;
if(num<=0)
throw "输入错误！";
while(first->next->next!=first)
{
for(int i=1;i<num;i++) //p向后移动num位，指向要删除的元素的前一个结点
{
p=p->next;
if(p==first) //若循环过程中出现p指向头结点，则跳过头结点
{
p=p->next;
}
}
if(p->next==first) //若循环结束后p指向最后一个元素，则要跳过头结点，并让头结点的next指向要删除元素的下一个
{
p=first;
q=p->next;
p->next=q->next;
//first->next=q->next;
cout<<q->data<<" ";
delete q;
}
else
{
q=p->next;
p->next=q->next;
cout<<q->data<<" ";
delete q;
}
}
cout<<endl;
cout<<"最后一个数为：";
return first->next->data;
}
void main()
{
int n,m;
cout<<"请输入约瑟夫问题的人数和间隔人数：";
cin>>n>>m;
cout<<"依次删除："<<endl;
CircularLinkedList Josephus1(n);//创建的对象调用第二个构造函数
cout<<Josephus1.Josephus(m)<<endl;
}。