josephus.cpp

用循环链表实现的约瑟夫问题。uuhorse

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

typedef struct Node 
{
	int				  data;
	struct Node *next;
} Node, * CLinkList;

void InitCList (CLinkList &L, int total);
void Joseph (CLinkList &L, int nout);
void main()
{
	CLinkList L;
	int total,nout;
	printf("Please input the total number:\ntotal = ");
	scanf("%d",&total);
	printf("Please input the number to go out:\nnout = ");
	scanf("%d",&nout);
	InitCList(L,total);
	Joseph(L,nout);
}
void InitCList (CLinkList &L,int total)
{
	CLinkList p;
	L=(CLinkList)malloc(sizeof(Node));
	p=L;
	for(int i=1;i<total;i++)
	{
		p->data=i;
		p->next=(CLinkList)malloc(sizeof(Node));
		p=p->next;
	}
	p->data=i;
	p->next=L;
}
void Joseph (CLinkList &L,int nout)
{
	CLinkList p,q;
	int num=1;
	p=L;
	while (p!=p->next)
	{
		num=(++num)%nout;
		if(!num)
		{
			q=p->next;
			p->next=q->next;
			num=(num++)%nout;
			printf("%5d",q->data);
			free(q);
		}
		p=p->next;
	}
	printf("%5d\n",p->data);
	free(p);
}