本文由 linuxROS 整理发布，首发于 linuxros.cn，转载请注明出处。

从排序到迷宫寻路Ubuntu下C语言重温经典算法

大学里学的排序、链表、栈、队列、二叉树、AVL、DFS/BFS……是不是忘得差不多了？这篇把数据结构与算法里的经典货色用纯C语言重新实现一遍，每段代码已在Ubuntu 24.04 + GCC环境下编译运行验证通过，可以直接复制粘贴拿去跑。先收藏起来，有空翻出来复习一下，比看教材高效得多。

一、算法全景图：从排序到寻路

写代码久了，天天手写算法的时候不多，但面试要考、底层优化要用、读源码也绕不开。从基础排序到树的旋转、再到图的搜索，一张图看清全貌：

flowchart LR subgraph 排序["排序算法"] direction TB A1["冒泡排序"] --- A2["快速排序"] end subgraph 线性["线性结构"] direction TB B1["链表/反转"] --- B2["栈 LIFO"] --- B3["队列 FIFO"] end subgraph 树["树结构"] direction TB C1["二叉搜索树"] --- C2["AVL自平衡"] end subgraph 图["图搜索"] direction TB D1["DFS深度优先"] --- D2["BFS广度优先"] end 排序 -->|"O(n²)→O(n log n)"| 线性线性 -->|"LIFO/FIFO"| 树树 -->|"BST→AVL"| 图 style 排序 fill:#E3F2FD,stroke:#1976D2,stroke-width:2px style 线性 fill:#FFF8E1,stroke:#F57C00,stroke-width:2px style 树 fill:#E8F5E9,stroke:#388E3C,stroke-width:2px style 图 fill:#F3E5F5,stroke:#7B1FA2,stroke-width:2px

二、排序算法：冒泡与快排的C语言实现

排序是算法里最基础的一类，面试最爱考。选两个典型：冒泡排序直观好懂，快速排序是分治思想的经典案例。

冒泡排序：相邻比较逐个冒泡

思路很简单——每轮把相邻元素两两比较，大的往后移，一轮下来最大的就"冒"到最后面。优化点在于加个swapped标记，如果一轮下来没有交换，说明已经排好序，直接结束。

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;  /* 提前结束，少跑无用轮 */
    }
}

int main(void) {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

编译运行：

gcc -o bubble bubble.c && ./bubble
# 输出：11 12 22 25 34 64 90

快速排序：分治递归原地交换

快排的思想是选一个基准值（pivot），把小于它的放左边，大于它的放右边，然后递归处理左右两部分。平均时间复杂度 O(n log n)，实际运行速度通常比归并排序更快。

void quick_sort(int arr[], int low, int high) {
    if (low >= high) return;
    int pivot = arr[high];          /* 选最后一个元素做基准 */
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
    int pi = i + 1;                 /* 基准的最终位置 */
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
}

快排的 pivot 选法有很多讲究，随机选或三数取中能避免最坏情况 O(n²)。上面的实现选最后一个元素，在已排序数组上会退化，但代码最简洁，适合理解原理。

三、单向链表：插入、打印与反转

链表是很多高级数据结构的基础。相比数组，链表插入删除 O(1)，但随机访问 O(n)。用头插法建链表，再实现一个原地反转。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* list_insert_head(Node* head, int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = val;
    n->next = head;
    return n;
}

void list_print(Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

Node* list_reverse(Node* head) {
    Node *prev = NULL, *curr = head;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

int main(void) {
    Node* head = NULL;
    head = list_insert_head(head, 30);
    head = list_insert_head(head, 20);
    head = list_insert_head(head, 10);

    printf("原始链表: "); list_print(head);
    head = list_reverse(head);
    printf("反转后:   "); list_print(head);

    /* 别忘了释放 */
    while (head) { Node* t = head; head = head->next; free(t); }
    return 0;
}

编译运行：

gcc -o linkedlist linkedlist.c && ./linkedlist
# 原始链表: 10 -> 20 -> 30 -> NULL
# 反转后:   30 -> 20 -> 10 -> NULL

反转链表是面试中的高频题。核心思路是三个指针 prev/curr/next 同步移动，每次把 curr 的 next 指向 prev。
来自 linuxros.cn · linuxROS

四、栈与队列：LIFO和FIFO的数组实现

栈和队列是最基础的两个线性结构。栈是后进先出（LIFO），队列是先进先出（FIFO）。用数组实现，固定容量，不用指针，不容易出错。

栈：push和pop

#include <stdio.h>
#include <stdbool.h>

#define STACK_MAX 100

typedef struct {
    int data[STACK_MAX];
    int top;
} Stack;

void stack_init(Stack* s) { s->top = -1; }

bool stack_push(Stack* s, int val) {
    if (s->top >= STACK_MAX - 1) return false;
    s->data[++(s->top)] = val;
    return true;
}

bool stack_pop(Stack* s, int* out) {
    if (s->top < 0) return false;
    *out = s->data[(s->top)--];
    return true;
}

int main(void) {
    Stack s; stack_init(&s);
    stack_push(&s, 10); stack_push(&s, 20); stack_push(&s, 30);
    int val;
    while (stack_pop(&s, &val)) printf("%d ", val);  /* 30 20 10 */
    printf("\n");
    return 0;
}

队列：环形数组实现

普通队列出队后前面空间浪费，用环形数组（取模运算）可以复用空间：

#define QUEUE_MAX 100

typedef struct {
    int data[QUEUE_MAX];
    int front, rear, count;
} Queue;

void queue_init(Queue* q) { q->front = 0; q->rear = -1; q->count = 0; }

bool queue_enqueue(Queue* q, int val) {
    if (q->count >= QUEUE_MAX) return false;
    q->rear = (q->rear + 1) % QUEUE_MAX;
    q->data[q->rear] = val;
    q->count++;
    return true;
}

bool queue_dequeue(Queue* q, int* out) {
    if (q->count <= 0) return false;
    *out = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX;
    q->count--;
    return true;
}

五、二叉搜索树与AVL自平衡树

二叉搜索树：插入与中序遍历

BST 的规则很简单：左子树所有节点值小于根，右子树所有节点值大于根。中序遍历就能得到有序序列。

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* bst_insert(TreeNode* root, int val) {
    if (!root) {
        TreeNode* n = (TreeNode*)malloc(sizeof(TreeNode));
        n->val = val; n->left = n->right = NULL;
        return n;
    }
    if (val < root->val)
        root->left = bst_insert(root->left, val);
    else if (val > root->val)
        root->right = bst_insert(root->right, val);
    return root;
}

void bst_inorder(TreeNode* root) {
    if (!root) return;
    bst_inorder(root->left);
    printf("%d ", root->val);
    bst_inorder(root->right);
}

int main(void) {
    TreeNode* root = NULL;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = bst_insert(root, vals[i]);
    printf("BST中序: "); bst_inorder(root); printf("\n");
    /* 输出: 20 30 40 50 60 70 80 */
    return 0;
}

AVL树：四种旋转保持平衡

普通 BST 插入有序数据时会退化成链表，查找效率从 O(log n) 降到 O(n)。AVL 树通过平衡因子（左右子树高度差）和四种旋转来保持平衡：

LL型：左子树的左子树过深 → 右旋一次
RR型：右子树的右子树过深 → 左旋一次
LR型：左子树的右子树过深 → 先左旋子节点，再右旋
RL型：右子树的左子树过深 → 先右旋子节点，再左旋

typedef struct AVLNode {
    int val, height;
    struct AVLNode *left, *right;
} AVLNode;

int avl_height(AVLNode* n) { return n ? n->height : 0; }
int avl_max(int a, int b) { return a > b ? a : b; }

AVLNode* avl_rotate_right(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = avl_max(avl_height(y->left), avl_height(y->right)) + 1;
    x->height = avl_max(avl_height(x->left), avl_height(x->right)) + 1;
    return x;
}

AVLNode* avl_rotate_left(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = avl_max(avl_height(x->left), avl_height(x->right)) + 1;
    y->height = avl_max(avl_height(y->left), avl_height(y->right)) + 1;
    return y;
}

AVLNode* avl_insert(AVLNode* node, int val) {
    if (!node) {
        AVLNode* n = (AVLNode*)malloc(sizeof(AVLNode));
        n->val = val; n->height = 1; n->left = n->right = NULL;
        return n;
    }
    if (val < node->val)
        node->left = avl_insert(node->left, val);
    else if (val > node->val)
        node->right = avl_insert(node->right, val);
    else return node;

    node->height = 1 + avl_max(avl_height(node->left), avl_height(node->right));
    int bf = avl_height(node->left) - avl_height(node->right);

    if (bf > 1 && val < node->left->val)  return avl_rotate_right(node);        /* LL */
    if (bf < -1 && val > node->right->val) return avl_rotate_left(node);        /* RR */
    if (bf > 1 && val > node->left->val) { node->left = avl_rotate_left(node->left); return avl_rotate_right(node); } /* LR */
    if (bf < -1 && val < node->right->val) { node->right = avl_rotate_right(node->right); return avl_rotate_left(node); } /* RL */
    return node;
}

测试插入序列 [10, 20, 30, 40, 50, 25]，AVL 树自动调整，根节点为 30，高度为 3，中序遍历输出 10 20 25 30 40 50。

六、迷宫寻路：DFS与BFS对比

迷宫问题是图搜索的经典应用。DFS（深度优先）一条路走到黑再回溯，BFS（广度优先）层层扩散，保证找到最短路径。

flowchart LR subgraph DFS["DFS 深度优先"] direction TB F1["入口 0,0"] --> F2["往深处探"] F2 --> F3{"碰到死路?"} F3 -->|"是"| F4["回退一格"] F4 --> F2 F3 -->|"否"| F5["继续深入"] F5 --> F6["到达出口"] end subgraph BFS["BFS 广度优先"] direction TB G1["入口 0,0"] --> G2["探索相邻节点"] G2 --> G3["距离=1的所有节点"] G3 --> G4["逐层向外扩散"] G4 --> G5{"抵达出口?"} G5 -->|"否"| G4 G5 -->|"是"| G6["最短路径"] end DFS -- "对比" --- BFS style F6 fill:#E8F5E9,stroke:#388E3C,stroke-width:2px style G6 fill:#E8F5E9,stroke:#388E3C,stroke-width:2px style F4 fill:#FFEBEE,stroke:#D32F2F style DFS fill:#E3F2FD,stroke:#1976D2,stroke-width:2px style BFS fill:#FFF8E1,stroke:#F57C00,stroke-width:2px

DFS递归实现

#include <stdio.h>
#include <stdbool.h>

#define ROWS 5
#define COLS 5

typedef struct { int r, c; } Point;

bool dfs_maze(int maze[ROWS][COLS], int r, int c, int er, int ec,
              bool visited[ROWS][COLS], Point path[], int* pi) {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return false;
    if (maze[r][c] == 1 || visited[r][c]) return false;

    visited[r][c] = true;
    path[*pi].r = r; path[*pi].c = c; (*pi)++;

    if (r == er && c == ec) return true;  /* 找到了 */

    int dr[] = {-1, 1, 0, 0};  /* 上下左右 */
    int dc[] = {0, 0, -1, 1};
    for (int i = 0; i < 4; i++) {
        if (dfs_maze(maze, r + dr[i], c + dc[i], er, ec, visited, path, pi))
            return true;
    }
    (*pi)--;  /* 回溯：撤销这一步 */
    return false;
}

BFS队列实现

bool bfs_maze(int maze[ROWS][COLS], int sr, int sc, int er, int ec) {
    bool visited[ROWS][COLS] = {false};
    Point q[ROWS * COLS];
    int front = 0, rear = 0;

    q[rear++] = (Point){sr, sc};
    visited[sr][sc] = true;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (front < rear) {
        Point p = q[front++];
        if (p.r == er && p.c == ec) return true;

        for (int i = 0; i < 4; i++) {
            int nr = p.r + dr[i], nc = p.c + dc[i];
            if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS
                && maze[nr][nc] == 0 && !visited[nr][nc]) {
                visited[nr][nc] = true;
                q[rear++] = (Point){nr, nc};
            }
        }
    }
    return false;
}

测试用的迷宫：

DFS 找到一条路径：(0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) → (4,2) → (4,3) → (4,4)。BFS 同样能找到。实际场景中 BFS 保证最短路径，但 DFS 内存占用更少。

七、算法复杂度速查

算法/结构	时间复杂度	空间复杂度	核心思想
冒泡排序	O(n²)	O(1)	相邻比较交换
快速排序	O(n log n) 平均	O(log n)	分治 + 基准分区
链表反转	O(n)	O(1)	三指针原地反转
栈 push/pop	O(1)	O(n)	数组 + top 指针
队列 enq/deq	O(1)	O(n)	环形数组取模
BST 插入/查找	O(log n) 平均	O(n)	二分查找树
AVL 插入/查找	O(log n) 保证	O(n)	平衡因子 + 旋转
DFS 迷宫	O(4^(m×n))	O(m×n)	递归回溯
BFS 迷宫	O(m×n)	O(m×n)	队列逐层扩散

八、常见踩坑与提醒

坑	原因	解法
快排有序数组退化	选最后一个元素做 pivot	随机选 pivot 或三数取中
链表反转后忘记释放	只关注算法逻辑	遍历 free 每个节点
栈/队列数组越界	未检查边界条件	push/enq 前判断 count/max
BST 退化成链表	插入顺序正好有序	用 AVL 或红黑树替代
AVL 旋转后高度未更新	忘记重算 height	旋转后先算子节点高度再算父节点
DFS 迷宫无限递归	未标记 visited	进入节点立即标记 visited
BFS 队列溢出	未限制队列大小	用环形队列或限制最大节点数

九、值得收藏的开源参考

这几个 GitHub 仓库值得收藏，都是终端可视化或纯 C 实现：

仓库	亮点
`krahets/hello-algo`	128k+ Star，动画图解数据结构与算法，支持 C 语言等 14 种语言，清华邓俊辉教授与亚马逊李沐推荐
`creme332/console-maze-solver-ai`	终端纯字符实现的 DFS/BFS/Dijkstra/A* 迷宫寻路，无任何图形库依赖
`YamanSD/SortingVisualizer`	Python 排序算法可视化，GUI 交互式观察排序过程

从排序到链表，从栈队列到 AVL 树，再到迷宫寻路，这些算法是每个程序员的内功。真正面试时不一定让你手写 AVL 旋转，但理解了这些基础，遇到复杂问题才能拆解。所有代码在 Ubuntu 24.04 + GCC 下验证通过，复制到 .c 文件里 gcc 编译就能跑。