结构

数据结构的逻辑结构与存储结构的关系是抽象与具体的关系。

逻辑结构

是指数据对象中数据元素之间的相互关系。

• 集：记录

  快速的判断一个点是否存在

• 线：有序

  有序和混乱是相对的概念

  有序可以做减治，混乱只能暴力FOR遍历

• 树：分类

  边数=点数-1，因为根节点入度为0，其他节点入度为1.

• 图：依赖

  DAG(Directed Acyclic Graph)

  DAG，核心就是值传递

  如果是环图，要引入单调收敛的状态变量来使节点加状态变量共同组成一个DAG

存储结构

又名物理结构，是指数据的逻辑结构在计算机中的存储形式。

• 顺序存储
• 链式存储
• 散列存储或哈希存储

两要素

• 节点

• 边

  代表节点之间的关系，可以有向可以无向（无向边即两条相反的有向边）

  可以表示节点之间值传递的关系

值传递

DAG，核心就是值传递

如果是环图，要引入单调收敛的状态变量来使节点加状态变量共同组成一个DAG

1. DAG

   1. 前端：数据响应式原理
   2. 后端：
      1. 类、接口之间的继承、实现、依赖的关系
      2. 的依赖关系
      3. 观察者模式
   3. 数据库：在进行增加、删除和更新操作时：
      1. 索引更新
      2. 外键约束带来的级联删除

2. 先序和后序

• 先序：已知点 -> 未知点
• 后序：未知点 -> 已知点

3. 不设置单调收敛的变量会出现循环依赖（死锁），造成死循环。

4. 优化：滚动数组优化，只需要记录dp_1, dp_2，来记录前两个节点的值，每次求解后滚动更新

5. n依赖于n-1, n-2两个节点的递推关系的问题：

   递推公式如下：dp[n] = f(dp[n - 1], dp[n - 2])

   其中f可以是任何二元函数，如求max, min, +, -, /, *等，如果f不是纯函数，还可以结合外部变量实现一些更加复杂问题的求解

6. np问题：

   • 排序类：n!，如博弈型DP
   • 组合类：2^n，如背包问题、LIS等问题

7. 入度代表的语义是什么？

   代表该点的依赖

8. 递推四要素

   如下以斐波那契为例：

   1. 状态：dp[n]表示第n个斐波那契数的值
   2. 边界：dp[0], dp[1]
   3. 递推：dp[n] = dp[n-1] + dp[n-2]
   4. 方向：
      • 先序：DFS、BFS、FOR
      • 后序：DFS

9. 请写出在DAG图定义如下构成的递推公式：

   a为当前节点的权值

   • 最短路径：dp(n) = min{ dp(n - 1), dp(n - 2)} + a;
   • 最长路径：dp(n) = max{ dp(n - 1), dp(n - 2)} + a;
   • 路径个数：dp(n) = sum{ dp(n - 1), dp(n - 2)} + 1;

10. 了解普通队列、优先队列、双端队列这三种队列

    • 普通队列：FIFO
    • 优先队列：可以根据优先级进行“插队”，从而求最短路
    • 双端队列：队列两边都可以入队