需求表达：C语言链表实现约瑟夫环问题
分析：
实现：
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int payload ;
struct node* next ;
}node ;
/*Function:在约瑟夫环尾部插入一个结点。add
* param:node* tail 约瑟夫环的尾巴结点;
* return: node* tail 返回新的约瑟夫环尾巴结点
* */
node* add ( node* tail){
if(tail == NULL){
tail = (node* ) malloc(sizeof(node)) ;
tail -> next = tail ;
return tail ;
}
else{
node* new_tail = (node* ) malloc (sizeof(node));
new_tail -> next = tail -> next ;
tail -> next = new_tail ;
return new_tail;
}
}
/*Function:遍历约瑟夫环，traverse_joseph_circle
*param:node* tail
*return :void
*
*
* */
void traverse_joseph_circle(node* tail){
node* move = tail ;//作移动的指针
//整体思路：有点结点的情况下，进入遍历；把尾结点和头结点的关系给干掉，展成一条链，回到头结点，往下移动，在往下移动前，先游历这个结点，在判断能不能往下
游历。
while(move != NULL){
move = move -> next ;//移动回头结点
printf("%d ;", move -> payload) ;
if (move == tail) break ;
}
printf("\n");
}
/*Function:约瑟夫环问题的实现。eliminate
*param :node* tail; int step
*return: void
*
* */
void eliminate(node* tail,int step){
node* move = tail ;
node* save_previous = tail ;
int count = 0 ;
while (NULL != tail && (move != move -> next)){
save_previous = move ;
move = move -> next ;if(++ count == step){
save_previous -> next = move -> next ;
printf("当前要删结点：%d\n",move -> payload);
if (tail == move ) tail = save_previous ;//更新约瑟夫环
free(move);
printf("当前结点：\n");
traverse_joseph_circle (tail) ;
move = save_previous ;
count = 0 ;
}
}
}
int main(){
node* tail;
//构建十个结点的约瑟夫环
int i ;
for ( i = 0 ; i < 20 ; i ++ ){
tail = add (tail );
tail -> payload = i ;
}
traverse_joseph_circle (tail) ;
eliminate(tail,3);
}
效果：
[xx@localhost joseph_circle]$ ./joseph_circle.out
0 ;1 ;2 ;3 ;4 ;5 ;6 ;7 ;8 ;9 ;
当前要删结点：2
当前结点：
0 ;1 ;3 ;4 ;5 ;6 ;7 ;8 ;9 ;
当前要删结点：5
当前结点：
0 ;1 ;3 ;4 ;6 ;7 ;8 ;9 ;
当前要删结点：8
当前结点：
0 ;1 ;3 ;4 ;6 ;7 ;9 ;
当前要删结点：1
当前结点：
0 ;3 ;4 ;6 ;7 ;9 ;
当前要删结点：6
当前结点：
0 ;3 ;4 ;7 ;9 ;
当前要删结点：0
当前结点：
3 ;4 ;7 ;9 ;
当前要删结点：7
当前结点：
3 ;4 ;9 ;
当前要删结点：4
当前结点：
3 ;9 ;
当前要删结点：9
当前结点：
3 ;