C语言数据结构是计算机科学的基石。理解数据在内存中如何组织，以及如何高效地操作它们，是写出高性能程序的关键。
下面我将由浅入深，为你系统性地讲解C语言中的核心数据结构，并配上代码示例。
第一部分：预备知识
在开始之前，有几个C语言的核心概念需要先掌握，它们是实现数据结构的基础：
- 指针：数据结构的“粘合剂”。通过指针，我们可以在内存中动态地连接不同块的数据（如链表）。
- 动态内存分配：malloc(), calloc(), realloc(), free()。这些函数允许我们在程序运行时（堆上）按需创建和销毁数据，而不是在编译时（栈上）固定大小。
- 结构体（struct）：用于将不同类型的数据（如 int 和 char*）组合成一个新的自定义数据类型，用来表示数据结构的节点。
第二部分：线性数据结构
线性结构的特点是数据元素之间存在一对一的线性关系。
- 数组（Array）
这是最基础、最紧凑的数据结构，在内存中占据连续的空间。
• 优点：访问速度快（O(1)时间复杂度），可通过下标直接操作。
• 缺点：大小固定（静态数组），插入和删除操作效率低（需要移动大量元素）。
• 实现：
c
#include <stdio.h>
int main() {
int arr[5] = {1, 2, 3, 4, 5}; // 静态声明
arr[2] = 10; // 直接访问
printf(“%d\n”, arr[2]);
return 0;
} - 链表（Linked List）
为了解决数组大小固定和插入删除成本高的问题，链表诞生了。它由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。
• 优点：动态大小，插入和删除操作高效（只需修改指针）。
• 缺点：无法随机访问，查找需要遍历（O(n)时间复杂度），且需要额外的指针存储空间。
• 实现（单链表节点）：
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(“内存分配失败\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;
}
3. 栈（Stack）
一种后进先出（LIFO，Last In First Out）的数据结构，就像一叠盘子，只能从顶部取放。
• 核心操作：push（压入）、pop（弹出）、peek（查看栈顶）。
• 应用：函数调用栈、表达式求值、撤销操作。
• 实现方式：既可以用数组（顺序栈，简单快速），也可以用链表（链式栈，大小不限）。
4. 队列（Queue）
一种先进先出（FIFO，First In First Out）的数据结构，就像排队买票，先来的人先服务。
• 核心操作：enqueue（入队，从队尾添加）、dequeue（出队，从队首移除）。
• 应用：任务调度、消息队列、广度优先搜索（BFS）。
• 实现方式：通常使用链表实现，或使用“循环数组”来避免顺序队列的假溢出问题。
第三部分：树形数据结构
树形结构具有分层特性，数据元素之间存在一对多的关系。
- 二叉树（Binary Tree）
每个节点最多有两个子节点（左孩子和右孩子），是最重要的树形结构。
• 关键概念：根节点、叶子节点、深度、前/中/后序遍历。
• 代码（节点定义与中序遍历）：
c
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 中序遍历：左 -> 根 -> 右
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
2. 二叉搜索树（BST，Binary Search Tree）
一种特殊的二叉树，它满足：左子树所有节点的值 < 根节点的值 < 右子树所有节点的值。
• 优点：查找、插入、删除的平均时间复杂度为 O(log n)。
• 缺点：在最坏情况下（如插入有序数据）会退化成链表，复杂度变为 O(n)。
3. 平衡二叉树与堆
• AVL树 / 红黑树：为了解决BST退化问题而设计的自平衡二叉搜索树，保证查找效率稳定在 O(log n)。（C++ STL 中的 std::map 就是红黑树）。
• 堆（Heap）：一种特殊的完全二叉树。大顶堆的根节点是最大值，小顶堆的根节点是最小值。它常被用作实现优先队列，堆排序的时间复杂度为 O(n log n)。
第四部分：散列（Hash）与图
- 哈希表（Hash Table）
哈希表通过哈希函数将键（Key）映射到数组中的某个位置，从而实现极快的存取。
• 优点：查找、插入、删除的平均时间复杂度为 O(1)。
• 缺点：数据无序，且需要处理哈希冲突（两个不同键映射到同一位置）。
• 解决冲突的方法：链地址法（同一位置的元素用链表存储）和开放地址法（向后探测空位）。
• 应用：数据库索引、缓存系统（Redis）。 - 图（Graph）
图用于表示多对多的网络关系，由顶点（Vertex）和边（Edge）组成。
• 存储方式：
o 邻接矩阵：使用二维数组，直观但浪费空间（适合稠密图）。
o 邻接表：使用数组+链表，节省空间（适合稀疏图，也是主流方式）。
• 核心算法：
o 深度优先搜索（DFS，Depth-First Search）：借助栈（或递归）实现。
o 广度优先搜索（BFS，Breadth-First Search）：借助队列实现。
o 最短路径：Dijkstra算法、Floyd算法。
第五部分：如何选择数据结构？
在实际开发中，没有“最好”的数据结构，只有“最合适”的。你可以参考这个决策流程：
- 需要频繁通过下标访问吗？ -> 用数组。
- 大小动态变化，且频繁在中间插入/删除？ -> 用链表。
- 需要“后进先出”处理数据？ -> 用栈。
- 需要“先进先出”处理数据？ -> 用队列。
- 需要快速查找（且数据有序）？ -> 用二叉搜索树。
- 需要近乎瞬间的查找（按键取值）？ -> 用哈希表。
- 需要处理复杂的关系网络（如地图导航）？ -> 用图。
总结与进阶建议
- 纸上画图：在学习链表、树等结构时，建议先在纸上画出节点和指针的连接关系，再对照着写代码，会清晰很多。
- 画内存图：理解 malloc 在堆上分配的空间，以及指针变量在栈上存储的地址，这是理解数据结构的关键。
- 重视边界条件：在实现时，一定要重点思考空指针（NULL）、空表、表头和表尾等特殊情况的处理。
- 学习路线：如果刚开始学习，可以按照数组 -> 链表 -> 栈与队列 -> 树 -> 哈希表 -> 图这个顺序来逐步深入。
数据结构的学习需要大量的编码练习。如果你对上面某个具体结构（比如二叉树的非递归遍历、哈希表的完整实现）感兴趣，或者想看看完整的代码示例，可以告诉我，我们可以深入聊聊。祝你学习顺利！😊
