数据结构

分类

1. 逻辑结构

树，图，数组，哈希，等等

2. 物理结构

计算机保存数据的结构

• 顺序结构（易查找，难插入）
• 链式结构（元素用指针相连）

指针保存的是链表下一个元素的地址

空间复杂度

对象头信息消耗16字节，数组头信息消费24个字节（都还不包含内容信息）

一个字节有八位！

（非）线性数据结构

线性结构是什么？

一个前驱一个后继

数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。线性结构是一个有序数据元素的集合。

线性结构特点：

• 线性结构有唯一的首元素（第一个元素）
• 线性结构有唯一的尾元素（最后一个元素）
• 除首元素外，所有的元素都有唯一的“前驱”
• 除尾元素外，所有的元素都有唯一的“后继”

数据元素之间存在“一对一”的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

常用的线性结构有 线性表，栈，队列，双队列，循环队列，一维数组，串。
线性表中包括顺序表、链表等，其中，栈和队列只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。

---

非线性结构
非线性结构是什么？
非线性结构中各个数据元素不再保持在一个线性序列中，数据元素之间是一对多，或者是多对一的关系。根据关系的不同，可分为层次结构（树）和群结构（图）。

常见的非线性结构有二维数组，多维数组，广义表，树(二叉树等)，图。（其中多维数组是由多个一维数组组成的， 可用矩阵来表示，他们都是两个或多个下标值对应一个元素，是多对一的关系，因此是非线性结构。）

相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。

顺序表

优势：查询

1. 遍历

实现Iterable接口实现iterator();方法

2. 容量可变

链表

优势：增删

1. 单向链表

实现：ArrayList

例题：合并两个升序的链表

快慢指针：

1. 中间值问题
2. 是否有环
3. 有环入口问题

难题：链表的反转

2. 双向链表

实现：LinkedList

栈

栈的表示方法：

Deque<Integer> stack = new LinkedList<Integer>();

堆

定义

可以被看做一棵树的数组对象，满足以下特性：

• 完全二叉树
• 堆的某个节点不大于或不小于其父节点

分类：

• 最大堆：根节点最大
• 最小堆：根节点最小

插入操作

时间复杂度：(N代表的是堆中元素的个数，个数增加带来的操作查询次数变化)

插入操作的时间复杂度取决于堆的高度h，堆的高度约等于logN+1
$$
O(logN)
$$

1. 先放在靠左边的位置，需要符合完全二叉树的定义
2. 递归向上判断，如果比父节点大就上升，小则不操作

示例：

删除操作

时间复杂度：
$$
O(logN)
$$

堆的删除只能删除堆顶元素

1. 删除堆顶元素，将最后一个元素赋值给堆顶
2. 自上而下沉降，对比左右节点，选则最大的交换

示例：

堆的构建

自顶向上

时间复杂度：（遍历数组N * 上滤操作logN）
$$
O(NlogN)
$$

数组—>堆

自顶向下建堆

1. 将数组遍历，每个新元素放在堆的末尾
2. 放置堆的末尾进行上滤，以构建最大堆为例，新元素如果大于父节点元素则上移，反之不操作

自下而上

时间复杂度：
$$
O(N)
$$
对每个父节点进行下滤

堆排序

方法一：

视频第8:30

依次弹出优先队列（最小堆）的顶部元素

时间复杂度：
$$
O(NlogN)
$$
方法二：大根堆排序

时间复杂度：
$$
O(NlogN)
$$

1. 每次排序将堆顶元素和最后一个元素替换（如果该元素已经被替换过，则选他前面的元素）
2. 之后对剩余元素进行大根堆排序
3. 重复1、2

步骤：

队列

树

概念：

• 路径长度：两个节点之间通路的长度
• 权：节点的值，可以为选择频率
• 度：节点所包含的子节点个数，如H的度就为1

完全二叉树

若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

哈夫曼树

带权路径长度（WPL）和最短的树为哈夫曼树(最优二叉树)

特点：

• 哈夫曼树不唯一
• 权值越大离根越近

前后中序遍历推导

已知两种遍历的顺序推出二叉树，本题要求至少有一个中序遍历的结果不然无法推出

• 前序序列：ABDEFGCHI
• 中序序列：DBFEGACIH
• 后续序列：？

解题方法：

1. 前序遍历的第一个为根节点A

   后续遍历最后一个是根节点

2. 中序遍历中根节点A左右为二叉树的左右子树

3. 中序遍历的第一个是左子树最左端的元素

4. 自下往上推断、通过一个顺序推断大致顺序，然后再对比是否满足其他

结果：DFGEBIHCA

图

图也能分为有向图、无向图

表示方法：邻接矩阵、链表

第i、j个元素是否为1，为1则i、j相连

判断是否有环？

有向图和无向图的判断方法各有差异

• 拓扑图：不断消除叶子节点，消除
• DFS