数据结构与算法-基础
所以作为一个程序员，数据结构和算法都是必备的知识
数据结构
程序 = 数据结构 + 算法
线性结构
数据之间存在一对一的关系，像排队一样，同时只有零个或一个前驱和后继
- 集合中必存在唯一的一个”第一个元素”
- 集合中必存在唯一的一个”最后的元素”
- 除最后元素之外，其它数据元素均有唯一的”后继”
- 除第一元素之外，其它数据元素均有唯一的”前驱”
常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)
非线性结构
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图
树形结构
数据之间存在一对多的关系，就像一棵树一样，一个树干上上会有零条或多条树枝，树枝上又有很多的树叶
- 结点：表示树中的元素
- 结点的度：结点的边数
- 树的度：树中各结点度的最大值
- 叶子结点：度为0的结点
- 分支结点：度不为0的结点
- 孩子：结点子树的根
- 双亲：结点的上层结点叫该结点的双亲
- 祖先：从根到该结点所经过的分支上的所有结点
- 子孙：以某个结点为根的子树中的任一结点
- 兄弟：同一双亲的孩子
- 结点的层次：从根结点到树中某个结点所经过的路径上的分支数称为该结点的层次
- 堂兄弟：同一层不同双亲的结点
- 树的深度：树中结点的最大层次数
- 无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树
- 有序树：树中任意一个结点的各孩子结点有严格排列次序的树
- 森林：树的集合，一棵由根结点和 n 个子树构成的树，把树的根结点删除后，树就变成了包含 n 棵树的森林
图形结构
数据之间存在多对多的关系，就像地图一样，每个地点之间都由一条或多条路相连
- 边：两个节点的连接称之为边
- 顶点：节点在图形结构中也被称为顶点
- 路径：一个顶点到另一个顶点的经过的的线路称为路径
图的类型
无向图：顶点A与顶点B之间的边是无方向的，可以从A到B，也可以从B到A
有向图：顶点A与顶点B之间的边是有方向的，可以从A到B，但不可以从B到A
带权图：顶点A与顶点B之间的边是带有属性的，如A到B的 距离。
复杂度
时间复杂度
时间复杂度是指程序运行的时间记作 $T(n)$，通常根据不同问题的规模 n ，以及执行次数 $f(n)$会得到一个复杂度 $O(f(n))$ ，记作 $T(n) = O(f(n))$
- 常数时间：记作 $O(1)$ ，执行次数为常数次
- 线性时间：记作 $O(n)$ ，执行次数与数据量成线性关系
- 对数时间：记作 $O(log n)$ ，执行次数随着数据增大而减小
- 线性对数时间：记作 $O(n log n)$ ， 具有线性时间和对数时间的性质
- 指数时间：记作 $O(n^n)$
空间复杂度
空间复杂度是指程序执行时消耗的空间记作 $ S(n) $ ，通常根据输入本身占用的空间 n ，以及执行时临时占用的空间 $f(n)$会得到一个复杂度 $O(f(n))$ ，记作 $S(n) = O(f(n))$
度量方法
常用基本公式
$O(a) = O(1)$ 其中
a为常数
$O(an) = O(n)$ 其中a为常数
$O(an^2 + bn + c) = O(n^2)$ 其中a, b, c均为常数，结果只保留最高次项
以下是我用根据这些复杂度画的图
仓库地址：https://github.com/jesspig/data-structures-and-algorithms/tree/main/basic