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日

相关文章

  • C++如何实现BitMap数据结构

    下面我将详细讲解C++如何实现BitMap数据结构的完整攻略，包含以下几个方面： 什么是BitMap数据结构 如何使用C++实现BitMap数据结构 BitMap数据结构的应用示例说明 1. 什么是BitMap数据结构 BitMap数据结构也叫位图，是一种非常简单而高效的数据结构，它主要是用来对大量数字进行存储和操作的。所谓BitMap，就是将一个数字序列通…

    数据结构 2023年5月17日
    00

  • 带你了解Java数据结构和算法之递归

    带你了解Java数据结构和算法之递归 什么是递归？ 递归是一种算法或计算机程序的设计方法，在程序执行过程中直接或间接的调用自身。 递归的实现方式 递归的实现通常使用函数进行的。在函数中，我们首先检查停止条件（递归基）是否满足，如果满足，我们停止递归；否则，我们调用自身递归进行下一步计算。 递归的应用场景 递归通常在解决问题中使用。对于像树、图等复杂结构的遍历…

    数据结构 2023年5月17日
    00

  • C语言数据结构旋转链表的实现

    C语言数据结构旋转链表的实现 1. 什么是旋转链表 旋转链表是一种特殊的链表，其特点是将链表的最后一个节点移动到最前面，形成一个环形链表的效果。比如下面这个链表： 1 -> 2 -> 3 -> 4 -> 5 经过一次旋转之后变成了： 5 -> 1 -> 2 -> 3 -> 4 2. 实现思路 旋转链表的实现思路…

    数据结构 2023年5月17日
    00

  • AtCoder Beginner Contest 299

    A – Treasure Chest (abc299 a) 题目大意 给定一个包含 |*.的字符串，其中|两个，*一个，问*是否在两个|之间。 解题思路 找到两个|的下标\(l, r\)以及 *的下标\(mid\)，看看是否满足 \(l < mid < r\)即可。 神奇的代码 #include <bits/stdc++.h> usi…

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

  • C#常用数据结构之数组Array

    C#常用数据结构之数组Array 什么是数组 在C#中，数组是一种数据结构，它可以用于存储具有相同数据类型的多个元素。数组中的元素可以通过下标来访问，数组下标从0开始，最大下标为数组长度-1。 声明和初始化数组 声明数组 声明数组需要指定数据类型和数组名称，括号中指定数组的容量。例如，声明一个包含5个整数的数组： int[] arr = new int[5]…

    数据结构 2023年5月17日
    00

  • C++语言数据结构 串的基本操作实例代码

    下面是“C++语言数据结构 串的基本操作实例代码”的完整攻略。 什么是串 在计算机领域中，串是由一系列字符组成的数据结构。可以将其理解为一个字符数组，每个字符处于数组中的一个位置，并且可以通过下标位置访问对应的字符。 C++中的串类型可以使用字符数组来表示，另外还有标准库中的string类型。 基本操作 下面是实现串的基本操作的示例代码，并进行了详细的解释。…

    数据结构 2023年5月17日
    00

  • C语言实现通用数据结构之通用椎栈

    C语言实现通用数据结构之通用椎栈 概述 通用椎栈（Generic Linked List Stack），简称GLL Stack，是一种通用的数据结构，能够以动态的方式存储和访问任意类型的数据。GLL Stack 采用链表实现，可以进行进栈（push）、出栈（pop）、查看栈顶元素（peek）、判断栈是否为空（isEmpty）等基本操作。 基本操作 数据结构定…

    数据结构 2023年5月17日
    00

  • c语言 数据结构实现之字符串

    下面是详细讲解“c语言 数据结构实现之字符串”的完整攻略。 1. 什么是字符串？ 字符串是由一组字符组成的序列，字符可以是字母、数字、标点符号等，字符串常用于文本处理。 在C语言中，字符串是以‘\0’ 结束的字符数组。 2. 字符串的常见操作 常见的字符串操作包括：复制、比较、连接、查找等。 2.1 字符串复制 字符串复制是将一个字符串的内容复制到另一个字符…

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