main.cpp

约瑟夫环的实现

#include <iostream>  //实现约瑟夫环
using namespace std;

struct node  //定义一个结构体用于存储小孩编号及一个后继指针
{
    int no;
    node* next;
};

void func(int n,int s,int m,node* p,node* q);  //申明一个用于让小孩按报数结果出列的函数

int main()
{
    int m=0,n=0,s=0;
    node *start,*end;  //指针start用于指示第一个小孩，end用于指示最后一个
    node *p,*q;

    cout<<"请输入小孩个数:"<<endl;

    cin>>n;
    cout<<endl;
    cout<<"小孩从s到m报数，请分别输入s和m"<<endl;
    cin>>s>>m;
    cout<<endl;

    start=end=new node;  //申请结点
    start->no=1;  //起始小孩编号为1
    for (int i=2;i<=n;i++)  //将所有小孩编号存入
    {
        p=new node;
        p->no=i;
        end->next=p;
        end=p;
    }
    end->next=start;  //形成环形链表
    q=end;
    cout<<"小孩依次出列的顺序为：";
    cout<<endl;
    func(n, s, m, p, q);  //调用函数

    delete p;
    delete q;  //释放空间
    delete start;
    delete end;

    return 0;
}

void func(int n, int s, int m, node* p, node* q)
{
    while (n>0)  //小孩从s到m报数，直到报m的前一个小孩
    {
        for (int j=s;j<m;j++)
        {
            q=q->next;
        }
        p=q->next;  //将报m的小孩的地址给p

        cout<<p->no<<"    ";  //输出报m的小孩编号
        q->next=p->next;  //去掉m点后，将断掉的链表接起来
        n--;  //去掉一个编号后接着报数
    }

}