编辑“︁C 语言链表基础”︁

= C语言链表基础 =

== 介绍 ==  
'''链表（Linked List）'''是C语言中一种重要的动态数据结构，它通过指针将一组零散的内存块串联起来，每个内存块称为一个'''节点（Node）'''。与数组不同，链表不需要连续的内存空间，可以高效地进行插入和删除操作。链表广泛应用于操作系统、文件系统、数据库等领域。

链表主要分为：  
* '''单向链表'''：每个节点包含数据和指向下一个节点的指针。  
* '''双向链表'''：节点包含指向前一个和后一个节点的指针。  
* '''循环链表'''：尾节点指向头节点，形成环形结构。

== 单向链表的结构 ==  
一个单向链表的节点通常由两部分组成：  
1. '''数据域'''：存储实际数据。  
2. '''指针域'''：存储指向下一个节点的地址。

用C语言结构体表示如下：  
<syntaxhighlight lang="c">  
struct Node {  
    int data;           // 数据域  
    struct Node* next;  // 指针域  
};  
</syntaxhighlight>

== 链表的基本操作 ==  

=== 创建链表 ===  
以下代码演示如何创建一个包含3个节点的单向链表：  
<syntaxhighlight lang="c">  
#include <stdio.h>  
#include <stdlib.h>  

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

int main() {  
    // 创建3个节点  
    struct Node* head = NULL;  
    struct Node* second = NULL;  
    struct Node* third = NULL;  

    head = (struct Node*)malloc(sizeof(struct Node));  
    second = (struct Node*)malloc(sizeof(struct Node));  
    third = (struct Node*)malloc(sizeof(struct Node));  

    // 赋值并链接节点  
    head->data = 1;  
    head->next = second;  

    second->data = 2;  
    second->next = third;  

    third->data = 3;  
    third->next = NULL;  

    // 遍历链表并打印  
    struct Node* current = head;  
    while (current != NULL) {  
        printf("%d -> ", current->data);  
        current = current->next;  
    }  
    printf("NULL\n");  

    return 0;  
}  
</syntaxhighlight>  

'''输出'''：  
<pre>  
1 -> 2 -> 3 -> NULL  
</pre>  

=== 插入节点 ===  
在链表中插入节点分为：  
1. 头部插入  
2. 尾部插入  
3. 中间插入  

以下示例展示在头部插入新节点：  
<syntaxhighlight lang="c">  
void insertAtHead(struct Node** head_ref, int new_data) {  
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));  
    new_node->data = new_data;  
    new_node->next = *head_ref;  
    *head_ref = new_node;  
}  
</syntaxhighlight>  

=== 删除节点 ===  
删除指定值的节点：  
<syntaxhighlight lang="c">  
void deleteNode(struct Node** head_ref, int key) {  
    struct Node* temp = *head_ref, *prev = NULL;  

    if (temp != NULL && temp->data == key) {  
        *head_ref = temp->next;  
        free(temp);  
        return;  
    }  

    while (temp != NULL && temp->data != key) {  
        prev = temp;  
        temp = temp->next;  
    }  

    if (temp == NULL) return;  

    prev->next = temp->next;  
    free(temp);  
}  
</syntaxhighlight>  

== 链表的可视化表示 ==  
使用Mermaid绘制单向链表：  
<mermaid>  
graph LR  
    A[Head] --> B[1]  
    B --> C[2]  
    C --> D[3]  
    D --> E[NULL]  
</mermaid>  

== 实际应用案例 ==  
'''场景'''：实现一个简单的学生成绩管理系统，使用链表动态添加和删除学生记录。  

<syntaxhighlight lang="c">  
struct Student {  
    int id;  
    char name[50];  
    float grade;  
    struct Student* next;  
};  

void addStudent(struct Student** head, int id, char* name, float grade) {  
    struct Student* new_student = (struct Student*)malloc(sizeof(struct Student));  
    new_student->id = id;  
    strcpy(new_student->name, name);  
    new_student->grade = grade;  
    new_student->next = *head;  
    *head = new_student;  
}  
</syntaxhighlight>  

== 时间复杂度分析 ==  
链表操作的复杂度：  
* 访问：<math>O(n)</math>  
* 插入/删除（已知位置）：<math>O(1)</math>  
* 搜索：<math>O(n)</math>  

== 常见问题与注意事项 ==  
1. '''内存泄漏'''：每次调用<code>malloc()</code>后必须调用<code>free()</code>。  
2. '''空指针检查'''：操作前需验证指针是否为<code>NULL</code>。  
3. '''头节点处理'''：插入/删除头节点时需要特殊处理。  

== 总结 ==  
链表是C语言中灵活的数据结构，适合动态数据管理。掌握其核心操作（创建、插入、删除、遍历）是学习高级数据结构（如树、图）的基础。通过实践案例（如学生管理系统）可以加深理解。

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言高级数据结构]]