josephus.c

来自「用循环链表解Josephus问题。设有n个人围坐在一个圆桌周围」· C语言 代码 · 共 62 行

#include<stdio.h>   
  typedef struct node{
  int n;   
  struct node *m;
  } NODE;  
  NODE *head;/*定义一个指向该结构体的头指针*/
  
  NODE *create(int x)/*创建具有x个结点的单链表*/  
  {   
  NODE *p;   
  int i=1;   
  p=head=(NODE *)malloc(sizeof(NODE));   
  head->m=head; /*造循环链表时头指针的指针域设置*/  
  while(i<=x)   
  {   
  p->n=x+1-i;   
  p->m=head->m;   
  head->m=p;   
  i++;   
  p=(NODE *)malloc(sizeof(NODE));   
  }   
  return(head);   
  } 
  
  void output(int a,int b)   
  {   
  int i;   
  NODE *p,*q;   
  p=head; /*将指针移到起始结点，即第a个结点*/    
  i=0;   
  while(i<a)   
  {   
  p=p->m;   
  i++;   
  }    /*删除满足报数值的结点*/
  while(p->m!=p)   
  {   
  i=1;   
  while(i<b)/*找到符合报数值结点的前一个结点,即第b-1个结点*/  
  {   
  p=p->m;   
  i++;   
  }    /*先输出，后删除*/
  q=p->m;   
  printf("%d",q->n);   
  p->m=q->m;   
  free(q);   
  }   
  printf("%d",p->n);/*输出仅剩的结点*/ 
  }   
  
  main()   
  { 
  int location,callnum;    
  printf("\ninput location=");   
  scanf("%d",&location);   
  printf("\ninput callnum=");   
  scanf("%d",&callnum); 
  head=create(location);   
  output(location,callnum);       
  }