#ifndef Josephus_circle//判斷是否被定義過Josephus_circle
#define Josephus_circle
 
struct Node//定義一個結(jié)構(gòu)體，用來表示每一個結(jié)點 
{
 int data;//表示每一個結(jié)點的數(shù)字，也就是序號
    Node* next;//定義一個結(jié)構(gòu)體指針，用來指向后一個結(jié)點
};
 
class Josephus//定義一個類，里面包含有三個接口，和兩個私有成員變量
{
public :
 Josephus(int n);//定義一個構(gòu)造函數(shù)，用來創(chuàng)建一個約瑟夫環(huán)
 ~Josephus();//析構(gòu)函數(shù)，用以銷毀一個約瑟夫環(huán)
 void ResultShow(int m);//展示出圈順序
private :
 Node * rear,*first;//定義一個節(jié)點形指針，用來指向最后一個結(jié)點
};
#endif

#include<iostream>//引入輸入輸出流
#include"約瑟夫環(huán).h"http://引入約瑟夫環(huán)頭文件
 
using namespace std;
 
 Josephus::Josephus(int n) 
{
  first=rear = new Node;//將頭指針和尾指針指向第一個新建的結(jié)點，也就是初始化指針
  rear->data = 1;//首先，將第一個結(jié)點數(shù)據(jù)域賦值為1
  for (int i = 2; i <= n; i++) //從2開始
  {
   Node* s = new Node;//定義一個Node形指針s，指向新建的一個結(jié)點
   rear->next = s;//將指向頭結(jié)點的尾指針指向下一個結(jié)點，也就是s所指的結(jié)點
   s->data = i;//將新建的結(jié)點數(shù)字域賦值為i
   rear = s;//將尾結(jié)點移動到新建結(jié)點s
  }
  rear->next = first;//在循環(huán)過后，將尾結(jié)點和頭節(jié)點連接起來，構(gòu)成循環(huán)鏈表
}
Josephus::~Josephus()
{
 if (first!=rear)//判斷環(huán)是否為空
 {
  while (first != rear)//每次循環(huán)都是當(dāng)頭節(jié)點不等于尾結(jié)點時候，開始刪除：……
  {
   Node * p = first;//定義一個新的節(jié)點形指針，指向頭節(jié)點，用作暫存要刪去的結(jié)點
   first = first->next;//將頭節(jié)點移動到下一個結(jié)點
   delete p;//刪除之前頭節(jié)點所指向的結(jié)點
  }
  delete rear;//在刪除完成后，剩下的最后就只有尾結(jié)點了，刪除即可
 }
 else 
 {
  cout << "約瑟夫環(huán)為空，請先建立新環(huán)！" << endl;//空表提示
 }
}
void Josephus::ResultShow(int m)
{
 cout << "出環(huán)順序為：" << endl;
 Node * p = first;//定義一個Node類型的p，等于first
 Node * pre=first,* reserve=nullptr;//定義pre等于first，和一個代替p指針被刪除的結(jié)點的指針
 int count = 1;//定義一個計數(shù)的count使其為一
 while (p->next != p)//如果p->next所指向的結(jié)點是p的話，表示，這已經(jīng)是最后一個結(jié)點了，該節(jié)點為最后出圈
 {
  if (count < m)//count來計數(shù)，每次到了m就出圈對應(yīng)結(jié)點
  {
   pre = p;//將pre等于p，以便于表示p變換前的結(jié)點
   p = p->next;//p向下一結(jié)點移動
   count++;//移動一次count加一次
  }
  else//每次count=m時候就開始刪除對應(yīng)結(jié)點
  {
   pre->next = p->next;//首先從環(huán)中摘去要刪除的p所指的結(jié)點
   reserve = p;//使用reserve來保存被摘去的結(jié)點p
   cout << p->data << "\t";//輸出結(jié)點p所數(shù)據(jù)域，輸出在屏幕上表示p結(jié)點的出圈
   p = p->next;//p指向下一結(jié)點，以便于下一輪的循環(huán)
   delete reserve;//刪除保存p的reserve所對應(yīng)的結(jié)點
   count = 1;//將計數(shù)恢復(fù)為1，以便下一輪計數(shù)
  }
 }
 cout << p->data << endl;//這最后一個就是最后出圈的結(jié)點，也就是所謂的勝利者，最后單獨輸出屏幕
 delete p;//輸出最后再刪除這一結(jié)點，釋放內(nèi)存
 pre=first=rear=p = NULL;//避免野指針出現(xiàn)使其指向空
}

#include<iostream>//引入輸入輸出流
#include"約瑟夫環(huán).h"http://引入頭文件
 
using namespace std;
 
//主函數(shù)區(qū)域
int main() {
 int m, n;
 cout << "請輸入約瑟夫環(huán)人數(shù)以及密碼\n";
 cout << "人數(shù)n：";
 cin >> n;
 cout << endl << "密碼m：";
 cin >> m;
 Josephus L(n);//創(chuàng)建一個約瑟夫環(huán)，環(huán)數(shù)為10
 L.ResultShow(m);//定義密碼m，輸出出圈順序
 return 0;
}