循环链表解决带密码的约瑟夫环问题

约瑟夫环

什么是约瑟夫环？

这里用循环链表实现一个带密码的约瑟夫环

意思是有n个人，编号1-n，他们每个人手里拿着属于自己的密码。大家按照编号坐成一圈，然后给定一个数m，然后大家从头进行0-m报数，报到m的人出列，交出密码，剩余的人从这里开始继续报数，规则一样...直到全部出列，问你最后的密码是什么?

easy

// 有头结点循环链表实现约瑟夫环问题  
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;
typedef struct rnode{
	int num;//序号 
	int key;//密码 
	rnode* next;
}rnode;
typedef rnode* ringlist; 

Status creat(ringlist* L){
	*L=(rnode*)malloc(sizeof(rnode));
	if(*L==NULL){
		printf("空间分配失败！\n");
		return ERROR;
	}
	(*L)->next=NULL;
	return OK;	
}
 
Status init(ringlist* L,int n){//
    rnode* tail=*L;
	for(int i=1;i<=n;i++){
		rnode *newx;
		newx=(rnode*)malloc(sizeof(rnode));
		if(!newx){
			printf("空间分配失败！\n");
			return ERROR;
		}
		newx->next=*L;
		newx->num=i;
		printf("输入第%d个节点的密码：",i);
		scanf("%d",&newx->key);
//		newx->key=i;
		tail->next=newx;
		tail=tail->next;
	}
	return OK;
	
}
int kill(ringlist L,int m,int res[]){//实现报m出列 ,结果存在res中 
	int cnt=0;//报数计数器  
	int len=0;//res数组计数器  
	rnode *p=L->next,*q=L,*del;
	while(p!=q){//p==q时  表示只有头节点  
		if(p==L){//一个循环 越过头节点  
			p=p->next;
			q=q->next;
			continue;
		}
		cnt++;
		if(cnt==m){
			res[++len]=p->key;
			del=p;
			p=p->next;
			q->next=p;
			free(del);
			cnt=0;
		}
		else{
			p=p->next;
			q=q->next;
		}
	}
	return len; 
}

void show(ringlist L){
	rnode* p=L->next;
	printf("\n");
	while(p!=L){
		printf("第%d个人的密码是%d\n",p->num,p->key);
		p=p->next;
	}
	printf("\n"); 
}

int main()
{
	ringlist L;
	int n,m,res[999],len;
	printf("输入人的个数: ");
	scanf("%d",&n);
	creat(&L); 
	init(&L,n);
	show(L);
	printf("输入循环的基数：");
	scanf("%d",&m); 
	len=kill(L,m,res);
	printf("约瑟夫密码是：\n");
	for(int i=1;i<=len;i++)	
		printf("%d ",res[i]);
	
	return 0;
}
           

还写了一个没有头结点的，完全类似，唯独判断结束的地方有些修改

// 无头结点循环链表实现约瑟夫环问题  
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;
typedef struct rnode{
	int num;//序号 
	int key;//密码 
	rnode* next;
}rnode;
typedef rnode* ringlist; 

Status init(ringlist* L,int n){//无头结点插入多项式  
	*L=(rnode*)malloc(sizeof(rnode));
	if(*L==NULL){
		printf("空间分配失败！\n");
		return ERROR;
	}
	(*L)->num=1;
	printf("输入第1个节点的密码：");
	scanf("%d",&(*L)->key);
	(*L)->next=*L;
	rnode* tail=*L;

	for(int i=2;i<=n;i++){
		rnode *newx;
		newx=(rnode*)malloc(sizeof(rnode));
		if(!newx){
			printf("空间分配失败！\n");
			return ERROR;
		}
		newx->next=*L;
		newx->num=i;
		printf("输入第%d个节点的密码：",i);
		scanf("%d",&newx->key);
		tail->next=newx;
		tail=tail->next;
	}
	return OK;
}

int kill(ringlist L,int m,int res[]){//实现报m出列 ,结果存在res中 
	int cnt=0;//报数计数器  
	int len=0;//res数组计数器  
	rnode* p=L,*del;
	rnode* pre=L;
	
	int flag=1;
	while(flag){
		cnt++;
		if(cnt==m){
			//pre=p->next;
			while(pre->next!=p)//找到前一个节点的位置，用于删除当前节点 	
				pre=pre->next;
			res[++len]=p->key;
			del=p;
			p=p->next;
			if(p->next==p)
				flag=0;//判断终点  
			pre->next=p; 
			free(del);
			cnt=0;
		}
		else
			p=p->next;
	}
	return len; 
}

void show(ringlist L){
	rnode* p=L->next;
	printf("\n");
	while(p!=L){
		printf("第%d个人的密码是%d\n",p->num,p->key);
		p=p->next;
	}
	printf("\n"); 
}


int main()
{
	ringlist L;
	int n,m,res[999],len;
	printf("输入链表 的长度: ");
	scanf("%d",&n);
	init(&L,n);
	show(L);
	printf("输入循环的基数：");
	scanf("%d",&m); 
	len=kill(L,m,res);
	printf("\n约瑟夫密码是：\n");
	for(int i=1;i<=len;i++)	
		printf("%d ",res[i]);
	
	return 0;
}