单链表是数据结构中最基础且重要的概念之一，它是一种线性数据结构，由一系列节点（也称为元素或记录）组成，每个节点包含数据域和指针域。指针域指向下一个节点，最后一个节点的指针域通常为NULL，表示链表的结束。在C语言中，单链表的操作主要包括创建、插入、删除、遍历和查找等。下面将详细解释这些基本操作。
1. 创建单链表：
创建单链表首先要定义一个结构体来表示链表节点，通常命名为`struct Node`，包含数据和指向下一个节点的指针。然后，我们需要一个头节点来追踪链表的起始位置。初始化时，头节点通常为空。
```c
typedef struct Node {
int data;
struct Node* next;
} ListNode;
ListNode* createList() {
ListNode* head = NULL;
return head;
}
```
2. 插入节点：
在单链表中插入节点分为在链表头部插入和在指定位置插入。在头部插入只需改变头节点，而插入到指定位置则需要找到插入点并更新前后节点的指针。
```c
// 在链表头部插入节点
void insertAtHead(ListNode** head, int data) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// 在指定位置插入节点
void insertAtPosition(ListNode** head, int position, int data) {
if (position == 1) {
insertAtHead(head, data);
} else {
ListNode* current = *head;
for (int i = 1; i < position - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) return; // 位置超出链表长度
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = data;
newNode->next = current->next;
current->next = newNode;
}
}
```
3. 删除节点：
删除节点同样分为删除头节点和删除指定位置的节点。删除操作需要处理好指针的连接。
```c
// 删除头节点
void deleteFirstNode(ListNode** head) {
if (*head == NULL) return;
ListNode* temp = *head;
*head = (*head)->next;
free(temp);
}
// 删除指定位置的节点
void deleteNodeAtPosition(ListNode** head, int position) {
if (*head == NULL || position == 1) {
deleteFirstNode(head);
return;
}
ListNode* current = *head;
for (int i = 1; i < position - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL || current->next == NULL) return; // 位置超出链表长度
ListNode* temp = current->next;
current->next = current->next->next;
free(temp);
}
```
4. 遍历单链表：
遍历链表通常用于打印链表的所有元素或进行其他操作。通过头节点开始，沿着next指针顺序访问每个节点。
```c
void traverseList(ListNode* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
```
5. 查找节点：
查找单链表中的特定节点可以通过线性搜索实现，即从头节点开始逐个比较直到找到目标节点或遍历完整个链表。
```c
ListNode* searchListNode(ListNode* head, int target) {
ListNode* current = head;
while (current != NULL) {
if (current->data == target) {
return current;
}
current = current->next;
}
return NULL; // 如果未找到目标节点，返回NULL
}
```
通过这些基本操作，我们可以构建和操作单链表。了解这些概念对于学习更复杂的数据结构和算法至关重要。不断练习和理解这些基础知识，将有助于提升你的编程技能和解决问题的能力。
