数据结构

定义：
计算机中存储、组织数据的方式。
数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

数据结构与算法的关系

用烹饪来举例子的话数据结构就像是食材的摆放方式，算法就是从下订到到出餐的过程，冰箱里的食物调料无序的穿插摆放，那么在烹饪的时候自然需要耗费更多时间，而一个分类好的食材可以快速缩短查找所需的时间，更有甚者，良好的数据结构能够像是预制菜一样，大大减少算法的复杂度。

常见的数据结构

链表

特征

链表的数据在逻辑是呈现线性连续的，但是在存储中可以是分开的
链表中的每个数据为 

1
2
graph LR
   A["数据内容|下一个的数据地址"]

查找数据的时候就通过数据所包含的下一个数据的地址进行查找
逻辑上长成这样

1
2
3
graph LR
    A["内容1|地址"]--> B["内容2|地址"]
    B --> c["内容3|地址"]

知道地址为null即为遍历完毕
由于我们在查找内容的时候是使用的地址进行的查找，所以数据的物理位置可以不相邻，一个在天南，一个在海北，只要有地址，在逻辑上他们就是一条链表

双向链表

上面的链表虽然突破了存储数据在物理上的限制，但是还是存在一个问题，一旦需要查找，就必须得从头查到尾，而且不能回头，所以如果我们把一个数据设计为

1
2
graph LR
   A["上一个地址|数据内容|下一个地址"]

那么既可以从这个节点往下一个节点找，也可以实现往上一个节点进行查找
功能是多了，那么代价是什么呢？<–上一个地址的存储空间

循环链表

如果我们把上面普通链表的最后一个元素的地址指针设置为第一个元素的地址，那么这串数据在逻辑上就是首尾相连永无止境的，这个就叫循环链表 

1
2
3
4
graph LR
    A["内容1|地址"]--> B["内容2|地址"]
    B --> c["内容3|地址"]
    c --> A

双向循环链表

循环链表+双向链表√

数组

特征

数组是数据呈现线性排列的一种数据结构，重点在于数组在物理上也是连续的。
如果说链表是拿着门牌号去世界各地找数据，那么数组就是规划整齐地小区，如果要找到五栋的人，只需要从一栋开始，往后数4栋就是了。
举个例子：

  1. 我们创建了一个数组a[],设置每一个元素之间间隔8个bit
  2. 记下了这个数组的起始点a[0]地址
  3. 那我们查找a[10086]的时候只需要寻找a[0]+10085*8个bit后面的内容就是了

比较链表和数据

查找数据100086

链表：需要访问10085个数据才能知道第10086的
数组：直接一次找到

删除10086

链表：直接更改前后两个数据的地址实现
数组：需要要求10086往后所有的数据都往前挪一格来保证数据的有序

总结：两个不同的数据类型要按需取用，看是需要快速查询，少量更改还是大量更改，少量查询

栈（Stack）

特征

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。所以是后进先出
就像是往箱子里取放书一样，只能操作最表面的东西。

逻辑结构示意图：

1
2
3
4
5
6
7
8
9
10
11
graph TD
    subgraph 栈结构
        direction BT
        D4["栈底 (Bottom)"]
        D3["数据元素 3"]
        D2["数据元素 2"]
        D1["栈顶 (Top)"]
        D4 --> D3
        D3 --> D2
        D2 --> D1
    end

每次读取或者存入只能在栈顶操作，上面的没走下面的也就走不了

操作原理示意图 (LIFO)：

1
2
3
4
5
graph LR
    A[入栈 Push] -->|进入| B{栈}
    B{栈} -->|出去| C[出栈 Pop]
    style B fill:#f9f,stroke:#333,stroke-width:2px
    note1[最后进入的元素最先出来]

队列（Queue）

就像是一个缓冲区一样，先进先出，可以理解为高速收费站，大家都按顺序通过。

逻辑结构示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph LR
    subgraph 队列结构
        direction LR
        Rear["队尾 (Rear)"]
        D3["数据元素 3"]
        D2["数据元素 2"]
        D1["数据元素 1"]
        Front["队头 (Front)"]
        
        Rear --> D3
        D3 --> D2
        D2 --> Front
        Front --> D1
    end

树

在存储上和链表其实很像，只不过链表只包含了后续的一个地址，而数包含了后续的多个地址，所以在逻辑结构上就像下图一样。

单个节点
1
2
graph TD
  root["数据内容|叶子1地址|叶子2地址"]
树的逻辑结构 
1
2
3
4
5
6
7
graph TD
    root[根节点: A] --> B[节点: B]
    root --> C[节点: C]
    B --> D[节点: D]
    B --> E[节点: E]
    C --> F[节点: F]
    E --> G[节点: G]

树的一些概念

术语 定义（结合示例）
根节点 没有父节点的节点（示例中的 A），是整棵树的起点
叶子节点 没有子节点的节点（示例中的 D、G、F），像树的叶子
父/子节点 若 X 直接指向 Y，则 X 是 Y 的父节点，Y 是 X 的子节点（比如 B 是 D 的父节点，D 是 B 的子节点）
兄弟节点 有同一个父节点的节点（比如 D 和 E 是兄弟，B 和 C 是兄弟）
节点的度 一个节点拥有的子节点数量（比如 B 的度是 2，E 的度是 1，D 的度是 0）
树的度 整棵树中所有节点的度的最大值（示例中树的度是 2）
树的深度/高度 从根节点到最远叶子节点的层数（层数从 1 开始，示例中树的深度是 4：A→B→E→G）

特殊的树

为了让树适合各种各样的场景，可以延伸出很多特殊的数

  1. 二叉树：就是每个节点最多只有两个节点的树，也就是度最大为2

  2. 满二叉树：二叉树的一种除叶子节点外，所有非叶子节点的度都为 2（都有左右子节点），且所有叶子节点在同一层。

    1
    2
    3
    4
    5
    6
    7
    graph TD
        A[1] --> B[2]
        A --> C[3]
        B --> D[4]
        B --> E[5]
        C --> F[6]
        C --> G[7]

  3. 完全二叉树：按层序遍历（从上到下、从左到右）给节点编号，每个节点的编号与满二叉树对应位置一致（简单说：除最后一层外，其他层节点都满，最后一层叶子靠左）。

    1
    2
    3
    4
    5
    6
    graph TD
        A[1] --> B[2]
        A --> C[3]
        B --> D[4]
        B --> E[5]
        C --> F[6]

  4. 二叉搜索树（BST）：满足「左子树所有节点值 < 根节点值 < 右子树所有节点值」，支持快速查找 / 插入 / 删除（时间复杂度 O(logn)），是数据库索引、排序算法的基础。

    1
    2
    3
    4
    5
    6
    7
    graph TD
        root[8] --> left1[4]
        root --> right1[12]
        left1 --> left2[2]
        left1 --> right2[6]
        right1 --> left3[10]
        right1 --> right3[14]

二叉树的计算

二叉树的基本性质

设二叉树的节点总数为 $n$，其中：

  • $n_0$：叶子节点数（度为 0）
  • $n_1$：度为 1 的节点数
  • $n_2$：度为 2 的节点数

则满足核心关系：
$$n = n_0 + n_1 + n_2$$
结合边数性质 $\sum \text{degree}(v) = 2(n - 1)$，推导得：
$$0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = 2(n_0 + n_1 + n_2 - 1)$$
化简后得到二叉树最核心的性质：
$$n_0 = n_2 + 1$$

最大节点

在二叉树的第k层上，最多有$2^k - 1$（k>0）减一个节点

完全二叉树高度

$h = \lfloor \log_2 n \rfloor + 1$（$n \geq 1$）

图

概念

图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
即所有的节点之间可以随意相连

图的定义

通常点的有穷非空集合$V ( G )$ 和顶点之间边的集合$E ( G )$组成
$$G=(V,E)$$

通常用$|V|$来表示点的数量，$|E|$来表示边的数量

图的基本概念和术语

  1. 有向图
    当两个节点之间的边存在方向意义时称之为有向图，一般用<v,w>来表示从v指向w的弧，且<v,w>与<w,v>所表示的意义不一样
  2. 无向图
    两个结点之间的边不存在方向，用(w,v)来表示
  3. 子图
    图$G1=(V1,E1)$与$G2=(V2,E2)$，若$E2$是$E1$的子集，$V2$是$V1$的子集，即$E2$是$E1$的子图,也就是即拥有子图的所有点，又拥有子图的所有边
  4. 连通
    两个点之间存在路径即为连通，若图中任意两个顶点都是连通的，则称图连通图，否则称为非连通图
  5. 连通分量
    无向图中的极大连通子图称为连通分量