数据结构与算法

2021-11-12 23:51:48   146  举报





AI智能生成

数据结构与算法是计算机科学的核心领域，它们为解决实际问题提供了基础工具和方法。数据结构是用于存储和组织数据的特定方式，如数组、链表、栈和队列等，而算法则是一系列步骤来执行特定任务或解决特定问题，如排序、搜索和图遍历等。通过选择合适的数据结构和算法，可以有效地提高程序的性能和效率。在软件开发中，熟练掌握数据结构与算法是成为一名优秀程序员的关键要素。

数据结构

数据结构与算法

算法

算法和数据结构

作者其他创作

大纲/内容

线性数据结构

数组

优点

按照索引，查询/遍历速度快

缺点

大小固定，创建后无法扩容

只能存储一种类型数据

添加删除速度慢

适用场景

频繁查询，数据量不大，少增删操作

栈

特殊的线性结构，只能在一端进行操作

特点

先进先出

适用场景

常用于实现递归方面的操作；如：斐波那契数列

队列

特殊的线性结构，一端操作数据入队，一端操作数据出队

特点

先进先出

适用场景

先进先出特点，多线程阻塞队列中，常使用

链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现

根据指针指向分类

单向链表

双向链表

循环链表

优点

不需要初始化容量，可以任意加减元素；
加减元素只需要更改前后指针

缺点

含有大量指针域（每个节点数据都有），内存消耗高；
遍历元素需要遍历链表，比较耗时

适用场景

数据量少，频繁增删元素

串

概念

结构

匹配算法
（字符串匹配算法）

BF算法

KMP算法

算法

排序

插入排序

直接插入排序

对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；

从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。

希尔排序
（缩小增量排序）

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

交换排序

冒泡排序

快速排序

使用分治法策略

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

选择排序

简单选择排序

对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮排序，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

堆排序

将序列构造成一棵完全二叉树；
把这棵普通的完全二叉树改造成堆，便可获取最小值 ,输出最小值；
删除根结点，继续改造剩余树成堆，便可获取次小值 ,输出次小值；
重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序。

归并排序

是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
递归深度为log2n

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

基数排序

(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中
（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中

不从最高位开始排序的原因，主要是出于空间的考虑，
因为如果按照最高位开始排序，则之后的地位都需要创建一个完整的基数排序空间，空间占用量成指数增长

拓扑排序

将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

查找

概念

线性表查找

顺序查找

二分查找

分块查找

树形查找

二叉树查找

AVL树查找

B-树

B+树

哈希查找

概念

冲突解决

拉链法

图论算法

贪婪算法

分治算法

动态规划

随机化算法

回溯算法

高级数据结构

自顶向下伸展树

红黑树

确定性跳跃表

AA树

treap树

k-d树

配对堆

散列表

根据键值（key/value）进行访问的数据结构；
通过key/value来映射到集合中的元素，这样可以很快找到集合中的元素

堆

定义

最大堆
（大根堆）

堆中某个节点总是不大于父节点

最小堆
（小根堆）

堆中某个节点总是不小于（最小堆）父节点

性质

堆的常用结构使用二叉树表示，不特指的话为一棵完全二叉树，通常不必用指针，
而是用数组来实现堆的存储堆：
数组起始单元为1，在数组中按照完全二叉树的层序存储，
根节点放在下标为1的位置中
对于下标为i的结点，其父结点的下标为i/2取整，反过来，i的左右结点分别是2i和2i+1

常用堆

二叉堆

斐波那契堆

注意

堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。

例如，
在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。
--唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

可以使用普通树来模拟堆，但是那对空间是极大的浪费。

并不是每一个最小堆都是一个有序数组！要将堆转换成有序数组，需要使用堆排序。

实现

堆仅仅使用一个数据来存储数组，且不使用指针

基本操作

shiftUp()

如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。
这样是这个节点在数组的位置上升

shiftDown()

如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”

常见应用

构建优先队列

因为堆有序，常用来做数组排序——堆排序

树

概述

定义

1.每个节点有零个或多个子节点
2.没有父节点的节点称为根节点；
3.每一个非根节点有且只有一个父节点；
4.除了根节点外，每个子节点可以分为多个不相交的子树；

术语

节点的度

一个节点含有的子树的个数称为该节点的度

叶节点/终端节点

度为0的节点称为叶节点

非终端节点/分支节点

度不为0的节点

节点的层次

从根开始定义起，根为第1层，根的子节点为第2层，以此类推

树的高度或深度

树中节点的最大层次

森林

由m（m>=0）棵互不相交的树的集合称为森林

遍历方式

前序遍历

父左右

中序遍历

左父右

后续遍历

左右父

层序遍历

从根节点开始，一层层往下

常见树

二叉树

概述

定义

1.每个节点最多有两个子树，节点的度最大为2；
2.左子树和右子树是有顺序的，顺序不能颠倒；
3.即使某个节点只有一个子树，也要区分左右节点

第i层至多有2^(i-1)个结点;
深度为k的二叉树至多有2^k-1个结点

特点

二叉树是数组和链表的折中方案，
增加、删除速度都快，并且对查询也有算法优化；
在动态处理大批量数据的时候很有用

满二叉树

一棵深度为k且有2^k-1（2的k次幂减1）个结点的二叉树称为满二叉树

完全二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
它的左、右子树也分别为二叉排序树。

存在的问题

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定；
在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。
原因：由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。
这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度

自平衡二叉搜索树

AVL树

概述

它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
（注：平衡二叉树应该是一棵二叉排序树）

n个结点的AVL树最大深度约1.44log2n

查找、插入和删除在平均和最坏情况下都是O(logn)

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树；
这个方案很好的解决了二叉查找树退化成链表的问题，
把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多

AVL树的自平衡操作——旋转

左左/右右

单旋转

左左情况，单旋转自平衡处理

左右/右左

多旋转

子主题

2-3树

性质

1.满足AVL树的性质；
2.节点可以存放1个或2个元素；
3.每个节点有两个或三个子节点。

2-3树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3的节点可能存放 2 个元素，而且每个节点可能拥有 3 个子节点。

2-3树存在以下两种节点：2-节点（存在两个子节点）和3-节点（存在3个子节点）

红黑树
（RB-tree）

概述

自平衡二叉查找

可以在O(logn)时间内做查找，插入和删除

性质

在二叉查找树强制的一般要求以外增加：
1.节点是红色或黑色；
2.根是黑色；
3.所有叶子都是黑色（叶子是NIL节点）；
4.每个红色节点下有两个黑节点（每个叶子到根的路径上不能有两个连续的红色节点）；
5.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。

SBT

Splay

Treap

Treap
（树堆）

B树
（B-树）

概念

是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），
数据库索引技术里大量使用者B树和B+树的数据结构

规则

一棵m阶B-树，或为空树，或为满足下列特性的m叉树：

1）树中每个结点至多有m棵子树；
2）若根节点不是叶子节点，则至少有两棵子树；
3）除根之外的所有非终端结点至少有[m/2]（）向上取整）棵子树；
4）所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An），

       n：为结点中的关键字树，
       A：为指向子树根结点的指针，
       K：为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn；

5）所有的叶子结点都出现在同一层次上，并且不带信息

（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）

多叉平衡查找树

参考

从B树、B+树、B*树谈到R 树

平衡二叉树、B树、B+树、B*树理解其中一种你就都明白了

B+树

概念

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找

规则

1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
4）非叶子节点的子节点数=关键字数（来源百度百科）
（根据各种资料这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，
虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

分裂

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；
只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

应用场景

数据库索引

B*树

概念

规则

B*树是B+树的变种，相对于B+树他们的不同之处如下：
（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）
（2）B+树节点满时就会分裂，
而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），
如果兄弟节点未满则向兄弟节点转移关键字，
如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，
而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

分裂

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

B*树分配新结点的概率比B+树要低，空间使用率更高。

R树

哈夫曼树

概念

在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

结构

适用场景

典型运用