C语言实现循环链表

实现循环链表,我们需要定义一个结构体来表示链表中的每个节点,其中包含一个指向下一个结点的指针。

下面是一个示例结构体的定义:

struct Node {
    int data;
    struct Node* next;
};

其中,data表示节点存储的数据,next是指向下一个节点的指针。

我们需要定义以下操作来构建循环链表:

  1. 创建一个空链表
struct Node* createList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = head;
    return head;
}

其中,我们建立了一个空链表,头节点的next指针指向它自身。

  1. 在链表的末尾插入一个元素
void insert(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;

    struct Node* p = head;
    while (p->next != head) {
        p = p->next;
    }

    p->next = newNode;
}

通过这种方式,我们可以将一个元素添加到链表的末尾。

  1. 从链表中删除元素
void delete(struct Node* head, int data) {
    struct Node* p = head;
    while (p->next != head) {
        if (p->next->data == data) {
            struct Node* temp = p->next;
            p->next = temp->next;
            free(temp);
            return;
        }
        p = p->next;
    }
}

从链表中删除一个元素,需要遍历链表查找该元素,找到后删除节点。

下面是一个简单的例子,展示如何使用循环链表来实现Josephus问题。该问题的描述如下:

  • N个人围成一个圆圈,依次编号为1, 2, … ,N
  • 从第一个人开始依次报数,报到M的人出圈,下一个人继续从1开始报数,直到只剩下一个人为止

假设N=5,M=2,下面是解决方案:

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = head;
    return head;
}

void insert(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;

    struct Node* p = head;
    while (p->next != head) {
        p = p->next;
    }

    p->next = newNode;
}

void delete(struct Node* head, int data) {
    struct Node* p = head;
    while (p->next != head) {
        if (p->next->data == data) {
            struct Node* temp = p->next;
            p->next = temp->next;

            free(temp);
            return;
        }
        p = p->next;
    }
}

void josephus(int n, int m) {
    struct Node* head = createList();

    for (int i = 1; i <= n; i++) {
        insert(head, i);
    }

    struct Node* p = head->next;
    while (p->next != p) {
        for (int i = 0; i < m - 1; i++) {
            p = p->next;
        }
        delete(head, p->data);
        p = p->next;
    }
    printf("The last one is %d.\n", p->data);

    free(p);
    free(head);
}

int main() {
    int n = 5, m = 2;
    josephus(n, m);

    return 0;
}

上面的代码首先创建了一个包含元素1到元素N的循环链表。然后通过遍历链表的方式进行Josephus问题的求解。最后输出最终剩余的元素编号。

下面是该代码的运行结果:

The last one is 3.

除了Josephus问题,循环链表还可以用于实现栈和队列等数据结构,这里就不再赘述。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言实现循环链表 - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • SpringBoot整合Redis入门之缓存数据的方法

    下面是 “SpringBoot整合Redis入门之缓存数据的方法” 的完整攻略。 简介 在高并发访问下,数据库成为了性能瓶颈,为了解决这个问题,我们可以加入缓存来减轻数据库的压力,提高网站的响应速度。Redis作为一个高性能的内存数据库,被广泛应用于缓存系统中。在SpringBoot中,通过RedisTemplate来实现redis的缓存数据。 环境准备 首…

    C 2023年5月23日
    00
  • 深入了解Java 脚本化api编程

    深入了解Java 脚本化API编程攻略 什么是Java 脚本化API Java 脚本化API是一组Java类和接口,它们使Java应用程序可以在运行时解释和运行脚本。该API提供了与脚本语言交互和制定脚本规则的功能,使Java程序具备动态性和灵活性。可以使用这个API来编写插件、脚本、宏或涉及领域专业语言的自定义工具。 Java 脚本化API的应用场景 Ja…

    C 2023年5月23日
    00
  • 你可能不知道的JSON.stringify()详解

    你可能不知道的JSON.stringify()详解 简介 JSON.stringify() 是 JavaScript 内置的一个可将对象转换为 JSON 字符串的方法。它将对象序列化为一个字符串,以便于存储或传输。JSON.stringify() 还可以接受一个函数作为第二个参数,用于控制转换过程。 JSON.stringify() 的参数 JSON.str…

    C 2023年5月23日
    00
  • C++实现银行排队系统

    C++实现银行排队系统 介绍 银行排队系统是一种经典的模拟系统。该系统可以模拟银行中客户的流动、排队、服务等过程。通过模拟,可以帮助银行评估服务能力,从而提高工作效率。本文将介绍如何使用C++实现银行排队系统。 系统设计 队列的实现 队列是银行排队系统的核心数据结构。在C++中,可以使用STL中的队列容器来实现队列。以下是如何定义一个整型队列: “`c++…

    C 2023年5月23日
    00
  • C++中函数指针详解及代码分享

    关于“C++中函数指针详解及代码分享”的完整攻略,我为大家总结如下: 1. 什么是函数指针? 函数指针是一个指向函数的指针变量。函数指针可以像普通函数一样被调用,其语法形式为: 返回值类型 (*指针变量名)(参数列表); 其中,指针变量名可以被赋值为相同参数列表和返回类型的函数地址。可以使用函数指针来传递函数作为参数、实现回调函数等。 举个例子,假如我们有一…

    C 2023年5月24日
    00
  • c语言实现从源文件从文本到可执行文件经历的过程

    C语言实现从源文件到可执行文件的过程可以概括为以下几个步骤: 编写源代码文件 预处理源代码文件 编译预处理后的源代码文件生成目标文件 链接目标文件生成可执行文件 下面我将详细讲解每一步骤和其示例说明。 1. 编写源代码文件 源代码文件是指程序员编写的包含C语言程序源代码的文本文件。它通常使用文件扩展名为.c或.cpp。源代码文件的内容包括程序员编写的程序逻辑…

    C 2023年5月23日
    00
  • C/C++ extern关键字用法示例全面解析

    当在 C/C++ 中需要引用其他源文件中定义的变量或函数时,可以使用 extern 关键字。extern 关键字用于将某个全局变量或函数声明为外部定义,以便在该程序中的其他文件中使用。 下面通过几个示例来详细介绍 extern 关键字的用法。 示例一:在不同文件中使用全局变量 假设我们有以下两个 C 文件: source1.c #include <st…

    C 2023年5月23日
    00
  • vscode调用c项目后怎么引用dll?

    在VSCode中调用C语言项目,如果需要使用动态链接库(DLL)的话,一般需要进行以下步骤: 创建动态链接库 先编写动态链接库的代码并生成DLL文件。例如,编写一个示例代码,将其保存为 “hello.c”,编译并生成DLL文件 “hello.dll”。示例代码如下: #include <stdio.h> #include <stdlib.h…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部