C语言经典算法有哪些实用技巧？

论文：C语言经典算法集锦

算法是计算机科学的灵魂，而C语言因其高效、灵活和接近硬件的特性，成为实现和教学算法的经典语言，本文旨在系统性地梳理和阐述在C语言环境下实现的一系列经典算法，内容涵盖数据结构基础（如链表、栈、队列）、排序算法（如快速排序、归并排序）、查找算法（如二分查找）、图算法（如深度优先搜索、广度优先搜索）以及动态规划（如斐波那契数列、背包问题）等，对于每个算法，本文将详细阐述其核心思想，并提供清晰、可读的C语言代码实现，辅以时间复杂度和空间复杂度的分析，最后探讨其典型应用场景，本文旨在为C语言学习者、开发者以及对算法感兴趣的读者提供一个全面、实用的算法参考手册。

C语言；算法；数据结构；排序；查找；图算法；动态规划

计算机科学的核心问题之一是“如何有效地组织和处理数据”，算法，作为解决特定问题的一系列清晰、有限的指令，正是这一问题的答案，自计算机诞生以来，无数经典的算法被提出和优化,它们构成了现代软件工程的基石。

C语言由丹尼斯·里奇于1972年发明，以其简洁、高效、强大的指针操作和直接内存管理能力而闻名，它不仅是操作系统（如Linux、Unix）和嵌入式系统的首选开发语言，也是数据结构与算法课程的入门教学语言，在C语言中实现算法,能够让开发者更深刻地理解算法的内部工作机制和底层资源消耗。

本文的目的并非创造新的算法，而是对那些在计算机科学领域经久不衰、应用广泛的经典算法进行一次集中的、以C语言为载体的展示和分析，通过阅读本文,读者将能够：

1. 回顾并巩固核心数据结构（链表、栈、队列）的C语言实现。
2. 掌握几种最重要排序和查找算法的原理与代码。
3. 理解图论中两种基本的遍历算法。
4. 初步接触动态规划这一强大思想,并通过简单案例入门。
5. 建立对算法效率（时间/空间复杂度）的基本评估能力。

数据结构基础

数据结构是算法操作的对象，高效的数据结构是高效算法的前提，本节将介绍三种最基础的非线性数据结构：链表、栈和队列。

1 链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

核心思想： 由一系列节点组成，每个节点包含两部分：数据域和指向下一个节点的指针域，链表的插入和删除操作效率高,无需移动大量元素。

C语言实现：

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}
// 打印链表
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
int main() {
    Node* head = NULL; // 空链表
    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    printList(head); // 输出: 30 -> 20 -> 10 -> NULL
    return 0;
}

复杂度分析：

• 时间复杂度：
  • 插入（头部）：O(1)
  • 查找：O(n),最坏情况下需遍历整个链表。
  • 删除：O(n)，查找节点为O(n)，删除操作本身为O(1)。
• 空间复杂度： O(n),n为链表长度。

2 栈

栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素，这一端被称为栈顶，另一端称为栈底，栈遵循 后进先出 的原则。

核心思想： 主要操作为 push（入栈，添加元素到栈顶）和 pop（出栈，移除栈顶元素）。

C语言实现（基于数组）：

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;
void initStack(Stack* s) {
    s->top = -1;
}
bool isEmpty(Stack* s) {
    return s->top == -1;
}
bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}
void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->items[++s->top] = value;
}
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1; // 错误码
    }
    return s->items[s->top--];
}
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->items[s->top];
}
int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top element: %d\n", peek(&s)); // 输出 30
    printf("Popped element: %d\n", pop(&s)); // 输出 30
    printf("Top element: %d\n", peek(&s)); // 输出 20
    return 0;
}

复杂度分析：

• 时间复杂度： O(1)，所有操作（push, pop, peek）都只涉及对栈顶指针的访问和修改。
• 空间复杂度： O(n),由数组预定义大小决定。

3 队列

队列也是一种特殊的线性表，它遵循 先进先出 的原则，元素在队尾插入,在队头删除。

核心思想： 主要操作为 enqueue（入队）和 dequeue（出队）。

C语言实现（基于循环数组）：

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 5
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}
bool isEmpty(Queue* q) {
    return q->front == -1;
}
bool isFull(Queue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
}
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) { // 队列中只剩一个元素
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return item;
}
int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued: %d\n", dequeue(&q)); // 输出 10
    printf("Dequeued: %d\n", dequeue(&q)); // 输出 20
    return 0;
}

复杂度分析：

• 时间复杂度： O(1),所有操作都只涉及对队头和队尾指针的访问和修改。
• 空间复杂度： O(n),由数组预定义大小决定。

排序算法

排序算法是将一组数据按照特定顺序（如升序或降序）重新排列的算法，它是计算机科学中最基本、最重要的算法之一。

1 快速排序

快速排序是一种高效的排序算法，采用 分治法 策略。

核心思想：

1. 选择基准： 从数列中挑出一个元素，称为 "基准"。
2. 分区： 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，在这个分区退出之后,该基准就处于数列的中间位置。
3. 递归： 递归地将小于基准值元素的子数列和大于基准值元素的子数列进行排序。

C语言实现：

#include <stdio.h>
// 交换两个元素
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);     // 小于基准的元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加小于基准的元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi是分区后基准的位置
        int pi = partition(arr, low, high);
        // 递归地对基准左边和右边的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

复杂度分析：

• 时间复杂度：
  • 平均情况：O(n log n)
  • 最坏情况：O(n²)，当数组已经有序或逆序时,分区极度不平衡。
  • 最好情况：O(n log n)
• 空间复杂度： O(log n),主要是递归调用栈的深度。

2 归并排序

归并排序也是一种采用 分治法 的排序算法。

核心思想：

1. 分解： 将数组分成两半,递归地对每一半进行排序。
2. 合并： 将两个已排序的子数组合并成一个有序的数组。

C语言实现：

#include <stdio.h>
#include <stdlib.h>
// 合并两个已排序的子数组
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // 创建临时数组
    int L[n1], R[n2];
    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    // 合并临时数组
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
// 归并排序主函数
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, arr_size - 1);
    printf("Sorted array: \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

复杂度分析：

• 时间复杂度： O(n log n),在各种情况下表现稳定。
• 空间复杂度： O(n),需要额外的空间来存储临时数组。

查找算法

查找算法是在一个数据集合中寻找特定元素的过程。

1 二分查找

二分查找是一种在有序数组中查找特定元素的搜索算法。

核心思想： 每次比较都使搜索范围减半。

1. 从数组的中间元素开始，如果中间元素正好是要查找的元素,则搜索过程结束。
2. 如果要查找的元素大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找。
3. 重复这个过程,直到找到目标元素或搜索范围为空。

C语言实现：

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        // 检查x是否在中间位置
        if (arr[m] == x)
            return m;
        // 如果x大于中间元素，则它只能在右半部分
        if (arr[m] < x)
            l = m + 1;
        // 如果x小于中间元素，则它只能在左半部分
        else
            r = m - 1;
    }
    // 如果元素不存在
    return -1;
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present in array\n")
                   : printf("Element is present at index %d\n", result);
    return 0;
}

复杂度分析：

• 时间复杂度： O(log n),每次迭代都将搜索空间减半。
• 空间复杂度： O(1)，迭代实现，递归实现为O(log n)。

图算法

图是由顶点和边组成的非线性数据结构,用于表示多对多的关系。

1 深度优先搜索

DFS是一种用于遍历或搜索树或图的算法。

核心思想： 尽可能深地搜索图的分支，当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点,这一过程一直进行到已发现从源节点可达的所有节点为止。

C语言实现（基于邻接表）：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表节点
struct Node {
    int vertex;
    struct Node* next;
};
// 图结构
struct Graph {
    int numVertices;
    struct Node* adjLists[MAX_VERTICES];
    int visited[MAX_VERTICES];
};
// 创建新节点
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}
// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // 无向图，添加从dest到src的边
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}
// DFS递归函数
void DFS(struct Graph* graph, int vertex) {
    struct Node* adjList = graph->adjLists[vertex];
    struct Node* temp = adjList;
    graph->visited[vertex] = 1;
    printf("Visited %d\n", vertex);
    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        temp = temp->next;
    }
}
int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    printf("Depth First Search starting from vertex 0:\n");
    DFS(graph, 0);
    return 0;
}

复杂度分析：

• 时间复杂度： O(V + E)，其中V是顶点数，E是边数,每个顶点和每条边都会被访问一次。
• 空间复杂度： O(V),用于存储访问标记和递归调用栈。

2 广度优先搜索

BFS也是一种用于遍历或搜索树或图的算法。

核心思想： 从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法中止,一般用队列数据结构来辅助实现。

C语言实现（基于邻接表和队列）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// 邻接表节点 (与DFS相同)
struct Node {
    int vertex;
    struct Node* next;
};
// 队列节点 (用于BFS)
struct QueueNode {
    int data;
    struct QueueNode* next;
};
// 队列结构
struct Queue {
    struct QueueNode *front, *rear;
};
// 创建队列节点
struct QueueNode* newQueueNode(int k) {
    struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    temp->data = k;
    temp->next = NULL;
    return temp;
}
// 创建空队列
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}
// 入队
void enQueue(struct Queue* q, int k) {
    struct QueueNode* temp = newQueueNode(k);
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}
// 出队
int deQueue(struct Queue* q) {
    if (q->front == NULL) return -1;
    struct QueueNode* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return data;
}
// BFS主函数 (需要DFS中的createGraph, addEdge和图结构)
void BFS(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();
    graph->visited[startVertex] = 1;
    enQueue(q, startVertex);
    while (q->front != NULL) {
        int currentVertex = deQueue(q);
        printf("Visited %d\n", currentVertex);
        struct Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enQueue(q, adjVertex);
            }
            temp = temp->next;
        }
    }
}
// main函数与DFS类似，调用BFS(graph, 0);

复杂度分析：

• 时间复杂度： O(V + E),与DFS相同。
• 空间复杂度： O(V),队列和访问标记在最坏情况下可能存储所有顶点。

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

1 斐波那契数列

斐波那契数列是动态规划最经典的入门案例。

问题描述： F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)。

核心思想： 递归求解会有大量重复计算，动态规划通过存储子问题的解（备忘录）来避免重复计算。

C语言实现（自底向上，带备忘录的迭代）：

#include <stdio.h>
// 带备忘录的斐波那契
int fibonacci(int n, int memo[]) {
    if (n <= 1) {
        return n;
    }
    // 如果已经计算过，直接返回
    if (memo[n] != 0) {
        return memo[n];
    }
    // 否则计算并存储
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}
int main() {
    int n = 10;
    int memo[n + 1]; // 备忘录数组，初始化为0
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n, memo));
    return 0;
}

复杂度分析：

• 时间复杂度： O(n),每个斐波那契数只计算一次。
• 空间复杂度： O(n),用于存储备忘录。

总结与展望

本文系统地介绍了在C语言环境下实现的一系列经典算法，从基础的链表、栈、队列数据结构，到高效的排序（快速排序、归并排序）和查找（二分查找）算法，再到图论中的遍历算法以及动态规划的入门案例，我们不仅看到了这些算法优雅的思想,也通过C语言代码实现了它们。

C语言的指针和手动内存管理特性，使得这些算法的实现更加贴近其本质，有助于开发者深刻理解算法的内部运作和资源开销，在链表操作中，指针的灵活运用是核心；在递归算法（如DFS、快速排序）中,对调用栈的理解至关重要。

算法的世界远不止于此,还有更多高级和专门的领域等待探索，

• 高级数据结构： 如堆、平衡二叉树（AVL树、红黑树）、哈希表、Trie树等。
• 更复杂的图算法： 如最短路径（Dijkstra、Floyd-Warshall算法）、最小生成树（Prim、Kruskal算法）。
• 字符串算法： 如KMP算法、Boyer-Moore算法。
• 贪心算法： 如霍夫曼编码、活动选择问题。

掌握这些经典算法是成为一名优秀程序员的必经之路，通过C语言实践它们，不仅能提升编程能力，更能锻炼逻辑思维和解决复杂问题的能力,希望本文能为读者的算法学习之旅提供一个坚实的起点。

参考文献

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. (2009). Introduction to Algorithms (3rd ed.). MIT Press. [2] Brian W. Kernighan, Dennis M. Ritchie. (1988). The C Programming Language (2nd ed.). Prentice Hall. [3] Mark Allen Weiss. (2025). Data Structures and Algorithm Analysis in C (4th ed.). Pearson. [4] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.