C语言线性表链式表示及实现的方法

1. 引言

线性表是一种常见的数据结构，它由一组有序的元素组成。线性表的存储方式主要有两种：顺序存储和链式存储。顺序存储使用数组来实现，而链式存储则使用链表来实现。本文将详细介绍C语言中线性表的链式表示及实现方法。

2. 链式存储结构

链式存储结构通过节点来存储数据元素，每个节点包含数据域和指针域。数据域用于存储数据元素，指针域用于指向下一个节点。链式存储结构的主要特点是：

• 动态分配内存，不需要预先分配固定大小的存储空间。
• 插入和删除操作效率高，时间复杂度为O(1)。
• 访问元素时需要从头节点开始遍历，时间复杂度为O(n)。

3. 单链表的定义

单链表是最简单的链式存储结构，每个节点只包含一个指向下一个节点的指针。单链表的节点定义如下：

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

4. 单链表的基本操作

4.1 初始化链表

初始化链表时，通常创建一个头节点，头节点不存储数据，仅用于标识链表的起始位置。

Node* initList() {
    Node *head = (Node*)malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;  // 头节点的指针域初始化为NULL
    return head;
}

4.2 插入节点

插入节点可以在链表的任意位置进行。常见的插入操作有头插法和尾插法。

4.2.1 头插法

头插法将新节点插入到头节点之后。

void insertAtHead(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));  // 创建新节点
    newNode->data = data;  // 设置新节点的数据域
    newNode->next = head->next;  // 新节点的指针域指向头节点的下一个节点
    head->next = newNode;  // 头节点的指针域指向新节点
}

4.2.2 尾插法

尾插法将新节点插入到链表的末尾。

void insertAtTail(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));  // 创建新节点
    newNode->data = data;  // 设置新节点的数据域
    newNode->next = NULL;  // 新节点的指针域初始化为NULL

    Node *current = head;
    while (current->next != NULL) {  // 遍历链表，找到最后一个节点
        current = current->next;
    }
    current->next = newNode;  // 最后一个节点的指针域指向新节点
}

4.3 删除节点

删除节点可以通过指定节点的位置或数据值来实现。

void deleteNode(Node *head, int data) {
    Node *current = head;
    while (current->next != NULL && current->next->data != data) {  // 查找要删除的节点
        current = current->next;
    }
    if (current->next != NULL) {  // 如果找到要删除的节点
        Node *temp = current->next;  // 临时保存要删除的节点
        current->next = temp->next;  // 当前节点的指针域指向要删除节点的下一个节点
        free(temp);  // 释放要删除的节点的内存
    }
}

4.4 查找节点

查找节点可以通过遍历链表来实现。

Node* findNode(Node *head, int data) {
    Node *current = head->next;
    while (current != NULL && current->data != data) {  // 遍历链表，查找指定数据的节点
        current = current->next;
    }
    return current;  // 返回找到的节点，如果未找到则返回NULL
}

4.5 遍历链表

遍历链表可以输出链表中的所有元素。

void traverseList(Node *head) {
    Node *current = head->next;
    while (current != NULL) {  // 遍历链表
        printf("%d ", current->data);  // 输出当前节点的数据
        current = current->next;
    }
    printf("\n");
}

5. 链表的优缺点

5.1 优点

• 动态分配内存，不需要预先分配固定大小的存储空间。
• 插入和删除操作效率高，时间复杂度为O(1)。
• 链表长度可以动态变化，不受固定大小的限制。

5.2 缺点

• 访问元素时需要从头节点开始遍历，时间复杂度为O(n)。
• 每个节点需要额外的指针域，增加了存储空间的开销。
• 链表的实现相对复杂，容易出错。

6. 总结

本文介绍了C语言中线性表的链式表示及实现方法。通过定义节点结构体，实现了链表的初始化、插入、删除、查找和遍历等基本操作。链式存储结构具有动态分配内存、插入和删除操作效率高等优点，但也存在访问元素效率低、存储空间开销大等缺点。在实际应用中，应根据具体需求选择合适的存储结构。