C语言：链表

介绍

链表是一种常见的数据结构，用于存储一系列线性数据。与数组不同，链表中的元素在内存中不必是连续存放的，而是通过指针将每个元素（节点）链接在一起。链表有很多种类型，例如单向链表、双向链表和循环链表。这里我们主要介绍单向链表。

单向链表

单向链表由一系列节点组成，每个节点包含两个部分：

1. 数据部分：存储节点的实际内容。
2. 指针部分：存储指向下一个节点的指针。

节点结构

在 C 语言中，我们可以通过定义一个结构体来表示链表的节点：

struct Node {int data;          // 数据部分struct Node* next; // 指针部分
};

创建节点

可以通过动态内存分配函数 malloc 来创建新节点：

#include <stdio.h>
#include <stdlib.h>// 定义节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}

插入节点

我们可以在链表的头部或尾部插入节点。以头部插入为例：

// 头部插入
void insertAtHead(struct Node** head, int data) {struct Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}

删除节点

删除链表中的节点也很常见。假设我们要删除值为 key 的节点：

void deleteNode(struct Node** head, int key) {struct Node* temp = *head;struct Node* prev = NULL;// 如果头节点本身就是要删除的节点if (temp != NULL && temp->data == key) {*head = 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);
}

遍历链表

遍历链表可以通过循环来实现：

void printList(struct Node* head) {struct Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}

尾部插入

尾部插入与头部插入类似，我们需要找到链表的最后一个节点，然后将新节点添加到末尾。

// 尾部插入
void insertAtTail(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}

查找节点

查找链表中的某个节点，返回其位置或者指针：

struct Node* searchNode(struct Node* head, int key) {struct Node* current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL; // 未找到
}

链表反转

反转链表是一个经典的问题，可以通过迭代的方式实现：

void reverseList(struct Node** head) {struct Node* prev = NULL;struct Node* current = *head;struct Node* next = NULL;while (current != NULL) {next = current->next; // 暂存下一个节点current->next = prev; // 反转当前节点的指针prev = current;       // 移动 prev 指针current = next;       // 移动 current 指针}*head = prev;
}

示例程序

程序1

#include <stdio.h>
#include <stdlib.h>struct Node {int data;struct Node* next;
};struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}void insertAtHead(struct Node** head, int data) {struct Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}void deleteNode(struct Node** head, int key) {struct Node* temp = *head;struct Node* prev = NULL;if (temp != NULL && temp->data == key) {*head = 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);
}void printList(struct Node* head) {struct Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;insertAtHead(&head, 1);insertAtHead(&head, 2);insertAtHead(&head, 3);printf("Created Linked List: ");printList(head);deleteNode(&head, 2);printf("Linked List after deletion of 2: ");printList(head);return 0;
}

输出结果：

程序2

#include <stdio.h>
#include <stdlib.h>// 定义节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 头部插入
void insertAtHead(struct Node** head, int data) {struct Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}// 尾部插入
void insertAtTail(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}// 删除节点
void deleteNode(struct Node** head, int key) {struct Node* temp = *head;struct Node* prev = NULL;if (temp != NULL && temp->data == key) {*head = 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);
}// 查找节点
struct Node* searchNode(struct Node* head, int key) {struct Node* current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL;
}// 反转链表
void reverseList(struct Node** head) {struct Node* prev = NULL;struct Node* current = *head;struct Node* next = NULL;while (current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}*head = prev;
}// 打印链表
void printList(struct Node* head) {struct Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;insertAtHead(&head, 1);insertAtHead(&head, 2);insertAtHead(&head, 3);printf("初始链表: ");printList(head);// 测试尾部插入insertAtTail(&head, 4);printf("尾部插入 4 后的链表: ");printList(head);// 测试删除节点deleteNode(&head, 2);printf("删除节点 2 后的链表: ");printList(head);// 测试查找节点struct Node* foundNode = searchNode(head, 3);if (foundNode) {printf("找到节点 3\n");} else {printf("未找到节点 3\n");}// 测试反转链表reverseList(&head);printf("反转后的链表: ");printList(head);return 0;
}

输出结果：