joseph.cpp

约瑟夫环问题

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



typedef struct LNode
{
	int number;      //序号
	int code;        //密码
	struct LNode *next;

}LNode,*LinkList;

void main()
{
	void joseph(int m,int n);
	joseph(20,7);
}



void joseph(int m,int n)
{
	//建立不带头节点的循环链表
	LinkList L=(LinkList)malloc(sizeof(LNode));
	LinkList p,pre;         //p指向当前节点，pre指向当前节点的前驱
	int i,j;
	pre=L;
	p=L;
	printf("Please input the codes:\n");  //输入密码
	L->number=1;           //先建立1个节点
	scanf("%d",&L->code);
	for(i=2;i<=n;i++)      //建立剩下的n-1个节点
	{	
		p=(LinkList)malloc(sizeof(LNode));	
		p->number=i;
		scanf("%d",&p->code);	
		pre->next=p;
		pre=p;
		p->next=L;

	}
	p->next=L;

	pre=L;
	p=pre;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<m;j++)           
		{
			//遍历链表(m-1)次
			pre=p;
			p=p->next;
		
		}
			pre->next=p->next;
			printf("The number which is out is: %d.\n",p->number);
			m=p->code;  //密码重新赋值
			free(p);
			p=pre->next;

	}


}