C语言实例解析精粹学习笔记——35（报数游戏）

实例35：

　　设由n个人站成一圈，分别被编号1，2，3，4，……，n。第一个人从1开始报数，每报数位m的人被从圈中推测，其后的人再次从1开始报数，重复上述过程，直至所有人都从圈中退出。

实例解析：

　　用链表求解本问题，先由n形成一个有n个表元组成的环，其中n个表元依此置值1~n。然后从环的第一个表元出发，连续略过m-1个表元，第m-1个表元的后继表元是第m个表元，将该表元从环中退出。接着再次从下一个表元出发，重复以上过程，直至环中表元都退出为止。

程序：

 #include <stdio.h>

 #include <stdlib.h>

 //定义表中表元

 struct ele{

     int no;           //表元的编号

     struct ele *link; //指向环的下一个表元的指针

 };

 int main()

 {

     int n,m,i;

     struct ele *h;   //表头指针

     struct ele *u;   //用于指向表中下一个表元的指针

     struct ele *p;   //用于指向第m个表元的指针

     printf("Please input n&m:\n");

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

     h = (struct ele *)malloc(sizeof(struct ele)); //形成首表元

     u = (struct ele *)malloc(sizeof(struct ele));

     h->no = ;

     /*形成剩下的n-1个表元*/

     for(i=; i<=n; i++)

     {

         u->link = (struct ele *)malloc(sizeof(struct ele));//为下一个表元分配一个地址

         u = u->link; //将u指向先一个表元

         u->no = i;

     }

     u->link = h;  //末表元后继首元，形成环

     puts("\nThe numbers of who will quit the cycle in turn are:");

     while(n)

     {

         for(i=; i<m; i++)   //掠过m-1个表元

             u=u->link;

         p = u->link;

         u->link = p->link;

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

         free(p);

         n--;

     }

     printf("\n\n Press any key to quit...\n");

     //printf("Hello world!\n");

     return ;

 }