算法筑基（九）：常用数据结构及其算法实现——C语言版

---

📖 前言

如果说算法是解决问题的灵魂，那么数据结构就是承载灵魂的躯体。没有合适的数据结构，再好的算法也无法高效运行。数组、链表、栈、队列、树、堆、并查集、哈希表……这些都是编程中最基础也最重要的数据结构，也是面试和工程开发的高频考点。

在前八篇文章中，我们已经使用了这些数据结构（如邻接表、并查集、堆等），但并未系统讲解它们的实现。本文将以 C 语言 为工具，从零实现这些经典数据结构，每一行代码都配有详细注释，并结合实际案例说明它们的使用场景。最后附上课后练习及答案，帮助你将理论知识转化为实际编码能力。

---

📌 本文目录

1. 数组与链表

   • 动态数组（Vector）
   • 单链表
   • 双链表

2. 栈与队列

   • 顺序栈
   • 链式栈
   • 循环队列

3. 树与二叉树

   • 二叉树遍历（递归与非递归）
   • 二叉搜索树（BST）

4. 堆

   • 最大堆（基于数组）

5. 并查集

   • 路径压缩 + 按秩合并

6. 哈希表

   • 拉链法实现（支持字符串键）

7. 数据结构对比总结

8. 课后练习与答案

---

1. 数组与链表

1.1 动态数组（Vector）

C 语言中没有内置的动态数组，需要手动管理内存，实现自动扩容。

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

typedef struct {
    int *data;
    int size;      // 当前元素个数
    int capacity;  // 当前容量
} DynamicArray;

// 初始化动态数组
void daInit(DynamicArray *arr, int initialCapacity) {
    arr->data = (int*)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
}

// 释放内存
void daFree(DynamicArray *arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = arr->capacity = 0;
}

// 扩容
void daResize(DynamicArray *arr, int newCapacity) {
    arr->data = (int*)realloc(arr->data, newCapacity * sizeof(int));
    arr->capacity = newCapacity;
}

// 在末尾添加元素
void daPushBack(DynamicArray *arr, int value) {
    if (arr->size == arr->capacity) {
        daResize(arr, arr->capacity * 2);
    }
    arr->data[arr->size++] = value;
}

// 删除末尾元素
void daPopBack(DynamicArray *arr) {
    if (arr->size > 0) arr->size--;
}

// 获取指定位置元素
int daGet(DynamicArray *arr, int index) {
    if (index < 0 || index >= arr->size) {
        fprintf(stderr, "索引越界\n");
        exit(1);
    }
    return arr->data[index];
}

// 设置指定位置元素
void daSet(DynamicArray *arr, int index, int value) {
    if (index < 0 || index >= arr->size) {
        fprintf(stderr, "索引越界\n");
        exit(1);
    }
    arr->data[index] = value;
}

int main() {
    DynamicArray arr;
    daInit(&arr, 4);
    for (int i = 0; i < 10; i++) daPushBack(&arr, i * i);
    printf("元素个数: %d, 容量: %d\n", arr.size, arr.capacity);
    for (int i = 0; i < arr.size; i++) printf("%d ", daGet(&arr, i));
    printf("\n");
    daFree(&arr);
    return 0;
}

案例：实现一个可以动态增长的整数集合，如统计学生成绩。

复杂度：

• 末尾插入均摊 O(1)（扩容时 O(n)）
• 随机访问 O(1)
• 中间插入/删除 O(n)

---

1.2 单链表

链表由节点构成，每个节点包含数据域和指向下一节点的指针。

#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));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 头部插入
void insertHead(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 尾部插入
void insertTail(Node **head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *cur = *head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = newNode;
}

// 删除值为 data 的第一个节点
void deleteNode(Node **head, int data) {
    if (*head == NULL) return;
    if ((*head)->data == data) {
        Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    Node *cur = *head;
    while (cur->next != NULL && cur->next->data != data) {
        cur = cur->next;
    }
    if (cur->next != NULL) {
        Node *temp = cur->next;
        cur->next = temp->next;
        free(temp);
    }
}

// 反转链表
void reverse(Node **head) {
    Node *prev = NULL;
    Node *cur = *head;
    Node *next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *head = prev;
}

// 打印链表
void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

// 释放链表
void freeList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        Node *temp = cur;
        cur = cur->next;
        free(temp);
    }
}

int main() {
    Node *head = NULL;
    insertTail(&head, 1);
    insertTail(&head, 2);
    insertTail(&head, 3);
    insertHead(&head, 0);
    printList(head);
    reverse(&head);
    printList(head);
    deleteNode(&head, 2);
    printList(head);
    freeList(head);
    return 0;
}

案例：实现一个简单的任务队列，支持头部插入和尾部删除。

复杂度：

• 头部插入/删除 O(1)
• 尾部插入 O(n)（若无尾指针）
• 查找 O(n)

---

1.3 双链表

双链表节点包含前驱和后继指针，便于双向遍历和删除。

typedef struct DNode {
    int data;
    struct DNode *prev, *next;
} DNode;

// 创建双链表节点
DNode* createDNode(int data) {
    DNode *node = (DNode*)malloc(sizeof(DNode));
    node->data = data;
    node->prev = node->next = NULL;
    return node;
}

// 尾部插入
void insertTailD(DNode **head, DNode **tail, int data) {
    DNode *node = createDNode(data);
    if (*head == NULL) {
        *head = *tail = node;
        return;
    }
    (*tail)->next = node;
    node->prev = *tail;
    *tail = node;
}

// 删除节点（已知指针）
void deleteNodeD(DNode **head, DNode **tail, DNode *node) {
    if (node->prev != NULL) node->prev->next = node->next;
    else *head = node->next;
    if (node->next != NULL) node->next->prev = node->prev;
    else *tail = node->prev;
    free(node);
}

案例：浏览器的前进后退功能，可以用双链表实现。

---

2. 栈与队列

2.1 顺序栈（数组实现）

#define STACK_MAX 100

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

void initStack(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
int isFull(Stack *s) { return s->top == STACK_MAX - 1; }

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("栈满\n");
        return;
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈空\n");
        return -1;
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (isEmpty(s)) return -1;
    return s->data[s->top];
}

案例：括号匹配、表达式求值。

2.2 链式栈

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

typedef struct {
    StackNode *top;
} LinkedStack;

void initLinkedStack(LinkedStack *s) { s->top = NULL; }

void pushLinked(LinkedStack *s, int value) {
    StackNode *node = (StackNode*)malloc(sizeof(StackNode));
    node->data = value;
    node->next = s->top;
    s->top = node;
}

int popLinked(LinkedStack *s) {
    if (s->top == NULL) return -1;
    int val = s->top->data;
    StackNode *temp = s->top;
    s->top = s->top->next;
    free(temp);
    return val;
}

2.3 循环队列（数组实现）

#define QUEUE_MAX 5

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

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

int isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

int isQueueFull(Queue *q) {
    return (q->rear + 1) % QUEUE_MAX == q->front;
}

void enqueue(Queue *q, int value) {
    if (isQueueFull(q)) {
        printf("队列满\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % QUEUE_MAX;
}

int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("队列空\n");
        return -1;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX;
    return val;
}

案例：BFS 的辅助结构、生产者-消费者模型。

---

3. 树与二叉树

3.1 二叉树节点与遍历

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

// 创建节点
TreeNode* createTreeNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 前序遍历（递归）
void preorder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历
void inorder(TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 后序遍历
void postorder(TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// 层序遍历（借助队列）
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, (int)(long)root);  // 这里简化，实际应存指针
    while (!isQueueEmpty(&q)) {
        TreeNode *cur = (TreeNode*)(long)dequeue(&q);
        printf("%d ", cur->data);
        if (cur->left) enqueue(&q, (int)(long)cur->left);
        if (cur->right) enqueue(&q, (int)(long)cur->right);
    }
}

3.2 二叉搜索树（BST）

// 插入
TreeNode* bstInsert(TreeNode *root, int data) {
    if (root == NULL) return createTreeNode(data);
    if (data < root->data)
        root->left = bstInsert(root->left, data);
    else if (data > root->data)
        root->right = bstInsert(root->right, data);
    return root;
}

// 查找
TreeNode* bstSearch(TreeNode *root, int data) {
    if (root == NULL || root->data == data) return root;
    if (data < root->data) return bstSearch(root->left, data);
    return bstSearch(root->right, data);
}

// 查找最小值节点
TreeNode* findMin(TreeNode *root) {
    while (root && root->left) root = root->left;
    return root;
}

// 删除节点
TreeNode* bstDelete(TreeNode *root, int data) {
    if (root == NULL) return NULL;
    if (data < root->data)
        root->left = bstDelete(root->left, data);
    else if (data > root->data)
        root->right = bstDelete(root->right, data);
    else {
        // 找到要删除的节点
        if (root->left == NULL) {
            TreeNode *right = root->right;
            free(root);
            return right;
        } else if (root->right == NULL) {
            TreeNode *left = root->left;
            free(root);
            return left;
        } else {
            // 有两个孩子：找到右子树的最小节点替换
            TreeNode *min = findMin(root->right);
            root->data = min->data;
            root->right = bstDelete(root->right, min->data);
        }
    }
    return root;
}

案例：实现一个动态集合，支持插入、查找、删除。

复杂度：

• 平均 O(log n)
• 最坏 O(n)（退化为链表）

---

4. 堆（优先队列）

最大堆的实现（使用数组）。

#define MAX_HEAP_SIZE 100

typedef struct {
    int data[MAX_HEAP_SIZE];
    int size;
} MaxHeap;

void initHeap(MaxHeap *h) { h->size = 0; }

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

// 上浮
void siftUp(MaxHeap *h, int idx) {
    while (idx > 0 && h->data[(idx - 1) / 2] < h->data[idx]) {
        swap(&h->data[(idx - 1) / 2], &h->data[idx]);
        idx = (idx - 1) / 2;
    }
}

// 下沉
void siftDown(MaxHeap *h, int idx) {
    int n = h->size;
    while (1) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int largest = idx;
        if (left < n && h->data[left] > h->data[largest]) largest = left;
        if (right < n && h->data[right] > h->data[largest]) largest = right;
        if (largest == idx) break;
        swap(&h->data[idx], &h->data[largest]);
        idx = largest;
    }
}

void pushHeap(MaxHeap *h, int value) {
    if (h->size >= MAX_HEAP_SIZE) return;
    h->data[h->size] = value;
    siftUp(h, h->size);
    h->size++;
}

int popHeap(MaxHeap *h) {
    if (h->size == 0) return -1;
    int max = h->data[0];
    h->data[0] = h->data[h->size - 1];
    h->size--;
    siftDown(h, 0);
    return max;
}

案例：实现优先级任务调度，堆排序。

---

5. 并查集（Union-Find）

#include <stdio.h>
#define MAX 1000

int parent[MAX];
int rank[MAX];  // 秩（树高）

void initUF(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 路径压缩
    return parent[x];
}

void unionSets(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) {
        parent[rx] = ry;
    } else if (rank[rx] > rank[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank[rx]++;
    }
}

int main() {
    initUF(10);
    unionSets(1, 2);
    unionSets(2, 3);
    unionSets(4, 5);
    printf("find(1)=%d, find(3)=%d\n", find(1), find(3));
    printf("find(4)=%d, find(5)=%d\n", find(4), find(5));
    return 0;
}

案例：Kruskal 最小生成树、连通分量检测。

---

6. 哈希表（拉链法）

下面实现一个支持字符串键的哈希表。

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

#define TABLE_SIZE 100

typedef struct HashNode {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode *buckets[TABLE_SIZE];
} HashMap;

// 简单的哈希函数（djb2）
unsigned int hash(const char *key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash % TABLE_SIZE;
}

HashMap* createMap() {
    HashMap *map = (HashMap*)malloc(sizeof(HashMap));
    for (int i = 0; i < TABLE_SIZE; i++) map->buckets[i] = NULL;
    return map;
}

void put(HashMap *map, const char *key, int value) {
    int idx = hash(key);
    HashNode *cur = map->buckets[idx];
    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;   // 更新
            return;
        }
        cur = cur->next;
    }
    // 头插法
    HashNode *newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = (char*)malloc(strlen(key) + 1);
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = map->buckets[idx];
    map->buckets[idx] = newNode;
}

int get(HashMap *map, const char *key) {
    int idx = hash(key);
    HashNode *cur = map->buckets[idx];
    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) return cur->value;
        cur = cur->next;
    }
    return -1;  // 未找到
}

void deleteKey(HashMap *map, const char *key) {
    int idx = hash(key);
    HashNode *cur = map->buckets[idx];
    HashNode *prev = NULL;
    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) {
            if (prev == NULL)
                map->buckets[idx] = cur->next;
            else
                prev->next = cur->next;
            free(cur->key);
            free(cur);
            return;
        }
        prev = cur;
        cur = cur->next;
    }
}

void freeMap(HashMap *map) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        HashNode *cur = map->buckets[i];
        while (cur != NULL) {
            HashNode *temp = cur;
            cur = cur->next;
            free(temp->key);
            free(temp);
        }
    }
    free(map);
}

int main() {
    HashMap *map = createMap();
    put(map, "apple", 10);
    put(map, "banana", 20);
    put(map, "orange", 30);
    printf("apple: %d\n", get(map, "apple"));
    printf("banana: %d\n", get(map, "banana"));
    deleteKey(map, "apple");
    printf("apple after delete: %d\n", get(map, "apple"));
    freeMap(map);
    return 0;
}

案例：实现一个简单的键值存储，如缓存系统、字典。

---

📊 数据结构对比总结

数据结构	插入	删除	查找	适用场景
动态数组	末尾 O(1)	末尾 O(1)	随机 O(1)	随机访问多，插入删除少
链表	头 O(1)	头 O(1)	O(n)	频繁插入删除，不关心随机访问
栈	O(1)	O(1)	-	函数调用、括号匹配
队列	O(1)	O(1)	-	BFS、缓冲
二叉搜索树	平均 O(log n)	平均 O(log n)	平均 O(log n)	动态有序集合
堆	O(log n)	O(log n)	O(1)取最值	优先队列、堆排序
并查集	近似 O(1)	-	近似 O(1)	连通性问题
哈希表	平均 O(1)	平均 O(1)	平均 O(1)	键值存储、去重

---

🎯 如何选择数据结构？

• 需要随机访问 → 数组
• 频繁插入/删除 → 链表
• 后进先出 → 栈
• 先进先出 → 队列
• 动态有序集合 → 二叉搜索树（或平衡树）
• 获取最值 → 堆
• 集合合并/查询 → 并查集
• 键值映射 → 哈希表

---

✍️ 课后练习与答案

练习题目

1. 实现一个双向链表的插入、删除、反转操作。
2. 用栈实现一个简单的计算器（支持 + - * / 和括号）。
3. 用循环队列实现一个环形缓冲区。
4. 实现一个二叉搜索树，并输出所有节点的层次遍历结果。
5. 用并查集判断图中是否存在环。
6. 用哈希表统计一篇文章中每个单词出现的次数。

参考答案

1. 双向链表反转

void reverseDList(DNode **head, DNode **tail) {
    DNode *cur = *head;
    while (cur != NULL) {
        DNode *next = cur->next;
        cur->next = cur->prev;
        cur->prev = next;
        cur = next;
    }
    DNode *tmp = *head;
    *head = *tail;
    *tail = tmp;
}

2. 简单计算器（中缀表达式，使用两个栈）

// 此处仅给出核心思路：使用运算符优先级，两个栈（操作数栈和运算符栈）
// 具体实现较长，可参考经典算法。

3. 环形缓冲区

// 循环队列本身就是环形缓冲区，可直接使用前面定义的 Queue。

4. 二叉搜索树层次遍历

// 直接调用 levelOrder 函数即可。

5. 并查集判断环（无向图）

int hasCycle(int edges[][2], int n, int edgeCount) {
    initUF(n);
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        if (find(u) == find(v)) return 1;
        unionSets(u, v);
    }
    return 0;
}

6. 哈希表统计单词

// 读取文章，按空格/标点分割单词，插入哈希表，最后遍历输出计数。

---

🌟 寄语

数据结构是程序员的“兵器库”。熟练掌握它们的实现和应用，能让你在面对不同问题时，迅速选择最合适的工具。C 语言实现数据结构，虽然比高级语言繁琐，但能让你真正理解内存管理、指针操作等底层细节，这对你的编程生涯大有裨益。

至此，本系列九篇文章已经涵盖了排序、搜索、图论、动态规划、贪心、分治、字符串、数学、数据结构等核心内容。希望你能坚持动手实践，将这些知识内化为自己的技能。

算法之路，道阻且长，行则将至。 愿你在编程的世界里不断探索，越走越远！

---

如果这个系列对你有帮助，欢迎分享给更多朋友。
有任何问题或建议，欢迎评论区交流！