C 语言链表基础
链表是C语言中一种重要的数据结构，它通过指针将一系列节点连接起来，形成一个动态的数据集合。与数组不同，链表的大小可以动态调整，插入和删除操作更加高效。本文将逐步讲解链表的基本概念、实现方法以及实际应用场景。
什么是链表？
链表是一种线性数据结构，由一系列节点（Node）组成。每个节点包含两个部分：
- 数据域：存储实际的数据。
- 指针域：存储指向下一个节点的指针。
链表的最后一个节点的指针域通常指向 NULL，表示链表的结束。
链表的类型
链表主要分为以下几种类型：
- 单链表：每个节点只有一个指针，指向下一个节点。
- 双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
- 循环链表：链表的最后一个节点指向第一个节点，形成一个环。
本文主要介绍单链表的实现。
单链表的实现
定义节点结构
在C语言中，链表节点可以通过结构体来定义。以下是一个简单的节点结构体定义：
c
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};
创建链表
创建链表的第一步是创建头节点。头节点是链表的起点，通常不存储实际数据。
c
struct Node* head = NULL; // 初始化头节点为NULL
插入节点
在链表中插入节点有两种常见方式：
- 在链表头部插入：新节点成为链表的头节点。
- 在链表尾部插入：新节点成为链表的最后一个节点。
在链表头部插入
以下代码展示了如何在链表头部插入一个新节点：
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; // 更新头节点为新节点
}
在链表尾部插入
以下代码展示了如何在链表尾部插入一个新节点：
c
void insertAtTail(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 = NULL; // 新节点指向NULL，表示链表的结束
if (*head_ref == NULL) { // 如果链表为空，新节点成为头节点
*head_ref = new_node;
return;
}
struct Node* last = *head_ref;
while (last->next != NULL) { // 找到链表的最后一个节点
last = last->next;
}
last->next = new_node; // 将新节点插入到链表尾部
}
删除节点
删除链表中的节点通常需要找到待删除节点的前一个节点，然后调整指针以跳过待删除节点。
c
void deleteNode(struct Node** head_ref, int key) {
struct Node* temp = *head_ref;
struct Node* 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); // 释放内存
}
遍历链表
遍历链表是指依次访问链表中的每个节点，通常用于打印链表内容或查找特定节点。
c
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data); // 打印当前节点的数据
node = node->next; // 移动到下一个节点
}
printf("NULL\n");
}
实际应用场景
链表在实际编程中有广泛的应用，以下是一些常见的应用场景：
- 动态内存管理：链表可以动态分配内存，适合处理不确定大小的数据集合。
- 实现栈和队列：链表可以方便地实现栈（LIFO）和队列（FIFO）数据结构。
- 图算法：链表常用于表示图的邻接表。
- 文件系统：链表可以用于实现文件系统的目录结构。
总结
链表是C语言中一种重要的数据结构，具有动态调整大小的优势。本文介绍了单链表的基本概念、实现方法以及实际应用场景。通过学习链表，你可以更好地理解指针和动态内存管理的原理。
提示
链表是学习更复杂数据结构（如树和图）的基础。建议通过编写代码来加深对链表的理解。
附加资源与练习
- 练习：尝试实现双链表和循环链表，并比较它们与单链表的异同。
- 资源：阅读《C程序设计语言》（K&R）中的指针和结构体章节，进一步巩固基础知识。
- 挑战：编写一个程序，使用链表实现一个简单的任务管理器，支持添加、删除和查看任务。
通过以上内容，你应该对C语言中的链表有了初步的了解。继续练习和探索，你将能够熟练运用链表解决实际问题。