约瑟夫环——静态循环链表，动态循环链表

静态循环链表

struct node{
    int flag;
    int next;
}arr[11];

#include"stdio.h"
#include"stdlib.h"
#include"s.h"
main(){
    int i,j,k;
    for(i=0;i<11;i++){
        arr[i].flag =1;
        arr[i].next =i+1;
    }
    arr[10].next=1;
    j=10;
    for(i=0;i<5;i++){
        for(k=0;;){
            if(k<3){
                j=arr[j].next;
                k+=arr[j].flag ;
            }
            else
                break;
        }
        arr[j].flag =0;
    }
    for(i=0;i<11;i++){
        printf("%d ",arr[i].flag);
    }
    printf("\n");
    system("pause");
}

动态循环链表

#define Total 6
#define Num 4
typedef int DataType;
typedef struct node{
    DataType password;
    int number;
    struct node *next;
}ListNode;

#include"stdio.h"
#include"stdlib.h"
#include"s.h"
void InsertNode(ListNode **list,ListNode *head,int i,DataType x){
    ListNode *p;
    p=(ListNode*)malloc(sizeof(ListNode));
    p->number =i;
    p->password =x;
    if(*list==NULL){
        *list=p;
        p->next =NULL;
    }
    else{
        p->next =head->next ;
        head->next =p;
    }
}
void CreateJoseph(ListNode **link,int n){
    ListNode *head=NULL,*list=NULL;
    int i;
    int password[]={6,2,5,8,3,4};
    for(i=0;i<n;i++){
        InsertNode(&list,head,i+1,password[i]);
        if(i==0){
            head=list;
        }
        else{
            head=head->next ;
        }
        printf("%d ",password[i]);
    }
    printf("\n");
    head->next =list;
    *link=list;
}
void ExJoseph(ListNode **link,int m){
    ListNode *p,*q;
    int i;
    p=q=*link;
    while(q->next !=p){
        q=q->next ;
    }
    while(p!=p->next ){
        for(i=0;i<m-1;i++){
            q=p;
            p=p->next ;
        }
        q->next =p->next ;
        printf("%d ",p->number );
        m=p->password ;
        free(p);
        p=q->next ;
    }
    printf("\n");
    printf("last person:%d",p->number );
}
main(){
    ListNode *link;
    CreateJoseph(&link,Total);
    ExJoseph(&link,Num);
    system("pause");
}

用到二级指针，在创建约瑟夫环的过程中，需要插入数据节点，而插入过程中最好用指针，定义两个指针，一个为list指针，用于记录第一个节点，以便形成循环链表，另一个为辅助指针head指针，用于指向插入链表的节点，在插入函数中最终是对该指针进行操作，一级指针只能改变指针指向数据的内容，不可取，二级指针可以改变list指针地址的指向，使其指向链表的头节点，并保存。
在输出约瑟夫环的函数中定义两个节点，p,q。并使q只想p之前。循环结束的条件是只剩一个节点，在循环过程中，经过第一次循环过后，删除p节点，并将p的密码赋值给m,q的下一个节点指向p的下一个节点，释放p，重新赋值p为删除节点之后q的下一个节点。