目录
首先什么是约瑟夫环
约瑟夫环是循环链表中的一个经典问题；题目描述：n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈；
假设10个人围成一圈，依次编号1到10，按从小到大顺序报数，报到3的人出局，流程示意图如下
约瑟夫环实现方式
我个人倾向于循环链表；
一、创建结构体变量
typedefstructNode{ intdata; //数据域structNode*next; //指针域}Node;
二、初始化链表
Node*Create(){ Node*head; head= (Node*)malloc(sizeof(Node)); if (head==NULL) { exit(1); } head->next=NULL; returnhead; }
三、构建循环链表
创建一个临时结点tail，将头结点head赋予tail，插入新结点p，让tail的next指向p，p的next指向head的下一个结点即结点p；同时让tail移到p的位置，为下个结点插入做准备；这样一个循环链表就初步完成了；
代码块
Node*Push(Node*head,Node*tail,int1){ p->data=i; tail->next=p; p->next=head->next; tail=p; returnhead; }
四、删除链表
voidPrint(Node*head){ Node*q=head; q->next=p->next; printf("%d ", p->data); free(p); p=q->next; }
五、完整代码及注释讲解
typedefstructNode{ intdata; structNode*next; }Node; //创建结构体变量Node*Create(){ Node*head; head= (Node*)malloc(sizeof(Node)); if (head==NULL) { exit(1); } head->next=NULL; returnhead; } intmain() { intn, m,i; Node*tail, *p, *q; Node*head=Create(); scanf("%d %d", &n, &m); //输入n个人围一圈及报数m的人出局//判断如果插入的数据为0或者以报数0为出局，则结束操作if (n==0||m==0) { return0; } else { tail=head; //开始没有数据，故尾结点tail与头结点重合for ( i=0; i<n; i++) { p= (Node*)malloc(sizeof(Node)); //插入新结点需，先申请动态内存if (p==NULL) { //判断动态内存是否申请成功printf("申请失败!"); exit(1); } p->data=i+1; //以下4步为插入新结点及数据的操作，具体分析请看上面构建循环链表tail->next=p; p->next=head->next; tail=p; } } p=head->next; //插入完数据后，将最后一个结点的临时结点移到第一个数据处q=tail; //然后临时结点到尾结点处i=1; while (p!=q) { //首尾结点是否重合，重合则表示只剩一个数据，结束循环if (i==m) { //对报数m的人进行出局操作q->next=p->next; //以下四步为删除操作printf("%d ", p->data); free(p); //一定记得将删除链表处的内存释放，以免内存内存泄漏p=q->next; i=1; //删除后，重新从1开始报数 } else { //没有报数到m，则p，q结点都往后移一位q=p; //先q移到p的位置p=q->next; //然后p移到q的下一个位置i++; } } printf("%d", p->data); //打印最后一位出局的人的号数return0; }
