c语言链表的基本操作

在C语言中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的基本操作包括创建、插入、删除和遍历等。

下面是一个简单的链表节点结构体定义：

1. struct Node {
2.     int data;
3.     struct Node* next;
4. };

其中，data表示节点中的数据元素，next是指向下一个节点的指针。

1. 创建链表：

链表的创建通常是通过定义一个指向链表头节点的指针，然后逐个添加节点来实现的。例如：

1. struct Node* head = NULL; // 定义指向链表头节点的指针，初始化为空
2. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
3. new_node->data = 1; // 设置节点中的数据元素
4. new_node->next = NULL; // 设置节点的指针为空
5. head = new_node; // 将头指针指向新节点

1. 插入节点：

链表的插入操作通常是在链表的末尾或指定位置插入新节点。在链表末尾插入节点的操作比较简单，只需要将新节点的指针指向原链表的最后一个节点的指针即可。例如：

1. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
2. new_node->data = 2; // 设置节点中的数据元素
3. new_node->next = NULL; // 设置节点的指针为空
4. if (head == NULL) { // 如果链表为空，将新节点设置为头节点
5.     head = new_node;
6. } else { // 否则，将新节点插入到链表末尾
7.     struct Node* last = head;
8.     while (last->next != NULL) { // 遍历找到链表的最后一个节点
9.         last = last->next;
10.     }
11.     last->next = new_node; // 将最后一个节点的指针指向新节点
12. }

要在指定位置插入节点，需要先找到插入位置的前一个节点，然后将前一个节点的指针指向新节点，新节点的指针指向下一个节点。例如：

1. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
2. new_node->data = 3; // 设置节点中的数据元素
3. new_node->next = NULL; // 设置节点的指针为空
4. struct Node* prev = head; // 定义指向插入位置前一个节点的指针
5. struct Node* curr = head->next; // 定义指向插入位置的指针，初始化为头节点的下一个节点
6. while (curr != NULL && curr->data < 20) { // 遍历找到插入位置的前一个节点和插入位置的节点
7.     prev = curr;
8.     curr = curr->next;
9. }
10. prev->next = new_node; // 将前一个节点的指针指向新节点
11. new_node->next = curr; // 将新节点的指针指向插入位置的节点（如果存在）

1. 删除节点：

删除节点需要找到需要删除的节点，然后将前一个节点的指针指向下一个节点。例如：

1. struct Node* delete_node = head; // 定义指向要删除节点的指针，初始化为头节点
2. struct Node* prev = NULL; // 定义指向要删除节点前一个节点的指针
3. struct Node* curr = head; // 定义指向要删除节点后一个节点的指针
4. while (curr != NULL && curr != delete_node) { // 遍历找到要删除的节点和它前后的节点
5.     prev = curr;
6.     curr = curr->next;
7. }
8. if (prev == NULL) { // 如果要删除的是头节点
9.     head = delete_node->next; // 将头指针指向要删除节点的下一个节点
10. } else { // 如果要删除的是中间节点或尾节点
11.     prev->next = delete_node->next; // 将前一个节点的指针指向要删除节点的下一个节点
12. }
13. free(delete_node); // 释放要删除的节点的内存空间

1. 遍历链表：

遍历链表通常是通过定义一个指针指向链表头节点，然后循环遍历每个节点的数据元素。例如：

1. struct Node* curr = head; // 定义指向当前节点的指针，初始化为头节点
2. while (curr != NULL) { // 循环遍历每个节点
3.     printf("%d ", curr->data); // 输出当前节点的数据元素
4.     curr = curr->next; // 将当前节点的指针指向下一个节点
5. }

以上是链表的基本操作，链表的其他操作还包括反转链表、查找元素等。

1. 反转链表：

反转链表需要定义一个指针指向当前节点，另一个指针指向下一个节点，然后将两个指针交换位置，直到两个指针相遇为止。例如：

1. struct Node* reverse_list(struct Node* head) {
2.     struct Node* prev = NULL; // 定义指向当前节点前一个节点的指针
3.     struct Node* curr = head; // 定义指向当前节点的指针，初始化为头节点
4.     struct Node* next = NULL; // 定义指向当前节点后一个节点的指针
5.     while (curr != NULL) { // 遍历链表
6.         next = curr->next; // 将当前节点的指针指向下一个节点
7.         curr->next = prev; // 将当前节点的指针指向前一个节点
8.         prev = curr; // 将当前节点的前一个节点指针指向当前节点
9.         curr = next; // 将当前节点的指针指向下一个节点
10.     }
11.     return prev; // 返回反转后的链表头节点指针
12. }

1. 查找元素：

查找元素需要遍历链表，直到找到目标元素或遍历到链表末尾为止。例如：

1. int search(struct Node* head, int target) {
2.     struct Node* curr = head; // 定义指向当前节点的指针，初始化为头节点
3.     while (curr != NULL) { // 遍历链表
4.         if (curr->data == target) { // 如果当前节点的数据元素等于目标元素
5.             return 1; // 返回1表示找到目标元素
6.         }
7.         curr = curr->next; // 将当前节点的指针指向下一个节点
8.     }
9.     return 0; // 返回0表示未找到目标元素
10. }