在编程世界中，数据结构是构建高效程序的基石。无论是日常开发中的数据存储，还是算法题中的逻辑实现，掌握核心数据结构及其 C 语言实现都至关重要。本文将从线性表（顺序表、链表）入手，逐步深入栈、队列，最终聚焦二叉树与堆，结合完整代码实现与实战场景，带大家从零到一掌握这些核心数据结构。
一、线性表：数据结构的基础
线性表是 n 个具有相同特性的数据元素的有限序列，逻辑上呈线性结构，物理存储分为连续（数组）和非连续（链式）两种形式，是栈、队列等复杂结构的基础。
1.1 顺序表：数组的封装与优化
1.1.1 核心概念
顺序表是用物理地址连续的存储单元存储数据的线性结构，底层基于数组实现，封装了增删改查等常用接口，解决了原生数组灵活性不足的问题。类比来看，数组就像 "炒西蓝花"，而顺序表则是 "绿野仙踪"—— 在基础食材上增加了规范化的处理流程。
1.1.2 分类与缺陷
- 静态顺序表：使用定长数组存储，缺陷明显：空间给少了不够用，给多了造成浪费。
// 静态顺序表 typedef int SLDataType; #define N 7 typedef struct SeqList { SLDataType a[N]; // 定长数组 int size; // 有效数据个数 } SL;- 动态顺序表：按需申请空间，通过
capacity记录容量，size记录有效数据个数，支持动态扩容。
// 动态顺序表 typedef int SLDataType; #define INIT_CAPACITY 4 typedef struct SeqList { SLDataType* a; // 动态数组指针 int size; // 有效数据个数 int capacity; // 空间容量 } SL;1.1.3 核心接口实现
动态顺序表的关键在于扩容机制和高效的增删改查，以下是核心接口的完整实现：
// SeqList.h 头文件声明 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int SLDataType; #define INIT_CAPACITY 4 typedef struct SeqList { SLDataType* a; int size; int capacity; } SL; // 初始化和销毁 void SLInit(SL* ps); void SLDestroy(SL* ps); void SLPrint(SL* ps); // 扩容 void SLCheckCapacity(SL* ps); // 头部/尾部插入删除 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); // 指定位置插入/删除 void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x); // SeqList.c 实现 void SLInit(SL* ps) { assert(ps); ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (ps->a == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); } ps->size = 0; ps->capacity = INIT_CAPACITY; } void SLDestroy(SL* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } void SLCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { // 扩容为原来的2倍 SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); exit(EXIT_FAILURE); } ps->a = tmp; ps->capacity *= 2; } } // 尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); ps->a[ps->size++] = x; } // 尾删 void SLPopBack(SL* ps) { assert(ps && ps->size > 0); ps->size--; } // 头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); // 数据后移 for (int i = ps->size; i > 0; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; ps->size++; } // 头删 void SLPopFront(SL* ps) { assert(ps && ps->size > 0); // 数据前移 for (int i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } // 按位置插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); // 从pos位置开始后移 for (int i = ps->size; i > pos; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[pos] = x; ps->size++; } // 按位置删除 void SLErase(SL* ps, int pos) { assert(ps && ps->size > 0); assert(pos >= 0 && pos < ps->size); // 从pos+1位置开始前移 for (int i = pos; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } // 查找元素 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; // 未找到 }1.1.4 优缺点分析
- 优点：支持随机访问（O (1) 时间复杂度），尾插尾删效率高。
- 缺点：中间 / 头部插入删除需移动元素（O (N) 时间复杂度）；扩容存在空间浪费和拷贝开销。
1.2 链表：非连续存储的灵活选择
1.2.1 核心概念
链表是物理存储非连续、逻辑连续的线性结构，通过指针链接结点实现数据访问。每个结点包含数据域和指针域，类比火车车厢 —— 每节车厢独立存在，通过挂钩连接。
1.2.2 单链表结构与实现
单链表是最基础的链表结构，每个结点仅存储下一个结点的地址，以下是完整实现：
// SList.h 头文件声明 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int SLTDataType; // 单链表结点结构 typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* next; // 指针域，指向next结点 } SLTNode; // 打印链表 void SLTPrint(SLTNode* phead); // 头部/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopFront(SLTNode** pphead); // 查找结点 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 指定位置插入/删除 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); void SLTErase(SLTNode** pphead, SLTNode* pos); // 销毁链表 void SListDestroy(SLTNode** pphead); // SList.c 实现 // 创建新结点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); } newnode->data = x; newnode->next = NULL; return newnode; } // 打印链表 void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur) { printf("%d ", pcur->data); pcur = pcur->next; } printf("\n"); } // 尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { // 空链表 *pphead = newnode; return; } // 找到尾结点 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; } // 尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); // 只有一个结点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } // 找到倒数第二个结点 SLTNode* prev = NULL; SLTNode* ptail = *pphead; while (ptail->next) { prev = ptail; ptail = ptail->next; } free(ptail); prev->next = NULL; } // 头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; } // 头删 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); tmp = NULL; } // 查找结点 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; // 未找到 } // 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* tmp = pcur; pcur = pcur->next; free(tmp); } *pphead = NULL; }1.2.3 链表 vs 顺序表：核心对比
| 对比维度 | 顺序表 | 链表（单链表） |
|---|---|---|
| 存储空间 | 物理连续 | 逻辑连续，物理非连续 |
| 随机访问 | 支持（O (1)） | 不支持（O (N)） |
| 插入删除 | 中间 / 头部 O (N) | 仅需修改指针（O (1)） |
| 空间效率 | 可能存在扩容浪费 | 按需申请，无浪费 |
| 应用场景 | 频繁访问，少量增删 | 频繁增删，少量访问 |
二、栈与队列：受限的线性表
栈和队列是特殊的线性表，其操作受到限制，分别遵循 "后进先出" 和 "先进先出" 原则，广泛应用于算法优化、数据缓冲等场景。
2.1 栈：后进先出（LIFO）
2.1.1 核心概念
栈仅允许在栈顶进行插入（压栈）和删除（出栈）操作，类比叠盘子 —— 最后放的盘子最先被拿走。栈的实现优先选择数组，因为数组尾插尾删效率高。
2.1.2 完整实现
// stack.h 头文件声明 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; // 数组存储 int top; // 栈顶指针（指向栈顶元素下一个位置） int capacity; // 容量 } ST; // 初始化栈 void STInit(ST* ps); // 销毁栈 void STDestroy(ST* ps); // 入栈 void STPush(ST* ps, STDataType x); // 出栈 void STPop(ST* ps); // 取栈顶元素 STDataType STTop(ST* ps); // 获取栈大小 int STSize(ST* ps); // 判断栈是否为空 bool STEmpty(ST* ps); // stack.c 实现 void STInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); } ps->top = 0; ps->capacity = 4; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void STPush(ST* ps, STDataType x) { assert(ps); // 扩容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); exit(EXIT_FAILURE); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top++] = x; } void STPop(ST* ps) { assert(ps && !STEmpty(ps)); ps->top--; } STDataType STTop(ST* ps) { assert(ps && !STEmpty(ps)); return ps->a[ps->top - 1]; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }2.2 队列：先进先出（FIFO）
2.2.1 核心概念
队列允许在队尾插入（入队）、队头删除（出队），类比排队买票 —— 先到的人先买票。队列优先选择链表实现，避免数组头删时的数据移动。
2.2.2 完整实现
// Queue.h 头文件声明 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; // 队列结点 typedef struct QueueNode { QDataType val; struct QueueNode* next; } QNode; // 队列结构（管理队头和队尾） typedef struct Queue { QNode* phead; QNode* ptail; int size; } Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 入队 void QueuePush(Queue* pq, QDataType x); // 出队 void QueuePop(Queue* pq); // 取队头元素 QDataType QueueFront(Queue* pq); // 取队尾元素 QDataType QueueBack(Queue* pq); // 判断队列是否为空 bool QueueEmpty(Queue* pq); // 获取队列大小 int QueueSize(Queue* pq); // Queue.c 实现 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* tmp = pcur; pcur = pcur->next; free(tmp); } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { // 空队列 pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq && !QueueEmpty(pq)); if (pq->phead->next == NULL) { // 只有一个结点 free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* tmp = pq->phead; pq->phead = pq->phead->next; free(tmp); } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq && !QueueEmpty(pq)); return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq && !QueueEmpty(pq)); return pq->ptail->val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }三、二叉树：非线性数据结构的核心
二叉树是树形结构的核心，每个结点最多有两个子树（左子树、右子树），是非线性数据结构，广泛应用于搜索、排序、文件系统等场景。
3.1 核心概念与结构
- 满二叉树：每一层结点数达到最大值，层数为 k 时结点总数为 2ᵏ-1。
- 完全二叉树：除最后一层外，每一层结点数均满，最后一层结点从左到右连续排列。
- 链式存储：每个结点包含数据域、左指针（指向左子树）、右指针（指向右子树）。
// 二叉树结点结构 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType val; struct BinaryTreeNode* left; // 左子树指针 struct BinaryTreeNode* right; // 右子树指针 } BTNode;3.2 二叉树的遍历
遍历是二叉树操作的基础，分为前序、中序、后序（递归实现）和层序（队列实现）四种方式。
3.2.1 递归遍历实现
// 创建新结点 BTNode* BuyBTNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail"); exit(EXIT_FAILURE); } newnode->val = x; newnode->left = newnode->right = NULL; return newnode; } // 前序遍历：根 -> 左 -> 右 void PreOrder(BTNode* root) { if (root == NULL) { printf("N "); // 用N表示空结点 return; } printf("%d ", root->val); PreOrder(root->left); PreOrder(root->right); } // 中序遍历：左 -> 根 -> 右 void InOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); } // 后序遍历：左 -> 右 -> 根 void PostOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); }3.2.2 层序遍历实现（借助队列）
// 层序遍历：自上而下、自左至右 void LevelOrder(BTNode* root) { if (root == NULL) return; Queue q; QueueInit(&q); QueuePush(&q, root); // 根结点入队 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->val); // 左孩子入队 if (front->left) { QueuePush(&q, front->left); } // 右孩子入队 if (front->right) { QueuePush(&q, front->right); } } QueueDestroy(&q); printf("\n"); }3.3 堆：特殊的完全二叉树
堆是满足 "双亲结点值大于等于（大堆）或小于等于（小堆）子结点值" 的完全二叉树，常用于堆排序和 Top-K 问题。
3.3.1 堆的实现（大堆）
// Heap.h 头文件声明 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; } HP; // 初始化堆 void HPInit(HP* php); // 销毁堆 void HPDestroy(HP* php); // 插入元素 void HPPush(HP* php, HPDataType x); // 删除堆顶元素 void HPPop(HP* php); // 取堆顶元素 HPDataType HPTop(HP* php); // 判断堆是否为空 bool HPEmpty(HP* php); // 获取堆大小 int HPSize(HP* php); // Heap.c 实现 // 交换两个元素 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } // 向上调整（插入元素后维护堆结构） void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { // 大堆：孩子>父亲则交换 Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } else { break; } } } // 向下调整（删除堆顶后维护堆结构） void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; // 左孩子 while (child < n) { // 选择左右孩子中较大的一个 if (child + 1 < n && a[child + 1] > a[child]) { child++; } // 孩子>父亲则交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HPInit(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; } void HPDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; } void HPPush(HP* php, HPDataType x) { assert(php); // 扩容 if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(EXIT_FAILURE); } php->a = tmp; php->capacity = newCapacity; } // 插入到末尾并向上调整 php->a[php->size++] = x; AdjustUp(php->a, php->size - 1); } void HPPop(HP* php) { assert(php && !HPEmpty(php)); // 交换堆顶和最后一个元素 Swap(&php->a[0], &php->a[php->size - 1]); php->size--; // 向下调整堆顶 AdjustDown(php->a, php->size, 0); } HPDataType HPTop(HP* php) { assert(php && !HPEmpty(php)); return php->a[0]; } bool HPEmpty(HP* php) { assert(php); return php->size == 0; } int HPSize(HP* php) { assert(php); return php->size; }3.3.2 堆的应用：Top-K 问题
Top-K 问题是求海量数据中前 K 个最大 / 最小元素，用堆实现效率极高（时间复杂度 O(nlogk)）。
// 求前K个最大元素（用小堆实现） void TopK(int* a, int n, int k) { assert(a && n > 0 && k > 0 && k <= n); HP hp; HPInit(&hp); // 用前k个元素建小堆 for (int i = 0; i < k; i++) { HPPush(&hp, a[i]); } // 剩余元素与堆顶比较，大于堆顶则替换并调整 for (int i = k; i < n; i++) { if (a[i] > HPTop(&hp)) { hp.a[0] = a[i]; AdjustDown(hp.a, hp.size, 0); } } // 输出结果 printf("前K个最大元素："); while (!HPEmpty(&hp)) { printf("%d ", HPTop(&hp)); HPPop(&hp); } printf("\n"); HPDestroy(&hp); }四、实战演练：经典算法题
4.1 顺序表算法题：移除元素（LeetCode 27）
int removeElement(int* nums, int numsSize, int val) { int dest = 0; for (int src = 0; src < numsSize; src++) { if (nums[src] != val) { nums[dest++] = nums[src]; } } return dest; }4.2 链表算法题：反转链表（LeetCode 206）
BTNode* reverseList(BTNode* head) { BTNode* prev = NULL; BTNode* cur = head; while (cur) { BTNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }4.3 栈算法题：有效的括号（LeetCode 20）
bool isValid(char* s) { ST st; STInit(&st); while (*s != '\0') { if (*s == '(' || *s == '[' || *s == '{') { STPush(&st, *s); } else { if (STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); STPop(&st); if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{')) { STDestroy(&st); return false; } } s++; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }
