《C程序设计教程(等2版)》习题7.5和习题8.6编程练习

/* C程序设计教程（等2版）谭浩强著， 习题7.5和习题8.6类似，其中习题8.6要求使用链表来实现。
7.5 有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，
问最后留下的是原来等几号的那位。

Input a number of people to n, and n is between 1 and 1000. Use an array[n], let array[i]=1. If a
person quit, a corresponding array element becomes '-1'. Use k to count the numbers of array[n]
that are equal '1'. At first m=0, after a cycle, let m=(k+m)%3. When array[i]==1 && (k+m)%3==0,
let array[i]='-1'. At end of a cycle, j is equal reserved people. When j==1, exit cycle.*/

#include

int main()
{ int remove_from_circle (int n);
  int i,k;
  printf ("Please input a integer number of people between 1 and 1000: \n");
  scanf ("%d", &k);
  if (k<1 || k >1000) printf ("The input number is not right.\n");
  else { i=remove_from_circle (k);
  printf ("The number of last reserve person is: %d .\n",i);
  }
  return 0;
}

int remove_from_circle (int n)
{ int i,j=n,k=n,m=0,x=0,array[1000];
  if (n<1 || n>1000) return (-1);
  for (i=0; i   while (j!=1)
  { j=0;k=0;
    for (i=0; i     { if (array[i]==1)
      { ++j;++k;
      if ((k+m)%3==0) { array[i]=-1; --j; }
      else x=i;
      }
    }  
  m=(k+m)%3;
  }
  return (x+1);
}

============================================================

/* 习题8.6 13个人围成一个圈，从等1个人开始报号1,2,3。凡是报到3者退出圈子。找出最后留在圈中的人的序号。要求用链表实现。
在这里使用了循环链表，编程的时候会方便一些。
reserved in circle, using a cycle chain table. It's easy and useable.
the "creat ()" function can creat a cycle chain table, and the "reserved_in_circle  ()" function can remove people, and find the last reserved person. */

#include
#include
#define LEN sizeof (struct person)
struct person
{ int num;
  struct person * next;
};

int main ()
{ struct person * creat (int n);
  int reserved_in_circle (struct person * head);
  struct person * head;
  int i,n=13;
  head=creat(n);            //调用creat函数，返回第1个结点的起始地址
  i=reserved_in_circle (head);
  printf ("The number of the reserved person is %d.\n",i);
  return 0;
}

struct person * creat (int n)    //建立链表的函数
{ struct person * head, * p1, * p2;
  int i=1;
  p1=p2= (struct person *) malloc (LEN);
  p1->num = i;
  head=NULL;
  while (i <= n)
  { if (i==1) head=p1;
    else p2->next=p1;
    p2=p1;
    p1= (struct person *) malloc (LEN);
    p1->num = ++i;
  }
  p2->next=head;
  free (p1);
  return (head);
}

int reserved_in_circle (struct person * head)    //按规则删除链表里报数为3的结点的函数
{ struct person * p1, * p2 ;
  int i;
  if (head == NULL) return 0;
  p2=head;
  p1=p2->next;
  i=2;
  while (p1 != p2)            //当循环链表只有1个结点时，退出循环    
  { if (i%3==0)             //当报数为3时删除一个结点
    { if (p1 == head) head=p1->next;    //如果要删除的结点是头指针指向的结点，则让头指针指向下一个结点
      p2->next = p1->next;
      free (p1);
      p1=p2->next;
      i++;
    }
    p2=p1;
    p1=p1->next;
    i++;
  }
  return (p1->num);
}