/*  Name: 双向链表实现约瑟夫双向生死游戏   Description: 约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，  然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；  因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，  并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，  逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，  直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。*/#include
    
     using namespace std;//===================================双向循环链表的结点类====================================class Node{      friend class Doublelist;      friend void DoubleJoseph();            public:             Node();             int data;             Node *prior;             Node *next;       private:};//=====================================双向循环链表类=========================================class Doublelist{      friend void DoubleJoseph();      public:             void Creatlist(Doublelist &L);             int getLength(Doublelist &L);             Doublelist();      private:              Node *Head;};//=====================================Doublelist类的构造函数,初始化首结点数据=================Node::Node(){            data = 0;            prior = NULL;            next = NULL;}//======================================Doublelist类的构造函数,初始化首结点数据=================Doublelist::Doublelist(){                        Head = NULL;}//======================================建立双向循环链表=========================================void Doublelist::Creatlist(Doublelist &L){     cout << "请输入双向生死游戏的总人数N:";     int n;     cin >> n;     Node *p,*s;     for(int i = 1;i <= n;i++)     {             p = new Node;             p->data = i;             p->next = NULL;             if(i == 1)             {                  L.Head = p;                   p->prior = NULL;                  s = L.Head;             }             else             {                  s->next = p;                  p->prior = s;                  s = s->next;             }       }     s->next = L.Head;     L.Head->prior = p;}//====================================获取双向链表的长度==============================int Doublelist::getLength(Doublelist &L){    Node *p = L.Head;    int count = 0;    while(p->next != L.Head)    {                  count++;                  p = p->next;    }    count++;    return count;}//=======================================实现约瑟夫双向生死游戏=========================void DoubleJoseph(){     Doublelist L;     L.Creatlist(L);           cout << "请输入游戏开始的位置S:";     int s;     cin >> s;          cout << "请输入正向的死亡数字M:";     int m;     cin >> m;          cout << "请输入逆向的死亡数字W:";     int w;     cin >> w;          cout << "请输入剩余的生者人数";     int k;     cin >> k;     cout << endl;          Node *p,*q,*r;     p = L.Head;     for(int i = 0;i < s-1;i++)     {             p = p->next;     }     int t = 1;     while(k < L.getLength(L))     {          if(t%2)//选择游戏方式          {                  //报数,寻找m结点                  for(int j = 0; j < m-1; j++)                 {                         q = p;                         p = p->next;                 }                 //元素出列                  if(p == L.Head)                 {                         r = p;                         L.Head = p->next;                         q->next = p->next;                         p->next->prior = q;                         p = p->next;                 }                 else                 {                     r = p;                     q->next = p->next;                     p->next->prior = q;                     p = p->next;                 }                 cout << "第" << t <<"个死者的位置是:" << r->data << '\n';                 t++;          }          else          {              for(int j = 0;j < w - 1;j++)              //报数,选择w结点               {                               q = p;                               p = p->prior;              }              //元素出列               if(p == L.Head)              {                   r = p;                   L.Head = p->prior;                   q->prior = p->prior;                   p->prior->next = q;                   p = p->prior;              }              else              {                  r = p;                  q->prior = p->prior;                  p->prior->next = q;                  p = p->prior;              }              cout << "第" << t << "个死者的位置是:" << r->data <
     
      next != L.Head)     {                   cout << p->data <<'\t';                   p = p->next;     }     if(p)     cout << p->data << '\t';     cout << '\n';}//===============================================主函数,调用DoubleJoseph()函数==================================================int main(){	cout << "现有N人围成一圈，从第S个人开始依次报数，正向报M的人出局，再由下一人开始报数，";	cout << "逆时针数到的第W人出局。再从他逆时针的下一个人数起，顺时针数M人。";	cout << "如此循环，直到剩下K个乘客为止。"<< '\n' << '\n';	DoubleJoseph();		system("pause");	return 0;}