# c-algorithm **Repository Path**: casterrow/c-algorithm ## Basic Information - **Project Name**: c-algorithm - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-06-10 - **Last Updated**: 2026-06-15 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # C语言算法 ### 2009 统考真题 - 已知一个带有表头结点的单链表，结点结构为| data | next |，假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。 #### 解答 - 时间复杂度O(n) ``` int find_k_to_end(LinkList list, int k) { if (list == NULL || k <= 0) return 0; LNode *fast = list->next; //fast指针 LNode *slow = list->next; //slow指针 for (int i = 0; i < k; i++) { if (fast == NULL) return 0; //链表长度小于k直接查找失败 fast = fast->next; } // fast遍历到链表尾部，slow的位置就是要找的元素 while (fast != NULL) { fast = fast->next; slow = slow->next; } printf("result = %d", slow->data); // 输出data域的值 return 1; } ``` ### 2010 统考真题 - 设将 $n$ ($n > 1$) 个整数存放到一维数组 $R$ 中。设计一个在时间和空间两方面都尽可能高效的算法。将 $R$ 中保存的序列循环左移 $p$ ($0 < p < n$) 个位置，即将 $R$ 中的数据由 $(X_0, X_1, ..., X_{n-1})$ 变换为 $(X_p, X_{p+1}, ..., X_{n-1}, X_0, X_1, ..., X_{p-1})$。 #### 解答 - 时间复杂度O(n) - 空间复杂度O(1) ``` void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } ``` ``` void reverse(int arr[], int left, int right) { while (left < right) { // 交换左右指针指向的元素，传输组地址 swap(&arr[left], &arr[right]); // 向中间靠拢 left++; right--; } } ``` ``` void left_rotate_array(int arr[], int size, int p) { reverse(arr, 0, p - 1); reverse(arr, p, size - 1); reverse(arr, 0, size - 1); } ``` ### 2011 统考真题 - 一个长度为 $L$ ($L >= 1$) 的升序序列 $S$，处在第 $ L/2 $ 个位置的数称为 $S$ 的中位数。例如，若序列 $S_1 = (11, 13, 15, 17, 19)$，则 $S_1$ 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 $S_2 = (2, 4, 6, 8, 20)$，则 $S_1$ 和 $S_2$ 的中位数是 11。现在有两个等长升序序列 $A$ 和 $B$，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$ 的中位数。 #### 解答 - 时间复杂度O(n) - 空间复杂度O(1) ``` void get_median(int arr1[], int arr2[], int size) { int i = 0, j = 0, count = 1; while (i < size && j < size) { if (count == size) { if (arr1[i] <= arr2[j]) printf("%d ", arr1[i]); else printf("%d ", arr2[j]); break; //结束循环 } if (arr1[i] < arr2[j]) { i++; count++; continue; } if (arr2[j] < arr1[i]) { j++; count++; continue; } if (arr1[i] == arr2[j]) { i++; j++; if (count == size - 1) { if (arr1[i] <= arr2[j]) printf("%d ", arr1[i]); else printf("%d ", arr2[j]); break; //结束循环 } count = count + 2; } } } ``` ### 2012 统考真题 - 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being，相同的后缀为ing。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 value | next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置。 #### 解答 - 时间复杂度O(n) ``` LNode *find_suffix_node(LinkList str1, LinkList str2) { int size1 = 0, size2 = 0; //链表为空或者只有头节点直接返回NULL if (str1 == NULL || str1->next == NULL || str2 == NULL || str2->next == NULL) return NULL; LNode *p1 = str1->next, *p2 = str2->next; while (p1 != NULL) { p1 = p1->next; size1++; } while (p2 != NULL) { p2 = p2->next; size2++; } p1 = str1->next; //p1再回到str1->next p2 = str2->next; //p2再回到str2->next if (size1 > size2) //先遍历str1走size1-size2个位置 for (int i = 0; i < size1 - size2; i++) p1 = p1->next; if (size1 < size2) //先遍历str2走size2-size1个位置 for (int i = 0; i < size2 - size1; i++) p2 = p2->next; //此时str1和str2长度一样长 LNode *p = NULL; //共同后缀的指针 bool flag = false; while (p1 != NULL) { if (p1->value == p2->value && !flag) { p = p1; //相等且flag设为false，p指向当前元素 flag = true; //flag设为true } if (p1->value != p2->value) { flag = false; //flag设为false if (p1->next != NULL) p = p1->next; //不相等p指向下一个元素 } p1 = p1->next; p2 = p2->next; } if (p && flag) return p; return NULL; } ``` ### 2013 统考真题 - 知一个整数序列 $A = (a_0, a_1, ..., a_{n-1})$，其中 $0 <= a_i < n$ ($0 <= i < n$)。若存在 $a_{p_1} = a_{p_2} = ... = a_{p_m} = x$ 且 $m > n/2$ ($0 <= p_k < n, 1 <= k <= m$)，则称 $x$ 为 $A$ 的主元素。例如 $A = (0, 5, 5, 3, 5, 7, 5, 5)$，则 5 为主元素；又如 $A = (0, 5, 5, 3, 5, 1, 5, 7)$，则 $A$ 中没有主元素。假设 $A$ 中的 $n$ 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 $A$ 的主元素。若存在主元素，则输出该元素；否则输出 -1。 #### 复杂度分析 - 时间复杂度O(n) - 空间复杂度O(1) #### 解题思路 - 摩尔投票法 ``` 主元素是数组中出现次数超过 n/2 的元素，要理解候选主元素算法（摩尔投票法）的原理，需从“主元素的性质”和“抵消思想”两个核心角度分析，结合代码逐步拆解逻辑： 一、主元素的定义与算法目标 主元素是数组中出现次数超过 n/2 的元素。算法目标是高效找到这个元素（或判断不存在）。 二、算法核心思想：“抵消”与“候选保留” 摩尔投票法的关键是 “不同元素相互抵消，最终剩下的候选可能是主元素 （1）主元素 x 的数量 多于所有非主元素的总和（因为 x > n/2，非主元素总和 < n/2） （2）若让 x 和非 x 的元素“两两抵消”，最终剩下的一定是 x（因为 x 数量更多，抵消后仍有剩余） ``` ``` int get_majority_element(int arr[], int size) { int count = 1; //候选主元素个数，初始未1 int m = arr[0]; //候选主元素默认为arr[0] for (int i = 1; i < size; i++) { if (arr[i] == m) count++; //出现候选主元素，count++ else { if (count > 0) count--; //未出现候选主元素且count > 0，count-- else { m = arr[i]; //count = 0，重新设置主元素为arr[i] count = 1; //count重新设为1 } } } if (count == 0) return -1; //count减为0，则不存在主元素 count = 0; //需要统计主元素的个数是否大于 size / 2 for (int i = 1; i < size; i++) if (arr[i] == m) count++; return (count <= size / 2) ? -1 : m; } ``` ### 2018 统考真题 - 给定一个含 $n$ ($n <= 1$) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 $\{-5, 3, 2, 3\}$ 中未出现的最小正整数是 1；数组 $\{1, 2, 3\}$ 中未出现的最小正整数是 4。 #### 复杂度分析 - 时间复杂度O(n) - 时间复杂度O(n) ``` int find_miss(int arr[], int size) { int *a = malloc((size + 1) * sizeof(int)); //初始化数组 for (int i = 1; i <= size + 1; i++) a[i] = 0; for (int j = 0; j < size; j++) { if (arr[j] <= 0 || arr[j] - 1 > size + 1) continue; a[arr[j] - 1] = 1; } for (int k = 0; k <= size; k++) if (a[k] == 0) return k + 1; //第一个为0的下标+1就是要找的元素 return 1; } ``` ### 2019 统考真题 - 设线性表 $L =(a_1, a_2, ..., a_{n-1}, a_n)$采用带头结点的单链表保存，请设计一个空间复杂度为 $O(1) $且时间上尽可能高效的算法，重新排列$ L $中的各结点，得到线性表 $(a_1, a_n, a_2, a_{n-1}, ...)$ #### 复杂度分析 - 时间复杂度O(n) - 空间复杂度O(1) ``` void reset_list(LinkList list) { LNode *fast = list->next, *slow = list->next; // 1. 找中点 while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } // 2. 逆置后半段 LNode *prev = NULL; // 前一个节点 LNode *curr = slow->next; // 当前节点（从第一个数据节点开始） LNode *next = NULL; // 下一个节点 while (curr != NULL) { next = curr->next; // 1. 暂存后继节点 curr->next = prev; // 2. 当前节点指向前一个节点（反转） prev = curr; // 3. 前移 prev curr = next; // 4. 前移 curr } // 如果带头结点，最后要把头结点指向新的首节点 slow->next = prev; // 3. 合并 // 假设 first 是前半段头，second 是后半段逆置后的头 LNode *first = list->next; // 前半段开始 LNode *second = slow->next; // 后半段开始（逆置后） // 断开前后半段，防止干扰 slow->next = NULL; // 交叉合并 while (second != NULL) { // 1. 保存后继 LNode *temp1 = first->next; LNode *temp2 = second->next; // 2. 插入 second 到 first 后面 first->next = second; second->next = temp1; // 3. 指针后移 first = temp1; second = temp2; } } ``` ### 2020 统考真题 - 定义三元组 $(a, b, c)$ ($a, b, c$ 均为整数) 的距离 $D = |a-b| + |b-c| + |c-a|$。给定 3 个非空整数集合 $S_1$、$S_2$ 和 $S_3$，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c)$ ($a \in S_1, b \in S_2, c \in S_3$) 中的最小距离。例如 $S_1 = \{-1, 0, 9\}$，$S_2 = \{-25, -10, 10, 11\}$，$S_3 = \{2, 9, 17, 30, 41\}$，则最小距离为 2，相应的三元组为 $(9, 10, 9)$。 #### 复杂度分析 - 时间复杂度O(n) - 空间复杂度O(1) - ``` int get_min_distance(int arr1[], int size1, int arr2[], int size2, int arr3[], int size3) { int d = INT_MAX; //设置一个很大的数 int best_a = 0, best_b = 0, best_c = 0; int i = 0, j = 0, k = 0; //三个数组的指针 while (i < size1 && j < size2 && k < size3) { int a1 = arr1[i], a2 = arr2[j], a3 = arr3[k]; // 计算当前距离 int dist = calc_distance(a1, a2, a3); // 更新最小距离及对应三元组 if (dist <= d) { d = dist; best_a = a1; best_b = a2; best_c = a3; } //指针移动策略，谁最小谁往前移动 if (a1 <= a2 && a1 <= a3) i++; else if (a2 <= a3 && a2 <= a1) j++; else k++; } printf("triplet: (%d, %d, %d)\n", best_a, best_b, best_c); return d; } ```