Manchester-C语言程序设计教程（第三版）课后习题10.5(循环链表，最易理解实现，附带图解）

解题思路:
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 <malloc.h>
#include <iostream>
using namespace std;

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

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

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


int main()
{
    int    n;                      /* 人数 */
    node    head1;                  /* 链表的头结点 */
    int    baoshu = 3;
    cin >> n;
    /* cin >> baoshu; */          /*加上这句，实现n个人，报数数为baoshu */
    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结点*/
    }

    cout << p->number;
    free( p );      /* 把最后一个结点free*/
}

别忘点赞哦-.-