学步园

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始从1报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

与下一个人继续报数，则下个是m的倍数的人出列，意思是一样的。

/*
author :lingling
date: 2011-10-05
description:  循环列表实现josephos
*/

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

typedef struct node
{
	int data;
    node* next;
}LinkList;

LinkList* create(int );
void JOSEPHUS(int ,int ,int ,LinkList*);


void main()
{
	int n=9;
	int m=5;
	int k=1;
	LinkList* p;
	p = create(n);
	/*for(int i=0;i<n;i++)
	{
		printf("%d->",p->data);
		p= p->next;
	}*/
		
	JOSEPHUS(n,m,k,p); //共n个人，m的出列，从k开始报数
}
LinkList* create(int n)
{
   LinkList* head,*p;
   head= (LinkList*)malloc(sizeof(LinkList));
   head->data=1;
   head->next=head;   //一个数据的循环链表，没有表头
   p=head;
   for (int i=1;i<n;i++)  //不断插入进去，建立一个循环链表
   {
	   LinkList* t=(LinkList*)malloc(sizeof(LinkList));
	   t->data=i+1;
	   p->next=t;
	   t->next=head;
	   p=p->next;
   }
  
   return head;
}
void JOSEPHUS(int n,int m,int k,LinkList* p)
{
   LinkList* r,s;
  
  while (k--)  //把指针移到当前报数的人的编号
  {
	  r=p;
	  p=p->next;
  }
  while (n>1)
  {
	  for (int s=m-1;s>1;s--)
	  {
		  r = p;
		  p=p->next;
	  }
	  r->next=p->next;
	  printf("%d",p->data);
	  printf("\n");
	  free(p);
	  p=r->next;
	  r=p;       //把r移动下一个人
	  p=p->next;
	  n--;
  }
  printf("最后一个出局的是%d",p->data);
  printf("\n");

}

结果

现在对链表的操作熟悉了，但是这个的实现也是参考了答案，并且在调试的时候改正的。