2023数据结构重点梳理

type

status

date

slug

summary

数据结构重点(from 吴昊)

一.进出栈操作,可能或不可能出栈的序列

1.进出栈操作

进栈 (Push) 和出栈 (Pop) 操作是指在栈这种数据结构中的两种基本操作。栈是一种具有后进先出 (LIFO) 特性的数据结构，类似于我们平时堆叠的一叠书。

进栈操作将元素放入栈的顶部，而出栈操作将栈顶元素移除。

下面是进出栈操作的示例：

进栈 (Push) 操作：

将元素放入栈顶

栈顶指针上移

出栈 (Pop) 操作：

移除栈顶元素

栈顶指针下移

进栈和出栈操作可以用于构建各种算法和数据结构，如函数调用堆栈、括号匹配、表达式求值等。

2.可能或不可能出栈的序列

1.理论分析与结论

对于一个给定的序列，判断是否能够通过进栈和出栈操作得到该序列是一个常见的问题。以下是一个判断序列是否可能出栈的例子：

给定一个序列 [a, b, c, d, e]，以下是可能的进栈和出栈序列：

进栈序列：a, b, c, d, e

出栈序列：e, d, c, b, a

在此序列中，我们按照 a, b, c, d, e 的顺序进栈，并按照 e, d, c, b, a 的顺序出栈。这是一种可能的进出栈序列。

这里有一规律可记 　　任何出栈的元素后面出栈的元素必须满足以下三点：　　1、在原序列中相对位置比它小的，必须是逆序； 　　2、在原序列中相对位置比它大的，顺序没有要求； 　　3、以上两点可以间插进行。

结论:后入栈的,出栈后比他先入栈且还未出栈的一定倒序排在后面(对每一个元素都适用!)

因此可以有一下思路:

选择一个元素(可以从第一个开始依次判断)

根据该元素判断已入栈元素(例如下面例子中选择出栈元素D则可判断出ABCD肯定都已入栈)

查看该元素在出栈序列前的元素,判断已出栈元素

判断已入未出是否满足结论要求

2.案例分析

技术之瞳阿里巴巴技术笔试心得习题2.65： 　　一个栈的入栈序列为ABCDEF，则不可能的出栈序列是（D）　　A、DEFCBA　　　　B、DCEFBA　　　　C、FEDCBA 　　D、FECDBA　　　　E、ABCDEF　　　　F、ADCBFE

分析:此处考察栈的先进后出特性,且此处的入栈和出栈顺序是未知的有可能入栈中穿插出栈:

例如可以先入栈ABCD,后出栈D，然后入栈E，出栈E，入栈F，出栈F，然后CBA依次出栈，也就是A选项的情况。

B选项并未出现结论的情况,顺序可以为:ABCD入栈,D,C出栈,E入栈E出栈,F入栈F出栈,BA出栈.

C选项并未出现结论的情况,顺序可以为:ABCDEF入栈然后顺序出栈

E选项虽然直观上完全不符合先进后出,但是可以出栈是穿插在入栈中的,因此即进即出即可满足,且也满足结论要求

F选项并未出现结论的情况,顺序可以为:A入A出,BCD入DCB出,EF入FE出

D选项的错误出在"CD"上,E之前F出栈则ABCD均为出栈,因此都应该是倒序,而CD是正序,则与结论相悖,答案错误

二.矩阵中求某个位置的地址,或给出地址求对应位置

三.特殊矩阵的用一维存储的映射函数

首先回顾有关于矩阵的几种数据类型

1.数组

1.1一维数组

一维数组起始地址设置为Loc,数组中每个元素大小都相同,且存储时是连续存放的.

数组元素a[i]的存放地址=Loc+i*sizeof(ElemType),其中0≤i≤(n-1)

1.2二维数组

二维数组有两种存储方式，分别是行优先存储和列优先存储

对于M行N列的二维数组b [M] [N]，设二维数组b的初始地址为Loc，则：

（1）若按行优先存储，则bi的存储地址=Loc+(iN+j)*sizeof(ElemType)。

（2）若按列优先存储，则bi的存储地址=Loc+(jM+i)*sizeof(ElemType)。

2.矩阵

2.1普通矩阵

学过线性代数就不必多说了,可以按照二维数组存储方式

注意:描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始。

2.2特殊矩阵

注意,本节及一下讨论的都是方阵

2.2.1对称矩阵

若n阶方阵中任意一个元素aij都有aij=aji，则该矩阵为对称矩阵。按普通的存储方式即二维数组存储就浪费存储空间了。

对称矩阵的压缩存储策略：只存储主对角线和下三角区或者主对角线和上三角区。

2.2.1.1 策略1以及对应映射函数

存储策略:只存储主对角线+下三角区的元素,并且按行优先原则将各元素存入一维数组,因此需要存储(n+1)*n/2个元素.存储是为了使用，因此存储方式要使得访问矩阵中的某个元素时能很快找到它.可以实现映射函数:将矩阵元素a[i] [j]的下标映射为一维数组的b[k]的下标,其中i,j从1开始到n,k从0到(n+1)*n/2 - 1.因此矩阵的a[i][j]元素对应于一维数组的：

i≥j时是b[i(i-1)/2+j-1]；

i<j时是b[j(j-1)/2+i-1]。

2.2.1.2 策略二以及对应映射函数

存储策略：只存储主对角线+下三角区的元素，并且按列优先原则将各元素存入一维数组中，因此需要存储(n+1)*n/2个元素。存储是为了使用，因此存储方式要使得访问矩阵中的某个元素时能很快找到它。可以实现一个映射函数——将矩阵元素a[i] [j]的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2-1。因此矩阵的ai元素对应于一维数组的：

i≥j时是b[(2n-j+2)(j-1)/2+i-j]；

i<j时是b[(2n-i+2)(i-1)/2+j-i]。

2.2.2三角矩阵

2.2.2.1 上三角矩阵

上三角矩阵：除了主对角线和上三角区，其余的元素都相同，如下：

存储策略：按行优先原则将两个阴影部分合成的三角形区域的元素存入一维数组中，并在最后一个位置存储常量c，因此需要存储(1+n)*n/2+1个元素。可以实现一个映射函数——将矩阵元素a[i] [j]的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2。因此矩阵的ai元素对应于一维数组的：

i≤j时是b[(2n-i+2)(i-1)/2+j-i](列优先公式);

i<j时是b[(1+n)*n/2]。

2.2.2.2 下三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同，如下：

存储策略：按行优先原则将两个阴影部分合成的三角形区域的元素存入一维数组中，并在最后一个位置存储常量c，因此需要存储(1+n)n/2+1个元素。可以实现一个映射函数——将矩阵元素a[i] [j]的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)n/2。因此矩阵的ai元素对应于一维数组的：

i≥j时是b[i(i-1)/2+j-1](行优先公式)；

i<j时是b[(1+n)*n/2]。

2.2.3 三对角矩阵

三对角矩阵又称带状矩阵：当|i-j|>1时，有a[i][j]=0，其中1≤i,j≤n。

存储策略：按行优先原则，只存储带状部分，因此需要存储3n-2个元素。可以实现一个映射函数——将矩阵元素ai的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到3n-3。因此矩阵的ai元素对应于：

|i-j|>1时是0；

|i-j|≤1时是一维数组的b[2i+j-3]。

有一个问题，若已知数组下标k，如何得到矩阵的i,j？b[k]是数组中第k+1个元素，对应于矩阵的第i=⌈(k+2)/3⌉行第j=k-2i+3列的元素，⌈m⌉是对m向上取整。

2.2.4 稀疏矩阵

稀疏矩阵是非0元素远少于矩阵元素个数的矩阵,0很多

存储策略1:使用顺序存储三元组<行,列,值>

存储策略2:使用链式存储三元组<行,列,值>,即十字链表法,其中非0数据的节点如下:

全部节点如下

上图中：绿色为向右域right，指向第i行的第一个元素，红色为向下域down，指向第j列的第一个元素。

4.七种排序的算法思想,伪代码或第二轮or第三轮的排序结果

先放一张图镇楼

1.冒泡排序(交换排序之一)

1.原理：

在无序区间中，将两两相邻的元素进行比较，每一轮比较出最大的一个元素，交换到有序区间。

2.步骤：

1.冒泡排序的主要思想是两两比较，因此先确定要比较多少次，因为前面经过比较只剩最后一个元素的时候，最后一个元素必定已经有序，因此，如果有n个元素，只需要比较n-1次。

2.进行两两比较的过程，从第一个元素开始，把它与它两两相邻的元素比较，把大的换到右边，一直比较，直到把数组里最大的元素换到最右边，因为只需要比较到倒数第二个元素的时候，它与倒数第一个元素比较已经可以换到最右边，因此下标只需要到数组的倒数第二个就行。

3.实现

这个实现方法其实与我们常认为的冒泡排序,也就是从第一位开始与下一个比较有所不同

若将原序列”倒置”,也就是将0 index在上,MAX Index在下竖向放置,则此算法更为形象的表现了”冒泡”的状态

2.快速排序(交换排序之二)

高手来的最快的一集,都什么年代还不会用快排?

1.原理

从待排序的区间取一个基准值，比基准值大的放到基准值的右边，比基准值小的放到基准值的左边，对于左右两边，再次重复这样的步骤。

快速排序是冒泡排序的改进算法，它采用了分治的思想，将原问题划分为若干个规模更小的子问题，子问题的依旧与原问题是相似的，递归解决所有的子问题，也就解决了原问题。

2.步骤(每一次递归)

1.从待排序区间取一个数作为基准值

2.遍历待排序区间，把所有比基准值小的数放到基准值的左边，比基准值大的放到基准值的右边，这个过程使用专业的术语叫做partition.

3.对于基准值的左右两边重复以上过程，直到整个序列变得有序。

3.实现

光说原理体会不到其精妙之处,直接来看代码吧

一行代码,别急,这只是对递归函数的一层包装罢了,继续看核心函数QSort:

很直观吧,经典的前后分治递归,重点在于partition函数是如何实现计算枢轴量的,再来看:

3.直接选择排序(选择排序之一)

1.原理：

每一次从无序区间选出最大（或者最小）的元素，放在有序区间的最后（或者无序区间的最前），直到所有的元素有序。

2.步骤：（此步骤针对无序区间在前，有序区间在后）

1.找到到无序区间的最大值元素的下标

2.将无序区间最大值元素的下标交换到有序区间的最后一个

3.重复此过程，直到数组有序

3.实现

4.堆排序(选择排序之二)

1.原理：

堆排序也是选择排序中的一种，找到无序区间中的最大值（或者最小值），将它交换到有序区间的最后（或者无序区间的最前）。与直接选择排序最大的不同在于，它不在使用遍历的方式来寻找无序区间的最大值（或最小值），而是通过创建堆的方式来创建最大值（或者最小值）。

将待排序序列构造称成一个大顶堆,此时整个序列最大值就是堆顶根节点,将其移走(其实是于堆数组末位元素交换,此时末位元素到达根节点位置),然后将剩余的序列重新构造为大顶堆.如此反复执行便可

2.步骤：

1.创建堆，要创建堆，先实现向下调整。所谓向下调整,便是遍历所有的非叶子节点,从下往上,从右到左将每个非叶子节点作为根节点,将其和其子树调整为大顶堆

2.创建堆以后，堆顶元素就是最大值，找到了最大值就将它交换到最后，放到无序区间的最后

3.放到无序区间最后以后，再从堆顶进行向下调整，调整长度减掉有序区间的长度

3.实现

先来看主方法代码:

再来看看关键函数HeapAdjust(堆调整)函数是如何实现的:

总之是比较目标节点和其孩子节点,谁最大谁做根.

5.直接插入排序(插入排序之一)

1.原理：

每次在无序区间选择无序区间的第一个元素，在有序区间找到合理的位置插入。可以将它想象成平时打牌我们对于扑克牌的排序。

2.步骤：

1.遍历整个无序区间，循环选择无序区间的第一个元素

2.在有序区间找到合适的位置，进行插入即可。（在插入时，要提前把不合适的位置往后搬）

3.实现:

其中r[0]是空位,初始可以设置为0,作为整体移动时用于比较大小的哨兵

6.归并排序

1.原理:

归并排序的原理是原序列先分割成一个一个的小的子序列，先使每个子序列有序，再将子序列合并，得到一个完整的有序序列，这就是归并排序。

2.步骤（我这里采用二路归并）：

1.先将原来的无序序列分割成若干个子序列，当分割到一个序列里只有一个元素时说明分割完毕。

2.再将分割后的子序列不断归并，归并的原理是合并两个有序的子序列，一直归并，直到归并得到一个完整的序列。

3.实现

先看主程序:

主程序就一行代码,还是对核心函数的一层包装,.因为核心函数使用了递归调用.

再看核心函数MSort的实现:

现在来看看Merge函数的代码实现

7.桶/箱排序

桶排序(或称箱排序)并不是一个具体的排序，而是一个逻辑概念。

之所以叫桶，是因为他会根据数据状况设计出一个容器，里面每个index将相当于一个桶。在遍历数据的时候将根据划分将数据一次放入每个桶中，遍历结束后将桶依次倒出。在每个桶内部，数据会被处理成有序结构。具体操作可以参考记数排序。

核心思想就是大问题化小,按照一定规则将待排序数据放入数个桶中,并用其他排序方法分别对每个桶的数据进行排序,最后按照一定要求输出

桶排序的特点:

非基于比较的排序，与被排序的样本的实际数据状况很有关系。并不能作为一个通解被应用在普遍场景下，所以实际中并不经常使用。
时间复杂度O(N)，额外空间复杂度O(N)
稳定的排序

1.计数排序

1.1算法原理

为何把计数排序放在桶排序之下呢,其实计数排序的开辟新空间做映射的思想与桶排序属于同一类思想,因此作为桶排序思想的一种实现在此出现.其中之所以叫”非比较排序”,就是因为算法中的排序核心并不是从直接比较出发,而是用”已排序结构”,例如顺序数组的下标,只记录频次即可

1.2算法步骤

计算开辟空间:开辟一块可以容纳待排序数据的空间,如数据 [4,4,6,8,9,3,3,0] ,最大为9,最小为0,因此我们开辟十个空间用于容纳这一堆数据.但是并不是必须从0开始,而是恰好容纳即可,因此只需要(Max-Min+1)块空间.

统计数据出现次数:依旧是上述例子,统计频次,并将频次填入对应下标空间中,本例子使用了长度为10的频次数组tmp

输出排序:遍历频次数组tmp,对频次不为0的空间输出下标值,并减小对应下标的频次,直到所有频次为0为止

1.3算法实现

直接来看代码

very EZ.

2.基数排序

基数排序也是桶排序的一种拓展,与计数排序相比,基数排序在桶中存储的是不同数量的满足某一条件(一般是个/十/百位相同)的原始数值,而计数排序在桶中存储的是原始数值的频数,而非原始数值本身

（1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用

（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法

1.原理

将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

2.步骤

确定数组中的最大元素有几位（MAX）（确定执行的轮数）

创建0~9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成

依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直至MAX轮结束输出数组。

3.实现

五.给出哈希函数和探测方法(链表),求哈希存储过程和查找一个元素需要的次数

六.计算时间复杂度

时间复杂度是一种函数，定量地描述了该算法运行的时间。既然是一种函数，就涉及到自变量与因变量。因变量代表是时间复杂的规模，自变量是时间复杂度的执行时间。

这里的执行时间并不是秒，分钟这类的具体时间，它表示的是一种“执行次数”。要想计算时间复杂度首先得找到该算法中的循环，算法中循环执行的次数就是算法的时间复杂度。

计算时间复杂度的一般规律(用大O表示法)

1.去除表达式中所有加法常数
2.修改的表达式中只保留最高阶项,因为只有它对最终结果产生影响
3.如果最高阶项系数存在且不是1,则将其系数变为1,得出最后的表达式

常见的时间复杂度

1.常数阶

函数内循环为常数次或者没有循环,时间复杂度为O(1).

2.线性阶

就像上面第一题一样,只有一层循环,时间复杂度随n的增大线性增加,函数在图像上表示为一条经过原点的直线,O(N).

3.对数阶

例题:给定 n 个元素的升序有序数组 a[n] 和整数k，求 k 在数组中的下标，不存在输出-1。

这道题是经典的查找问题,一般最快的情况是使用二分查找

left和right指数组最左边和最右边的下标.每次将这个数组砍一半,求出mid中间下标. 由于是升序排列,如果中间下标代表的数大于给定的数k,那么k必定在中间下标的左边. 那么就将mid+1的值赋给right,反之则将mid+1的值赋给left,每次将数组砍一半直到找到数k为止.

n->n/2->n/4->n/8.....直到n变为1.

这个循环次数是对数的值,很显然是以二为底,数组个数n的对数O().

4.指数阶

指数阶一般是算法题的暴力解法,一般是多层循环的嵌套,例如上面题二中,最大是两层n次循环的嵌套因此`时间复杂度为O(),n的平方次,要是三层n次循环的嵌套则为O().

5.根号阶 例题:给定一个数 n,问 n 是否是一个素数.

常见的方法就是暴力法,n和每个小于n大于1的数相除如果都除不进,则n为素数.不过这次我们选择更为简单的方法例如:

只需要枚举所有小于根号n的数,使n与其相除 ,这样时间复杂度就小了很多.那为什么只需要枚举小于根号n个数呢?

因为假设n是数k的因子,那么也必定是数k的因子,所以不需要枚举小于k这么多数,只需要枚举根号n个数就可以了.

6.阶乘阶

阶乘阶的讨论没有意义,阶乘级的时间复杂度一般在刷题时过不了,一般会用动态规划代替.

时间复杂度推导法则

1.单个循环体推导法则

对于一个循环，假设循环体的时间复杂度为O(n)，循环次数为 m，则这个循环的时间复杂度为O()。

此时时间复杂度为即。

2.多重循环体推导法则

对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为O(n*a*b*c...)。分析的时候应该由里向外分析这些循环。

此时时间复杂度为，即 O()。

3.多个时间复杂度的推导法则

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

此时时间复杂度为 max(O()，O(n))，即 O()。

4.条件语句的推导法则

对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。

此时时间复杂度为，即。

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

七.二叉树三种遍历,求解二叉树中各种数值(叶子节点个数,度为1,2的节点个数,计算祖先节点,树高度)

所谓”什么序遍历”中的”序”指的是根节点的位置

1.前序遍历:根→左→右

若二叉树为空，什么都不做，否则：

算法实现:

2.中序遍历:左→根→右

二叉树为空，什么也不做，否则：

算法实现:

3.后序遍历:左→右→根

若二叉树为空，什么也不做，否则：

算法实现:

4.计算二叉树各项属性

1.计数

计数就是对一些特殊节点进行计数,例如计算叶子节点数量,计算度为1或2的节点的数量,方法都很类似,遇到则计数器加上:

叶子节点个数：遍历二叉树，每当遇到一个节点的左右子节点都为空时，累加叶子节点计数器。

度为1的节点个数：遍历二叉树，每当遇到一个节点只有一个子节点时，累加度为1的节点计数器。

度为2的节点个数：遍历二叉树，每当遇到一个节点有两个子节点时，累加度为2的节点计数器。

2.祖先节点

这个问题主要是因为一个节点只会存储他的孩子节点指针,如果直接访问一个节点本身并不能找到它的父节点;但如果可以有一个方法找到他的父节点那我们也可找到父节点的父节点,依次类推,一个方法就可以找到某节点的所有祖先节点.

但是我们更希望一劳永逸,如果有一个方法可以一次性找到所有节点的父节点就好了,那我们不得不使用哈希表这样的数据结构来存储父节点内容:

初始化一个空栈和一个空哈希表（或字典）。栈用来存储遍历过程中的节点，哈希表用来存储每个节点的父节点值。

将根节点入栈，并将根节点的值设置为哈希表的键，父节点值设为 None。

进入循环，直到栈为空：

出栈一个节点，将其视为当前节点。

遍历当前节点的子节点：

对于每个子节点，将其入栈，并将子节点的值设置为哈希表的键，父节点值设置为当前节点的值。

循环结束后，可以通过查询哈希表找到目标节点的父节点值。

在这个方法中，通过将节点和父节点值的关系一同入栈，可以在后续操作中通过栈的弹出顺序来还原节点的层次结构和父节点信息。

请注意，这种方法会以栈的方式保存遍历过程中的节点状态，因此在空间消耗方面可能会有一定的考量。

3.求树高

我们先对树高这个概念做一个标准化算法化的描述:什么是树高?树的高度(或深度)就是树中结点的最大层数。

在算法中我们用后序遍历的递归算法,对每一个结点都进行如下操作：

后序遍历其左子树求树高

后序遍历其右子树求树高

对这个结点进行下面操作：

比较其左右子树的高度大小

若左>右，则选择左的高度；反之，选择右的高度

将上一步选出的高度+1，并作为返回值返回

举个例子:

比如上面这个图，按照后序遍历的序列，最先到达1节点,因为1是叶子节点,所以左右子树高度都为0,返回0+1,也就是将其父节点4的左子树高度返回.第二个遍历到达2,同理返回4的右子树高度0+1.

终于到了不是叶子节点的4节点,左右子树高度都为1,则返回1+1给5节点,这样就得到了根节点的左子树高度.

代码实现也并不复杂:

后期标注:重新问了这个考点,其实没那么复杂,应该是对完全二叉树的下标关系的考察…,有点无语了,想半天四五个方法结果用不上….上述方法对所有二叉树都适用,甚至对所有树结构都适用,自然对完全二叉树也适用,但是由于完全二叉树的特殊层序一维存储方式,父节点和子节点的下标有公式可以直接计算:

对于给定的子节点下标 childIndex，可以通过以下公式计算父节点的下标：

左子节点的下标：leftChildIndex = 2 * parentIndex + 1

右子节点的下标：rightChildIndex = 2 * parentIndex + 2 其中，parentIndex 是父节点的下标，通过这个公式可以从子节点的下标计算出父节点的下标。

注意了!!该情况针对于index从0开始!也就是数组存储情况,如果从1开始算根节点的话,那都应该对这个公式减一

2.对于完全二叉树的高度，可以利用节点的下标来计算。对于一颗有n个节点的完全二叉树,树的高度(下取整);

八.堆的初始化,堆排序,堆删除等调节过程

1.堆的初始化

1.原理

堆的初始化其实十分直接了当.

以大顶堆为例,根据大顶堆的本身性质:根节点比孩子节点都大,我们构造大顶堆的方法就是让每个非叶子节点和它的孩子节点比较,谁大谁上到根节点位置就好(小顶堆同理)

2.实现

别急,我们可以暂且先了解原理,具体实现方法不如与接下来的堆排序一起看

2.堆排序

1.原理

顾名思义,堆排序就是用到堆的排序,因为堆自带已排序的属性,利用这一点我们可以实现时间复杂度更低的排序算法.

堆排序的基本思想就是:将待排序的序列构造为一个大顶堆.此时整个序列最大值就是堆顶的根节点,将其移走(其实是将末尾元素与其交换,现在末尾元素在堆顶,最大值在末尾输出并释放)然后将剩余n-1个元素重新构造为大顶堆,如此反复执行.

2.实现

根据原理,主体程序依旧是堆创建函数,因此我们直接来看代码:

依旧有点函数包装的样子,其中核心函数HeapAdjust如下:

外层循环是对关键字较大的孩子节点筛选,对应节点与其子节点比较交换完后,还要对交换位置的节点的子节点再做对比.

3.堆增删

堆的创建过程就是通过一步步调整完成的,因此堆序列产生变化后也可以重新调整为堆

九.霍夫曼树

1.基本介绍

给定n个权值为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也成为了霍夫曼树。霍夫曼树是带权路径长度最短的树，权值较大的节点离根较近

2.霍夫曼树的几个重要概念

1.路径和路径长度：在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的通路，成为路径。通路中分支的数目称为路径长度。若规定根节点的层数为1，则从根节点到第L层节点的路径长度为L-1 2.节点的权和带权路径长度：若将树中节点付给一个有着某种意义的数值，则这个数值成为该节点的权（值）。节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积。 3.树的带权路径长度：树的带权路径长度规定为所有叶子节点的带权路径长度之和，记为WPL（weighted path length），权值越大的节点离根节点越近的二叉树才是最优二叉树 WPI最小的就是霍夫曼树

3.构造思路

根据给定的n个权值{…}构成n颗二叉树的集合F={…},其中每颗二叉树只有一个带权为的根节点,左右子节点都为空

在F中选取两颗根节点权最小的树作为左右子树构造一颗新的二叉树,且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和.

在F中删除这两棵树,同时将新得到的二叉树加入F

重复2,3直到F中只含一棵树,这棵树就是霍夫曼树

4.霍夫曼编码:米奇妙妙压缩

一篇文章中不同的字符有不同的频数

这是一个关于一个英文统计集中字母占比的统计,我们可以将每个字母当作一个节点,将其频数赋予它为权值,利用这26个节点可以构造一个霍夫曼编码树

霍夫曼树可以使带权路径长度最短,霍夫曼编码树就可以让文章的二进制编码长度更短;因为在计算机中所有的内容都是二进制表现的,因此字符也不例外:a可以做01,b11,c0101…但是如果一些高频出现的字符比如s的编码过长就会使整体长度过长,x这样的低频字符编码短也会浪费空间.

霍夫曼编码就是使高频高权值字符更靠近根,编码长度更短;低频字符编码长度更长,根据树结构进行编码:

从霍夫曼树根节点出发,左拐取0,右拐取1.例如图中’l’的路径是:左左右,因此编码为001

同时可以发现,霍夫曼编码因为子树的根节点不会是原序列节点,从一个原序列节点到下一个原序列节点必会经过一个辅助节点(子树根节点)因此不会出现容易混淆的情况

eg.10,100与1001就容易混淆,如果要设计长短不一的编码,则必须是任意字符的编码都不会是另一字符编码的前缀,这种编码被称作”前缀编码”

但实际过程中不一定按照频数进行赋权,因此对同样的内容可能有不同的霍夫曼编码,因此还涉及到解码问题,双方要使用相同的霍夫曼编码原则

十.AVL树增删调节

1.回顾AVL树概念

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，

左右两个子树也都是一棵平衡二叉树。

在AVL树中，任何节点的两个子树的高度最大差别为 1 ，所以它也被称为平衡二叉树

1.1平衡因子（Balance Factor，简写为bf）

平衡因子（bf）：结点的左子树的深度减去右子树的深度。即：

结点的平衡因子 = 左子树的高度 - 右子树的高度 。

在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1;

由 AVL树的定义可知,上面的两个图都不是 AVL树（平衡二叉树）.

2.AVL树作用

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况

由上图可知，同样的结点，由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下，会导致二叉树的高度是O(N)，而AVL树就不会出现这种情况，树的高度始终是O(lgN).高度越小，对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因。

3.AVL调整操作

先给一个结论,在对四种旋转展开描述:

如果最小不平衡子树根节点的平衡因子大于1时就右旋,小于-1时就左旋

若最小不平衡子树的BF和其子树的BF符号相反时,就需要对其子节点先旋转一次使符号相同,然后在对最小不平衡子树做旋转

3.1插入—— 左左型的右旋(LL)：

由上图可知：在插入之前树是一颗AVL树，而插入结点之后，T的左右子树高度差的绝对值不再<=1，此时AVL树的平衡性被破坏，我们要对其进行旋转。

在结点T的 左结点（L） 的 左子树（L） 上做了插入元素的操作，我们称这种情况为 左左型 ，我们应该进行右旋转。

右旋具体步骤:

T向右旋转成为L的右结点

L的右节点Y 放到 T的左孩子上

3.2、插入——左右型的左右旋(LR)：

由上图可知，我们在T结点的左结点的右子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再<=1，如果只是进行简单的右旋，得到的树仍然是不平衡的。

在结点T的 左结点（L） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为左右型(LR)，我们应该进行左右旋。

左右旋转的步骤:

第1次是左旋转：

L节点左旋转，成为R的左节点

R的左节点（Y1）左旋转，成为 L的右节点（即左子节点左转）

第2次是右旋转：

T节点右旋转，成为R的右节点

R的右节点（Y2）右旋转，成为T的左节点（即右子节点右转）

3.3、插入——右右型的左旋：

由上图可知：在插入之前树是一颗AVL树，而插入新结点之后，T的左右子树高度差的绝对值不再 <+ 1，此时AVL树的平衡性被破坏，我们要对其进行旋转。

在结点T的 右结点（R） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为右右型(RR)，我们应该进行左旋转。

左旋具体步骤:

T向左旋转成为R的左结点

R的左节点Y放到T的右孩子上

3.4、插入——右左型的右左旋：

由上图可知，我们在T结点的右结点的左子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再<1，如果只是进行简单的左旋，得到的树仍然是不平衡的。

在结点T的 右结点(R)的左子树（L）上做了插入元素的操作，我们称这种情况为右左型(RL)，我们应该进行右左旋。

右左旋的两次旋转步骤：

第1次是右旋转：

R 节点右旋转，成为L的右节点

L的右节点（Y2）右旋转，成为R的左节点（即右子节点右转）

第2次是左旋转：

T 节点左旋转，成为L的左节点

L的左节点（Y1）左旋转，成为T的右节点（即左子节点左转）

十一.拓扑排序

首先声明:

有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。

无向图没有拓扑序列。

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网(Activity On Vertex Network)

AOV网中的弧表示活动之间存在的某种制约关系,AOV网中不能存在回路,让某个活动的开始要以自己完成作为先决条件,显然是不可以的.

1.拓扑排序算法

对AOV网做拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或AOV网中不存在入度为0的顶点为止

在谈到具体代码之前,不得不思考一下需要用到的数据结构.在拓扑排序中,需要删除节点,因此相比邻接矩阵,邻接表会更加方便.因此需要对AOV网建立一个邻接表.考虑到算法过程中始终要查入度为0的顶点,需要在原先顶点表节点结构中加入一个入度域in.涉及到的代码结构如下:

在算法中,还需要辅助的数据结构——栈,用来存储处理过程中入度为0的顶点,目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点

来看代码:

十二.判断图是否为连通图,图的连通构建,是否存在环路等算法

要讨论这些问题,不得不先提到图的遍历方法了

1.深度优先遍历(DFS:Depth First Search)

顾名思义,深度优先就是在一个空间中”打破砂锅问到底”,一路走到黑后没找到再回去走另一条路;整体算法思路就是:从图的某个顶点出发,访问此顶点,然后从该顶点未被访问的邻接点出发深度优先遍历(或叫深度优先搜索),直到图中所有和该顶点相连通的顶点都访问到.这个说的其实是连通图,对于非连通图,分别对图的连通分量做就好了.某种程度上与树的前序遍历十分类似.

来看代码:

上部分是算法核心递归部分,下部分是对遍历数组的初始化和核心外层包装,这里用的图结构是邻接矩阵,其实邻接链表也完全可以:

外层包装一模一样,只是核心因为数据结构不同所以探索方式略有不同.

从时间复杂度上来讲,邻接矩阵因为要访问所有矩阵所有元素,因此时间复杂度为,而邻接表的时间取决于顶点数量和边的数量,因此时间复杂度为;不难看出,对于点多边少的稀疏图,显然邻接链表的结构效率更高.

2.广度优先算法(BFS:Breadth First Search)

与深度优先算法相对,不要一路走到黑,按照一定”层次”划分空间,优先排除不太可能的层次(例如找手机的时候你肯定不会去看煤气罐里有没有);上面说DFS与树的前序遍历类似,那么BFS就与树的层序遍历类似,算法思路大概是:将起始顶点放顶层,与其邻接的顶点放第二层,与第二层邻接且不包括上层的顶点放第三层…依次类推;

将顶层顶点入队列,对每一个队列中的顶点做如下操作:在队首时出队列,并将该顶点的下层邻接顶点入队列,依次往复直到图中所有顶点都遍历过.

来看代码:

对于邻接链表的广度优先遍历,与邻接矩阵的差别不大:

3.连通图

顾名思义,所有顶点都连通的图.既然所有顶点都连通,那么我们就可以遍历到所有的顶点,因此判断一个图是否是连通图的最直接方法就是遍历:

选择任意一个节点作为起始节点，并进行深度优先搜索或广度优先搜索。

如果在搜索过程中，所有节点都被访问到了，那么图是连通的。

如果存在未被访问到的节点，那么图不是连通的。

因此我们可以通过该方法，如果图是连通的，则从任意一个节点出发，能够到达图中的所有其他节点.

至于寻找图的连通构建和判断是否存在环路，可以使用图遍历算法，如深度优先搜索（DFS）或广度优先搜索（BFS），以及添加一些额外的标记来实现。以下是一种思路：

连通构建：从任意一个节点出发，进行深度优先搜索或广度优先搜索，将所有访问到的节点添加到一个集合中，从而得到一个连通构建。

判断环路：在深度优先搜索过程中，可以使用额外的标记来记录当前路径上已经访问过的节点。如果在搜索的过程中遇到了已经标记过的节点，那么就说明存在环路。

对于连通构建，可以使用多次深度优先搜索或广度优先搜索来找到图中的所有连通构建。每次搜索时，选择一个未被访问过的节点作为起始节点，并记录所访问到的所有节点。

对于判断环路，可以在进行深度优先搜索时，每次搜索一个节点时，使用额外的标记来记录当前路径上已经访问过的节点。如果在搜索的过程中遇到了已经标记过的节点，那么就说明存在环路。

十三.两种最小耗费生成树算法(Kruskal,Prim),两种最短路径算法(Dijkstra,Floyd)

1.最小生成树

构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)

2.Prim算法

普里姆(Prim)算法代码如下:对于一个存储结构为邻接矩阵的加权图,其中INFINITY为权值极大值,不妨是65535,MAXVEX为顶点个数最大值.

看完代码再看定义:假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合.算法从U={}(∈V) ,TE={}开始.重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边()并入集合TE,同时并入U,直到U=V为止.此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树.

看昏了哥们,但是可以说点简单的,主要实现过程就是拓展出一个额外空间用于存储对应下标顶点最小弧权值(代码中对应额外空间就是lowcost),遍历lowcost中最小值并做”探测”,所谓探测就是找到最小值对应下标节点然后对此节点再做权值比较并存储入lowcost,直到所有节点探测完毕.

在整体流程中,时间排序为:确定一个弧→探索下一节点

3.Kruskal算法

换个思考方式,Prim算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树.

如果我们用边为目标去构建,因为权值在边上,直接去找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已.此时我们就用到了图的存储结构中的边集数组结构.以下edge边集数组结构的定义代码:

算法代码如下,其中MAXEDGE为边数量的极大值,MAXVEX为顶点个数最大值.

在程序中,parent数组中begin位置存的数据是end(就是parent[begin]=end),所以取到parent数组中的数据parent[i]=j代表()边在最小生成树中,若在原图中不相连,parent[i]=j代表着子树暂时到头

Find函数为什么不直接输入f返回f呢?(废话,那我要他做毛线)其实这就是这个算法中”向图深处探索”的方法实现,如果parent[f]>0,代表这以f为begin的位置有一条边在生成树中了,因此我们不直接返回f,而是返回parent[f],也就是对应边的end,从end节点找,从而实现探查过程.

到此我们再说Kruskal算法的实现定义:

假设N=(V,{E})是连通网,则令最小生成树的初始状态只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量.在E中选择代价最小的边,若该边依附的顶点落在T的不同连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边.依次类推,直到T中所有顶点都在同一连通分量上为止.时间复杂度为

4.Dijkstra算法

这是一个按照路径长度递增的次序产生最短路径的算法

1.算法思路

Dijkstra算法并非一步求出两点间的最短路径,而是一步步求出他们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到想要的结果.

直接看代码吧:

在修正前的的部分没啥好说的,正经的对邻接矩阵做遍历寻找最短边.修正在这个算法中极其重要,为了避免存在更短路径(比如到直接连通权值为3,到直接连通权值为1,和直接连通权值为3,如果没有修正这一步,算法将给出这条路径,并不比直接连通更短).同时修正这一步也包含了探查的过程,从目前最短路径的终点(在代码中是修正前下标为k的节点)再向前探测一个节点(G.arc[k][w])

5.Floyd算法

Floyd算法是一种用于解决图中任意两点之间的最短路径的经典算法。它采用动态规划的思想，通过不断更新两点之间的最短路径长度来求解最短路径。

先来看个最简单的案例吧,下图为一个十分简单的三顶点连通图

先定义两个二维数组D[3][3]和P[3][3],D代表顶点到顶点的最短路径权值和的矩阵.P代表对应顶点的最小路径的前驱矩阵.在未分析任何顶点之前,我们将D命名为,其实就是初始的图的邻接矩阵;将P命名为,初始化如下所示

首先来分析:所有顶点经过后到达另一顶点的最短路径.因为只有三个顶点,因此需要查看,得到.矩阵中表示的是的权值为5,我们发现,和上面的Dijkstra算法的修正问题相反:”绕远反而更近”,所以我们就让,同样的,于是有了矩阵,因为有变化,所以P矩阵对应的和也修改当前中转的顶点的下标0,于是就有了,也就是说

接下来,其实就是在和的基础上继续处理所有顶点经过和后到达另一顶点的最短路径,得到接下来的几组矩阵完成所有顶点到所有顶点的最短路径计算工作

来看代码吧:

这样最短路径就算完成了,那么如何由P这个路径数组得出具体的路径呢?

假如有个9*9的P矩阵,其中P[0][8]=1,代表到需要经过,用1代替0,P[1][8]=2同理用2代替1,最终到遍历结束.

求最短路径的显示代码可以这样写:

十四.动态规划,贪心算法思想分析.

1.贪婪算法

1.最优化问题

• 每个最优化问题都包含一组限制条件(constraint)和一个优化函数(optimization function)；

• 符合限制条件的问题求解方案称为可行解(feasible solution)；

• 使优化函数取得最佳值的可行解称为最优解(optimal solution)。

2.贪婪算法思想

在贪婪算法(greedy method)中采用逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。

作出贪婪决策的依据称为贪婪准则(greedy criterion)。