数据结构与算法
2021-11-12 23:51:48 147 举报
AI智能生成
数据结构与算法是计算机科学的核心领域,它们为解决实际问题提供了基础工具和方法。数据结构是用于存储和组织数据的特定方式,如数组、链表、栈和队列等,而算法则是一系列步骤来执行特定任务或解决特定问题,如排序、搜索和图遍历等。通过选择合适的数据结构和算法,可以有效地提高程序的性能和效率。在软件开发中,熟练掌握数据结构与算法是成为一名优秀程序员的关键要素。
作者其他创作
大纲/内容
线性数据结构
数组
优点
按照索引,查询/遍历速度快
缺点
大小固定,创建后无法扩容
只能存储一种类型数据
添加删除速度慢
适用场景
频繁查询,数据量不大,少增删操作
栈
特殊的线性结构,只能在一端进行操作
特点
先进先出
适用场景
常用于实现递归方面的操作;如:斐波那契数列
队列
特殊的线性结构,一端操作数据入队,一端操作数据出队
特点
先进先出
适用场景
先进先出特点,多线程阻塞队列中,常使用
链表
链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现
根据指针指向分类
单向链表
双向链表
循环链表
优点
不需要初始化容量,可以任意加减元素;
加减元素只需要更改前后指针
加减元素只需要更改前后指针
缺点
含有大量指针域(每个节点数据都有),内存消耗高;
遍历元素需要遍历链表,比较耗时
遍历元素需要遍历链表,比较耗时
适用场景
数据量少,频繁增删元素
串
概念
结构
匹配算法
(字符串匹配算法)
(字符串匹配算法)
BF算法
KMP算法
算法
排序
插入排序
直接插入排序
对于给定的一组记录,初始时假定第一个记录自成一个有序的序列,其余的记录为无序序列;
从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列为止。
希尔排序
(缩小增量排序)
(缩小增量排序)
把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。
随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。
交换排序
冒泡排序
快速排序
使用分治法策略
选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
选择排序
简单选择排序
对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将记录与第一个记录的位置进行交换;接着对不包括第一个记录以外的其他记录进行第二轮排序,得到最小的记录并与第二个记录进行位置交换;重复该过程,直到进行比较的记录只有一个为止。
堆排序
将序列构造成一棵完全二叉树 ;
把这棵普通的完全二叉树改造成堆,便可获取最小值 ,输出最小值 ;
删除根结点,继续改造剩余树成堆,便可获取次小值 ,输出次小值 ;
重复改造,输出次次小值、次次次小值,直至所有结点均输出,便得到一个排序 。
把这棵普通的完全二叉树改造成堆,便可获取最小值 ,输出最小值 ;
删除根结点,继续改造剩余树成堆,便可获取次小值 ,输出次小值 ;
重复改造,输出次次小值、次次次小值,直至所有结点均输出,便得到一个排序 。
归并排序
是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)
递归深度为log2n
递归深度为log2n
归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。
基数排序
(1)分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中
(比如53,个位为3,则放入3号桶中)
(2)收集,再将放置在0~9号桶中的数据按顺序放到数组中
(比如53,个位为3,则放入3号桶中)
(2)收集,再将放置在0~9号桶中的数据按顺序放到数组中
不从最高位开始排序的原因,主要是出于空间的考虑,
因为如果按照最高位开始排序,则之后的地位都需要创建一个完整的基数排序空间,空间占用量成指数增长
因为如果按照最高位开始排序,则之后的地位都需要创建一个完整的基数排序空间,空间占用量成指数增长
拓扑排序
将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
查找
概念
线性表查找
顺序查找
二分查找
分块查找
树形查找
二叉树查找
AVL树查找
B-树
B+树
哈希查找
概念
冲突解决
拉链法
图论算法
贪婪算法
分治算法
动态规划
随机化算法
回溯算法
高级数据结构
自顶向下伸展树
红黑树
确定性跳跃表
AA树
treap树
k-d树
配对堆
散列表
根据键值(key/value)进行访问的数据结构;
通过key/value来映射到集合中的元素,这样可以很快找到集合中的元素
通过key/value来映射到集合中的元素,这样可以很快找到集合中的元素
堆
定义
最大堆
(大根堆)
(大根堆)
堆中某个节点总是不大于父节点
最小堆
(小根堆)
(小根堆)
堆中某个节点总是不小于(最小堆)父节点
性质
堆的常用结构使用二叉树表示,不特指的话为一棵完全二叉树,通常不必用指针,
而是用数组来实现堆的存储堆:
数组起始单元为1,在数组中按照完全二叉树的层序存储,
根节点放在下标为1的位置中
对于下标为i的结点,其父结点的下标为i/2取整,反过来,i的左右结点分别是2i和2i+1
而是用数组来实现堆的存储堆:
数组起始单元为1,在数组中按照完全二叉树的层序存储,
根节点放在下标为1的位置中
对于下标为i的结点,其父结点的下标为i/2取整,反过来,i的左右结点分别是2i和2i+1
常用堆
二叉堆
斐波那契堆
注意
堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。
例如,
在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。
--唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。
在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。
--唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。
可以使用普通树来模拟堆,但是那对空间是极大的浪费。
并不是每一个最小堆都是一个有序数组!要将堆转换成有序数组,需要使用堆排序。
实现
堆仅仅使用一个数据来存储数组,且不使用指针
基本操作
shiftUp()
如果一个节点比它的父节点大(最大堆)或者小(最小堆),那么需要将它同父节点交换位置。
这样是这个节点在数组的位置上升
这样是这个节点在数组的位置上升
shiftDown()
如果一个节点比它的子节点小(最大堆)或者大(最小堆),那么需要将它向下移动。这个操作也称作“堆化(heapify)”
常见应用
构建优先队列
因为堆有序,常用来做数组排序——堆排序
树
概述
定义
1.每个节点有零个或多个子节点
2.没有父节点的节点称为根节点;
3.每一个非根节点有且只有一个父节点;
4.除了根节点外,每个子节点可以分为多个不相交的子树;
2.没有父节点的节点称为根节点;
3.每一个非根节点有且只有一个父节点;
4.除了根节点外,每个子节点可以分为多个不相交的子树;
术语
节点的度
一个节点含有的子树的个数称为该节点的度
叶节点/终端节点
度为0的节点称为叶节点
非终端节点/分支节点
度不为0的节点
节点的层次
从根开始定义起,根为第1层,根的子节点为第2层,以此类推
树的高度或深度
树中节点的最大层次
森林
由m(m>=0)棵互不相交的树的集合称为森林
遍历方式
前序遍历
父左右
中序遍历
左父右
后续遍历
左右父
层序遍历
从根节点开始,一层层往下
常见树
二叉树
概述
定义
1.每个节点最多有两个子树,节点的度最大为2;
2.左子树和右子树是有顺序的,顺序不能颠倒;
3.即使某个节点只有一个子树,也要区分左右节点
2.左子树和右子树是有顺序的,顺序不能颠倒;
3.即使某个节点只有一个子树,也要区分左右节点
第i层至多有2^(i-1)个结点;
深度为k的二叉树至多有2^k-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)。
原因:由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。
这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度
在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。
原因:由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。
这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度
自平衡二叉搜索树
AVL树
概述
它或者是一棵空树,或者是具有下列性质的二叉树:
它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
(注:平衡二叉树应该是一棵二叉排序树)
它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
(注:平衡二叉树应该是一棵二叉排序树)
n个结点的AVL树最大深度约1.44log2n
查找、插入和删除在平均和最坏情况下都是O(logn)
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树;
这个方案很好的解决了二叉查找树退化成链表的问题,
把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多
这个方案很好的解决了二叉查找树退化成链表的问题,
把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多
AVL树的自平衡操作——旋转
左左/右右
单旋转
左左情况,单旋转自平衡处理
左右/右左
多旋转
子主题
2-3树
性质
1.满足AVL树的性质;
2.节点可以存放1个或2个元素;
3.每个节点有两个或三个子节点。
2.节点可以存放1个或2个元素;
3.每个节点有两个或三个子节点。
2-3树本质上也是一棵搜索树,和二叉搜索树的区别在于,2-3的节点可能存放 2 个元素,而且每个节点可能拥有 3 个子节点。
2-3树存在以下两种节点:2-节点(存在两个子节点)和3-节点(存在3个子节点)
红黑树
(RB-tree)
(RB-tree)
概述
自平衡二叉查找
可以在O(logn)时间内做查找,插入和删除
性质
在二叉查找树强制的一般要求以外增加:
1.节点是红色或黑色;
2.根是黑色;
3.所有叶子都是黑色(叶子是NIL节点);
4.每个红色节点下有两个黑节点(每个叶子到根的路径上不能有两个连续的红色节点);
5.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。
1.节点是红色或黑色;
2.根是黑色;
3.所有叶子都是黑色(叶子是NIL节点);
4.每个红色节点下有两个黑节点(每个叶子到根的路径上不能有两个连续的红色节点);
5.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。
SBT
Splay
Treap
Treap
(树堆)
(树堆)
B树
(B-树)
(B-树)
概念
是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),
数据库索引技术里大量使用者B树和B+树的数据结构
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),
数据库索引技术里大量使用者B树和B+树的数据结构
规则
一棵m阶B-树,或为空树,或为满足下列特性的m叉树:
A:为指向子树根结点的指针,
K:为关键字,且Ai-1所指子树中所有结点的关键字均小于Ki,An所指子树中所有结点的关键字均大于Kn;
- 1)树中每个结点至多有m棵子树;
- 2)若根节点不是叶子节点,则至少有两棵子树;
- 3)除根之外的所有非终端结点至少有[m/2]()向上取整)棵子树;
- 4)所有的非终端结点中包含下列信息数据:(n,A0,K1,A1,K2,A2,…,Kn,An),
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+树是用第一种方式实现);
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的数据创建一个新的节点出来;
(1)首先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),b*树的初始化个数为(cei(2/3*m))
(2)B+树节点满时就会分裂,
而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),
如果兄弟节点未满则向兄弟节点转移关键字,
如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;
特点
在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高,
而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少;
而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少;
分裂
当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。
B*树分配新结点的概率比B+树要低,空间使用率更高。
R树
哈夫曼树
概念
在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,也被称为最优二叉树。
结构
适用场景
典型运用
哈夫曼编码
trie 树(字典树)
前缀树,典型运用:关键字过滤
图
概念
图是由结点的有穷集合V和边的集合E组成。
在图结构中常常将结点称为顶点,
边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。
在图结构中常常将结点称为顶点,
边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。
术语
定点
边
边上带权重的为带权图
按照顶点方向划分
有向图
无向图
图的表示
邻接矩阵
无向图
有向图
缺点
占用空间太大
邻接表
图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点
逆邻接表
每一个顶点作为链表的头节点,后继节点所存储的是能够直接达到该顶点的相邻顶点
十字链表
邻接表+逆邻接表=十字链表
十字链表
邻接多重表
边集数组
遍历
深度优先遍历
利用栈实现
广度优先遍历
利用队列实现
应用
最小生成树
最短路路径
无权图
广度优先算法
带权图
迪杰斯特拉算法
多源最短路径
佛洛依德算法
拓扑排序
关键路径
0 条评论
下一页