C语言算法实战：从数组去重到快速排序精解

1. C语言算法题精解从入门到实战我至今还记得大学时第一次接触C语言算法的场景——面对一堆看似简单的题目却无从下手。经过十多年的开发实践我整理了这套C语言算法解题方法论特别适合已经掌握基础语法但算法能力薄弱的学习者。这些题目覆盖了数组处理、指针操作、排序算法等核心知识点都是企业笔试和实际开发中的高频考点。2. 基础算法题型解析2.1 数组去重算法实现数组去重是面试中最常见的初级算法题看似简单却暗藏玄机。我们先看最基础的实现方案void removeDuplicates(int arr[], int *size) { if (*size 0) return; int newSize 1; for (int i 1; i *size; i) { int isDuplicate 0; for (int j 0; j newSize; j) { if (arr[i] arr[j]) { isDuplicate 1; break; } } if (!isDuplicate) { arr[newSize] arr[i]; } } *size newSize; }这个暴力解法时间复杂度为O(n²)适合小规模数据。实际开发中更推荐先排序后去重的方案时间复杂度可降至O(nlogn)int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } void removeDuplicatesSorted(int arr[], int *size) { if (*size 0) return; qsort(arr, *size, sizeof(int), compare); int newSize 1; for (int i 1; i *size; i) { if (arr[i] ! arr[i-1]) { arr[newSize] arr[i]; } } *size newSize; }重要提示处理字符串去重时要注意\0结束符的位置否则可能导致缓冲区溢出2.2 矩阵转置算法剖析二维数组转置是理解内存布局的绝佳案例。以2行3列转置为3行2列为例void transpose(int src[2][3], int dst[3][2]) { for (int i 0; i 2; i) { for (int j 0; j 3; j) { dst[j][i] src[i][j]; } } }这个基础版本有几个优化点支持动态行列数原地转置方阵情况使用指针运算提升性能优化后的版本void transposeOptimized(int *matrix, int rows, int cols) { int size rows * cols - 1; int visited[size 1]; memset(visited, 0, sizeof(visited)); for (int start 1; start size; start) { if (visited[start]) continue; int current start; int temp matrix[current]; do { int next (current * rows) % size; int swap matrix[next]; matrix[next] temp; temp swap; visited[current] 1; current next; } while (current ! start); } }3. 排序算法深度实现3.1 快速排序的C语言实现快速排序是面试必考算法这个实现包含三数取中优化void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) swap(arr[low], arr[mid]); if (arr[low] arr[high]) swap(arr[low], arr[high]); if (arr[mid] arr[high]) swap(arr[mid], arr[high]); return mid; } int partition(int arr[], int low, int high) { int pivotIndex medianOfThree(arr, low, high); int pivotValue arr[pivotIndex]; swap(arr[pivotIndex], arr[high]); int i low; for (int j low; j high; j) { if (arr[j] pivotValue) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[high]); return i; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }3.2 排序算法性能对比算法类型时间复杂度(平均)空间复杂度稳定性适用场景冒泡排序O(n²)O(1)稳定小规模数据选择排序O(n²)O(1)不稳定交换成本高的场景插入排序O(n²)O(1)稳定基本有序数据快速排序O(nlogn)O(logn)不稳定通用场景归并排序O(nlogn)O(n)稳定链表排序/外部排序4. 实用算法技巧汇编4.1 浮点数相等判断的陷阱新手常犯的错误是用直接比较浮点数。正确做法#include math.h int isEqual(double a, double b) { return fabs(a - b) DBL_EPSILON; }更健壮的实现应考虑相对误差int isEqualRel(double a, double b) { double diff fabs(a - b); a fabs(a); b fabs(b); double largest (b a) ? b : a; return diff largest * DBL_EPSILON; }4.2 位操作实用技巧判断奇偶if (x 1) { // 奇数 } else { // 偶数 }交换两个数a ^ b; b ^ a; a ^ b;求绝对值int abs(int x) { int mask x (sizeof(int) * CHAR_BIT - 1); return (x mask) ^ mask; }5. 综合案例停车场管理系统核心算法这个课程设计项目涉及多个算法知识点#define MAX_SIZE 100 typedef struct { char plate[10]; time_t enterTime; } Vehicle; typedef struct { Vehicle data[MAX_SIZE]; int top; } Stack; typedef struct { Vehicle data[MAX_SIZE]; int front, rear; } Queue; // 栈操作 void push(Stack *s, Vehicle v) { if (s-top MAX_SIZE-1) { s-data[s-top] v; } } Vehicle pop(Stack *s) { if (s-top 0) { return s-data[s-top--]; } Vehicle empty {, 0}; return empty; } // 队列操作 void enqueue(Queue *q, Vehicle v) { if ((q-rear 1) % MAX_SIZE ! q-front) { q-data[q-rear] v; q-rear (q-rear 1) % MAX_SIZE; } } Vehicle dequeue(Queue *q) { if (q-front ! q-rear) { Vehicle v q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return v; } Vehicle empty {, 0}; return empty; } // 计费算法 double calculateFee(time_t enter, time_t exit) { double hours difftime(exit, enter) / 3600.0; if (hours 0.5) return 0; // 30分钟内免费 if (hours 2) return 5; // 2小时内5元 return 5 ceil(hours - 2) * 2; // 之后每小时2元 }6. 算法调试与优化技巧6.1 内存错误排查使用gdb调试段错误(segmentation fault)的基本流程编译时添加-g选项gcc -g program.c -o program启动gdb调试gdb ./program常用命令run # 运行程序 backtrace # 查看调用栈 frame N # 切换到第N帧 print variable # 打印变量值 break filename:line # 设置断点 next # 单步执行6.2 性能优化策略空间换时间使用查找表替代实时计算// 预计算0-255的二进制1的个数 static const unsigned char bits_in_char[256] { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, // ...剩余数据省略 }; int countBits(unsigned int n) { int count 0; unsigned char *p (unsigned char*)n; for (int i 0; i sizeof(n); i) { count bits_in_char[p[i]]; } return count; }循环展开优化// 优化前 for (int i 0; i 100; i) { sum array[i]; } // 优化后 for (int i 0; i 100; i 4) { sum array[i]; sum array[i1]; sum array[i2]; sum array[i3]; }数据局部性优化按行访问二维数组// 差的访问方式按列 for (int j 0; j cols; j) { for (int i 0; i rows; i) { sum matrix[i][j]; } } // 好的访问方式按行 for (int i 0; i rows; i) { for (int j 0; j cols; j) { sum matrix[i][j]; } }7. 进阶算法挑战7.1 DES加密算法实现DES算法虽然现在安全性不足但仍是理解分组加密的经典案例。核心结构typedef struct { uint32_t subkeys[16][48]; } DESContext; // 初始置换表 static const int IP[64] {58, 50, ...}; void desInit(DESContext *ctx, const uint8_t key[8]) { // 生成16轮子密钥 // ... } void desEncryptBlock(DESContext *ctx, const uint8_t input[8], uint8_t output[8]) { // 初始置换 // 16轮Feistel网络 // 最终置换 // ... }7.2 数据结构综合应用链表排序typedef struct Node { int data; struct Node *next; } Node; // 合并两个有序链表 Node* merge(Node *a, Node *b) { Node dummy; Node *tail dummy; dummy.next NULL; while (a b) { if (a-data b-data) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return dummy.next; } // 归并排序主函数 Node* mergeSort(Node *head) { if (!head || !head-next) return head; // 快慢指针找中点 Node *slow head; Node *fast head-next; while (fast fast-next) { slow slow-next; fast fast-next-next; } Node *mid slow-next; slow-next NULL; return merge(mergeSort(head), mergeSort(mid)); }8. 算法学习路线建议基础阶段1-2个月掌握基本数据结构数组、链表、栈、队列理解时间/空间复杂度分析熟练实现基础排序算法提高阶段3-6个月学习树、图等高级数据结构掌握分治、贪心、动态规划等算法思想刷LeetCode简单/中等难度题目进阶阶段6个月研究高级图算法Dijkstra、A*等学习字符串匹配算法KMP、Boyer-Moore挑战系统设计问题个人经验建议每天保持2-3道算法题的练习量重点不是数量而是每道题都彻底理解。我习惯用笔记本记录每道题的多种解法和思路演变过程