C++约瑟夫环的循环单链表 C++实现约瑟夫环的循环单链表

#ifndef Josephus_circle//判断是否被定义过Josephus_circle
#define Josephus_circle
 
struct Node//定义一个结构体，用来表示每一个结点 
{
 int data;//表示每一个结点的数字，也就是序号
    Node* next;//定义一个结构体指针，用来指向后一个结点
};
 
class Josephus//定义一个类，里面包含有三个接口，和两个私有成员变量
{
public :
 Josephus(int n);//定义一个构造函数，用来创建一个约瑟夫环
 ~Josephus();//析构函数，用以销毁一个约瑟夫环
 void ResultShow(int m);//展示出圈顺序
private :
 Node * rear,*first;//定义一个节点形指针，用来指向最后一个结点
};
#endif

#include<iostream>//引入输入输出流
#include"约瑟夫环.h"//引入约瑟夫环头文件
 
using namespace std;
 
 Josephus::Josephus(int n) 
{
  first=rear = new Node;//将头指针和尾指针指向第一个新建的结点，也就是初始化指针
  rear->data = 1;//首先，将第一个结点数据域赋值为1
  for (int i = 2; i <= n; i++) //从2开始
  {
   Node* s = new Node;//定义一个Node形指针s，指向新建的一个结点
   rear->next = s;//将指向头结点的尾指针指向下一个结点，也就是s所指的结点
   s->data = i;//将新建的结点数字域赋值为i
   rear = s;//将尾结点移动到新建结点s
  }
  rear->next = first;//在循环过后，将尾结点和头节点连接起来，构成循环链表
}
Josephus::~Josephus()
{
 if (first!=rear)//判断环是否为空
 {
  while (first != rear)//每次循环都是当头节点不等于尾结点时候，开始删除：……
  {
   Node * p = first;//定义一个新的节点形指针，指向头节点，用作暂存要删去的结点
   first = first->next;//将头节点移动到下一个结点
   delete p;//删除之前头节点所指向的结点
  }
  delete rear;//在删除完成后，剩下的最后就只有尾结点了，删除即可
 }
 else 
 {
  cout << "约瑟夫环为空，请先建立新环！" << endl;//空表提示
 }
}
void Josephus::ResultShow(int m)
{
 cout << "出环顺序为：" << endl;
 Node * p = first;//定义一个Node类型的p，等于first
 Node * pre=first,* reserve=nullptr;//定义pre等于first，和一个代替p指针被删除的结点的指针
 int count = 1;//定义一个计数的count使其为一
 while (p->next != p)//如果p->next所指向的结点是p的话，表示，这已经是最后一个结点了，该节点为最后出圈
 {
  if (count < m)//count来计数，每次到了m就出圈对应结点
  {
   pre = p;//将pre等于p，以便于表示p变换前的结点
   p = p->next;//p向下一结点移动
   count++;//移动一次count加一次
  }
  else//每次count=m时候就开始删除对应结点
  {
   pre->next = p->next;//首先从环中摘去要删除的p所指的结点
   reserve = p;//使用reserve来保存被摘去的结点p
   cout << p->data << "\t";//输出结点p所数据域，输出在屏幕上表示p结点的出圈
   p = p->next;//p指向下一结点，以便于下一轮的循环
   delete reserve;//删除保存p的reserve所对应的结点
   count = 1;//将计数恢复为1，以便下一轮计数
  }
 }
 cout << p->data << endl;//这最后一个就是最后出圈的结点，也就是所谓的胜利者，最后单独输出屏幕
 delete p;//输出最后再删除这一结点，释放内存
 pre=first=rear=p = NULL;//避免野指针出现使其指向空
}

#include<iostream>//引入输入输出流
#include"约瑟夫环.h"//引入头文件
 
using namespace std;
 
//主函数区域
int main() {
 int m, n;
 cout << "请输入约瑟夫环人数以及密码\n";
 cout << "人数n：";
 cin >> n;
 cout << endl << "密码m：";
 cin >> m;
 Josephus L(n);//创建一个约瑟夫环，环数为10
 L.ResultShow(m);//定义密码m，输出出圈顺序
 return 0;
}