C程序习题-链表实现猴子选大王[11.9]

    13个人围成一圈，从第一个人开始顺序报号1,2,3。凡报到“3”者退出圈子。找出最后留在圈子里的人是原来的序号(用链表实现)。

    其实这道题，在前面的练习中。我已经做过了，那是用一个数组，到报到者将其值赋值为零。当到最后一个时，返回数组中的第一个元素。

    现在这个题目，我们使用链表结构，链表结构最显著的特征是，移除一个元素非常的方便，只需调整指针即可。当指向下一个元素为NULL即该元素为最后一个元素。其实原理都一样。只是我觉得用链表操作更合理，更快捷。我编写的函数，含有初始化链表，输出链表。处理链表等操作。代码如下：

#include <stdio.h>
#define SIZE sizeof(struct person)

struct person
{
       int number;
       struct person *next;
};

struct person * init(int); //初始化链表

struct person * input(int); //对链表的number进行赋值，并返回链表项指针。

void print(struct person *); //打印链表

struct person * operate(struct person *,int); //对链表进行操作，求出最后结果。

int main(int argc,char *argv[])
{
    struct person *head;
    int n,i;
    printf("please input a number:");
    scanf("%d",&n);
    head = init(n);
    printf("the source linktable is:\n");
    print(head);
    printf("\nplease input report number is out:");
    scanf("%d",&i);
    head = operate(head,i);
    printf("\nthe link table is :");
    print(head);
    system("pause");
    return 0;
}

struct person * init(int n)
{
       int i = 0;
       struct person *head,*p1,*p2;
       while(i < n)
       {
         p1 = input(i + 1);
         if (0 == i)
         {
            head = p1;
         }
         else
         {
             p2->next = p1;
         }
         p2 = p1;
         i ++;
       }
       p2->next = NULL;
       return head;
       
}

struct person * input(int num)
{
       struct person * myperson = (struct person *)malloc(SIZE);
       myperson->number = num;
       return myperson;
}

void print(struct person *head)
{
     struct person *p;
     p = head;
     while(p != NULL)
     {
             printf("%d ",p->number);
             p = p->next;
     }
}

struct person * operate(struct person *head,int num)
{
     int count = 1;
     struct person *p1,*p2,*del;
     p1 = head;
     printf("the exit number is: \n");
     while(1)
     {
          if (head->next == NULL)
          {
             break;
          }
          if (count == num)
          {
             if (p1 == NULL)
             {
                p1 = head;
             }
             del = p1;
             printf("%d ",del->number);
             if (del == head)
             {
                head = del->next;
             }
             else
             {
                 p2->next = p1->next;
             }
             p1 = p1->next;
             free(del);
             count = 1;
             continue;
          }
          if (p1 == NULL)
          {
             p1 = head;
             continue;
          }
          else
          {
             p2 = p1;
             p1 = p1->next;
          }
          
          count ++;
          
     }
     printf("\nthe result is : %d\n",head->number);
     return head;
}