1. Python技术站首页
  2. 数据结构

C语言一篇精通链表的各种操作

• 数据结构

C 语言精通链表操作攻略

简介

链表是一种常用的数据结构，它相对于数组等数据结构来说，具有更高的灵活性和增删操作的效率。在 C 语言中，我们可以用指针来实现链表，这也是指针与动态内存分配的重要应用之一。本文将提供在 C 语言中精通链表操作的攻略，包括链表的创建、添加、删除、搜索、遍历等常用操作。

基本结构体定义

链表一般由结构体和指针构成，下面我们定义一个链表结构体节点：

struct ListNode {
    int val;
    struct ListNode* next;
};

其中，val 表示节点中存储的值，next 表示下一个节点的指针。为了方便后续的实现，我们还定义一个指向链表开头的指针：

typedef struct ListNode* LinkedList;

创建链表

首先，我们需要创建一个空链表。因为链表的第一个节点没有前驱节点，所以需要特别处理一下：

LinkedList createLinkedList() {
    LinkedList head = (LinkedList)malloc(sizeof(struct ListNode));
    head->next = NULL;
    return head;
}

手动添加节点

接下来，我们手动向链表中添加几个节点：

LinkedList head = createLinkedList();
LinkedList p = (LinkedList)malloc(sizeof(struct ListNode));
p->val = 1;
p->next = NULL;
head->next = p;

LinkedList q = (LinkedList)malloc(sizeof(struct ListNode));
q->val = 2;
q->next = NULL;
p->next = q;

这样就创建了一个有两个节点的链表。

添加节点

在链表结尾处添加一个节点

为了在链表结尾处添加一个节点，我们需要先找到链表的最后一个节点，即 next 指针为NULL的节点。然后在此节点之后，添加新的节点即可：

void addAtTail(LinkedList head, int val) {
    // 找到最后一个节点
    LinkedList p = head;
    while (p->next) {
        p = p->next;
    }

    // 在最后一个节点之后添加新的节点
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    p->next = newNode;
}

在链表头部添加一个节点

在链表头部添加节点与在链表尾部添加节点相似，只是我们需要让新节点指向原来的头节点，然后将新节点作为新的头节点即可：

void addAtHead(LinkedList head, int val) {
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = head->next;
    head->next = newNode;
}

在链表中间添加一个节点

为了在链表的中间位置添加一个节点，我们需要先找到要插入的位置，移动指针即可：

void addAtIndex(LinkedList head, int index, int val) {
    // 链表头结点为第0个元素
    if (index <= 0) {
        addAtHead(head, val);
        return;
    }

    // 找到要插入节点的前驱节点
    LinkedList p = head;
    for (int i = 0; i < index - 1; i++) {
        p = p->next;
        if (p == NULL) {
            return; // index 超出链表范围
        }
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = p->next;
    p->next = newNode;
}

删除节点

删除指定节点

为了删除指定的节点，我们需要先找到这个节点的前驱节点，然后将前驱节点的 next 指针，指向要删除节点的后继节点即可：

void deleteNode(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next != NULL && p->next->val != val) {
        p = p->next;
    }
    if (p->next == NULL) {
        return; // 没有节点包含val值
    }

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

删除指定下标的节点

为了删除指定下标的节点，我们需要先找到要删除节点的前驱节点：

void deleteAtIndex(LinkedList head, int index) {
    // 链表头结点为第0个元素
    if (index < 0) {
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index; i++) {
        p = p->next;
        if (p == NULL) {
            return; // index 超出链表范围
        }
    }

    LinkedList temp = p->next;
    if (temp == NULL) {
        return; // index 超出链表范围
    }

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

搜索节点

为了搜索指定值的节点，我们只需要遍历整个链表，直到找到一个值为指定值，或者链表遍历结束：

LinkedList searchLinkedList(LinkedList head, int val) {
    LinkedList p = head->next;
    while (p != NULL && p->val != val) {
        p = p->next;
    }
    return p;
}

遍历节点

遍历节点是链表的最常见操作之一，我们可以用循环来遍历整个链表：

void traverseLinkedList(LinkedList head) {
    LinkedList p = head->next;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
}

示例运行

下面是这些链表操作的完整代码和使用示例：

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

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode* LinkedList;

LinkedList createLinkedList() {
    LinkedList head = (LinkedList)malloc(sizeof(struct ListNode));
    head->next = NULL;
    return head;
}

void addAtTail(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next) {
        p = p->next;
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    p->next = newNode;
}

void addAtHead(LinkedList head, int val) {
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = head->next;
    head->next = newNode;
}

void addAtIndex(LinkedList head, int index, int val) {
    if (index <= 0) {
        addAtHead(head, val);
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index - 1; i++) {
        p = p->next;
        if (p == NULL) {
            return;
        }
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = p->next;
    p->next = newNode;
}

void deleteNode(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next != NULL && p->next->val != val) {
        p = p->next;
    }
    if (p->next == NULL) {
        return;
    }

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

void deleteAtIndex(LinkedList head, int index) {
    if (index < 0) {
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index; i++) {
        p = p->next;
        if (p == NULL) {
            return;
        }
    }

    LinkedList temp = p->next;
    if (temp == NULL) {
        return;
    }

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

LinkedList searchLinkedList(LinkedList head, int val) {
    LinkedList p = head->next;
    while (p != NULL && p->val != val) {
        p = p->next;
    }
    return p;
}

void traverseLinkedList(LinkedList head) {
    LinkedList p = head->next;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
}

int main() {
    LinkedList head = createLinkedList();
    addAtHead(head, 5);
    addAtTail(head, 6);
    addAtIndex(head, 1, 4);
    deleteAtIndex(head, 1);
    LinkedList p = searchLinkedList(head, 5);
    printf("5 是否在链表中：");
    if (p) {
        printf("是");
    } else {
        printf("否");
    }
    printf("\n链表：");
    traverseLinkedList(head);
    printf("\n");

    return 0;
}

输出结果为：5 是否在链表中：是 链表：5 6

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言一篇精通链表的各种操作 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月17日
下一篇 2023年5月17日

相关文章

  • JavaScript数据结构yocto queue队列链表代码分析

    JavaScript数据结构yocto queue队列链表代码分析 什么是队列？ 队列（Queue）是一种基础的数据结构，属于线性结构，它的特点是在队列尾插入元素，同时在队列头删除元素，遵循先进先出（FIFO）的原则。队列可以简单的理解为排队，先到达的先被服务，而后到达的则等在队列尾排队等待。队列的应用非常广泛，例如排队系统、消息队列等。 队列的实现方式 队…

    数据结构 2023年5月17日
    00

  • JavaScript数据结构常见面试问题整理

    JavaScript数据结构常见面试问题整理 介绍 JavaScript是一种广泛使用的脚本语言，用于在Web上创建动态效果，验证表单，增强用户体验等。它是一种高级语言，使用许多数据结构来存储和处理数据。在面试中，考官通常会问一些与JavaScript数据结构相关的问题，这篇文章将整理一些常见的面试问题和他们的解答，以便帮助你做好准备。 常见问题 1. 什么…

    数据结构 2023年5月17日
    00

  • Python内存管理器如何实现池化技术

    Python内存管理器使用了池化技术来进行内存管理，这使得Python程序的内存管理效率比较高。下面我将详细介绍Python内存管理器如何实现池化技术： 1. 内存分配 Python内存管理器在Python运行时，会维护多个大小不同的内存块池，每个池的大小相同。当Python程序需要分配内存时，会首先在池中寻找是否有剩余内存块可以分配。如果有，则分配给程序使…

    数据结构 2023年5月17日
    00

  • JavaScript数据结构之链表的实现

    JavaScript数据结构之链表的实现 什么是链表 链表是一种线性数据结构，其中的元素在内存中不连续地存储，每个元素通常由一个存储元素本身的节点和一个指向下一个元素的引用组成。相比较于数组，链表具有如下优缺点： 优点：动态地添加或删除元素时，无需移动其它元素。(数组则需要移动其它元素) 缺点：不能随机地访问某个元素，必须从头开始顺序遍历。(而数组可以通过索…

    数据结构 2023年5月17日
    00

  • Java数据结构顺序表的详细讲解

    Java数据结构顺序表的详细讲解 什么是顺序表？ 顺序表是一种线性结构，它通过一段连续的存储空间来存储一组元素，每个元素占用一个固定大小的存储单元，元素之间按照一定的顺序紧密排列。 顺序表的实现 在Java中，顺序表可以通过数组实现。数组是一种非常基础的数据结构，它可以用来存储相同类型的数据，数组元素的地址是连续的，因此可以通过下标访问数组中的元素。 实现步…

    数据结构 2023年5月17日
    00

  • C语言数据结构之算法的时间复杂度

    关于C语言数据结构之算法的时间复杂度，需要先了解一些基本概念。 什么是时间复杂度 时间复杂度是算法的一种衡量标准，用于评估算法的执行效率。表示代码执行的时间和数据量之间的关系，通常用大O符号来表示，称为“大O记法”。 时间复杂度的分类 时间复杂度可分为以下几类： 常数阶：O(1) 对数阶：O(log n) 线性阶：O(n) 线性对数阶：O(n log n) …

    数据结构 2023年5月17日
    00

  • 代码随想录–二叉树

    二叉树 二叉树–二叉树的递归遍历 题目： 144.二叉树的前序遍历(opens new window) 145.二叉树的后序遍历(opens new window) 94.二叉树的中序遍历 题解： 前序遍历 class Solution { public List<Integer> preorderTraversal(TreeNode root…

    算法与数据结构 2023年4月18日
    00

  • [Week 19]每日一题（C++，数学，并查集，动态规划）

    目录 [Daimayuan] T1 倒数第n个字符串（C++，进制） 输入格式 输出格式 样例输入 样例输出 解题思路 [Daimayuan] T2 排队（C++，并查集） 输入格式 输出格式 样例输入1 样例输出1 样例输入2 样例输出2 样例输入3 样例输出3 数据规模 解题思路 [Daimayuan] T3 素数之欢（C++，BFS） 数据规模 输入格…

    算法与数据结构 2023年5月4日
    00
合作推广
合作推广
分享本页
返回顶部