0 基本知识

什么是数据结构

在学习具体的数据结构之前，先理清几个基本概念。这些概念在考试和面试中经常出现，也是理解后续所有章节的基础。

数据

数据是计算机能识别、存储和处理的符号集合。数字、字符、图片、音频——凡是能被计算机处理的东西，都是数据。

数据元素

数据元素是数据的基本单位，在程序中通常作为一个整体进行考虑和处理。一个数据元素可以由多个数据项组成。

举个例子：一个学生记录是一个数据元素，它包含姓名、学号、成绩等多个数据项。

概念	类比	示例
数据	整个通讯录	全班同学的联系方式
数据元素	通讯录中的一条记录	张三的完整信息
数据项	记录中的一个字段	张三的电话号码

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包含两个层面：

逻辑结构：数据元素之间的抽象关系（与存储无关）
物理结构（存储结构）：数据在计算机内存中的实际存储方式

逻辑结构

逻辑结构描述数据元素之间的抽象关系，与计算机如何实现无关。主要分为四大类：

逻辑结构	关系	说明	典型例子
集合结构	元素同属一个集合，无其他关系	最松散的结构	{1, 3, 5, 7}
线性结构	一对一（1:1）	元素排成一条线	[[C_线性表_LinearList
树形结构	一对多（1:N）	层层分支	二叉树、B树、文件系统
图形结构	多对多（M:N）	任意连接	社交网络、地图导航

graph TD
    subgraph 集合结构
        S1((1)) --- S2((3)) --- S3((5)) --- S4((7))
    end
    
    subgraph 线性结构
        L1[1] --> L2[2] --> L3[3] --> L4[4]
    end
    
    subgraph 树形结构
        T1[1] --> T2[2]
        T1 --> T3[3]
        T2 --> T4[4]
        T2 --> T5[5]
        T3 --> T6[6]
    end
    
    subgraph 图形结构
        G1((A)) --- G2((B))
        G1 --- G3((C))
        G2 --- G3
        G2 --- G4((D))
        G3 --- G4
    end

关键区分：逻辑结构关注的是”元素之间有什么关系”，不关心”元素存在哪里”。同一个线性结构，可以用数组存储，也可以用链表存储——这就是逻辑结构和物理结构的分离。线性结构中最基础的抽象是线性表，它的定义与两种实现见线性表与顺序表。

物理结构（存储结构）

物理结构描述数据在计算机内存中的实际存储方式。主要分为两种：

顺序存储

把逻辑上相邻的元素，存储在物理位置也相邻的存储单元中。

内存地址:  1000   1004   1008   1012   1016
存储内容: [  1  ][  2  ][  3  ][  4  ][  5  ]
           ←──── 连续的内存块 ────→

特点：

支持随机访问（按下标取值 O(1)）
插入/删除需要移动大量元素 O(n)
需要预先分配连续空间

典型代表：数组

链式存储

不要求逻辑上相邻的元素在物理位置上也相邻，元素间的逻辑关系通过附加的指针来表示。

内存地址:  1000      2056      1532
存储内容: [ 1 | ●]→[ 2 | ●]→[ 3 | ●]→NULL
           ↑         ↑         ↑
           不连续！靠指针链接

特点：

不支持随机访问（必须从头遍历 O(n)）
插入/删除只需修改指针 O(1)
动态分配，不需要预先知道数据规模

典型代表：链表

对比

维度	顺序存储	链式存储
内存分配	预先分配连续空间	动态分配，按需申请
随机访问	O(1)	O(n)
插入/删除	O(n)（需移动元素）	O(1)（已知位置时）
空间利用	可能浪费（预分配过多）	按需使用，但指针占额外空间
缓存友好	好（连续内存，局部性）	差（节点分散，cache miss）

还有一种散列存储：用哈希函数直接计算元素的存储地址，典型代表是哈希表。它既不是纯粹的顺序存储，也不是链式存储，而是通过数学映射直达目标位置。

数据的运算

无论哪种数据结构，基本运算都可以归纳为以下几类：

运算类型	说明	示例
查找（Search）	在数据结构中找到指定元素	在数组中找值为 5 的元素
插入（Insert）	在数据结构中添加新元素	在链表头插入新节点
删除（Delete）	从数据结构中移除指定元素	删除二叉树的叶节点
修改（Update）	更新指定元素的值	修改数组 arr[3] 的值
遍历（Traverse）	访问数据结构中的每个元素	中序遍历二叉树

内存和地址

计算机运行程序时，所有数据都存在内存（RAM）里。可以把内存想象成一排带编号的小格子，每个格子能存一小块数据，格子的编号就是它的地址（类似宾馆的房间号）。

程序里写的变量名、数组名，对 CPU 来说都不存在——CPU 只认地址。所以理解”数据放在哪、怎么找到它”，是理解一切数据结构的第一步。

数据宽度

一个格子能存多少数据，取决于数据宽度。比如：

char 占 1 字节
int 占 4 字节
double 占 8 字节

数据宽度也叫”元素大小”。后面学数组时你会看到：第 i 个元素的地址 = 起始地址 + i × 数据宽度，这个公式几乎贯穿整个教程。

字节

字节（Byte）是计算机存储的最小单位，1 字节 = 8 个二进制位（bit），能表示 0 ~ 255 的数字。

文件大小里的 KB、MB、GB 都基于字节：1 KB = 1024 字节，1 MB = 1024 KB。记住 $2^{10} = 1024 \approx 1000$ 就够了。

CPU

CPU 是计算机的”大脑”，负责执行指令。它工作时只跟寄存器（CPU 内部的小存储）打交道，而寄存器的数据要从内存读来。CPU 的速度非常快，快得内存跟不上——正是这个速度差距，引出了下面的”缓存”。

这一节不需要深究，只要记住一句话：CPU 读数据是有代价的，从不同地方读，速度差很多倍。

磁盘和存储

磁盘（硬盘/SSD）是”断电后数据还在”的地方。程序不运行时存在磁盘里，运行时要先加载到内存。

类比：内存是办公桌，磁盘是抽屉。拿东西桌面上最快，抽屉里要弯腰，慢得多（慢约十万倍）。所以数据结构的性能讨论，通常只关心内存，不关心磁盘。

缓存

因为 CPU 太快、内存太慢，计算机在中间加了一层速度更快的缓存（Cache），自动存最近用过的数据。CPU 每次读数据，会顺带把相邻的一小片数据一起搬进缓存（这叫”局部性”）。

这就是为什么：

数组（连续内存）从头到尾读一遍，非常快——因为一次能搬一大片进缓存；
链表（节点散落各处）跳着读，每次都”扑空”，慢得多。

同样的操作，数据摆得越连续，跑得越快。 这是整个教程反复出现的底层逻辑。

偏移

从某段内存的起点往前”数几格”，这个距离叫偏移（offset）。比如数组的第 3 个元素，距开头偏移是 3。

索引

索引（index）就是数组下标 i，从 0 开始。索引和偏移的关系：

偏移（字节） = 索引 \times 数据宽度

一个 int 数组，arr[3] 的字节偏移是 $3 \times 4 = 12$ 字节。

地址

地址是内存格子的编号，也是变量真正的”身份证”。数组里每个元素的位置：

元素地址 = 基地址 + 索引 \times 数据宽度

（基地址就是 arr[0] 的地址）这个公式是数组 O(1) 随机访问的全部秘密——只要一次乘法和加法，就能算出任意元素在哪。

指针

指针是一个”存的不是数据，而是别人地址”的变量。类比：一张纸条上写着”东西在第 12 号柜子里”。

需要知道的几点：

指针指向一个位置，也叫”引用”它；
指针可以为空（NULL），表示”不指向任何地方”，使用前要判断；
链表、树、图这些结构，本质都是靠指针把一个个分散的节点”串”起来。

数据抽象

数据结构可以拆成两层看：

对外：能干什么（提供的操作，比如”插入""查找”）；
对内：怎么存（具体实现，比如数组还是链表）。

这两层可以分开。比如”栈”只规定”后进先出、只能从顶部操作”这个规则，底层用数组实现也行、用链表实现也行——使用者完全不用关心。这种”只看规则、不看实现”的思想就是抽象。

所以后面学”栈""队列""哈希表”时，先分清它是一套规则（抽象），还是具体的实现，学习会顺畅很多。

数学基础

对数

$lo g_{2} n$ 的意思是：“2 要自乘几次才等于 n”。例如 $lo g_{2} 8 = 3$ ，因为 $2 \times 2 \times 2 = 8$ 。

为什么数据结构里到处都是 O(log n)：因为很多算法每做一次操作就”砍掉一半”（二分查找、二叉树的查找都是）。砍一半很快到底—— $lo g_{2} 100 万 \approx 20$ ，也就是说处理 100 万个数据，最多只需要约 20 步，这就是 O(log n) 强大之处。

幂

$2^{3} = 8$ 这种”指数”记法。计算机里到处是 2 的幂： $2^{10} = 1024$ 、内存容量 4GB/8GB/16GB（翻倍增长）、容器扩容”容量 ×2”。所以看到一个东西成倍翻，先想到幂。

几何级数

一串数每一项都是前一项的固定倍数（比如 1, 2, 4, 8, 16…），叫几何级数。它有个重要性质：

1 + 2 + 4 + \dots + n \approx 2 n

为什么学：vector 扩容是”每次容量翻倍”，把扩容的搬移代价加起来正好是几何级数，总和约 2n——所以”平均每次插入的代价是常数”，这就是均摊复杂度（后面容器章节会细讲）。

取模

取模 % 就是取余数：7 % 3 = 1。它把任意大的数字”圈”进一个固定范围，很像时钟：13 点就是 1 点（模 12）。

哪里会用到：环形队列用 (i + 1) % n 转圈；哈希表用 h(k) % M 把任意键映射进桶数组。“取模让数字循环起来”，记住这一句就够。

位运算

数据在计算机里是二进制（一串 0/1），直接对这串 0/1 做的运算叫位运算：

符号	含义	例子
`&`	与（按位）	`i & (-i)` 取出最低位的 1
`\|`	或（按位）	把某些位设为 1
`<<`	左移（×2）	`1 << 3 = 8`
`>>`	右移（÷2）	`8 >> 1 = 4`

这一节只需认识符号，知道”二进制、有位运算这回事”。真正用到的地方（树状数组的 lowbit）会单独讲解，到时候再回头看这里即可。

时间复杂度

描述”数据量变大时，操作次数增长得多快”，用大 O 记号表示：

记号	含义	例子
O(1)	常数次，与数据量无关	数组按下标取值
O(log n)	每翻一倍数据，只多加一步	二分查找
O(n)	与数据量成正比	从头扫一遍
O(n log n)	n 次 log 操作	快速排序
O(n²)	双重循环	冒泡排序

两个要点：

只看增长趋势，忽略常数：3n 和 100n 都写 O(n)；
常见速度排序： $O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (2^{n})$ 。

后面每学一个数据结构，都会配一张复杂度表，看懂这张表之前提就够了。

空间复杂度

和时间复杂度一个道理，只不过算的是”这个结构/算法额外占了多少内存”，一般记 O(1)（固定的几个变量）或 O(n)（需要一份跟数据一样大的空间）。

看表时”空间 O(n)“就是”要额外一份同等大小的内存”，不用想得更复杂。

最优解

同一个问题往往有多种解法。选一个”又快又省”的，就是最优解。注意时间和空间常常矛盾：

用空间换时间：多存一些中间结果（比如缓存），换来更快；
用时间换空间：少存东西，多算几遍。

学哈希表、记忆化等技巧时，会反复看到这种权衡。

运行时内存布局

程序运行时，它的内存大致分成几块区域：

代码段：存放程序指令本身；
调用栈（stack）：函数调用时自动分配空间，一层层”叠”起来，函数返回时自动回收。特点：自动管理、很快、大小有限（递归太深会溢出）；
堆（heap）：程序员手动申请的空间（C 的 malloc、C++ 的 new），用完后要手动释放。特点：手动管理、灵活、空间大。

注意区分：这里的”栈 / 堆”是内存区域，不是数据结构”栈 / 堆”。
数据结构里的”栈”是指”后进先出”的规则——恰好函数调用也是后进先出（最晚调用的函数最先返回），所以这个内存区域才借用了”栈”的名字。这也解释了为什么”递归”总跟”栈”联系在一起。

RootStack

探索