我的博客
欢迎来到我的博客
bunny.icu

考研408笔记-数据结构

考研408笔记-数据结构

数据结构绪论

基本概念

  1. 数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单元。
  2. 数据对象是具有相同性质的数据元素的集合,是数据的一个子集。
  3. 抽象数据类型(ADT)是指一个数学模型及定义在该模型上的一组操作。
  4. 数据的逻辑结构:线性结构(线性表、栈、队列)、非线性结构(图、树)。
  5. 数据的存储结构:
    1. 顺序存储:可以实现随机存取,只能使用相邻存储单元
    2. 链式存储:不要求在物理上相邻,指针占用额外空间
    3. 索引存储:检索速度快,索引表占用额外空间,修改时还需要修改索引表,花费较多时间
    4. 散列存储:检索存储都很快,但如果散列函数不好,可能出现冲突,解决冲突需要额外时间和空间
  6. 算法的五个特征:有穷性、确定性、可行性、输入、输出。
  7. 算法要实现的目标:正确性、可读性、健壮性、效率与低存储量需求。
  8. 一般总是考虑最坏情况下的事件复杂度,以保证算法的运行事件不会比它更长。
  9. 常见的渐进时间复杂度:O(1)<(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
  10. 原地工作算法指算法所需的辅助空间为常量,即O(1)
  11. 非递归算法的执行效率通常高于递归算法。

线性表

顺序表示

顺序存储方式并非只能用于存储线性结构还能用于图和树的存储,如满二叉树的顺序存储。

链式表示

链式存储可以方便地表示各种逻辑结构,因为链式存储用指针表示逻辑结构,而指针的位置是任意的。顺序存储只能用物理上的邻接关系来表示逻辑结构。

单链表

头结点可以不设任何信息,也可以记录表长等相关信息,头结点指针域指向线性表的第一个元素结点。

单向循环链表,只有表尾的比只有表头的强。

双链表

单链表的插入、删除算法的主要时间耗费在前驱结点的查找上,而双链表可以很方便的找到其前驱结点。

双链表插入、删除结点算法的时间复杂度为O(1)

静态链表

需要分配较大的存储空间,因为静态链表用数组表示。

比较

对于按值查找,顺序表无序时,顺序表和链表的时间复杂度都是O(n),顺序表有序时,可采用这边查找,顺序表的时间复杂度时O(log_2 n)

对于按序号查找,顺序表的事件复杂度是O(1),链表的时间复杂度是O(n)

链表在空间分配上比线性表灵活。

栈和队列

只允许在一端进行插入或删除操作的线性表。

将递归算法转换为非递归算法。通常需要借助栈来实现。

顺序存储

共享栈

对效率没有影响。

两个栈的空间相互调节。

链式存储

称为栈链。

不会出现栈满的情况

队列

顺序存储

循环队列

在不出现循环的情况下,队尾比队首大。

入队:队尾指针加1取模

出队:队首指针加1取模

队空状态(初始化)

先考虑存放一个元素的情况,再进行入队的逆运算。

队满状态

先考虑缺少一个元素的情况,再将一个元素入栈,建立队头队尾指针的关系。

链式存储

用链表形式存储时,删除元素从队头删除,一般情况下不需要求改队尾,但是如果队列中只有一个元素,删除队头后rear指针就没有了指向的元素,这时需要求改队尾指针为rear=front。

双端队列

输出受限

先写出选项给出的输出序列,再判断输入是否能满足该输出序列。

输入受限

先写出唯一的输入序列,在判断题目给出的输出序列是否能出现。

应用

栈的应用

括号匹配

表达式求值

递归算法

迷宫求解

进制转换

队列的应用

页面替换算法

树的层次遍历

图的广度优先搜索

解决速度不匹配、资源竞争问题(缓冲区)

特殊矩阵

对称矩阵

三角矩阵

三对角矩阵

稀疏矩阵

树的概念

树是边数比顶点数少1的连通图。

树的路径长度:树根到每个节点的路径长度的总和。

树的度数:树中节点的最大度数。

总节点数=总分支数+1,在许多计算中要利用此等式构造方程。

二叉树的概念

子树有左右之分。

二叉树可以为空,可以只有一个根节点,这两种树不是度数为2的树。

n_0=n_2+1

二叉树的最小高度为h=\log_2(n+1)

特殊二叉树

满二叉树

除最后一行外,所有的节点的度数都是2。

完全二叉树

除最后两行外,所有节点的度数都是2,倒数第二行靠前的节点度数都是2,靠后的节点度数都是1。

二叉排序树

左子树上所有节点的关键字均小于根节点上的关键字,右子树上所有关键字均大于根节点上的关键字。左子树和右子树又各是一棵二叉排序树。

平衡二叉树

任一节点左右子树深度之差不超过1。

存储

顺序存储

适用于满二叉树和完全二叉树,如果存放的不是这两种树,会浪费较多的存储空间。

链式存储

有数据域和左、右孩子指针

二叉树的遍历

先序、中序、后序

由先序遍历和中序遍历、中序遍历和后序遍历可以唯一地确定一棵树,先序遍历和后序遍历不能。

非递归

借助栈

层次遍历

借助队列

由遍历构造二叉树

线索二叉树

线索二叉树是一种物理结构。

引入线索二叉树是为了加快查找节点前驱和后继的速度。

中序线索化二叉树后,遍历不再需要借助栈,因为它的节点中隐藏了线索二叉树的前驱和后继信息。

n个节点的线索二叉树有n+1个线索。

标志域

0表示指针域指向左/右孩子

1表示指针指向前前驱/后继

不能解决的问题

因为没有指向根节点方向的指针,所以先序线索二叉树不能解决求先驱的问题,后续线索二叉树不能解决求后继的问题。

也正因如此,后序线索树的遍历仍需要栈的支持。

中序线索二叉树不存在这样的问题,因为先驱和后继都在下方。

森林

一棵树也可以称为森林。

存储

双亲表示法

孩子的指针指向双亲。

孩子表示法

将孩子用单链表连接起来。

孩子兄弟表示法

左指针指向第一个孩子,右指针指向兄弟。

森林、树、二叉树的转换

森林、树转换为二叉树:左指针指向第一个孩子,右指针指向相邻兄弟节点。

二叉树转换为树、森林同理。

树转换为二叉树,二叉树的根结点一定无右孩子。

应用

二叉排序树

若左子树非空,则左子树上所有结点关键字值均小于根节点的关键字的值。

若右子树非空,则右子树上所有结点关键字值均大于根节点的关键字的值。

左、右子树本身也分别是一棵二叉排序树。

删除

右子树空,用左子女填补。

左子树空,用又子女填补。

左右子树均不空,找中序第一个子女填补。

查找

对于高度为h 的二叉排序树,其插入和删除操作的运行时间都是O(h),如果二叉排序树是一个只有左、右孩子的单支树,运行时间是O(n),如果是平衡二叉树,运行时间是O(\log_2 n)

平衡二叉树

结点左右子树高度差为该结点的平衡因子。

构造

构造n层平衡二叉树所需的最小结点数为h_n=1+h_{n-1}+h_{n-2}, n_0=0, n_1=1

给的层数条件下,如果节点数最小,所有的非叶节点度都是1。

插入

在左孩子的左子树上插入新的结点,需要一次向右的旋转操作。

在右孩子的右子树上插入新的结点,需要一次向左的旋转操作。

在左孩子的右子树上插入新的结点,需要一次向左一次向右的旋转操作。

在右孩子的左子树上插入新的结点,需要一次向右一次向左的旋转操作。

插入的结点不一定是叶结点,因为可能会有平衡调整。

查找

含有n个结点的平衡二叉树深度为log_2 n,所有平衡二叉树的平均查找长度为O(log_2 n)

哈夫曼树

哈夫曼树是所有结点度为均0或m的树,m不一定为2。

用哈夫曼树可以设计出长度最短的二进制前缀编码。

任何编码都不是其他编码的前缀,这种编码称为前缀码。

对一组权值构造出来的哈夫曼树并不是唯一的。

不能仅依照长度来判断哈夫曼编码是否正确。

父节点的权值等于左右孩子的权值之和。

概念

  1. 线性表可以为空表,树可以为空树,但图不可以是空图。图的顶点集V一定非空,但边集G可以为空。
  2. 如果图G不存在重复边,不存在顶点到自身的边,则称图G为简单图。
  3. 多重图是跟简单图相对的概念。
  4. 完全图(也称简单完全图),是指任意两个顶点之间都有边的无向图,或任意两个顶点之间都有两个方向相反的两条弧的图。完全图属于简单图。
  5. 连通:两点之间路径存在。
  6. 如果无向图G中任何一对顶点都是连通的,则称图G为连通图。
  7. 无向图中的极大连通子图称为连通分量。
  8. 如果有向图G中任何一对顶点都是强连通(双向连通)的,则称图G为强连通图。
  9. 有向图中的极大连通子图称为强连通分量。
  10. 生成树是包含图中全部顶点的一个极小连通子图。非连通图可以生成森林。
  11. 无向图边的数量等于个顶点的度数之和。
  12. 边最少的无向图是树,边最少的有向图是环。
  13. 简单路径:顶点不重复出现。

存储

邻接矩阵

用一个一维数组存储顶点的信息,用一个二维数组存储边的信息。

稠密图适合用邻接矩阵表示。

表示带权有向图时,0和 \infty都不是有向边。

在一行中出现的次数表示出度,在一列中出现的次数表示入度。

邻接表

为图中每一个点建立一个单链表,结点表示依附于该顶点的边。

对有向图而言,结点表示以该边为尾的弧。

稀疏图适合用邻接表表示。

边表不包括顶点表。

顶点在边表中出现的次数之和表示该点的入度。

十字链表

用于存储有向图。

有顶点结点和弧结点,顶点结点的指针指向以该顶点为弧头、弧尾的第一个结点。

弧结点存储弧头、弧尾结点,指针指向与该弧弧头相同的下一条弧、与该弧弧尾相同的下一条弧。

邻接多重表

与十字链表类似,用来存储无向图。

遍历

基于邻接矩阵的遍历所得到的BFS序列和DFS序列是唯一的。

基于邻接表的遍历所得到的BFS序列和DFS序列不是唯一的。

广度优先

需要借助队列。

解决单源最短路径问题。

深度优先

类似树的先序遍历。

利用递归。

深度优先遍历可以判断图中是否存在回路。

图的连通性

如果图是连通的,从任意结点出发,一次遍历就可以访问途中所有顶点。如果图不是连通的,一次遍历只能访问到该顶点所在的连通分量。

应用

最小生成树

生成树是图的极小连通子图。

边的权值之和最小的生成树是最小生成树。

各边权值互不相等时,最小生成树是唯一的。 (这是充分不必要条件)

树的最小生成树是它本身。

prim算法

每次选一个顶点,加入到已构造的最小生成树中。

Kruskal算法

每次找权值最小且不形成环的边,时间复杂度为O(e\log_2e),其中O(\log_2e)是并查集的时间复杂度。

最短路径

Dijkstr算法

每次得到一个点的最短路径。时间复杂度为O(n^2)

Floyd算法

每次尝试在原路径中加入中间点,用更短的路径代替原路径。时间复杂度为O(n^3)

拓扑排序

从没有前驱的顶点开始。

若一个顶点有多个直接后继(出度>1),则拓扑排序的结果通常不唯一。

连通图的一个顶点出度为0,其他所有顶点出度为1的,则这个图的拓扑序列唯一。(这是充分不必要条件,参考P222第19题)

关键路径

以下概念中,最迟\geq最早。

最早发生时间

起点到此点的最长路径。

最迟发生时间

起点到终点的最长减此点到终点的最长。

最早开始时间

起点到事件的最长。

最迟开始时间

起点到终点的最长减此事件到终点的最长。

关键路径

最迟开始时间=最早开始时间的活动所在的路径为关键路径。

如果关键路径有多条,减短所有关键路径,才能达到缩短工期的目的。

查找

顺序查找

平均查找长度的计算:概率*当前长度

在一般线性表的顺序查找中,如果查找成功,平均查找长度为$\text{ASL}{成功}=\frac{n+1}2;如果查找失败,查找长度为\text{ASL}{失败}=n+1在有序表的顺序查找中,无论查找成功还是失败,平均查找长度都是\text{ASL}=\frac{n+1}2顺序查找的缺点是当n$较大时,平均查找长度较大,效率低;优点是对存储没有要求,顺序存储或链式存储皆可。

折半查找(二分查找)

适用于有序表。要求顺序存储。

查找过程对应的判定树是一棵二叉排序树。

判定树也是一棵平衡二叉树。

查找过程对应的判定树中所有的左右子树结点数相差1或相等,同一判定树中取整规则需固定(只能左子树多结点多1或只能右子树结点数多1)。

折半查找成功时,平均查找长度为\text{ASL}=\log_2(n+1)-1,效率高于顺序查找。

时间复杂度为O(\log_2 n)

分块查找

将查找表分成若干子块,块内元素可以无序,块之间要求有序。每个块的最大关键字小于下一个块中的所有关键字。再建立一个索引表,索引表中每个元素含有各块的最大关键字和第一个元素地址。

分块查找先在索引表中确定待查记录所在的块,再在块中使用顺序查找。

当块的数量s=\sqrt n时,平均查询长度取最小值\sqrt n+1

B树

定义

符合以下条件的多叉树称为m阶B树:

  1. 除根结点外,每个节点至少\lceil{m/2}\rceil-1个关键字,至少\lceil{m/2}\rceil个分叉
  2. 任何结点的所有字数高度相同
  3. 关键字有序

查找

略。

插入

如果插入后关键字个数等于m,必须对结点进行分裂。

分裂方法:将中间位置(⌈m/2⌉)的元素插入到原结点的父结点中,父结点关键字也超过上限,继续分裂,直至分裂过程传到根结点导致B树高度增1。

删除

  1. 删除非根结点关键字,用直接前驱或后继根结点的关键字填补删除的关键字,转换成删除根结点关键字的问题
  2. 删除根结点关键字,如果删除后所在结点的关键字少于⌈m/2⌉ – 1
    1. 如果左兄弟或右兄弟关键字多于⌈m/2⌉ – 1个,找兄弟结点借一个关键字,即可完成删除过程
    2. 如果左兄弟和右兄弟都只有⌈m/2⌉ – 1个关键字,就把删除关键字后的结点、兄弟结点、父结点两者之间的关键字进行合并,如果合并后父结点关键字少于⌈m/2⌉ – 1个,就继续合并父结点、叔结点、爷结点

B+树

定义

符合以下条件的多叉树称为m阶B+树:

  1. 每个分支结点最多有m棵子树,除根结点外最少有\lceil{m/2}\rceil棵子树
  2. 结点分支数等于关键字数,结点的值是分支结点的最大值
  3. 叶节点包含全部关键字
  4. 任何结点的所有子树高度相同
  5. 关键字有序

B+树与B树的不同之处

结点的子树与关键字数量相等。

结点关键字数量限制与B数不同。

非叶结点仅起索引作用,叶结点包含全部关键字,。

B+树支持顺序查找,而B树不能。

B+树根结点可以链接起来,支持顺序查找。

应用

数据库索引。

散列表

散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数。

任何设计出来的散列函数都不可能绝对地避免冲突。

理想情况下,对散列表查找的时间复杂度为O(1)

构造

散列函数的构造方法不用记。

处理冲突

发生聚集的原因是解决冲突的方法选择不当。

开放地址法

对于冲突,查找下一个空闲单元。

同义词在散列表中不一定相邻,中间可能有非同义词。

拉链法(链地址法、链接法)

把同义词存储在一个线性链表中。

性能

散列表的填充因子\alpha表示一个表的装满程度,即:

\alpha=\frac{\text{表中记录数}n}{\text{散列表长度}m}

模式匹配

求字串在主串中的位置

KMP算法

i指针不需要回溯,仅将字串向后滑动,滑动长度为最长相等前后缀长度。

next数组

next[0]=0,next[1]=1

next[n]=字符串前n字符号的最长相等前后缀长度+1。

失配后下次匹配时,j=next[j]

并查集

逻辑结构:集合

表示方式:森林

每个集合用一颗树表示,用一个长度为n的一维数组记录

元素值为父结点下标,根结点用负值表示

并(Union)

把一棵树作为另一棵树的根结点的子结点

不论是否优化时间复杂度都是:O(1)

并的优化

树很高时查找效率低,所以合并操作需要优化

用根结点的绝对值表示该集合元素的总个数

每次把小树作为大树的子结点

查(Find)

查找一个结点在哪个即可,可以找对应的树的根结点

判断两个结点书否属于是否属于同一个集合,可以根据是否属于同一个根结点来判断

Union优化前最坏的情况时间复杂度:O(n)

Union优化后最坏的情况时间复杂度:O(\log_2n)

应用

判断图的连通分量:构造并查集数组,查找有几个小于0的数

判断图是否有环:构造并查集,如果属于同一个集合的两个结点之间有边,就一定有环

Kruskal算法:用并查集避免出现环

三个应用本质上都是用并查集来判断顶点之间是否连通

红黑树

定义

红黑树是相对平衡的二叉搜索树

红黑树的特点:

  1. 结点是红色或黑色
  2. 根结点是黑色
  3. 叶结点是黑色,是失败结点
  4. 红色结点的孩子是黑色
  5. 从任何结点出发到所有空叶子的路径中黑色结点数量相等

助记:左根右,根叶黑,不红红,黑路同

性质

只有结点的路径最短,红黑交替的路径最长

红黑树可以保证最长路径不超过最短路径的两倍,所以说红黑树是相对平衡的二叉搜索树

优点:相对平衡;插入结点比较简单

插入

插入的新结点都是红色,如果不违法“不红红”的特征,就不用调整

如果违法“不红红”的特征,就要调整,看叔叔脸色行事

  1. 叔叔是黑色:旋转 + 染色
    1. LL:右单旋,父换爷 + 染色(原本的父和爷染色)
    2. RR:左单旋,父换爷 + 染色(原本的父和爷染色)
    3. RL:左右双旋,儿换爷 + 染色(原本的儿和爷染色)
    4. LR:右左双旋,儿换爷 + 染色(原本的儿和爷染色)
  2. 叔叔是红色:染色 + 变新(染色后爷结点视为新结点)
    1. 叔父爷染色,爷变新结点,再判断新结点是否违反红黑树特性;如果红色传递到根结点,直接涂黑即可

排序

概念

稳定性:如果相等的关键字在排序后次序不变,则称排序算法是稳定的。稳定性并不能衡量算法的优劣。

内部排序:在排序期间元素是全部放在内存中。内部排序算法在执行过程中通常要进行两部操作:比较和移动。

外部排序:排序期间元素无法全部同时存放在内存中,不许再内、外存中移动。

插入排序

在基本有序时速度较快 。

直接插入排序

每次处理未排序的第一个元素,将其向左移动到已排序元素的适当位置,重复此过程直到整体有序。
序列基本有序的情况下适合用直接插入排序。
最好情况是序列已经有序,时间复杂度为O(n)
平均和最坏情况的时间复杂为是O(n^2)
空间复杂度为O(1)

折半插入排序

将比较和移动分离。

比较次数比直接插入排序少。

时间复杂度:O(n^2)

希尔排序

每次循环选取一个步长(例如数组长度的一半),将距离等于步长的元素作为一组,各组组内进行直接插入排序。下次循环步长-1,重复此过程直到步长为1,即可完成排序。
最好情况与直接插入排序相同,即序列已经有序,时间复杂度为O(n)
平均情况下时间复杂度约为O(n^{1.3})
最坏情况为逆序,时间复杂度为O(n^2)
空间复杂度为O(1)

不稳定。

交换排序

冒泡排序

从右往左比较相邻的两个元素,如果右边的元素小于左边,则交换位置,每次循环会把未排序的最小元素换到最左边,重复此过程直到整体有序。
有一种优化方式,是用flag记录此轮循环中是否发生过交换,如果一次都没交换,则说明排序已经完成,可以直接结束。考研408默认采用这种方式。
优化后的冒泡排序最好情况为序列已经有序,时间复杂度为O(n)
平均和最坏情况时间复杂度为O(n^2)
空间复杂度为O(1)

快速排序

每次选取一个元素作为枢轴pivot(例如最左边的元素),将比枢轴小的元素换到左边,比枢轴大的元素换到右边,得到左右两个子序列,对两个子序列分别递归调用此方法,直到每个序列只有一个元素。
快速排序的辅助空间用于记录递归树,因此空间复杂度等于递归深度。
最好和平均情况时间复杂度为O(n\log_2n),递归深度为\log_2n,空间复杂度为O(\log_2n)
最坏情况为序列已经按顺序或逆序排列,时间复杂度为O(n^2),因为此时的枢轴不能将序列分为两个子序列,递归深度为n,空间复杂度为空间复杂度为O(n)
有一种优化的方式是取随机位置的元素作为枢轴,而不是第一个元素,这样可以避免最坏情况时间和空间复杂度过大的问题。考研408默认不采用这种方式。

每经过一趟排序,会有一个元素(枢轴)处于最终位置。

选择排序

简单选择排序

每次循环找到未排序的最小的元素,与未排序的第一个元素交换,重复此过程直到整体有序。

时间复杂度:O(n^2)

比较次数始终为n(n-1)/2

不稳定。

堆排序

堆的定义:根节点大于等于或小于等于孩子结点。

调整:从右到左,从下到上

建堆时间:O(n)

最好、最坏、平均时间复杂度:O(n\log_2 n)

不稳定。

归并排序

归并排序的思想是“分而治之”。
“分”的过程是如果元素数量大于1,则将序列分为尽可能等长的两个子序列。
“治”的过程是将子序列两两合并,合并后的序列内部是有序的,重复合并过程直到全部完成。
所有情况的时间复杂度均为O(n\log_2n),空间复杂度为O(n),辅助空间用于记录子序列。
归并排序可用于外部排序,数据占用的存储空间大于内存也能使用,因为子序列合并的过程不需要把全部数据读取到内存中。

基数排序

空间复杂度:O(r)

时间复杂度:O(d(n+r)),与初始状态无关。

只能对整数排序。

稳定。

内部排序比较

排序法 最好情况 平均情况 最坏情况 是否稳定 额外空间 备注
插入 O(n) O(n^2) O(n^2) O(1) 大部分已排好序时较好
冒泡 O(n) O(n^2) O(n^2) O(1) n较小时好
选择 O(n^2) O(n^2) O(n^2) O(1) n较小时好
希尔 O(n) O(n^{1.3}) O(n^2) O(1) 复杂度依赖于增长序列的函数,此数学问题尚未解决
快速 O(n\log_2n) O(n\log_2n) O(n^2) O(\log_2n)\sim O(n) n较大时好
O(n\log_2n) O(n\log_2n) O(n\log_2n) O(1) n较大时好
二路归并 O(n\log_2n) O(n\log_2n) O(n\log_2n) O(n) n较大时好
基数 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) B是真数(0~9),R是基数(个十百)

绝大多数内部排序只适用于顺序存储结构。

外部排序

外部排序通常采用归并排序方法。

增加归并路数可以减少归并次数,从而减少磁盘的I/O次数。

败者树

如果不用败者树,从m个元素中选择关键字最小的记录需要比较m-1次,每趟n个递归元素需要做(n-1)(m-1)次比较。

如果用败者树,比较次数就是这棵完全二叉树的深度\lceil\log_2 n\rceil,每趟n个递归元素需要做\lceil\log_2 n\rceil\cdot m次比较。

置换-选择排序

生成外部排序初始归并段。

在外部排序中,输入/输出缓冲区就是排序的内存工作区,做m路平衡归并排序需要m个输入缓冲区和1个输出缓冲区。

m路平衡归并排序,为实现输出/内部归并/输出的并行处理,需要设置2m个输入缓冲区和2个输出缓冲区。

最佳归并树

设计m路归并的优化方案。

是将哈夫曼树推广到m叉树的情形,记录数最多的最晚归并,缺额的归并段留到最后。

Reference

https://www.youtube.com/watch?v=pdjPmgzuSQI

版权声明


本作品系原创, 转载须遵循 CC BY-NC-ND 4.0 许可协议
本文标题:考研408笔记-数据结构
本文链接:https://www.bunny.icu/archives/891

推荐文章

发表评论

textsms
account_circle
email

bunny.icu

考研408笔记-数据结构
考研408笔记-数据结构
扫描二维码继续阅读
2021-12-28