链表操作、快速排序和归并排序（可运行代码）

### 链表操作 #### 1. 插入节点 在给定的代码中，提供了两种插入节点的方法：`insert_node_last` 和 `insert_node_order`。 - **`insert_node_last`**：该函数将节点添加到链表的末尾。首先检查当前节点的下一个节点是否为空，如果为空，则创建一个新节点，并将其设置为当前节点的下一个节点；如果非空，则递归调用自身，继续在链表中寻找尾节点。 ```c void insert_node_last(list *head, int value) { if (head->next == NULL) { list *node = (list *)malloc(sizeof(list)); node->data = value; node->next = NULL; head->next = node; } else { insert_node_last(head->next, value); } } ``` - **`insert_node_order`**：该函数将节点按照值大小插入链表中，保持链表有序。如果当前节点的下一个节点为空或其值大于待插入值，则创建新节点并插入；否则递归调用自身，在链表后续部分寻找合适位置。 ```c void insert_node_order(list *head, int value) { if (head->next == NULL || head->next->data >= value) { list *node = (list *)malloc(sizeof(list)); node->data = value; node->next = head->next; head->next = node; } else { insert_node_order(head->next, value); } } ``` #### 2. 删除节点 删除指定值的节点通过 `delete_node` 函数实现。首先检查当前节点是否存在以及其值是否等于待删除值，如果匹配，则删除当前节点；如果不匹配，则递归调用自身，在链表后续部分寻找待删除节点。 ```c void delete_node(list *head, int value) { if (head->next && head->next->data == value) { list *temp = head->next; head->next = head->next->next; free(temp); } else if (head->next->data != value) { delete_node(head->next, value); } } ``` #### 3. 打印链表 `print_list` 函数用于打印链表中的所有节点数据。 ```c void print_list(list *head) { if (head->next) { printf("%8d", head->next->data); print_list(head->next); } } ``` ### 排序算法 #### 1. 快速排序 快速排序是一种高效的排序方法，其基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 ```c void quik_sort(int a[], int start, int end) { int small_index = 0; int big_index = 0; int mid = 0; int key; int i = 0; if (start >= end) return; else { key = a[start]; for (i = start + 1; i <= end; i++) { if (a[i] < key) small[small_index++] = a[i]; else big[big_index++] = a[i]; } mid = start + small_index; for (i = 0; i < small_index; i++) a[start + i] = small[i]; a[mid] = key; for (i = 0; i < big_index; i++) a[i + mid + 1] = big[i]; quik_sort(a, start, mid - 1); quik_sort(a, mid + 1, end); } } ``` #### 2. 归并排序 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。它将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 ```c int merg(int *a, int start, int mid, int end) { int i = 0; int low = start; int high = mid + 1; while (low <= mid && high <= end) { if (a[low] <= a[high]) temp_array[i++] = a[low++]; else temp_array[i++] = a[high++]; } while (low <= mid) temp_array[i++] = a[low++]; while (high <= end) temp_array[i++] = a[high++]; for (i = 0; i <= end - start; i++) a[start + i] = temp_array[i]; } int merger_sort(int a[], int start, int end) { if (start < end) { int mid = (start + end) / 2; merger_sort(a, start, mid); merger_sort(a, mid + 1, end); merg(a, start, mid, end); } return 0; } ``` ### 总结 本文详细介绍了链表的基本操作，包括向链表末尾添加节点、按顺序插入节点、删除指定值的节点以及打印链表等。此外，还深入解析了快速排序和归并排序的实现细节，这两种排序算法都是计算机科学中非常重要的算法，广泛应用于各种场景。通过对这些知识点的学习，可以进一步提高对数据结构和算法的理解。