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

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