C语言中的线性链表是一种动态的数据结构，它允许我们在运行时根据需要添加或删除元素。与数组不同，链表不需要预先分配固定大小的内存空间。链表中的每个元素（通常称为节点）都包含两部分：数据域（存储实际数据）和指针域（指向链表中的下一个节点）。
链表节点结构体
首先，我们需要定义一个链表节点的结构体。这个结构体通常包含两部分：一个用于存储数据的成员（如int类型）和一个指向下一个节点的指针。
|
typedef struct ListNode { |
|
int data; // 数据域，存储节点的值 |
|
struct ListNode *next; // 指针域，指向下一个节点 |
|
} ListNode; |
链表的基本操作
接下来，我们将实现一些基本的链表操作，如插入节点、删除节点、遍历链表等。
插入节点
插入节点通常有两种情况：在链表头部插入和在链表中间或尾部插入。这里我们实现一个在链表头部插入节点的函数。
|
// 在链表头部插入节点 |
|
void InsertAtHead(ListNode **head, int value) { |
|
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); // 分配新节点的内存 |
|
if (!newNode) { |
|
// 内存分配失败的处理逻辑 |
|
exit(1); |
|
} |
|
newNode->data = value; // 设置新节点的数据 |
|
newNode->next = *head; // 新节点的next指向当前头节点 |
|
*head = newNode; // 更新头节点为新节点 |
|
} |
删除节点
删除节点时，我们需要找到要删除节点的前一个节点，并修改其next指针以跳过要删除的节点。
|
// 删除链表中的指定值节点 |
|
void DeleteNode(ListNode **head, int value) { |
|
ListNode *current = *head; // 当前节点指针 |
|
ListNode *prev = NULL; // 当前节点的前一个节点指针 |
|
|
|
// 查找要删除的节点 |
|
while (current != NULL && current->data != value) { |
|
prev = current; |
|
current = current->next; |
|
} |
|
|
|
// 如果未找到要删除的节点，直接返回 |
|
if (current == NULL) { |
|
return; |
|
} |
|
|
|
// 如果要删除的节点是头节点 |
|
if (prev == NULL) { |
|
*head = current->next; // 更新头节点 |
|
} else { |
|
prev->next = current->next; // 跳过要删除的节点 |
|
} |
|
|
|
free(current); // 释放要删除节点的内存 |
|
} |
遍历链表
遍历链表通常用于打印链表中的元素或查找特定元素。
|
// 遍历链表并打印元素 |
|
void PrintList(ListNode *head) { |
|
ListNode *current = head; // 从头节点开始遍历 |
|
while (current != NULL) { |
|
printf("%d ", current->data); // 打印当前节点的数据 |
|
current = current->next; // 移动到下一个节点 |
|
} |
|
printf("\n"); |
|
} |
释放链表内存
当我们不再需要链表时，需要释放其占用的内存。
|
// 释放链表内存 |
|
void FreeList(ListNode **head) { |
|
ListNode *current = *head; // 当前节点指针 |
|
ListNode *tmp; |
|
while (current != NULL) { |
|
tmp = current; // 保存当前节点的指针 |
|
current = current->next; // 移动到下一个节点 |
|
free(tmp); // 释放当前节点的内存 |
|
} |
|
*head = NULL; // 将头节点指针设为NULL |
|
} |
main 函数示例
最后，在main函数中，我们可以创建一个链表，执行插入、删除和打印操作。
|
int main() { |
|
ListNode *head = NULL; // 初始化链表头节点为NULL |
|
|
|
// 插入节点 |
|
InsertAtHead(&head, 3); |
|
InsertAtHead(&head, 2); |
|
InsertAtHead(&head, 1); |
|
|
|
// 打印链表 |
|
PrintList(head); |
|
|
|
// 删除节点 |
|
DeleteNode(&head, 2); |
|
|
|
// 再次打印链表 |
|
PrintList(head); |
|
|
|
// 释放链表内存 |
|
FreeList(&head); |
|
|
|
return 0; |
|
} |
在这个示例中，我们首先创建了一个空的链表，然后在链表头部插入了三个节点（值为1、2、3）。接着我们打印了链表的内容，删除了值为2的节点，并再次打印了链表的内容。最后，我们释放了链表占用的内存。
