C 语言算法与数据结构实战：从数组到递归的避坑之旅

数组——最基础的线性结构

数组是一片连续内存，存放同类型元素。它最大的好处是随机访问快，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;
}

这些内容覆盖了最常用的数据结构和算法，多动手写一写，理解才会更深。