什么是数据结构与算法

写程序时，你几乎总在做两件事：

1. 把数据放在某个地方（内存布局、容器选择）
2. 按某种步骤处理这些数据（查找、插入、排序、最短路径……）

前者对应数据结构，后者对应算法。二者合在一起，决定程序能不能在合理时间内跑完、内存会不会爆、代码好不好维护。

本文解决什么问题

帮你建立三件事：

• 数据结构与算法各自管什么
• 为什么必须一起学
• 本教程怎么读、会用到哪些 C / C++ 基础

用一个例子建立直觉

假设要在通讯录里找「张三」：

组织方式	查找办法	直觉代价
名字写在一张无序纸上	从上到下逐个看	人多就慢，约 $O(n)$
按拼音排好的名册	跳着翻（二分）	约 $O(\log n)$
App 里按姓名建索引	直接定位	平均接近 $O(1)$

同是「找人」，数据组织方式不同，可用的算法也不同，快慢差很多。这就是二者总要一起学的原因。

开发者视角

选型很少是「只选一个容器」。更常见的是：业务操作集合（插入？按键查？按序遍历？）→ 候选结构 → 用复杂度与实现成本拍板。

数据结构解决什么问题

数据结构回答：

• 元素之间有什么关系？（前后相邻？父子？任意连通？）
• 支持哪些操作？（随机访问、头尾插入、按键查找……）
• 这些操作的代价大概是多少？

常见大类：

类别	代表	直觉
线性结构	数组、链表、栈、队列	元素排成一条线
树形结构	二叉树、堆、并查集	一对多的层次 / 集合关系
图形结构	图	多对多的任意连接
散列结构	哈希表	用「算出来的位置」快速定位

逻辑结构 vs 存储结构

教材常区分两层，写代码时也很有用：

• 逻辑结构：数据之间的抽象关系（线性、树、图……）
• 存储结构（物理结构）：在内存里怎么落地（顺序存放、链式存放、索引、散列……）

同一逻辑结构可以有多种存储。例如「线性表」既可以是数组（顺序表），也可以是链表。

抽象数据类型（ADT）

ADT 描述「有哪些数据 + 允许哪些操作」，先不绑定具体实现。例如栈的 ADT 大致是：

• 数据：元素的线性序列
• 操作：push / pop / top / empty……

先想清 ADT，再选数组或链表实现，不容易在细节里迷路。C++ STL 的 std::stack、std::queue 等，本质上就是常用 ADT 的现成封装。

算法解决什么问题

算法是有穷、确定、可执行的解题步骤。同一问题往往有多种算法：

• 排序：冒泡、插入、归并、快速排序……
• 查找：顺序查找、二分查找、哈希查找……
• 图：DFS、BFS、最短路径、最小生成树……

评价时先抓两件事：

1. 对不对：结果是否符合题意（边界、空输入、重复元素……）
2. 好不好：时间与额外内存随输入规模如何增长（见 复杂度分析）

正确性优先于炫技。一个 $O(n^2)$ 但写对的版本，常常比一个「自以为 $O(n)$」却有坑的版本更有价值——尤其在你还要用它给优化版做对照时。

本教程的地图

章节	你将建立的能力
概述	概念、复杂度、递归
基本算法设计思想	蛮力 / 分治 / 减治 / 贪心 / 动态规划
线性表 → 栈队列 → 串数组	最常用的基础结构
树 → 图	层次与网络关系
查找 → 排序	高频算法专题

建议按侧边栏顺序读：后面的结构会反复用到前面的复杂度与设计思想。

C 和 C++ 在本教程中的角色

• C：用结构体、指针、数组把结构「拆开」看清楚，适合理解内存与指针关系
• C++：可用类封装；并在合适位置对照 STL（如 std::vector、std::deque、std::map），方便写工程代码

本教程示例以「能看懂、能改、能跑通核心逻辑」为优先，不会一上来堆完整工业级实现（异常安全、分配器、并发等）。

前置基础

你需要会写简单的 C 或 C++：变量、数组、指针、函数、结构体。若不熟，可先阅读站内 C 语言教程。

怎么自学这套教程

1. 每篇先弄清：解决什么问题、支持什么操作、复杂度如何
2. 自己敲一遍核心代码，改输入验证边界
3. 能口述「为什么选这个结构 / 算法」再进入下一篇
4. 把蛮力版留着，作为正确性基准

小结

• 数据结构 = 数据的组织方式与操作集合
• 算法 = 解决问题的步骤
• 选型是「结构 + 算法」一起决定性能与复杂度

下一篇学习用 复杂度分析 描述「快慢」与「费内存」。