【数据结构】使用循环链表结构实现约瑟夫环问题

发布时间:2023年12月19日

目录

1.循环链表的定义

2.约瑟夫环问题

3.创建循环链表

4.删除节点操作

5.打印所有节点

6.实现约瑟夫环问题的完整程序代码


🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。

💡本文由Filotimo__??原创,首发于CSDN📚。

📣如需转载,请事先与我联系以获得授权??。

🎁欢迎大家给我点赞👍、收藏??,并在留言区📝与我互动,这些都是我前进的动力!

🌟我的格言:森林草木都有自己认为对的角度🌟。

1.循环链表的定义

循环链表与常规链表的区别在于,其尾节点指向头节点,形成一个环形结构。循环链表可以分为单向循环链表和双向循环链表两种类型。

单向循环链表的定义为:每个节点包含一个数据元素和指向下一个节点的指针,而最后一个节点的指针会指向第一个节点,形成一个环形结构。

双向循环链表的定义为:每个节点包含一个数据元素以及两个指针,一个指向前一个节点,一个指向后一个节点,而第一个节点的前驱指针指向最后一个节点,最后一个节点的后继指针指向第一个节点,也形成了一个环形结构。

这种结构使得循环链表可以从任意节点开始遍历,并且可以方便地在链表中插入或删除节点。它可以通过不断重复遍历整个链表来实现循环的效果。

2.约瑟夫环问题

约瑟夫环问题是一个经典的数学问题,假设 n 个人站成一个环状,从第一个人开始报数,每次报到 m 的人出列,再从下一个人开始重新报数,直到所有人都出列。最后剩下的人的编号即为最后的获胜者。

解决约瑟夫环问题的步骤(设定问题的输入为n个人和要出局的报数m):

1. 将n个人编号为1到n。
2. 从第一个人开始报数,报到m的人出局。
3. 从出局的人的下一个人开始重新报数,继续报到m的人出局。
4. 重复第3步,直到只剩下一个人为止。

3.创建单向循环链表

typedef struct node {
    int number;
    struct node* next;
} person;

// 初始化一个循环链表,表示圆桌上的人
person* initlink(int n) {
    person* head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    person* cyclic = head;
    
    // 创建 n-1 个节点,并连接成循环链表
    for (int i = 2; i <= n; i++) {
        person* body = (person*)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next; 
    }
    
    cyclic->next = head;
    return head;
}

定义一个名为person的结构体,由整型变量number和指向下一节点的指针next构成。

函数initlink用于初始化一个循环链表,表示圆桌上的人。函数首先创建一个头节点,然后使用for循环创建其他的节点并连接成循环链表。最后返回头节点。

这段代码用于创建一个循环链表,其中头节点的number字段表示第一个人在圆桌上的位置,后续节点的number字段按顺序递增,最后一个节点的next字段指向头节点形成一个循环链表结构。

4.约瑟夫环求解过程

// 找到第 k 个人并开始报数,数到第 m 个人出列
void findandkillk(person* head, int k, int m) {
    person* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    
    person* p = head;
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    
    // 从第 k 个人开始报数,直到只剩下一个人
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        
        // 删除第 m 个人出列,并释放内存
        tail->next = p->next;
        printf("出列人的编号为: %d\n", p->number);
        
        person* temp = p;
        p = p->next;
        free(temp);
    }
    
    printf("出列人的编号为: %d\n", p->number);
    free(p);
}

从第k个人开始报数,每次报到第m个人就将其出列。

先用循环找到链表中的尾节点,即满足tail->next = head的节点。

再用循环找到链表中编号为k的节点,并在找到之前更新尾节点的位置。

再用循环进行报数和出列操作,直到链表中只剩下最后一个人。循环中的内层循环每次进行m-1次迭代,找到第m个人之前的节点并更新尾节点的位置。随后,删除第m个人,并释放其内存。外层循环在每次迭代之后更新当前节点的位置,并继续进行报数和出列操作。

最后,输出剩下的最后一个人的编号,并释放其内存。

5.实现约瑟夫环问题的完整程序代码

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int number;
    struct node* next;
} person;

// 初始化一个循环链表,表示圆桌上的人
person* initlink(int n) {
    person* head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    person* cyclic = head;
    
    // 创建 n-1 个节点,并连接成循环链表
    for (int i = 2; i <= n; i++) {
        person* body = (person*)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next; 
    }
    
    cyclic->next = head;
    return head;
}

// 找到第 k 个人并开始报数,数到第 m 个人出列
void findandkillk(person* head, int k, int m) {
    person* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    
    person* p = head;
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    
    // 从第 k 个人开始报数,直到只剩下一个人
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        
        // 删除第 m 个人出列,并释放内存
        tail->next = p->next;
        printf("出列人的编号为: %d\n", p->number);
        
        person* temp = p;
        p = p->next;
        free(temp);
    }
    
    printf("出列人的编号为: %d\n", p->number);
    free(p);
}

int main() {
    printf("输入圆桌上的人数 n: ");
    int n;
    scanf("%d", &n);
    person* head = initlink(n);
    
    printf("从第 k 人开始报数 (k > 1 且 k < %d): ", n);
    int k;
    scanf("%d", &k);
    
    printf("数到第 m 个人出列:");
    int m;
    scanf("%d", &m);
    
    findandkillk(head, k, m);
    
    return 0; 
}

代码中的主要函数有initlink和findandkillk。

initlink函数根据输入的人数 n,初始化一个循环链表。循环链表中的每个节点都存储一个人的编号,编号从 1 到 n。该函数返回链表的头节点指针。

findandkillk函数用于解决约瑟夫环问题。它接收初始化好的循环链表的头节点指针,起始编号 k 和报数间隔 m 作为参数。首先,它找到从第 k 个人开始报数的位置,并且记录该位置的上一个节点,即tail。接着,通过迭代法,每次报数到第 m 个人时,将其从链表中删除,并释放相应的内存空间。直到链表中只剩一个节点时,停止迭代,并输出最后剩下的那个人的编号。

在main函数中,用户输入要解决的约瑟夫环问题的相关参数,然后调用findandkillk函数进行求解。

程序截图如下:

文章来源:https://blog.csdn.net/m0_71369515/article/details/135037220
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。