数据结构--约瑟夫环(含密码,C++实现)

///*约瑟夫环问题是：编号为1，2······，n的n我的按顺时针方向围坐一圈，每人持有一个密码。ios

***一开始任选一个正整数做为报数上限值m，从第一我的开始顺时针方向自1开始顺序报数，测试

***报到m时中止报数。报m的人出列，将他的密码做为新的m值，从他的顺时针方向上的下spa

***一我的开始从新从1报数，如此下去，直到全部人所有出列为止。3d

***利用链式存储结构模拟此问题，按照出列顺序打印各人的编号指针

***测试数据： m的初值为20，n=7，七我的的密码依次为3,1,7,2,4,8,4。则首先出列的值为6blog

***                     依次正确的出列顺序应该为6,1,4,7,2,3,5。游戏

*///内存

<实现代码>ci

#include <iostream>input

using namespace std;

struct People{        

    int number;         //people的编号
    int password;     //每人持有一个密码
    People *next;      //建立链表节点people
};

class Joseph{                              //循环单链表的建立

private:
    int m_iPeopleNumber;           //参与的人数
    int m_iDeleteNumber;            //要删除的序号
    int m_iOverNumber;                //报数上限

    People *head;                          //链表的头结点

public:

    Joseph(int peopleNumber,int deleteNumber,int overNumber);
    ~Joseph();
    bool game();

};

Joseph::Joseph(int peopleNumber,int deleteNumber,int overNumber){
    m_iPeopleNumber = peopleNumber;
    m_iDeleteNumber = deleteNumber;
    m_iOverNumber = overNumber;
    People *temp1,*temp2;                                                                           //建立空指针
  
    for(int i = 1; i <= m_iPeopleNumber; i++){                                             //for循环用于初始化环 
        int inputPassword;
        cout<<"please enter NO."<<i<<" people's password:";
            head = temp1; 
            temp2 = temp1;

        } 

        //不然,temp2永远指向尾结点,新创建的结点都插入到temp2以后

        else{                                                                                                        
            temp2->next = temp1;
            temp2 = temp1;
        }
    }
    temp2->next = head;                                                                                 //循环链表的实现
}


Joseph::~Joseph(){
    delete head;
    head = NULL;

}

bool Joseph::game(){                                                                              //游戏开始
    if(m_iDeleteNumber >= m_iOverNumber || m_iDeleteNumber <= 0 ){
       cout<<"Your number is over!!"<<endl;
   return false;
    }

    People *temp1,*temp2,*temp;                                                         //建立空指针

     //用count定位到第m_iPeopleNumber我的,循环后,temp1指向这我的,temp2指向这我的的上一我的

    temp1 = head;
    int count;                                                                               
    int a = m_iDeleteNumber;                                                                //赋初值
    for(int i = 1; i <= m_iPeopleNumber; i++){                                     //游戏次数是人数减去一
       count = 1; 
       while(count < a){
           temp2 = temp1;
           temp1 = temp1->next;

           count ++;

        }

        cout<<"Delete it:"<<temp1->number<<endl;                  //出局人的编号
        temp = temp1;
        a = temp->password;                                                         //记录密码，用来删除下一我的
        temp2->next = temp1->next;                                             //将当前出局人的直接前驱和直接后继链接起来
        temp1 = temp->next;                                                          //下次从当前人的下一我的开始数
        delete temp;                                                                         //释放内存
    }
    cout<<endl;
    head = NULL;                                                                      //游戏结束没有人剩余
    return true;

}

int main(){
    int peopleNumber,deleteNumber,overNumber;

    cout<<"please enter overNumber:";
    cin>>overNumber;
    cout<<"please enter peopleNumber:";
    cin>>peopleNumber;
    cout<<"please enter deleteNumber:";
    cin>>deleteNumber;

    Joseph J1(peopleNumber,deleteNumber,overNumber);
    J1.game();

    return 0;

}

<运行结果>