C语言中的链表：定义、操作与实现

曈曈too

发布于 2023-02-27 15:44:42

1.9K0

发布于 2023-02-27 15:44:42

文章被收录于专栏：瞳瞳too的学习笔记

什么是链表

链表是一种常用的数据结构，它由若干个结点组成。每个结点都有两部分组成：数据域和指针域。数据域存储结点的值，而指针域则指向下一个结点。由于链表的每个结点都有指针域，所以链表可以动态分配内存。

链表的类型

链表主要分为单链表和双链表两种。单链表只有一个指针域，指向下一个结点，而双链表则有两个指针域，分别指向前驱结点和后继结点。

C语言中的链表

在C语言中，链表可以通过结构体和指针来实现。结构体可以存储结点的数据域和指针域，而指针则可以实现结点之间的连接。

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

链表的操作

插入结点：在链表的头部或尾部插入新结点。
删除结点：删除链表中指定的结点。
遍历链表：遍历链表中的每一个结点。
查找结点：查找链表中指定的结点。

链表的实现

下面是一个简单的链表实现的例子，包括创建链表、插入结点、删除结点、遍历链表等操作。

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

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

// 创建链表
struct Node* createList() {
    struct Node* head = NULL;
    return head;
}

// 插入结点
void insertNode(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

// 删除结点
void deleteNode(struct Node** head, int data) {
    struct Node* temp = *head, *prev;
    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

// 遍历链表
void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

int main() {
    struct Node* head = createList();
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    traverseList(head);
    deleteNode(&head, 2);
    printf("\n");
    traverseList(head);
    return 0;
}

以上就是C语言中链表的定义、操作和实现的简要介绍。链表是一种非常重要的数据结构，广泛应用于许多算法和程序中。了解链表可以帮助我们更好地理解和使用这种数据结构。链表中指定的结点。

链表的实现

下面是一个简单的链表实现的例子，包括创建链表、插入结点、删除结点、遍历链表等操作。

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

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

// 创建链表
struct Node* createList() {
    struct Node* head = NULL;
    return head;
}

// 插入结点
void insertNode(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

// 删除结点
void deleteNode(struct Node** head, int data) {
    struct Node* temp = *head, *prev;
    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

// 遍历链表
void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

int main() {
    struct Node* head = createList();
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    traverseList(head);
    deleteNode(&head, 2);
    printf("\n");
    traverseList(head);
    return 0;
}

在这个示例中，我们首先定义了一个结构体类型Node，其中包含了数据域和指针域。然后我们定义了一系列函数，用来实现链表的创建、插入、删除和遍历等操作。