数据结构基本概念
在正式学习各种数据结构之前，需要先掌握数据结构的分类方式、抽象数据类型的概念，并回顾 C 语言中与数据结构密切相关的核心知识点。
数据结构的分类
数据结构可以从两个维度进行分类：逻辑结构和存储方式。理解这两种分类方式，有助于在面对具体问题时快速判断应该选择哪一类数据结构。
上图展示了数据结构的完整分类体系，下面逐一说明。
按逻辑结构分类
逻辑结构描述的是数据元素之间的抽象关系，不涉及数据在内存中的实际存储方式。
| 类型 | 元素关系 | 典型例子 | 适用场景 |
|---|---|---|---|
| 线性结构 | 一对一的前后关系 | 数组、链表、栈、队列 | 数据有明显先后顺序，如待办事项列表、浏览历史 |
| 树形结构 | 一对多的层级关系 | 二叉树、BST、堆 | 数据有层级归属，如文件系统目录、组织架构 |
| 图形结构 | 多对多的网状关系 | 有向图、无向图、带权图 | 数据间关系复杂，如社交网络、地图导航 |
按存储方式分类
存储方式描述的是数据在内存中的实际组织方式。
| 类型 | 特点 | 典型例子 | 权衡 |
|---|---|---|---|
| 顺序存储 | 元素在连续的内存空间中依次存放 | 数组、用数组实现的栈/队列 | 访问快 (O(1))，但插入删除慢，大小固定 |
| 链式存储 | 元素可以分散存放，通过指针连接 | 链表、树、图（邻接表） | 插入删除快，但不支持随机访问，额外指针开销 |
| 索引存储 | 建立附加的索引表来定位数据 | 哈希表（通过哈希函数索引） | 查找极快，但需要额外空间存储索引结构 |
同一种逻辑结构可以用不同的存储方式来实现。例如，栈（逻辑上是线性结构）既可以用数组（顺序存储）实现，也可以用链表（链式存储）实现。选择哪种实现方式取决于具体应用场景对访问速度、增删效率和内存占用的不同要求。
抽象数据类型（ADT）
抽象数据类型（Abstract Data Type，简称 ADT）是数据结构学习中的一个核心概念。
它是指一组数据以及定义在这组数据上的一组操作的抽象描述，只关心"做什么"，不关心"怎么做"。
以"栈"为例来理解 ADT：
| ADT 层面（做什么） | 实现层面（怎么做） |
|---|---|
| 定义操作：push（入栈）、pop（出栈）、peek（查看栈顶） | 用数组实现：维护一个数组 + top 指针 |
| 定义行为：后进先出 (LIFO) | 用链表实现：以链表头作为栈顶 |
| 规定约束：只能从一端操作 | 两种实现都满足 ADT 定义，但性能特性不同 |
这种"接口与实现分离"的思想，是现代软件工程中模块化设计的基石。
当你使用一个栈时，只需要知道 push、pop 等操作的用法，而不需要关心底层是用数组还是链表实现的——这正是 ADT 的价值所在。
C 语言基础知识回顾
在学习数据结构之前，需要熟练掌握以下三个 C 语言核心知识点，它们几乎贯穿本教程所有章节。
指针（Pointer）
指针是 C 语言中最重要也最灵活的特性之一。它存储的是另一个变量的内存地址，通过指针可以间接访问和操作目标变量。
实例
int main() {
int num = 42; /* 普通整型变量 */
int *ptr = # /* ptr 是指向 int 的指针，存储 num 的地址 */
printf("num 的值: %d\n", num); /* 输出: 42 */
printf("num 的地址: %p\n", &num); /* 输出: 0x16d2f2f38（示例地址） */
printf("ptr 存储的地址: %p\n", ptr); /* 输出: 同上 */
printf("*ptr 解引用的值: %d\n", *ptr); /* 输出: 42，* 为解引用运算符 */
*ptr = 100; /* 通过指针修改 num 的值 */
printf("修改后 num = %d\n", num); /* 输出: 100 */
return 0;
}
指针在数据结构中的核心用途：
| 用途 | 示例 |
|---|---|
| 构建动态节点间的连接 | 链表节点中的 next 指针、树节点中的 left/right 指针 |
| 间接访问和修改数据 | 通过指针参数让函数修改外部变量的值 |
| 动态内存管理 | malloc 返回分配内存的起始地址，必须用指针接收 |
| 避免大量数据拷贝 | 函数传递大型结构体时，传指针比传值更高效 |
初学者最容易混淆的是
*和&的用法：声明时int *p表示 p 是指针类型；使用时*p表示解引用（取值）；&x表示取地址。这是两个完全不同的运算符，理解这个区别是用好指针的前提。
结构体（struct）
结构体允许将多个不同类型的数据组合成一个自定义类型，是构建链表节点、树节点等复合数据结构的基本单元。
实例
#include <string.h> /* strcpy 函数所在头文件 */
/* 定义链表节点结构体 */
struct Node {
int data; /* 数据域：存储实际数据 */
struct Node* next; /* 指针域：指向下一个节点 */
};
/* 定义学生信息结构体 */
struct Student {
int id; /* 学号 */
char name[50]; /* 姓名，字符数组 */
float score; /* 成绩 */
};
int main() {
/* 创建节点 */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL 表示当前没有后续节点 */
printf("node1.data = %d\n", node1.data); /* 输出: 10 */
/* 创建学生记录 */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "RUNOOB"); /* strcpy：将字符串复制到字符数组 */
stu.score = 95.5;
printf("学号: %d, 姓名: %s, 成绩: %.1f\n",
stu.id, stu.name, stu.score);
/* 输出: 学号: 1001, 姓名: RUNOOB, 成绩: 95.5 */
return 0;
}
结构体配合指针可以实现灵活的动态数据结构。例如，链表节点的自引用结构（struct Node* next 指向同类型的下一个节点）正是链表的实现基础。
动态内存分配
动态内存分配允许程序在运行时根据需要申请和释放堆内存，是构建大小可变的数据结构（如链表、树）的关键。
C 语言提供了四个核心函数：
| 函数 | 功能 | 示例 |
|---|---|---|
| malloc | 分配指定字节数的内存，内容未初始化 | int* p = malloc(10 * sizeof(int)); |
| calloc | 分配内存并初始化为零 | int* p = calloc(10, sizeof(int)); |
| realloc | 调整已分配内存的大小 | p = realloc(p, 20 * sizeof(int)); |
| free | 释放已分配的内存，归还给系统 | free(p); |
实例
#include <stdlib.h> /* malloc, free 所在的头文件 */
int main() {
int n = 5;
/* malloc: 在堆上分配 n 个 int 的连续空间 */
int* arr = (int*)malloc(n * sizeof(int));
/* 检查分配是否成功，malloc 失败时返回 NULL */
if (arr == NULL) {
printf("内存分配失败！\n");
return 1; /* 异常退出 */
}
/* 像普通数组一样使用动态分配的内存 */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* 赋值: 10, 20, 30, 40, 50 */
}
printf("动态数组内容: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* 输出: 动态数组内容: 10 20 30 40 50 */
free(arr); /* 释放内存，防止内存泄漏 */
arr = NULL; /* 好习惯：将指针置为 NULL，防止野指针 */
return 0;
}
C 语言不会自动回收动态分配的内存。每次
malloc（或calloc）都必须有对应的free，否则会导致内存泄漏。在实际项目中，内存泄漏会逐渐耗尽系统资源，最终导致程序崩溃。这是 C 语言初学者最容易犯的错误之一。