一起来看看C语言线性表的线性链表

一起来看看C语言线性表的线性链表攻略

线性链表概述

线性链表是线性表的一种实现方式，它通过每个节点中包含指向下一个节点的指针来实现表中元素之间的链接，可以动态地增加、删除节点。线性链表分为带头节点的链表和不带头节点的链表，其中带头节点的链表更为常见。

实现思路

结构体定义

我们可以定义一个结构体来表示每个节点，例如：

typedef struct ListNode {
    int data;               // 节点数据
    struct ListNode *next;  // 指向下一个节点的指针
} ListNode;

初始化

初始化链表需要创建头节点，具体步骤如下：

1. 使用malloc函数动态分配一个ListNode类型的结构体空间p；
2. 将头指针head指向p；
3. 将p的next指针赋值为NULL；
4. 释放p。

示例代码：

void InitList(ListNode **head) {
    *head = (ListNode *)malloc(sizeof(ListNode));  // 申请头节点空间
    (*head)->next = NULL;                          // 头节点指针域为空
}

插入节点

插入节点分为头插法和尾插法。头插法就是将新节点插入到链表的头部，尾插法就是将新节点插入到链表的尾部。

头插法

1. 使用malloc函数动态分配一个ListNode类型的结构体空间p；
2. 将新节点的数据存入p的data成员中；
3. 将p的next指针指向头节点的next指针所指向的节点；
4. 将头节点的next指针指向p。

示例代码：

void InsertHead(ListNode *head, int data) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));  // 申请新节点空间
    p->data = data;                                      // 存储数据
    p->next = head->next;                                // p指向第一个节点
    head->next = p;                                      // 变更头节点的指向
}

尾插法

1. 使用malloc函数动态分配一个ListNode类型的结构体空间p；
2. 将新节点的数据存入p的data成员中；
3. 将原链表的最后一个节点的next指针指向p；
4. 将p的next指针指向NULL，表示链表结束。

示例代码：

void InsertTail(ListNode *head, int data) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));  // 申请新节点空间
    p->data = data;                                      // 存储数据
    p->next = NULL;                                      // 新节点指向NULL
    ListNode *q = head;
    while (q->next != NULL) {
        q = q->next;                                    // 移动q指针到链表末尾
    }
    q->next = p;                                        // 链接新节点
}

删除节点

删除节点需要找到要删除的节点的前驱节点，具体步骤如下：

1. 如果链表中不存在节点，则直接返回；
2. 从头节点开始遍历链表；
3. 找到要删除节点的前驱节点；
4. 将前驱节点指向要删除节点的后继节点；
5. 释放要删除的节点。

示例代码：

void DeleteNode(ListNode *head, int data) {
    ListNode *p = head->next;
    ListNode *q = head;
    while (p != NULL && p->data != data) {
        q = p;          // 保留上一个节点
        p = p->next;    // 移动p指针查找节点data
    }
    if (p == NULL) {
        return;         // 不存在节点data
    }
    q->next = p->next;  // 上一个节点指向下一个节点
    free(p);            // 释放要删除的节点
}

打印链表

遍历链表，将每个节点的值打印出来即可。

示例代码：

void PrintList(ListNode *head) {
    ListNode *p = head->next;
    while (p != NULL) {
        printf("%d ", p->data); // 打印节点值
        p = p->next;            // 移动p指针
    }
    printf("\n");
}

销毁链表

遍历链表，依次释放每个节点的空间即可。

示例代码：

void DestroyList(ListNode *head) {
    ListNode *p = head;
    while (p != NULL) {
        ListNode *q = p;
        p = p->next;
        free(q);
    }
}

示例说明

示例一：使用头插法构建链表

ListNode *head;
InitList(&head);
InsertHead(head, 1);
InsertHead(head, 2);
InsertHead(head, 3);
PrintList(head);        // 输出：3 2 1

示例二：使用尾插法构建链表

ListNode *head;
InitList(&head);
InsertTail(head, 1);
InsertTail(head, 2);
InsertTail(head, 3);
PrintList(head);        // 输出：1 2 3

总结

线性链表是一种常见的数据结构，有助于我们理解数据结构的相关知识。在实现时，我们需要定义结构体、实现初始化、插入、删除、遍历、销毁操作等。在实际应用中，可以根据具体业务场景来选择使用带头节点的链表或不带头节点的链表实现。