链表的应用——猴子选大王

╰+攻爆jí腚メ 2023-07-18 03:22 23阅读 0赞

### 问题描述 ###

一群猴子，编号是123……m，这样的一群猴子（m）个按照1-m的顺序围圈坐，从第一只开始数，每数到第n个，该猴子就要离开次圈，这样依次下来至到圈中只剩下最后一只猴子，该猴子则为大王。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70][]

### 程序代码 ###

#include <stdio.h>
    #include <stdlib.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年3月15日
    
    */
    struct Monkey
    {
        int num;//猴子序号
        struct Monkey *next;//指向下一只猴子
    };
    int main()
    {
        int m,n,i,j,king;
        struct Monkey *head,*p1,*p2;
        printf("输入猴群数量：");
        scanf("%d",&m);
        printf("输入淘汰数：");
        scanf("%d",&n);
        if(n == 1)
        {
            king = m;
        }
        else
        {
            p1 = p2 = (struct Monkey *)malloc(sizeof(struct Monkey));//建立结点
            head = p1;//头结点
            head->num = 1;//第一只猴子
            for(i=1;i<m;i++)//用链表的尾插法
            {
                p1=(struct Monkey *)malloc(sizeof(struct Monkey));//建立新结点
                p1->num=i+1;//记录是第几只猴子
                p2->next = p1;//连接插入的结点
                p2 = p1;//指针始终指向链表尾部的上一个，以等待下一次进行链接
            }
            p2->next = head;//尾指针指向头指针，形成循环单链表
    
            p1 = head;//将动态指针指向头结点
            for(i=1;i<m;i++)
            {
                for(j=1;j<n-1;j++)
                    p1 = p1->next;//经过循环找到第n-1个
                p2 = p1->next;//p2指向最后一个节点
                printf("第%d轮淘汰%d\n",i,p2->num);
                p1->next = p2->next;//将为n的结点摘掉，重新建立链表
                p1 = p2->next;//又指向链表新一轮开始结点
                free(p2);//释放为n的结点
            }
            king = p1->num;
            free(p1);
        }
        printf("猴王是：%d\n",king);
        return 0;
    }

### 运行结果‘ ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70]: /images/20230528/891fc18eaec242a38917fbe6ef54651a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1]: /images/20230528/471e8ebeb4a74af6a7df13933f3db1f6.png