首页  思维导图  详情

数据结构与算法

2022-08-26 22:34:20   6  举报





AI智能生成

思维导图数据结构算法归纳

思维导图

思维

数据结构与算法

数据结构

算法

作者其他创作

大纲/内容

线性表

数组

物理上顺序存储，随机读取：根据下标读取元素的方式

插入

尾部

直接插入

中部

指定位置及以后元素后移，新元素插入指定位置

超范围插入

扩容一个数组容量为老数组2倍的新数组，然后将老数组数据拷贝到新数组，最后将新数组地址赋值给老数组

删除

中间删除

指定位置元素删除，其后的元素前移

尾部删除

读多写少场景

链表

单链表

双向链表

循环链表

双向循环链表

静态链表

特点：在物理上非连续、非顺序的数据结构，由若干节点所组成。随机存储

查找：只能从头结点开始按顺序查找

读少写多场景

栈

顺序栈

用数组实现

链式栈

用链表实现

先进后出，回溯，应用场景：递归、方法级联调用、面包屑

队列

普通队列

双端队列 deque

综合了栈和队列的优点

对头和队尾均可以入队或者出队

阻塞队列

并发队列

阻塞并发队列

循环队列

数组实现队尾：rear=(rear+1)%array.length; 对头：front=(front+1)%array.length; 能充分利用数组的空间，避免了数组元素的整理移动的麻烦

先进先出，应用场景：比如公平锁的等待队列，爬取网站url按入队顺序抓取和解析

结构

物理结构，内存中实实在在的存储结构

顺序存储结构

数组

链式存储结构

链表

逻辑结构，抽象的概念，依赖于物理结构而存在，可以使用任一物理结构实现

线性结构

顺序表

栈

队列

非线性结构

树

图

散列表 hash table

散列函数

jdk中的哈希函数并没有直接采用取模运算，而是使用了位运算的方式来优化性能

冲突解决

链表法

原理：数组中元素不仅仅是一个entry对象，
还是一个链表的头结点，当出现冲突时，
每一个entry对象通过next指针指向它的下一个entry节点。

使用场景：HashMap

开放寻址

原理：当一个key通过hash函数获得对应的数组下标已被占用时，
就寻找下一个可用的数组位置，
如果找不到或者达到了负载因子比例，就扩容后在寻址

使用场景：java中ThreadLocal

其他

动态扩容

当经过多次元素插入，散列表数组达到应饱和度，
key映射位置发生冲突的概率会逐步提高。这样一来，
大量元素拥挤在相同的数组下标位置，形成很长的链表，
对后续插入操作和查询操作的性能都有很大影响

散列表就需要扩展它的长度，数组的长度

JDK中HashMap，扩容条件size>=CapacityxLoadFactor 1 Capacity，
即hashMap的当前长度 22 LoadFactor,即HashMap的负载因子，默认0.75f

JDK中HashMap扩容过程：1 扩容，创建一个新的Entry空数组，长度是原数组的2倍
2 重新Hash,遍历原Entry数组，把所有的Entry重新Hash到新数组。
为什么要重新Hash？因为长度扩大了，
Hash规则随之改变。经过扩容，原本拥挤的散列表变得稀疏，
原有的Entry也重新得到了尽可能均匀的分配

位图

树

二叉树

平衡二叉树

二叉查找树

在二叉树上增加了几个条件

如果左子树不为股，则左子树所有节点的值均小于根节点的值

如果右子树不为空，则右子树上所有节点的值均大于根节点的值

左右子树也都是二叉查找树

平衡二叉查找树

AVL树

红黑树

树堆

完全二叉树

对于一个有n个节点的二叉树，按顺序层级编号，
则所有节点的编号为从1到n，如果这个树所有节点和同样深度
的满二叉树的编号从1到n的节点位置相同，则这个二叉树为完
全二叉树。只需要保证最后一个节点之前的节点都是满二叉即可，
最后一个节点可以不是满二叉

满二叉树

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点在同一层级上

存储

链式存储结构

数组存储结构

会按照层级顺序把二叉树的节点放到数组中对应的位置上。
如果某一个节点的左孩子或者右孩子空缺，则数组的相应位置也空出来。
比如12345X6X8 （X表示空置的位置）。
对于一个稀疏二叉树来说，用数组表示法是非常浪费空间的

主要应用于查找和维持相对顺序

1 二叉树的树形结构使它适合扮演索引的角色，比如二叉查找树。
时间复杂度 O(logn),和树的深度是一样的，和二分查找算法非常相似

2 要遵守二叉排序树的原则：左子树小于根节点，
右子树大于根节点，要保证平衡，否则为成为线性链表

自平衡算法

红黑树

AVL树

树堆

遍历顺序

深度优先遍历

前序遍历

根节点第一个，输出顺序：根节点、左子树、右子树。左子树遍历完了才遍历右子树

中序遍历

左子树第一个，输出顺序：左子树、根节点、右子树

后序遍历

左子树第一个，输出顺序：左子树、右子树、根节点

前中后的顺序是以根节点的位置定义。
前序指根节点在第一个。
中序指根节点在中间；后序指根节点在最后

遍历方式

递归

借助栈结构

广度优先

层序遍历，一层一层的遍历

借助数据结构：队列。根节点入队，根节点出队,，
获得左右子节点，子节点入队，左子节点出队，
获得左右节点入队，循环处理

多路查找树

B树

B+树

2-3树

2-3-4树

堆

小顶堆

任一个父节点的值，都小于或者等于子节点的值。子节点树不定。堆顶是整个堆中值最小的元素

大顶堆

任一个父节点的值，都大于或者等于子节点的值。子节点数不定。堆顶是整个堆中值最大的元素

优先级队列

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。使用大顶堆

最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。使用小顶堆

斐波那契堆

二项堆

二叉堆

完全二叉树，子节点数不能超过2个

小顶堆

大顶堆

存储顺序存储，所有节点存储在数组中。数组没有左右指针，如果定位左右子节点，依靠数组的下标，左子节点：2x父节点下标+1；右子节点：2x父节点下标+2

应用：堆排序及优先级队列的基础

如何构建堆

自动调整，把一个不符合堆的
树调整为一个符合堆特性的树

小顶堆

插入节点，上浮操作

O(logn)

删除节点，把堆最后一个节点临时补到根节点上，
然后子节点进行比较，如果比他们大，则做下沉操作

O(logn)

构建堆，本质上是让非叶子节点依次下沉

O(n)

大顶堆

插入节点，上浮操作

O(logn)

删除节点，下沉操作

O(logn)

构建堆，本质上是让非叶子节点依次下沉

O(n)

其他

树状数组

线段树

图

图的存储

邻接矩阵

临接表

拓扑排序

最短路径

关键路径

最小生成树

二分图

最大流

其他

数论

计算几何

概率分析

并查集

拓扑网络

矩阵算法

线性规划

复杂度

时间复杂度

最好

最坏

平均

均摊

渐进时间复杂度

大O表示法T(n)=O(*)

O(1)

O(n)

O(logn)

O(n^n)

空间复杂度

大O表示法S(n)=O(*)

基本算法思想

贪心算法

分治算法

动态规划

回溯算法

枚举算法

排序

O(n^2)

冒泡排序（bubble sort）

最小的往上冒，也即是最小的在前面，最大的在后面

相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或者等于右侧相邻元素时，位置不变

稳定排序

优化

1 设置有序标记，有序时跳出循环

2 每轮排序后，记录下最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了

3 鸡尾酒排序

元素比较和交换过程是双向的

第一轮从左到右

第二轮从右到左

第N轮

实现：外层循环控制所有排序回合，大循环内包含2个小循环，第一个小循环从左到右比较并交换元素（奇数轮）第二个小循环从右到左比较并交换元素（偶数轮）

实现：双重循环即可，外层负责循环的回合，内层负责比较值并交换值

插入排序

选择排序

希尔排序

O(nlogn)

快速排序,从冒牌排序演变而来

分治法，但仍属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。快速排序是很重要的算法，与傅里叶变换等算法并称为二十世纪十大算法

在每一轮挑选一个基准元素，并让其他比他大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆分成两个部分

基准元素(pivot)的选取

最简单的方式选择数列的第1个元素

遇到逆序要转换成顺序时，会退化为O(n^2)的排序

随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置

选定基准元素之后，要进行元素交换

双边循环法

单边循环法

递归和非递归实现

绝大多数递归，都可以用栈的方式来代替

空间复杂度O(logn)

不稳定排序

堆排序，使用堆(主要是二叉堆)的最大堆或者最小堆的堆顶元素时最大或者最小元素的特性，
删除堆顶元素后，堆调整后，堆顶又是第二大或者第二小的元素，循环删除，即得到有序数据

1 将无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。

2 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶

最坏时间复杂度O(nlogn)

空间复杂度O(1),没有新增额外的空间

归并排序

JDK Collections.sort采用归并排序或者Timsort

O(n)

计数排序

适用于取值范围不是很大的情况

需要借助一个数组，统计待排序数列中各个数值出现的次数，
以待排序中的最大值来决定统计数组的长度。数组长度=最大值+1

优化

数组长度=数列最大值-最小值+1 作为数组的长度；最小值作为偏移量，
用于计算数值在统计数组中的下标。那么一个数值在数组中的位置=数值-最小值，
即为实际数值在数组中的位置

比如95,93,91,98,99,90,99,93,91,92。不能创建长度99+1=100为数组，
会造成空浪费；以99-90+1=10长度的数组，就不会浪费空间

单纯排序没有问题

业务上要处理相同数值谁是谁的问，比如成绩，2个同学相同，
要看出哪个在前哪个在后时，还得继续优化

优化后的计数排序是稳定的排序

以一个空数组，值全部为0,数组大小为待排序数列中的最大值，以数组下标顺序作为待排序数列的对应值，比如值为3 ，就将数组下标为3的值+1；值为10，就将数组下标为10的值+1，有多个相同值时，下标对应的值就要+多次。最后，按数组小标列出统计值，出现多少次就输出几个。比如下标0的值为1（表示0出现1次），下标1的值为3（表示1出现3次）。输出排序后的梳理就是：0,1,1,1

计数排序强大，但是很少被使用，是有以下2个局限

1 当数列最大和最小值差距过大时，并不适用计数排序

比如给出20个随机整数，范围0到1亿之间，
这是如果用计数排序，需要创建长度为1亿的数组，
不但严重浪费空间，而且复杂度也会随之升高

2 当数列元素不是整数时，也不适用计数排序

比如数列中的元素都是小数，如25.124，
或者0.00,000,001这样的数字，则无法创建对应的统计数组，
这样显然无法进行计数排序

优化前是非稳定排序

基数排序

桶排序

弥补了计数排序的局限

1 桶(bucket):代表一个区间范围，里面可以承载一个或者多个元素

2 建多少个桶，如何确定桶的区间范围，有很多种不同的方式

桶的数量：最简单的方式，桶数量等于原始数列的元素数量，除最好一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定