[数据结构与算法]【4.7日题解】——约瑟夫问题(c代码表述）

?前言?

今日份水题开始。希望有想要提高的同学跟我们一起来刷题0.0
4.7日每日一题——约瑟夫问题

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min

P1996 约瑟夫问题

解题思路

搞个链表直接模拟就好了，没那么复杂。

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}NODE;

int main(){
    int m,n;
    scanf("%d %d",&m, &n);
    NODE head;      //头节点
    head.next = NULL;

    NODE *first;
    for(int i = 0;i < m;++i){   //建立链表
        NODE *tmp = (NODE *)malloc(sizeof(NODE));
        if(!i) first = tmp;
        tmp->data = m - i;
        tmp->next = head.next;//头插法
        head.next = tmp;
    }

    NODE *p = head.next,*q;
    if(n == 1){
        while(p){printf("%d ",p->data);p=p->next;}
        return 0;
    }
    first->next = head.next;//循环链表建立完成 0.0

    while(p != &head){
        for(int i = 0;i < n - 2;++i)    p = p->next;
        printf("%d ",p->next->data);
        if(p->next == p) break;
        q = p->next;
        p->next = p->next->next;
        p=p->next;
        free(q);
    }
    return 0;
}

挺好，不改了，不过看群友有拿数组模拟链表的，太强了。加油呀！

📑写在最后

今天就这样，明日再见0.0

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读