yue.c

约瑟夫算法 实现报到规定数值的人退出链表

#include <stdio.h>
#include <stdlib.h> 
/*#define n 13  宏定义,设定19个猴子  */
/*     #define m  4  报数最大报到4  */
typedef struct monkey /* 设计一个猴子的结构体,该结构体用monkey表示  */
/* link表示该结构体的指针  */
{ 
 int num; /* 它的号码  */
 struct monkey *next; /* 下个猴子的地址指针  */
} monkey,*link; 
 int i;
 int n,m;
 link p,head,p2;    /* 定义了三个猴子结构的指针  */
void creat()
{

 head=p=p2=(link)malloc(sizeof(monkey));/* 开辟空间用来存储猴子结构  */
 for(i=1;i<n;i++) /* 生成了个猴子结构的链表  */
 {
 p=(link)malloc(sizeof(monkey)); /* 开辟新空间用来存各个猴子结构  */
 p2->next=p;
 p2=p;
 }
 p2->next=head;/* 这步很重要,这样链表变成循环链表了,也就是说链表到了结  */
 /* 尾它的下个地址就是链表头了如此不停循环下去,就是个圆  */
 p=head;
 printf("The number of monkey\n");
 for(i=1;i<=n;i++)
 {
  p->num=i; /* 对猴子编号  */
  printf("%d NO:%d ",p->num,p->num);
  p=p->next; /* 指针指向下个猴子  */
 } /* 所有猴子编号结束  */
 i=0;
 p=head; /* 又将p指向了链表的头  */
 printf("\n");
}
action()
{
    while(1) 
 {
 i++;
 printf("NO.%d new num:%d  ",p->num,i);
 if(p->next==p)/* 这是结束条件,你想自己的下一个就是自己本身了,是不是说  */
 /* 明只剩下自己了,也就是大王了  */
 break;
 if(i==m) /* 如果这一个报到了数m  */
 {
   i=0; /* 再次从1开始报数,因为以后要执行i++语句  */
   printf("NO.%d exit\n",p->num); /* 这个号码的猴子要被淘汰  */
   p2->next=p->next;/* 将该猴子从链表中拿下  */
   p=p2->next;/* 指针指向下一个猴子  */
   continue; /* 该语句可以舍去,没有啥用  */
  }
 else /* 没有报到m的继续报数  */
  {
   if(i==m-1) p2=p;
   p=p->next;
  }
 }
 printf("\n");
 printf("Winner:%d",p->num);
}
void warn()
{
   if(n<=m)
  {
      printf("error! please input the new number(n>m)\n");
      scanf("%d%d",&n,&m);
      warn();
      getch();
   }
   else{
   creat();
   action();
   getch();
   }
}
   void main() 
{ 
  printf("please input monkey's number n and m(the number who will exit)\n");
  printf("n:  m:( n>m )\n");
  scanf("%d%d",&n,&m);
  warn();

}