单链表实现约瑟夫环问题

约瑟夫环

这里建议使用循环单链表

代码实现(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	",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;
}