main.c

josephus环的普通算法

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

//赖丛山 学号1070310213

//定义链表节点
   typedef struct Lnode{
       int data;
       struct Lnode*next;

   }*Linklist;

//函数参数n为人数，k为开始报数者的序号，m为出列者的序号
   void JOSEPHUS(int n,int k, int m)
   {
//p指向当前节点，r为p的前趋，list为头节点
       Linklist p,r,list;
       int i;
//建立循环链表。初始化
       for (i=1;i<=n;i++)
       {
           p=(Linklist)malloc(sizeof(struct Lnode));
           if(!p)
           {
               printf("No enough space");
               exit(0);
           }

           p->data=i;
           if(i==1)
           {
              list=p;
              r=p;
            }
           else
           r->next=p;
           r=p;

       }
//使链表循环
       p->next=list;
//使p指向头节点
       p=list;
//使p指向第1个报数者
       for (i=1;i<k;i++)
       {
           r=p;
           p=p->next;

           }


//循环出列并打印
       while (p->next!=p)
       {
           for(i=k;i<=m-1;i++)
           {
               r=p;
            p=p->next;

            }
            r->next=p->next;

            printf("%4d",p->data);
            free(p);
            p=r->next;

        }
        printf("%4d",p->data);
   }

int main()
{
   int n,k,m;

   printf("please enter the size of n,k,m\n");

   scanf("%d%d%d",&n,&k,&m);

//输入不正确情况
   if(n<=0||k<=0||m<=0)
   {
       printf("error!\n");
       exit(0);
   }
//调用函数
   JOSEPHUS(n,k,m);




return 0;
}