约瑟夫环.cpp

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的

#include<stdio.h>
#include<malloc.h>
typedef struct LNode{//构建结构体
	int password;//该人拥有的密码
	int num;//该人的编号
	struct LNode *next;
}LNode,*LinkList;

LinkList CreatLNode(int m){//构建m个人不含头结点的循环链表,并返回头指针
	int i;
	LinkList p_pri,p_cur,head;
	head=p_pri=p_cur=(LinkList)malloc(sizeof(LNode));
	printf("输入第1个人的密码:");
	scanf("%d",&p_cur->password);p_cur->num=1;
	for(i=1;i<m;i++){
		p_cur=(LinkList)malloc(sizeof(LNode));
		printf("输入第%d个人的密码:",i+1);
		scanf("%d",&p_cur->password);p_cur->num=i+1;
		p_pri->next=p_cur;
		p_pri=p_cur;
	}
	p_cur->next=head;
	return head;
}

void Cycle(LinkList L,int total,int place){//约瑟夫环的循环过程,同时输出出列的顺序号
	LinkList p_cur,p_pri,p;
	int i;
	p_pri=p_cur=p=L;
	while(total-->0)//每出列一个人,人的总数就少一
	{   
		i=1;  
        p_cur=p;
		while(i++<place)//查找要出列的结点,用p_cur表示要出列的结点
		{
			p_pri=p_cur;
			p_cur=p_cur->next;
		}
		printf("%5d",p_cur->num);//输出当前结点的编号
		place=p_cur->password;
		p_pri->next=p_cur->next;
		p=p_cur->next;
		free(p_cur);//释放已经出列的结点
	}
	printf("\n");
	return;	
}

void main()
{
	int n,k;
	LinkList L;
	printf("报数的总人数n:");
	scanf("%d",&n);
	if(n<=0) return;//不合法的n的值
	else   L=CreatLNode(n);
	printf("初始报数起始值k:");
	scanf("%d",&k);
	printf("出列的顺序为:");
	Cycle(L,n,k);
	return;
}