Manchester


私信TA

用户名:wenyajie

访问量:310664

签 名:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

等  级
排  名 1
经  验 62388
参赛次数 1
文章发表 188
年  龄 0
在职情况 学生
学  校 Xiamen University
专  业 计算机科学

  自我简介:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

解题思路:(原: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;

2017-12-22 22-10-34屏幕截图.png

2017-12-22 22-11-03屏幕截图.png

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

2017-12-22 22-11-27屏幕截图.png

2017-12-22 22-19-26屏幕截图.png

2017-12-22 22-11-54屏幕截图.png







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

   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*/
}

别忘点赞哦-.-

 

0.0分

31 人评分

  评论区

公式法提交上去答案错误
2019-04-06 12:12:37
刚刚自学了数据基础,趁着这个题又复习了一遍
2019-02-23 15:16:33
公式法不太懂
2018-11-17 10:38:11
2018-04-18 12:38:58
  • «
  • 1
  • »