需求表達：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 ;