数据结构与算法整理

发表于 2020-08-08 更新于 2024-01-13 分类于数据结构，算法

数据结构分类

线性结构

元素之间存在一对一的关系,线性结构按照存储的方式不同可以分为顺序结构和链式结构，如：数组、链表、队列、栈。

非线性结构

如：二维数组、多维数组、树结构、图结构

【数据结构】稀疏数组

稀疏数组是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组
参考：https://blog.csdn.net/weixin_41922289/article/details/94555391

普通存储（二维数组）

第一行存储原始数据总行数，总列数，总的非0数据个数
接下来每一行都存储非0数所在行，所在列，和具体值
转换步骤：首先要获取数据的总行数 -> 定义数组 -> 填值

字符串匹配分类

BF算法、BM算法、KMP算法的。参考:https://baijiahao.baidu.com/s?id=1659735837100760934&wfr=spider&for=pc

队列

先进先出数组、链。ArrayBlockingQueue,LinkedBlockingQueue,PriorityQueue
BlockQueue 接口方法

	Throws exception	Special value	Blocks	Times out
insert	add	offer	put	offer
remove	remove	poll	take	pull
examine	element	peek

链表

单向链表、双向链表，环形链表

约瑟夫环（丢手帕）

单项环形链表

栈

先进后出

应用场景

子程序调用（栈帧）
处理递归调用
表达式的转换[中缀表达式转后缀表达式]与求值（实际解决）
二叉树遍历
图形深度优先（depth-first）

Stack

前缀表达式（波兰表达式）、中缀表达式、后缀表达式（逆波兰表达式）

前缀表达式

从右至左扫描表

排序算法

将一组数据，依据指定的顺序排列

内部排序所有数据都加载到内存中进行排序

插入排序（直接插入排序、希尔排序）
选择排序（简单选择排序、堆排序）
交换排序（冒泡、快速排序）
归并排序
+基数排序

外部排序数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

算法时间复杂度

事后统计法

这种方法可行，但是有两个问题，一是要想对设计算法的运行性能进行评测，需要实际运行该程序；二是所得事件的统计量依赖于计算机硬件软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快。

事前估算的方法

通过分析某个算法的事件复杂度来判断哪个算法更优

一个算法花费的时间与算法中语句执行的次数成正比，哪个算法执行的次数越多，它花费的时间就越多，一个算法中语句执行次数称为语句频度或时间频度

分治算法

分而治之，把一个复杂问题分解为简单问题，多用递归解决。经典问题，汉诺塔问题

动态规划算法

算法的核心思想：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法与分支算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解中得到原问题的解
与分支算法不同的是，适用于动态规划求解的问题，经分解得到子问题往往不是相互独立的（既下一个字节阶段的求解是建立在上一个子阶段求解的基础上进行进一步求解）
动态规划可以通过填表的方式逐步推进，得到最优解
背包问题 01背包、完全背包

贪心算法

在问题进行求解时，在每一步的选择中都采取最好或者最优的选择，从而希望能够导致结果时最好或者最优的算法
贪心算法所得到的结果不一定时最优的结构，但是都是相对近似最优解的结果
贪心算法解决集合覆盖问题

1、遍历所有的广播电台，找到一个覆盖了最多未覆盖的地区的电台（此电台可能包含一些已覆盖的地区）
2、将这个电台加入到一个集合中，想办法把该电台覆盖的地区在下一次比较时去掉
3、重复第一步直到覆盖了所有的地区

红黑树

二叉查找树+平衡二叉树(大致平衡的)

核心性质

从根节点到任意叶子节点最长的路径不大于最短路径的二倍，在插入和删除操作中核心性质可能不再满足，所以在插入删除中要进行判断是否满足，但是直接判断是否满足核心性质麻烦，就用了五条容易判断的性质进行等价替换。

性质

根节点是黑色的
节点非黑即红
不每条路径上不能有连续两个红色节点
从任意节点到叶子节点黑节点数量相同
叶子节点都是黑色的

插入过程

1.如果插入节点的父节点不存在就将颜色改为黑色。(因为这个节点就是根节点)
2.如果插入的节点的父节点是黑色，则ok，直接return。
3.如果插入的节点的父亲节点和叔叔节点是红色，则变化父叔节点为黑色，再把祖父节点变为红色，然后将祖父节点作为node，从case1开始判断。
4.(1)父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。则父进行左旋，然后执行case5.
(2)父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的左子节点而父节点P又是其父节点的右子节点。
　　则父进行右旋，然后执行case5.
5.父变黑，祖父变红
(1)父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的右子节点。
则祖父进行左旋
(2)父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的左子节点而父节点P又是其父节点的左子节点。
则祖父进行右旋
左旋就是：逆时针
右旋就是：顺时针

删除操作六条：形式也是六个函数，if-else格式的。
1.删除的是根，直接删。

红黑树和avl(二叉平衡树)的比较

如果插入一个node引起了树的不平衡，AVL和RB-Tree(红黑树)都是最多只需要2次旋转操作，即两者都是O(1)；
但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次(因为不需要严格的平衡，从根到叶子的最长的可能路径不多于最短的可能路径的两倍长)旋转以及修改节点的颜色，只需要O(1)的复杂度。
其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
红黑树实际应用：
IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.
ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
java中TreeMap，jdk1.8的hashmap的实现.

B+树

B+ 树是一种树数据结构，是一个n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
B+树是对B树的一种变形树，它与B树的差异在于：
有k个子结点的结点必然有k个关键码；
非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录，便于区间查找和遍历。
B+ 树的优点在于：

由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。
数据存放的更加紧密，具有更好的空间局部性。
因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。
而且由于数据顺序排列并且相连，所以便于区间查找和搜索。
而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：

b+树的应用场景:

B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,
一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到).B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,
所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少.
二叉查找树的结构不适合数据库，因为它的查找效率与层数相关。越处在下层的数据，就需要越多次比较。对于数据库来说，每进入一层，就要从硬盘读取一次数据，
这非常致命，因为硬盘的读取时间远远大于数据处理时间，数据库读取硬盘的次数越少越好。这种数据结构，非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值，
那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在100万个数据中查找目标值，
只需要读取两次硬盘。

图的遍历

深度优先 Depth First Search 每次都在访问当前节点的第一个邻接点纵向挖掘深入，递归的过程

1、访问初始节点v，并标记该节点已经访问
2、查找节点v的第一个邻结点w
3、若w不存在，则返回第一步，从v的下一个节点继续访问
4、若w未被访问，对w进行深度访问
5、查找v的邻结点的下一个邻结点

广度优先

二叉树：
前序排序：根->左->右
中左->根->右
后左->右-> 根
左永远在前，根前中后

深度优先，广度优先

数据结构：
线性结构元素之间存在一对一的线性关系
顺讯存储
链式存储（链表）
数组、队列、链表、

递归

各种数学问题，八皇后问题，汉诺塔、阶乘、迷宫、球和篮子

各种算法中也会使用到递归，快排序，归并排序、二分查找、分治算法
将用栈解决的问题 –> 递归代码比较简洁

注意：
执行一个方法时，就创建一个栈空间（栈帧）
方法的局部变量是独立的，不会相互影响
如果方法中使用的是引用类型的变量，就会共享改类型的数据
递归必须向退出递归条件逼近，否则就会无限循环

二叉树：每个节点最多有两个子节点（左节点，右节点）

满二叉树：所有叶子节点都在最后一层且节点数为2^n-1，所有节点都有两个子节点
完全二叉树：所有叶子节点在最后一层或者倒数第二层，最后一层左边连续，倒数第二层右边连续

二叉树遍历：
前：根 -> 左 -> 右递归
中：左 -> 根 -> 右
后：左 -> 右 -> 根

所有遍历都是从根开始

顺序存储二叉树

二叉树的数据以数组的方式存放（完全二叉树）

n个元素的左节点 2n+1
n个元素的右节点 2n+2
n个元素的父节点（n-1）/2

线索话二叉树

堆排序

大顶堆根> 左右

小顶堆根 < 左右