什么是约瑟夫环

约瑟夫环是循环链表的一个典型应用，其描述如下：m个人围成一圈，从任意一个人开始，按顺时针顺序使所有人依次从1开始报数，报到n的人出列，然后使n之后的人接着从1开始报数，再次使报到n的人出列，不断重复此操作，并输出出局的先后顺序，直到最后只剩下一个人，如下示意图所示

假设8个人围成一圈，依次编号1到8，按从小到大顺序报数，报到3的人出局，流程如下

第一轮：从1到3，三号选手出局；

第二轮：4号选手从1开始报数，6号选手报到3，则6号选手出局；

第三轮：7号选手从1开始报数，1号选手报到3，则1号选手出局

第四轮：2号选手从1开始报数，5号选手报到3，则5号选手出局

第五轮：7号选手从1开始报数，2号选手报到3，则2号选手出局

第六轮：4号选手从1开始报数，8号选手报到3，则8号选手出局

第七轮：4号选手从1开始报数，此时只剩下4号和7号，所以4号报到3，4号出局，只剩7号

约瑟夫环的实现方式

一：数组链接方式实现；

二：数组标志位实现

三：循环链表实现（重点）；

因为我是学习循环链表的时候接触的约瑟夫环，所以本文只用第三种方式实现——循环链表实现，当然，循环链表实现约瑟夫环也有很多种写法，下面仅仅是我个人的观点，有不完善的地方还请见谅，下面让我们进入正文。

循环链表的构建

因为本文主要讲述的是用循环链表实现约瑟夫环，所以循环链表的创建就一带而过了，对循环链表不太熟悉的小伙伴也可以参考一下我的上一篇博客，里面对循环链表有比较清楚的讲解，点此链接可以直接进入：C语言数据结构篇——单循环链表的创建，插入，节点删除，打印等操作_Grande joie的博客-CSDN博客下面直接附上为大家封装好的函数

头结点和数据节点结构体的定义如下

typedef struct header//头结点
{
? ? int length;
? ? struct node* next;
}head;
typedef struct node//数据节点
{
? ? int val;
? ? struct node* next;
}node;

1， head* listcreat(）//循环链表的创建

head* listcreat()
{
    head* p;
    p=(head*)malloc(sizeof(head));
    p->next=NULL;
    p->length=0;
    return p;
}

2， void listinsert(head* p,int pos,int x)//循环链表数据节点的插入

void listinsert(head* p,int pos,int x)
{
    if(p==NULL||pos<0||pos>p->length)
    {
        printf("listinsert():error\n");
        return;
    }
    node* temp=(node*)malloc(sizeof(node));
    temp->val=x;
    node* pcur=p->next;//指向第一个数据节点
    node* plast=p->next;//指向最后一个数据节点
    while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点
    {
        plast=plast->next;
    }
    if(p->length==0)//判断循环链表为空的情况
    {
        p->next=temp;
        temp->next=temp;
    }
    else if(pos==0)//头插
    {
        plast->next=temp;
        temp->next=pcur;
        p->next=temp;
    }
    else if(pos==p->length)//尾插
    {
        plast->next=temp;
        temp->next=pcur;
    }
    else
    {
        node* pval=p->next;//pval用来指向要插入位置的数据节点
        for(int i=1;i<pos;i++)
        {
            pval=pval->next;
        }
        temp->next=pval->next;
        pval->next=temp;
    }
    p->length++;
    return;
}

void listdelete(head* p,int x)//循环链表数据节点的删除?

void listdelete(head* p,int x)
{
    node* temp;//temp指向要删除的节点
    temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        if(temp->val==x)
        {
            break;
        }
        temp=temp->next;
    }
     if(temp->val!=x)
    {
        printf("listdelete():error\n");
        return;
    }
    node* pcur=p->next;//pcur指向第一个节点
    node* plast=p->next;//plast用来指向最后一个节点
    while(plast->next!=pcur)
    {
        plast=plast->next;
    }
    if(p->length==1)//只有一个元素时
    {
        p->next=NULL;
    }
    else if(temp==pcur)//删除的是第一个节点
    {
        p->next=pcur->next;
        plast->next=pcur->next;
    }
    else if(temp==plast)//删除的是最后一个节点
    {
        node* pre=p->next;//指向倒数第二个节点
        while(pre->next!=plast)
        {
            pre=pre->next;
        }
        pre->next=pcur;
    }
    else
    {
        node* pre=p->next;
        while(pre->next!=temp)//使pre指向temp的前一个元素
        {
            pre=pre->next;
        }
        pre->next=temp->next;
    }
    p->length--;
}

void listprint(head* p)//循环链表的遍历打印（输出）?

void listprint(head* p)
{
    if(p==NULL||p->length==0)
    {
        printf("listprint():error");
        return;
    }
    node* temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
    }
    printf("\n");
    return;
}

有了这些封装函数，一个基础的循环链表就可以构建啦

循环链表在约瑟夫问题上的应用?

int main()
{
    head* p;定义循环链表头结点
    p=listcreat();
    printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n");
    printf("请输入约瑟夫环的总人数m\n");
    int m,n;
    scanf("%d",&m);
    printf("请输入被踢出的报数n\n");
    scanf("%d",&n);
    for(int i=m;i>0;i--)//围圈操作（即按要求构建循环链表）
    {
        listinsert(p,0,i);
    }
    printf("输出初始循环链表\n");
    listprint(p);
    node* temp=p->next;//定义指向循环链表第一个数据节点的指针，方便报数
    int count=1;//因为此时temp已经指向第一个人了，所以报数从1开始，多看几遍也许好理解一点
    printf("被踢顺序\n");
    while(temp->next!=temp)//剩下一个数时结束循环
    {
        if(count==n)//如果报数等于需要出局的数
        {
            node* pre=p->next;//用于保留位置使temp不至于丢失
            while(pre->next!=temp)//遍历到指向temp的前一个节点
            {
                pre=pre->next;
            }
            printf("%d ",temp->val);
            listdelete(p,temp->val);//出局操作（即删除该数据节点）
            //此时如果没有前面定义的pre，那么temp就没有任何指向了，而有了pre，出局后就可以用                            
            temp代表pre的指向，temp就不会丢失指向
            temp=pre;
            count=0;//因为temp指向了出局的前一个人，下一个人报数从一开始，所以报数先归0
            continue;//出局时就不执行遍历和报数操作
        }
        count++;
        temp=temp->next;
    }
    printf("\n");
    printf("链表中最后被剩下的是：\n");
    listprint(p);
}

完整代码?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct header
{
    int length;
    struct node* next;
}head;
typedef struct node
{
    int val;
    struct node* next;
}node;
head* listcreat()
{
    head* p;
    p=(head*)malloc(sizeof(head));
    p->next=NULL;
    p->length=0;
    return p;
}
void listinsert(head* p,int pos,int x)
{
    if(p==NULL||pos<0||pos>p->length)
    {
        printf("listinsert():error\n");
        return;
    }
    node* temp=(node*)malloc(sizeof(node));
    temp->val=x;
    node* pcur=p->next;//指向第一个数据节点
    node* plast=p->next;//指向最后一个数据节点
    while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点
    {
        plast=plast->next;
    }
    if(p->length==0)//判断循环链表为空的情况
    {
        p->next=temp;
        temp->next=temp;
    }
    else if(pos==0)//头插
    {
        plast->next=temp;
        temp->next=pcur;
        p->next=temp;
    }
    else if(pos==p->length)//尾插
    {
        plast->next=temp;
        temp->next=pcur;
    }
    else
    {
        node* pval=p->next;//pval用来指向要插入位置的数据节点
        for(int i=1;i<pos;i++)
        {
            pval=pval->next;
        }
        temp->next=pval->next;
        pval->next=temp;
    }
    p->length++;
    return;
}
void listdelete(head* p,int x)
{
    node* temp;//temp指向要删除的节点
    temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        if(temp->val==x)
        {
            break;
        }
        temp=temp->next;
    }
    node* pcur=p->next;//pcur指向第一个节点
    node* plast=p->next;//plast用来指向最后一个节点
    while(plast->next!=pcur)
    {
        plast=plast->next;
    }
    if(temp->val!=x)
    {
        printf("listprintf():error\n");
        return;
    }
    if(p->length==1)//只有一个元素时
    {
        p->next=NULL;
    }
    else if(temp==pcur)//删除的是第一个节点
    {
        p->next=pcur->next;
        plast->next=pcur->next;
    }
    else if(temp==plast)//删除的是最后一个节点
    {
        node* pre=p->next;//指向倒数第二个节点
        while(pre->next!=plast)
        {
            pre=pre->next;
        }
        pre->next=pcur;
    }
    else
    {
        node* pre=p->next;
        while(pre->next!=temp)//使pre指向temp的前一个元素
        {
            pre=pre->next;
        }
        pre->next=temp->next;
    }
    p->length--;
}
void listprint(head* p)
{
    if(p==NULL||p->length==0)
    {
        printf("listprint():error");
        return;
    }
    node* temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
    }
    printf("\n");
    return;
}
int main()
{
    head* p;
    p=listcreat();
    printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n");
    printf("请输入约瑟夫环的总人数m\n");
    int m,n;
    scanf("%d",&m);
    printf("请输入被踢出的报数n\n");
    scanf("%d",&n);
    for(int i=m;i>0;i--)
    {
        listinsert(p,0,i);
    }
    printf("输出初始循环链表\n");
    listprint(p);
    node* temp=p->next;
    int count=1;
    printf("被踢顺序\n");
    while(temp->next!=temp)//剩下一个数时结束循环
    {
        if(count==n)
        {
            node* pre=p->next;
            while(pre->next!=temp)//指向temp的前一个节点
            {
                pre=pre->next;
            }
            printf("%d ",temp->val);
            listdelete(p,temp->val);
            temp=pre;
            count=0;
            continue;
        }
        count++;
        temp=temp->next;
    }
    printf("\n");
    printf("链表中最后被剩下的是：\n");
    listprint(p);
}

循环链表在约瑟夫环上的应用就完整的写出来了，随便写点数据运行一下就是下面这个效果啦