chy.c

线性表 约瑟夫环

#include<stdio.h>
#define new(type) (type *)malloc(sizeof(type))
typedef struct rNode * RNodePtr;
typedef struct rNode {
int pos;
RNodePtr next;
}RNode,* RingList;
void InitRing(int n,RingList *R)
{ RNodePtr p,q;
  int i;
  *R=q=new(RNode); //创建有n个结点的循环单链表
  for(i=1;i<n;i++)
  { p=new(RNode);
    q->pos=i;
    q->next=p;
    q=p;
  }
     p->pos=n;
     p->next=*R;
     *R=p;//R指向循环链表表尾结点，作计数准备
}
void DeleteDeath(int n,int k,RingList *R)
{ int i,j;
  RNodePtr p,q;
  p=*R;
  for (i=1;i<=n/2;i++)     //删除一半结点
{ for(j=1;j<=k-1;j++)    //沿链前进k-1步
   p=p->next;
   q=p->next;                //q为被删结点
   p->next=q->next;      //删除
   printf("%4d",q->pos); //输出被删除的结点的位置
   free(q);
}
*R=p;
printf("\nfinished.\n");
}
main()
{ RingList R;
  RNodePtr p,q;
  int n,k;
  printf("n,k=");
  scanf("%d%d",&n,&k);
  InitRing(n,&R);
  DeleteDeath(n,k,&R);
}