單鏈表實現約瑟夫環問題

約瑟夫環

這裡建議使用迴圈單鏈表

代碼實現(c語言)

#include<stdio.h>
#include<stdlib.h>

typedef struct node{  
	int data;      
	struct node *next;    
}Node;

void ysflb(int n,int k){//總共n,k出去
 //創建鏈表
  Node *head = NULL,*p = NULL,*r = NULL,*next = NULL;
  head = (Node *)malloc(sizeof(Node));  //開空間
  if(head == NULL){     //判斷head是否創建成功，一般都成功
  	printf("Failed");
  	return;
  }
  
  head->data = 1;
  head->next = NULL; //這是第一個節點
  p = head;//p和head是同一個節點（指向）
 
  //迴圈，尾插
  for(int i = 2;i <= n; i++){
  	r = (Node *)malloc(sizeof(Node));
  	r->data = i;
  	r->next = NULL;
  	p->next = r;//p的next指向r，即將r連接再p的後面，一二節點連接完成。
	p = r;//將p向後移動一位，從第一個節點到了第二個節點   
  } 
    
   p->next = head; //讓p的next指回去第一個節點
   p = head; //p再指向第一個節點

   //迴圈鏈表創建完成 
   
   while(p->next != p){//判斷是否只剩一個元素
   	for(int i = 1;i < k;i++){
   		r = p; //r就是p的前一個節點，一會p會向後移動 
   		p = p->next;//p向後移動一位，p就是要出去的節點 
	   }
   	printf("%d\t",p->data); 
   	//刪除p 
    //越過當前節點，將前一個節點於當前節點的後一個相連
    r->next = p->next;//前一個節點的next指向後一個節點的next
    p = p->next;//p向移一個節點（p成為當前節點的後一個節點）
    }
    printf("最後剩餘："); 
    printf("%d",p->data); 
}


int main(){
	ysflb(10,3);
	return 0;
}