作为程序员，我们每天都在与数据打交道。你是否想过，为什么有些程序处理海量数据时依然飞快，而有些程序却随着数据量增加变得步履蹒跚？答案往往在于我们如何组织和存储这些数据。这就是我们今天要深入探讨的核心主题——数据结构。
在这篇技术笔记中，我们将以 C 语言为工具，一起重温并优化那些最基础、最重要的数据结构概念。无论你是正在准备技术面试，还是希望在日常编码中写出更高效的代码，这篇文章都将为你提供从理论到实践的全面视角。我们将探索数组的内存布局、栈的函数调用机制、链表的动态灵活性，以及更复杂的树与图结构。
数据结构本质上就是一套用来组织和存储数据的“容器”，目的是让我们能够高效地访问和修改这些数据。我们可以将它们大致分为两类：线性数据结构（如数组、栈、队列、链表）和非线性数据结构（如树、图）。让我们从最基础的开始，一点点揭开它们的神秘面纱。
目录
Arrays (数组)：内存中的连续布局
数组是最基本也是最重要的数据结构。想象一下，就像是一排紧挨着的储物柜，我们在内存中开辟了一块连续的区域来存储相同类型的数据。
为什么选择数组？
数组最大的优势在于随机访问的能力。因为内存是连续的，只要我们知道数组的起始地址（基地址）和每个元素的大小，我们就可以通过数学公式瞬间计算出第 N 个元素的地址，而不需要从头开始遍历。这就是数组访问速度快的原因，时间复杂度为 O(1)。
数组的声明与初始化实战
在 C 语言中，声明数组的方式非常灵活。让我们通过代码来看看几种常见的场景：
#include
int main() {
// 场景 1：指定大小。声明一个能装 10 个整数的数组
// 此时内存已分配，但内容可能是未初始化的垃圾值
int arr[10];
// 场景 2：指定初始化列表。编译器会自动根据元素个数推断数组大小
int counts[] = {10, 20, 30, 40};
// 场景 3：指定大小并初始化（推荐做法，清晰明了）
// 这里声明了一个大小为 6 的数组，但只初始化了前 4 个
// 在 C 语言中，未初始化的部分会自动被设置为 0
int primes[6] = {2, 3, 5, 7};
// 访问和修改元素
arr[0] = 100; // 将第一个元素赋值为 100
printf("第一个元素是: %d
", counts[0]); // 输出 10
printf("primes 的第 5 个元素 (未初始化): %d
", primes[4]); // 输出 0
return 0;
}
内存地址计算公式（核心技术点）
理解数组在内存中是如何存放的，是理解指针和数组下标的关键。
假设我们有一个数组 INLINECODE8090b9b9，INLINECODE715cd077 是下限（通常为 0），UB 是上限。计算数组长度很简单：
> Length = UB – LB + 1
如果要计算某个元素的内存地址，公式如下：
> Address(Loc(arr[k])) = Base_Address + w * k
- Base_Address: 数组的起始地址。
- w: 数据类型的大小（例如
int通常是 4 字节）。 - k: 索引下标。
多维数组的寻址：
当我们处理二维数组（矩阵）时，情况稍微复杂一点，取决于数据是按行还是按列存储（C 语言默认是按行主序）。
对于一个 INLINECODE1765be88 行 INLINECODE68fe4aa6 列的数组 INLINECODEfc284439，计算 INLINECODEa34a5706 的地址：
- 按行主序:
Address = Base + w * (n * i + j)
解释*：先跳过 INLINECODE6d1cafb1 个完整的行（每行有 INLINECODE47bb57b4 个元素），再移动 j 列。
- 按列主序:
Address = Base + w * (m * j + i)
解释*：这是 Fortran 等语言的方式，先跳过 j 个完整的列。
常见操作与性能陷阱
- 遍历：最基本的操作，利用循环结构。
for(int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
- 插入与删除：这是数组的弱项。
如果你想在数组中间插入一个元素，你必须先将其后的所有元素都向后移动一位，以腾出空间。这导致最坏情况下的时间复杂度为 O(n)。同样，删除元素也需要填补空缺。
> 实战建议：如果频繁需要在中间插入或删除数据，请考虑后续我们会讲到的链表结构。
- 搜索：
* 线性搜索: 逐个检查，O(n)。
* 二分查找: 如果数组是有序的，我们可以利用二分查找将效率提升至 O(log n)。
—
Stacks (栈)：LIFO 的艺术
栈是一种遵循后进先出 原则的线性数据结构。想象一摞盘子，你只能把新盘子放在最上面（入栈），也只能从最上面拿走盘子（出栈）。
栈的应用场景
在编程中，栈无处不在：
- 函数调用管理：每当一个函数被调用，它的局部变量和返回地址都会被“压”入栈帧；函数结束时，栈帧“弹出”。这就是为什么递归过深会导致“栈溢出”。
- 撤销操作：编辑器中的 Ctrl+Z 通常就是用栈来记录历史状态。
- 表达式求值：编译器如何计算
3 + 4 * 5？栈起到了决定性作用。
栈的基本操作代码实现
让我们定义一个简单的栈结构，并实现其核心功能：
#include
#include
#include
#define MAX 100
typedef struct {
int items[MAX];
int top;
} Stack;
// 初始化栈
void initialize(Stack *s) {
s->top = -1;
}
// 检查是否为空
bool isEmpty(Stack *s) {
return s->top == -1;
}
// 检查是否已满
bool isFull(Stack *s) {
return s->top == MAX - 1;
}
// Push (入栈) - 时间复杂度 O(1)
void push(Stack *s, int value) {
if (isFull(s)) {
printf("栈溢出！无法添加 %d
", value);
return;
}
s->items[++(s->top)] = value; // 先移动指针，再存值
printf("入栈: %d
", value);
}
// Pop (出栈) - 时间复杂度 O(1)
int pop(Stack *s) {
if (isEmpty(s)) {
printf("栈下溢！栈为空。
");
return -1;
}
return s->items[(s->top)--]; // 先取值，再移动指针
}
// Peek (窥视栈顶) - 时间复杂度 O(1)
int peek(Stack *s) {
if (isEmpty(s)) {
printf("栈为空。
");
return -1;
}
return s->items[s->top];
}
表达式表示法：中缀、前缀与后缀
在计算机科学中，理解这三种表示法对于编写编译器或计算器至关重要。
- 中缀: 我们习惯的写法，操作符在中间。例如
A + B。 - 后缀 (Reverse Polish Notation): 操作符在后面。
A B +。
* 优点：不需要括号，计算机处理起来非常高效，因为不需要优先级判断，直接用栈处理即可。
* 例子: INLINECODE164735cf 转换为 INLINECODE00d9cf8b。
- 前缀: 操作符在前面。
+ A B。
* 例子: INLINECODEafc6d348 转换为 INLINECODE15fd235c。
> 实战技巧：面试中常考“中缀转后缀”。你可以使用一个栈来暂存操作符：遇到数字直接输出，遇到操作符则与栈顶操作符比较优先级，决定是弹出还是压入。
—
Linked Lists (链表)：动态内存的王者
如果说数组是静态的、刚性的，那么链表就是动态的、灵活的。链表中的元素在内存中不需要连续存放。每个元素（节点）包含两部分：数据本身和指向下一个节点的指针。
为什么要用链表？
- 大小动态：不需要预先分配固定大小，内存按需分配。
- 高效的插入/删除：在已知位置插入或删除节点只需要修改指针，不需要移动大量数据（时间复杂度 O(1)，忽略查找时间）。
单向链表的基础实现
让我们用 C 语言构建一个链表节点，并演示如何插入数据：
#include
#include
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 在链表头部插入节点 (时间复杂度 O(1))
Node* insertAtHead(Node* head, int value) {
// 1. 创建新节点并分配内存
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败
");
return head;
}
newNode->data = value;
// 2. 让新节点指向原来的头节点
newNode->next = head;
// 3. 更新头指针指向新节点
head = newNode;
return head;
}
// 遍历打印链表
void printList(Node* head) {
Node* current = head;
printf("链表内容: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL
");
}
链表的常见陷阱与技巧
- 内存泄漏：链表最大的敌人。当你删除一个节点时，一定要记得
free()掉它，否则内存会越用越少。 - 指针丢失：在插入或删除操作时，一定要注意操作的顺序。如果你先断开了
A -> B的连接，还没把新节点连上，你就找不到后面的链表了！ - 快慢指针法：这是解决链表面试题的利器。例如，要找到链表的中间节点，不需要遍历两遍。你可以设置两个指针，快指针每次走两步，慢指针每次走一步。当快指针到达终点时，慢指针正好在中间。
—
Tree (树)：分层数据的艺术
当我们需要处理具有层级关系的数据（如文件系统、HTML DOM 结构、组织架构图）时，树结构是最佳选择。其中，二叉树 是最常用的形式，每个节点最多有两个子节点：左孩子和右孩子。
二叉树的遍历
理解树的遍历是处理树形结构的基础。我们可以按照根节点访问的顺序分为三种方式：
- 前序遍历: 根 -> 左 -> 右。常用于复制树结构。
- 中序遍历: 左 -> 根 -> 右。在二叉搜索树 (BST) 中，这会输出有序的序列。
- 后序遍历: 左 -> 右 -> 根。常用于删除树（先删孩子，再删父节点）或计算表达式。
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 前序遍历示例
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val); // 访问根
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
> 实战见解：面试中常考的“二叉搜索树 (BST)” 就是左子节点 < 根节点 < 右子节点的树。在 BST 中查找元素的时间复杂度类似于二分查找，平均为 O(log n)，但如果树退化为链表（斜树），则退化为 O(n)。这就引出了平衡树（如 AVL 树）的重要性。
—
Graphs (图)：复杂网络的建模
图是比树更一般化的数据结构。图由顶点（节点）和边组成。边可以是单向的（有向图）或双向的（无向图），甚至可以带有权重（权重图）。
图的表示方法
- 邻接矩阵：使用二维数组
matrix[i][j]表示节点 i 和 j 是否相连。
优点*：O(1) 时间判断两点是否相连。
缺点*：对于稀疏图（边很少），会浪费大量空间。
- 邻接表：使用数组和链表的组合。数组索引代表节点，每个数组元素指向一个链表，里面存储着与该节点相连的所有邻居。
优点*：节省空间，表示稀疏图的标准方式。
图的搜索算法
- 广度优先搜索 (BFS)：像水波纹一样层层向外扩散。使用队列实现。常用于找无权图的最短路径。
- 深度优先搜索 (DFS)：一条路走到黑，碰壁再回头。使用栈（或递归调用栈）实现。常用于拓扑排序或检测环。
—
Hashing (哈希)：极速查找
如果我们想在 O(1) 的时间内找到数据，哈希表是首选。
原理
哈希函数将键值映射到数组的某个索引。Hash(key) -> Index。
哈希冲突
当两个不同的键被映射到同一个索引时，就发生了冲突。解决冲突的常用方法：
- 链地址法：每个数组槽位存放一个链表。如果冲突，就挂在链表的末尾。这是 HashMap 的底层原理。
- 开放寻址法：如果冲突，就寻找下一个空的槽位（线性探测等）。
实际应用
- 数据库索引：虽然 B+ 树更常用，但哈希索引在某些场景下极快。
- 缓存：Redis 等缓存系统大量依赖哈希表。
- 去重：在大数据集中快速判断某个元素是否存在。
—
总结与下一步
我们已经一起快速浏览了计算机科学中最重要的几种数据结构。从连续紧凑的数组，到灵活多变的链表，再到规矩分明的树和错综复杂的图，每一种结构都有其独特的适用场景。
作为开发者，选择正确的数据结构往往比算法本身更重要。如果你需要快速访问，选数组；如果你需要频繁增删，选链表；如果你需要处理层级关系，选树；如果你需要处理网络关系，选图。
接下来的建议：
- 动手实现：不要只看代码，关掉浏览器，自己从头用 C 语言写一遍链表的增删改查，或者手写一个哈希表。你会发现很多细节问题只有在写代码时才能遇到。
- 刷题巩固：找一些经典的 LeetCode 题目，比如“反转链表”、“二叉树的最大深度”或“岛屿数量（图的DFS）”来检验你的理解。
希望这篇笔记能帮助你建立起扎实的知识体系。数据结构的世界深奥而有趣，让我们一起保持好奇心，继续探索吧！