Manchester-【出圈】（公式法+循环链表 附带图解）

解题思路:（原：1047: C语言程序设计教程（第三版）课后习题10.5）

在1047的 的基础上，把报数的数m改为自己输入，同时改为多组测试数据，并且输出带换行符；

思路一：(公式法)

#include <stdio.h>

int main()
{
    int n,m,s = 0;
    while(scanf("%d%d", &n,&m)!=EOF)
     {
        s = 0;
        for (int i = 2; i <= n; ++i)
        s = (s+m)%i;
        printf("%d\n", s+1);
     }
    return 0;
}

思路二(循环链表法)
    1:创建长度为n的循环链表（单链表的最后一个结点与首结点连接，不是头结点）；

    2:链表结点包括编号和next指针；

    3:从首结点p开始报数（p=p->next)，但是只报数到离开的结点的前一个结点，然后删除它后面的结点,更新报数的第一个结  点（p=p—>next）；用指针q指向要删除的结点；

    4:重复上述过程，直到链表中只有一个结点结束(即：p->next=p)；

    5:如下图假设有6个结点（6个人），报数数为3；

把头结点free了，因为删除过程中，头结点的next被删除的话，头结点next指向不安全地方，就不要用它了；

以上就是链表的实现过程，要挑战自己可以弄一个单链表实现的，再厉害一点可以顺序表，但顺序表不推荐，

   1.顺序表删除要移动大量元素

   2.报数到最后一个之后，返回第一个的实现过程复杂，需要用下标关系，很容易晕；

注意事项:
每个结点删除后都要free了，输出留下来的那个人之后也要把它的free了，输出带换行符；
参考代码:

#include<stdio.h>
#include <malloc.h>

typedef struct student {
    int        number;
    struct student    * next;
}*node, Node;                           /* 结点 */

node creat( int n );                    /* 创建链表函数 */

void function( node l1, int baoshu );   /* 运行函数 */


int main()
{
    int    n,baoshu;                      /* 人数 */
    node    head1;                           /* 链表的头结点 */
    while(scanf("%d%d",&n,&baoshu)!=EOF)
     {
     head1 = creat( n );                        /* 创建链表*/
     function( head1, baoshu );
     }
    return(0);
}


/*-------------------------------------------------------------*/

node creat( int n )
{
    node h;                                         /* 头结点指针 */
    h    = (node) malloc( sizeof(Node) );        /* 创建头结点 */
    h->next = NULL;                                 /* next指针域赋空 */
    node    q = h;                                  /* 定义指针q，指向头结点 */
    node    p;

    for ( int i = 1; i <= n; i++ )                  /* 创建n个结点 */
    {
        p        = (node) malloc( sizeof(Node) );
        (*p).number    = i;                    /* 输入编号 */

        p->next = q->next;                      /* 采用后差法插入节点 */
        q->next = p;
        q    = p;
    }
    q->next = h->next;                              /* 尾结点和首结点链接 */

    return(h);                                      /* 返回头结点 */
}


/*-------------------------------------------------------------*/
void function( node l1, int baoshu )              /* 移除实现 */
{
    node p = l1->next;                        /* 指向首结点 */
    free( l1 );                               /* free头结点 */
    node q = NULL;                             /* 指向被移除结点，用于释放移除的人的结点 */
    while ( p->next != p )
    {
        for ( int i = 1; i <= baoshu - 2; i++ ) /* 移动到离开的人的结点的前一个，只需要移动baoshu-2次； */
            p = p->next;

        q    = p->next;              /* 记录删去的人的结点 */
        p->next = q->next;           /* 把q结点从链表移除 */

        p = p->next;                 /* 移动到下一个开始报数的人，很重要这一步 */
        free( q );             /*释放q结点*/
    }

    printf("%d\n",p->number);   /*输出结果带换行*/
    free( p );      /* 把最后一个结点free*/
}

别忘点赞哦-.-