跳到主要内容C 语言算法与数据结构实战:从数组到递归的避坑之旅 | 极客日志C算法
C 语言算法与数据结构实战:从数组到递归的避坑之旅
通过 C 语言实例讲解数组、链表、栈、队列、排序、搜索、递归和分治等核心数据结构和算法,涵盖时间复杂度分析,以及内存泄漏、数组越界等五个常见避坑要点,帮读者牢固程序设计基础。
人间失格2 浏览 
算法与数据结构谁更重要?这个问题争论了很多年,但实际写程序时你会发现,两者根本分不开。算法是解决问题的步骤,数据结构是数据在内存里的组织方式,选错数据结构,再巧妙的算法也跑不起来。下面用 C 语言把最常用的数据结构和算法都过一遍,不是照搬教科书,而是挑那些写程序时真会遇到的场景。
时间复杂度与空间复杂度
先明确一个概念:怎么衡量一段代码的效率?主要看时间复杂度和空间复杂度——算法运行时间和内存占用随输入规模增长的变化趋势。
日常写代码心里要有根弦:能用 O(1) 就别用 O(n),能用 O(n) 就别用 O(n²)。下面三小段代码展示了常数、线性、平方三种复杂度,你一看就明白。
#include <stdio.h>
void func1() {
int a = 10;
int b = 20;
int c = a + b;
printf("c 的值:%d\n", c);
}
void func2(int n) {
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
printf("\n");
}
void func3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", i * j);
}
printf();
}
}
{
n = ;
func1();
func2(n);
func3(n);
;
}
"\n"
int
main
()
int
5
return
0
数组——最基础的线性结构
数组是一片连续内存,存放同类型元素。它最大的好处是随机访问快,O(1) 就能拿到任意下标元素;坏处是插入和删除得挪动后面所有元素。
遍历与查找
数组遍历是基本功,循环跑一遍就完事。查找分两种:如果数据无序,只能线性查找,从头到尾逐个比对;如果有序,二分查找能降到 O(log n)。先看遍历和线性查找的代码。
#include <stdio.h>
void traverse_array(int arr[], int length) {
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
traverse_array(arr, length);
return 0;
}
线性查找没什么花头,一个个对比,找到了返回下标,找不到返回 -1。
#include <stdio.h>
int linear_search(int arr[], int length, int target) {
for (int i = 0; i < length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
int target = 30;
int index = linear_search(arr, length, target);
if (index == -1) {
printf("未找到目标元素!\n");
} else {
printf("目标元素在数组中的下标:%d\n", index);
}
return 0;
}
链表——动态内存的线
链表不要求连续内存,每个节点存数据和指向下一个节点的指针。它在插入、删除时只需要改几个指针,O(1) 就能搞定,但访问第 k 个元素得从头开始遍历,O(n)。头插法最容易实现,每次把新节点挂到链表头部。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* create_list(int data[], int length) {
Node* head = NULL;
Node* new_node;
for (int i = 0; i < length; i++) {
new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("内存分配失败!\n");
return NULL;
}
new_node->data = data[i];
new_node->next = head;
head = new_node;
}
return head;
}
void traverse_list(Node* head) {
Node* ptr = head;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
int main() {
int data[] = {10, 20, 30, 40, 50};
int length = sizeof(data) / sizeof(data[0]);
Node* head = create_list(data, length);
if (head == NULL) {
return 1;
}
traverse_list(head);
Node* ptr = head;
Node* temp;
while (ptr != NULL) {
temp = ptr;
ptr = ptr->next;
free(temp);
}
return 0;
}
链表用完之后不 free 就是内存泄漏,C 语言特别要注意这点。
排序与搜索——处理大量数据
排序算法里冒泡最简单,适合小数据量或者教学,稍大点规模就要上快速排序或归并排序了。冒泡是每次把最大的数'冒'到最后,代码里两重循环。
#include <stdio.h>
void bubble_sort(int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int length = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, length);
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
return 0;
}
排序之外,搜索不能只靠线性,二分查找要求数组事先排好序。代码不贴了,核心就是不断折半,直到找到或者区间为空。
栈与队列——操作受限的线
栈是后进先出(LIFO),队列是先进先出(FIFO)。这种受限结构反而能解决很多实际问题,比如函数调用栈、消息队列。用数组实现一个栈很简单:
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100
typedef struct Stack {
int data[STACK_SIZE];
int top;
} Stack;
void stack_init(Stack* stack) {
stack->top = -1;
}
int stack_is_empty(Stack* stack) {
return stack->top == -1;
}
int stack_is_full(Stack* stack) {
return stack->top == STACK_SIZE - 1;
}
int stack_push(Stack* stack, int value) {
if (stack_is_full(stack)) {
printf("栈已满!\n");
return 0;
}
stack->top++;
stack->data[stack->top] = value;
return 1;
}
int stack_pop(Stack* stack) {
if (stack_is_empty(stack)) {
printf("栈已空!\n");
return 0;
}
int value = stack->data[stack->top];
stack->top--;
return value;
}
int stack_peek(Stack* stack) {
if (stack_is_empty(stack)) {
printf("栈已空!\n");
return 0;
}
return stack->data[stack->top];
}
int main() {
Stack stack;
stack_init(&stack);
stack_push(&stack, 10);
stack_push(&stack, 20);
stack_push(&stack, 30);
printf("栈顶元素:%d\n", stack_peek(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
return 0;
}
递归与分治——化繁为简
递归就是函数调用自身,一定要有明确的终止条件,不然就栈溢出了。分治是把大问题拆成小问题,分别解决再合并。计算阶乘是递归最直观的例子。
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
int n = 5;
int result = factorial(n);
printf("%d 的阶乘:%d\n", n, result);
return 0;
}
现实中递归可能带来重复计算或过深的调用栈,需要留意优化,比如用记忆化或改写成迭代。
避坑指南
- 内存泄漏:malloc 的东西记得 free
- 数组越界:下标从 0 到 length-1,循环边界别搞错
- 空指针:用指针之前判断是否为 NULL
- 递归栈溢出:递归深度太大就考虑迭代或尾递归
- 复杂度太高:数据量一大,O(n²) 的算法就别硬扛了
最后附一个检查数组越界的例子,这种防御性编程习惯很有用。
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < length; i++) {
if (i < 0 || i >= length) {
printf("数组下标越界!\n");
continue;
}
printf("%d ", arr[i]);
}
return 0;
}
这些内容覆盖了最常用的数据结构和算法,多动手写一写,理解才会更深。
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online