基本数据结构
数据结构
指针
指针在链表和其他使用地址的复杂数据结构(如树、图)中非常常用。指针的主要作用是存储和访问内存地址,使程序能够动态地管理数据结构中的元素。关键点在于理解指针的声明和使用是两个独立的概念。同时用于遍历数据结构的指针,也需要和对应数据结构的类型相同。就像是量我们的铅笔,我们需要用厘米尺而不是分米尺。
- 指针的声明:指针的声明告诉编译器变量是一个指针类型,并指定它将指向的内容类型。这一步只是定义了指针,而没有赋予它实际的地址。
- 指针的使用:指针使用的过程中包括为指针分配内存地址和通过指针访问或修改该地址处的数据。指针操作需要小心,因为不正确的操作可能导致内存泄漏或访问非法内存。
1 | //1.在声明的时候表示声明了一个指针变量 |
在解题和使用数据结构时,经常会看到->
符号。这个符号实际上是一个复合符号,称为”成员对象访问操作符”。它的作用是通过指针访问结构体或类的成员。
实际上,->
是对(*p).
的简化表达。(*p).
先解引用指针p
(即获取p
指向的对象),然后访问该对象的成员。而->
操作符将这两个步骤合并成一个更直观、更简洁的操作,使代码更易读。也就是说,假设有一个结构体的数据data
,被我们指向了,那么就是调用这个结构体指定位置的数据。
1 |
|
在链表中,当看到p->next =
这样的代码时,可以直观地理解为“当前p
指针所指节点的下一个节点是什么。”类似地,p->prior
这样的代码可以理解为“p
指针所指节点的上一个节点是什么。”
具体指定的变量要看指定数据结构的定义。
线性表
线性表是具有相同数据类型的数据元素构成的有限序列,如果用n
表示表长,则n=0
的时候线性表是一个空表。线性表最主要的特点如下:
- 除了第一个元素,每一个元素都由其直接前驱
- 除了最后一个元素,每个元素都有直接后继
- 由于存储的数据类型都相同,所以说每一个数据元素占据的内存区域大小是一致的
- 逻辑结构决定的线性表数据元素之间的关系,物理结构决定线性表使用内存的能力
常见的线性表有:数组、单链表、双链表、循环链表等等。以上的线性表的差别可能要从逻辑结构和物理结构来讨论
单链表
链表是一种常见且基础的数据结构,是一种线性表,但是他不是按线性顺序存取数据,而是在每一个节点里存到下一个节点的地址。也可以这样理解,链表是通过指针串联在一起的线性结构,每一个链表结点由两部分组成,数据域及指针域,链表的最后一个结点指向null
。也就是我们所说的空指针。
链表和数组不同的在于他们的索引,数组所用的索引是数组下标,而链表的索引是他们下一个数据的位置。每一个位置存储当前的值和下一个位置的地址。
实际上,数组和链表都使用索引来访问元素,但在物理存储方面有很大不同。数组在内存中分配一块连续的空间存储数据,因此元素之间的距离很小,可以直接通过开头位置的索引计算下一个元素的位置,无需使用指针。而链表的元素在内存中分布是离散的,难以计算下一个元素的位置,所以说需要使用指针。每个节点通过指针连接到下一个节点,因此需要指针来找到和链接每个数据元素。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。我们通过上面说到的可视化表示方法,将单链表可视化,如图所示:
链表头部插入
头指针是链表结构中的一个关键元素,位于链表的头部。引入头指针有以下两个主要优点:
头指针存储链表第一个节点的地址,使得我们能够始终找到链表的起点。这是操作链表的基础,无论是遍历、插入、删除等操作,都需要从头指针开始。
头指针的引入简化了链表操作逻辑。无论链表是空的还是非空的,头指针始终存在。对于空表,头指针指向
null
;对于非空表,头指针指向第一个节点。这种设计使得链表的操作更加一致和简洁。例如,在插入节点时,无需特别检查链表是否为空,因为操作总是从头指针开始。
链表头部插入元素:在链表第1
个链节点之前插入值为val
的链节点。
- 先创建一个值为
val
的链节点node
- 然后将
node
的next
指针指向链表的头节点head
。 - 再将链表的头节点
head
指向node
。
头结点是标注链表中的第一个位置!!!!!头结点只是一个指针变量,把它理解为遍历的起点
1 | struct Node{ |
链表尾部插入元素:在链表最后 1
个链节点之后插入值为val
的链节点。
- 先创建一个值为
val
的链节点node
。 - 使用指针
cur
指向链表的头节点head
- 通过链节点的
next
指针移动cur
指针,从而遍历链表,直到cur.next
为None
。 - 令
cur.next
指向将新的链节点node
。这里的尾指针始终指向我们的最后一个结点。
1 | // 用尾指针维护链表 |
插入操作
链表中间插入元素:在链表第 i
个链节点之前插入值为 val
的链节点。
- 使用指针变量
cur
和一个计数器count
。令cur
指向链表的头节点,count
初始值赋值为0
。 - 沿着链节点的 next 指针遍历链表,指针变量 cur 每指向一个链节点,计数器就做一次计数。
- 当遍历到
index-1
个链节点时停止遍历。 - 创建一个值为
val
的链节点node
。 - 将
node.next
指向cur.next
。 - 然后令
cur.next
指向node
。
1 | struct Node{ |
改变元素
将链表中第i
个元素值改为 val
:首先要先遍历到第 i
个链节点,然后直接更改第 i
个链节点的元素值。具体做法如下:
- 使用指针变量
cur
和一个计数器count
。令cur
指向链表的头节点,count
初始值赋值为 0。 - 沿着链节点的
next
指针遍历链表,指针变量cur
每指向一个链节点,计数器就做一次计数。 - 当遍历到第
index
个链节点时停止遍历。 - 直接更改
cur
的值val
。
1 | // 更改指定位置的数据 |
删除操作
链表最大的优点在于可以灵活的添加和删除元素。
- 链表进行访问元素、改变元素操作的时间复杂度为 O(n)。
- 链表进行头部插入、头部删除元素操作的时间复杂度是 O(1)。
- 链表进行尾部插入、尾部删除操作的时间复杂度是 O(n)。
- 链表在普通情况下进行插入、删除元素操作的时间复杂度为 O(n)。
链表的删除元素操作与链表的查找元素操作一样,同样分为三种情况:
- 链表头部删除元素:删除链表的第 1 个链节点。
- 链表尾部删除元素:删除链表末尾最后 1 个链节点。
- 链表中间删除元素:删除链表第
i
个链节点。
接下来我们分别讲解一下。
链表头部删除元素:删除链表的第
1
个链节点。直接将
self.head
沿着next
指针向右移动一步即可。
1 | // 删除头结点的元素 |
链表尾部删除元素:删除链表末尾最后 1 个链节点。
- 先使用指针变量
cur
沿着 next 指针移动到倒数第2
个链节点。- 然后将此节点的
next
指针指向null
即可。- 「链表尾部删除元素」的操作涉及到移动到链表尾部,操作次数为
n−2
次,因此,「链表尾部删除元素」的时间复杂度为O(n)
。
1 | // 删除链表尾部的数据 |
链表中间删除指定节点:删除链表第 i 个链节点。
- 先使用指针变量
cur
移动到第i−1
个位置的链节点。- 然后将
cur
的next
指针,指向要第i
个元素的下一个节点即可。
1 | // 删除中间段落的节点 |
总结,通过遍历到链表的目的位置的前一个,来进行删除链和接上链,链表的特殊逻辑结构导致了查找对应位置的数据时间复杂度特别大,主要花费时间在查找和遍历上。但是单纯用头插法和尾插法,还有删除操作效率特别快,而且插入数据是动态更新的。
双链表
在单链表的基础上,加一个指向后继的指针。
- 每个节点需要存储两个指针(
next
和prev
),因此在存储相同数量的元素时,双向链表比单向链表消耗更多的内存。 - 在双向链表中,在任意位置插入或者删除节点时,可以直接调整相邻节点的
next
和prev
指针,无需访问链表的头部。这使得插入操作更为简便。
依据上图,可以简单得出双链表的节点定义
1 | // 当然还是可以用头指针来标识这个链表的第一个数据 |
插入操作
插入操作根据插入的位置不同他们的时间复杂度不同
在头部插入节点:
- 创建一个新节点
new_node
。- 设置
new_node.next
为当前的头节点head
。如果头节点
head
不为None
,将head.prev
设置为new_node
。将
new_node.prev
设置为None
。- 更新链表的头节点为
new_node
。
1 | // 头插法更新双链表 |
在指定位置插入节点:
- 创建一个新节点
new_node
。- 设置
new_node.next
为node.next
。- 如果
node.next
不为None
,将node.next.prev
设置为new_node
。- 设置
new_node.prev
为node
。- 设置
node.next
为new_node
。
与单链表相比,双链表的操作需要控制四个指针,具体操作如下。
1 | // 指定位置插入数据 |
删除操作
如果是用数组模拟的双链表,删除只是把数据从数组中隐去
而已,这里还是按照用链表实现的方法。通常链表会有一个指针域和一个数据域。我们需要在解除掉q指针之前交换所有的数据信息。
1 | // 1.准备 |
静态链表*
数组来代替指针用来描述单链表,这种用数组来描述的链表就叫做『静态链表』,这种描述的方法叫做『游标实现法』,如下图所示
对应的线性表的静态链表存储结构代码如下
1 |
|
对静态链表进行初始化相当于初始化数组
1 | Status InitList(StaticLinkList space) { |
下面是一些需要注意的地方
- 一般对数组的第一个和最后一个元素做特殊处理,他们的
data
不存放数据 - 通常把未使用的数组元素称为备用链表
- 数组的第一个元素,即下标为
0
的那个元素的cur
就存放备用链表的第一个结点的下标 - 数组的最后一个元素,即下标为
MAXSIZE - 1
的cur
则存放第一个有数值的元素的下标,相当于单链表中的头结点作用
在静态链表中,我们主要解决的就是如何模拟动态链表结构的存储空间分配,也就是需要的时候申请,不需要的时候释放,在之前,我们提到过,为了辨明数组中哪些分量未被使用,解决的方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表,每当进行插入时, 便可以从备用链表上取得第一个结点作为待插入的新结点,我们以上面第示例来进行说明,比如我们要在 A
的后面插入 B
,如下图
我们要做的首先是获得空闲分量的下标
1 | int Malloc_SLL(StaticLinkList space) { |
接下来完成删除操作以上面的示例为例,这次我们来删掉 C
元素
1 | /* 删除在 L 中的第 i 个数据元素 */ |
结果如下
静态链表的优点是在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点,而缺点也比较明显,没有解决连续存储分配(数组)带来的表长难以确定的问题,失去了顺序存储结构随机存取的特性,即不能直接使用下标来找到指定的值了,因为它某些程度上来说,已经具备了一些单链表的特性了
循环链表*
循环链表一般使用尾插法实现
循环链表和非循环链表其实创建的过程以及思路几乎完全一样,唯一不同的是,非循环链表的尾结点指向空(NULL
),而循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为循环单链表(Circular linkedlist
),如图,为一个完整的循环单链表,最后一个位置的next
为头指针
循环单链表
对于循环单链表的结点,可以完全参照于单链表的结点设计,如图:
data
表示数据,其可以是简单的类型,next
表示指针,它永远指向自身的下一个结点,对于只有一个结点的存在,在循环单链表中next
指针则永远指向自身,对于循环单链表的尾部结点,next
永远指向开头。
1 | struct list{ |
在单链表的基础上,循环单链表的最后一个节点的 next
指向链表的第一个节点,形成一个环。无论链表中有多少个节点,最后一个节点都会链接到第一个节点。
1 | // 节点定义 |
初始化构造这个循环链表
1 | // 初始化一个循环链表 |
如果在循环单链表中设的是头指针,那么在尾部插入元素需要O(n)
的时间复杂度,如果设置尾指针,那么插入只需要O(1)。我们可以通过逐步的插入操作,创建一个新的节点,将原有链表尾结点的next指针修改指向到新的结点,新的结点的next指针再重新指向头部结点,然后逐步进行这样的插入操作,最终完成整个单项循环链表的创建。
这里用尾插法实现循环链表,将数据从右向左插入链表中。使用尾插法的原因是,方便将最后一个节点的next
指针指向头部位置。
1 | //定义节点结构 |
循环双链表
循环双向链表是一种更复杂的数据结构类型,它的节点包含指向其前一节点以及下一节点的指针。 循环双向链表在任何节点中都不包含NULL
。 链表的最后一个节点包含列表的第一个节点的地址。 链表的第一个节点还包含的前一个指针是指向最后一个节点的地址。
这里是使用尾插法构造循环双链表,和前面循环单链表一样,使用尾插法是更好维护链表。
1 | // 定义节点 |
插入操作
在循环双链表中,插入操作可以分为几种情况:在链表为空时插入、在链表头部插入、在链表尾部插入、以及在链表中间插入。如果链表为空,则插入的节点将成为链表的唯一节点,同时也是头节点和尾节点。
1 | // 链表为空插入 |
在链表中间插入时,需要遍历到指定位置,然后插入新节点,并更新相邻节点的指针。
1 | // 双链表中部插入 |
删除操作
删除操作可以分为几种情况:删除头节点、删除尾节点、删除中间节点,以及在链表为空或只有一个节点时进行删除。在双联表中,删除只需要更新两条链,我们遍历到指定删除的位置,由于我们只有这个点的信息,需要用这个P
指针表示前节点和后节点,p->prev
为前,p->next
为后。
那么删除当前这个P
节点,按照从左到右来也就是p->prev->next = p->next
。p->next->prev = cur->prev
。这样就删除完毕了。
1 | // 删除头结点 |
删除尾节点时,需要更新尾指针,并维护头节点的 prev
指针指向新的尾节点,新的尾节点的 next
指针指向头节点。
1 | // 删除尾结点 |
删除中间节点时,需要找到要删除的节点,并将其前驱节点的 next
指针指向后继节点,后继节点的 prev
指针指向前驱节点。
1 | void deleteAtPosition(int index) |
顺序表与链表的区别
数组 和 链表 之间的主要区别在于它们的结构。数组是基于索引的数据结构,其中每个元素与索引相关联。链表依赖于引用,其中每个节点由数据和对前一个和下一个元素的引用组成。引用通常使用指针来实现,他们的具体差别如下
数组
- 元素按顺序存储在连续的内存空间中,通过索引访问。
- 可以通过索引直接访问任意元素,访问速度快。具体访问时间为O(1)
- 在编译时分配固定大小的内存,扩展大小困难。不过可以通过结构体实现动态数组
- 插入和删除元素时,需要移动其他元素,效率较低。时间复杂度O(n)
- 由于元素连续存储,内存使用紧凑,但大小固定。
链表
- 元素(节点)存储在不连续的内存空间,通过指针相互连接。
- 需要从头开始顺序遍历才能访问特定元素,访问速度较慢。复杂度O(n)
- 在运行时动态分配内存,大小可灵活调整.
- 只需调整指针即可插入或删除节点,操作效率高。
- 每个节点存储数据和指针,使用更多内存,但灵活性高。
如果代码对内存的使用非常苛刻,那数组就更适合。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针,所以内存消耗会翻倍。而且,对链表进行频繁的插入、删除操作,还会导致频繁的内存申请和释放,容易造成内存碎片,触发语言本身的垃圾回收操作。如果代码对增删改查的方式使用的比较多,那么链表更为合适。因为它方便执行这些操作。
数组与广义表*
数组
数组:按一定格式排列起来的,具有相同类型的数据元素集合。一般都是采用顺序存储结构来表示数组。数组可以是多维的,但存储数据元素的内存单元地址是一维的,因此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题。
- 结论:线性表结构是数组结构的一个特例,而数组结构又是线性表结构的扩展。
- 特点:结构固定——定义后,维数和维界不再改变。
n维数组:若 n-1 维数组中的元素又是一个一维数组结构,则称为n维数组。
1 | typedef int ElemType; |
一维数组
一维数组:若线性表中的数据元素为非结构的简单元素,则称为一维数组。一维数组的逻辑结构是线性结构(定长的线性表)。声明的格式数据类型 变量名称[长度];各数组元素大小相同,且在物理上连续存放。
二维数组
二维数组可以理解为,一个一维数组中的每一个元素都是一个数组。其逻辑结构是一种非线性结构,可以用矩阵表示二维数组。
在内存中由于二维数组的存储结构是线性的,所以说应该将这个矩阵压缩为一维的,有两种方法,行优先存储和列优先存储。一个声明的二维数组可以这样理解,前面一个[]
表示为行,后面一个[]
可以表示为列。举个例子a[2][3]
按照行优先存储就是将申请得到的内存块分为两个大部分(注意是始终连续的),内部按照顺序结构存储着三个列数组。如果改为列优先,则将申请得到的内存块,分为三部分,按照顺序结构里面存储着两个行数组。
在内存中是连续的区块如果将a[2][3]
给具现化则为(这里与图片举例子不一样,但是原理是一样的):
- 行优先 :
a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]
- 列优先:
a[0][0] a[1][0] a[0][1] a[1][1] a[0][2] a[1][2]
设二维数组的行下标与列下标的范围[0,h1]
与[0,h2]
,当以行优先的方式求其存储结构关系,也就是内存相对位置的计算公式如下。其中L
是每个数组元素占据的存储单元。在行优先存储的二维数组中,计算元素地址的公式为 LOC(a[i][j]) = LOC(a[0][0]) + [i × (h2 + 1) + j] × L
,其中 i
跳过的行数乘以每行的元素总数(h2 + 1
),再加上列下标 j
,表示在当前行中找到特定元素。
设二维数组的行下标范围为 [0,h1]
,列下标范围为 [0,h2]
,每个数组元素占据 L
个存储单元。给定二维数组 a[h1+1][h2+1]
,i
表示行下标,j
表示列下标,LOC(a[i][j])
表示元素 a[i][j]
的内存地址。则以列优先的方式求其存储结构关系如下。可以简单记忆公式,列下标存储数组,则搜寻指定数组位置可以跳过列下标数量的数组块i
,其中内部块的个数为h1+1
,跳跃完之后然后用i
找到行下标。
这里的h2+1
和h1+1
就是他们的区间的范围,也即是用公式n-m+1
也就是m
到n
的距离
三维数组
三维数组:若二维数组中的元素又是一个一维数组结构,则称为三维数组。
特殊矩阵压缩存储
一个由m × n
个元素排成的m
行n
列的表。将矩阵描述为一个二维数组。矩阵的常规存储的特点:可以对其元素进行随机存取。数组的下标0与1与矩阵Aᵢ Aⱼ
的元素下标i
和j
的关系就是所谓的映射。对于矩阵内部的元素,如果有多个数据的值相同,就可以用矩阵压缩,只分配一个元素值的空间,用于减少内存的使用。
对称矩阵
对称矩阵是指元素以主对角线为对称轴对应相等的n
阶矩阵,即aᵢⱼ=aⱼᵢ
。注意,对称矩阵必须要是方阵。根据这个性质可以对矩阵进行压缩,只存储下(或者上)三角(包括主对角线)的数据元素。共占用 n(n+1) / 2
个元素空间,也就是矩阵的一半。
因为是存储下三角,所以是把矩阵中元素A[i][j](i>=j)
存放到数组Array
中。也就是从二维变为了一维,那么在这里看一下两者的对应关系。
上图给出了矩阵中部分元素在一维数组中的存储位置也就是索引,那么怎么确定其在一维数组中的索引呢,以上图的元素2
在原数组的索引为A[4][3]
,我们分为两个步骤来解决。第一步,我们可以通过计算当前行之上的所有行的元素,也就是使用等差数列的公式(每一行都比下一行少一个元素,公差为1
)
第二步回到这个元素所在行,直接加上它的列索引,即 10 + 3 = 13
,这就是 A[4][3]
在一维数组中的索引位置。
如果换成列优先存储,步骤相同,但要按列来计算。由于对称矩阵是方阵,所以行优先和列优先的计算最终是等价的,仅仅是记号上的差异。第一个步骤,计算除当前列以上的其他列中元素个数,还是使用等差数列。第二个步骤,回到这个元素所在列,直接加上它的行索引。其实也就是上面的行列向量的优先表达式的修改版,只不过其维护下标的方式不同。
其重点就是用n(n+1)/2
来进行数组下标维护的。无论是行优先还是列优先,基于对称矩阵的特性,我们可以通过以下公式直接计算 A[i][j]
在一维数组中的索引:
总体来说,由于对称矩阵的对称性,我们只需要存储下三角或上三角部分,因此在一维数组中存储的元素数量比完整矩阵减少了一半。也就可以推出其上三角和下三角的对应关系
三角矩阵
三角矩阵在线性代数中常常用于表示行最简或者列最简的方式,如果将其压缩的话其共占用 n(n+1) / 2 + 1
个元素空间。其中n(n+1)/2
是存储下或者上三角的,多出来的1
是用于存储常数c
的一个一维数组位置。
我们将矩阵分为上三角矩阵和下三角矩阵。在上三角矩阵中,下三角元素全为常数 c
;而在下三角矩阵中,上三角元素全为常数 c
。以上三角矩阵为例,其压缩规则为:只存储上三角元素,而不存储下三角元素,或仅用一个存储单元保存下三角非零元素。
我们采用一维数组来储存上三角矩阵,数组长度为 n(n+1)2+1
。一维数组的下标 k 与 n 阶上三角矩阵的元素 a(i,j)
之间的对应关系如下。其中的2n - i + 1
表示与自身长度i
对称的位置。
下三角矩阵的对应关系为:
其中第k = n*(n+1)/2
的位置存放的是常数c
1 |
|
1 | 输出结果 |
对角矩阵
也称为带状矩阵,就是所有的非零元素都集中在以对角线为中心的带状区域内(对角线的个数位奇数),即除了主对角线和主对角线上下若干条对角线的元素外,其它元素均为常数 c .
1 |
|
稀疏矩阵
稀疏矩阵是指,矩阵中的值的个数远远小于0
的个数。更精确的定义是非零元素的个数远远少于矩阵元素的个数(一般小于5%)非零元素个数 / 元素总个数 ≤ 0.05 则满足条件。稀疏矩阵有两种压缩存储方式:三元组法和十字链表法
三元组
用三个元来表示稀疏矩阵中非0
的数,也就是通过数组下标的映射来找到指定的值。由下图,我们可以知道,三元组由行标、列标、值三者构成。但是对这个稀疏矩阵压缩完成之后,其就失去了随机存储的能力。
1 |
|
十字链表是稀疏矩阵的链式存储法。矩阵的每一个非零元素用一个结点表示,该结点除了(row,col,vaule)
以外,还要添加两个链域:right
用于链接同一行中的下一个非零元素,down
用于链接同一列中的下一个非零元素。也就是用链式在逻辑上拉进了元素之间的距离。
1 | /*十字链表的存储结构*/ |
广义表*
线性表指的是n≥0
个元素a1, a2, a3…
的有序数列,并且线性表的元素具有原子性,即结构上是不可分割的一个整体。广义表Generalized list
则是线性表的一种扩展延伸。相对于线性表,广义表最大的特点在于其元素既可以是一个确定的类型,同时也可以是另一个有不定数量的元素组成的表(广义表)。不难看出从广义表的定义是递归的。广义表是线性表的递归数据结构。形式上为:
我们通常可以用GL = (a1, a2, a3… an)
来表示一个广义表,其中n
为表的长度,n>=0
,当n==0
时,我们称广义表为空表,GL
为广义表的名字。为了能更好的区分广义表中的元素我们有以下定义:
- 原子 如果
ai
是单个元素,我们称之为GL
的原子 - 子表 如果
ai
是一个广义表,我们陈之为GL
的子表
我们通常把广义表中的原子用小写字母表示,而子表用大写字母表示。例如
1 | A=() //空表 |
广义表的深度和长度
- 广义表的长度: 广义表中元素的个数(包括原子和子表)
- 广义表的深度: 广义表中括号的最大层数叫广义表的深度。
广义表的表头和表尾
- 表头: 当广义表不为空表时,第一个元素(可能为子表和原子)称为表头
- 表尾: 除去表头,剩余元素组成的新广义表称为表尾
1 | LS=(1,(1,2,3),5), 其中表头Head(LS)为原子1,表尾为Tail(LS)=((1,2,3),5) |
存储结构
广义表是一种递归的数据结构,它的元素具有两种,因此很难为广义表分配固定的存储空间,所以其存储结构适合用链式存储结构。为了能使原子和子表在结构上抱持一致,又容易区分我们通常采用如下结构:
1 | // ATOM == 0: 表示原子, LIST == 1: 表示子表 |
广义表的第二种存储结构
1 | // ATOM == 0: 表示原子, LIST == 1: 表示子表 |
广义表计算
以第二种存储结构为例
1 | int GLLength(GList g) { |
广义表的深度:对于带头节点的广义表g
,广义表深度的递归定义是它等于所有子表中表的最大深度加1
。若g
为原子,其深度为0
。
1 | int GLDepth(GList g) { |
队列*
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。它是一种特殊的线性表,特殊之处在于它只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。
队列是一种先进先出的数据结构,又称为先进先出的线性表,简称FIFO(First In First Out)
结构。也就是说先放的先取,后放的后取,就如同行李过安检的时候,先放进去的行李在另一端总是先出来,后放入的行李会在最后面出来。
这里使用结构体模拟循环队列,引入循环队列的主要目的是提高数组的空间利用率,一般用其他数据结构模拟的队列都是循环队列,需要注意的是,队首永远指向即将出队的元素,队尾永远指向队列中新入的数据。
1 | // 用结构体模拟队列 |
队列结构
一个数据结构由其逻辑结构和物理结构构成。队列可以通过链式和顺序两种方式表示。使用数组表示队列意味着连续分配一段内存,从而具备随机存取能力,能够快速访问指定位置的元素。而链式表示的队列则利用链表的优势,支持快速删除任意位置的元素,避免频繁移动的开销。
逻辑结构方面,队列可以通过不同的拓扑图像实现。例如,可以将队列视作一种循环结构,类似于一条咬着尾巴的蛇;也可以采用顺序结构,与数组类似;或者实现为离散的链式结构。
顺序结构
一个用数组实现的顺序队列如下图所示,从逻辑拓扑图可以看出队内元素都是挨在一起的
可以看到,要实现一个顺序队列,我们需要以下结构:
- 存储数据的数组 ——
data[]
- 表示队列的最大容量的值,也就是队头指针和队尾指针的最大距离
F-r+1
——MAXSIZE
- 标识队头端的队头下标 ——
front
- 标识队尾端的队尾下标 ——
rear
front
和 rear
会随着入队和出队操作而变化,为了方便起见,我们规定在非空队列中,队尾下标是队尾元素的下一个元素的下标。
1 | // 1. 队长 |
链式结构
我们使用带头节点的单链表来实现队列,如下图所示:
可以看到,要实现一个链队列,需要以下结构:
- 单链表的基本单元结点 ——
QueueNode
- 存储数据的数据域 ——
data
- 指向下一个结点的指针域 ——
next
- 存储数据的数据域 ——
- 指向链表的头指针,只是一个指针变量指向队首——
head
- 标识队头端的队头指针 ——
front
- 标识队尾端的队尾指针 ——
rear
其中,头指针 head
和队头指针 front
都指向了单链表的第一个结点,所以这个指针可以合二为一,队头指针即头指针。如此一来,我们可以借助链表的尾插法实现队列的入队操作,借助链表的头删法实现队列的出队操作。
1 | // 1. 节点 |
优先队列
优先队列是一种特殊的队列。在优先队列中,元素被赋予优先级,当访问队列元素时,具有最高优先级的元素最先删除。与普通队列最大的不同点在于 出队顺序。其出队顺序是按照优先级来决定的。
常见的优先级逻辑数据结构包括二叉堆和哈夫曼树,以及一些图算法(如 Dijkstra 算法和 Prim 算法)所使用的优先队列。优先队列根据元素的优先级进行排序,二叉堆则是实现优先队列的一种有效方式。因此,二叉堆常被称为优先队列。
二叉堆
二叉堆是一个完全二叉树,其内部节点按照一定逻辑进行排列。可以按照数据的大小简单分为两类堆:最大堆、最小堆
最大堆的逻辑结构:
- 它的任何一个双亲结点的值,均大于或等于左孩子和右孩子的值;
- 每条分支从根结点开始都是降序排序。
同理最小堆的逻辑结构:
- 它的任意一个双亲节点的值都小于或者等于左右孩子的值
- 每条分支从根节点开始都是升序排序
具体的逻辑结构如下图,我们的目的是将一个无序完全二叉树构造成为一个最大堆或者最小堆。其主要操作就两个,sink
(下沉)和 swim
(上浮),用以维护二叉堆的性质。还是举例子吧:下图是一颗普通的二叉树,是无序的
下图是一个二叉堆,为一个最小堆
这个二叉堆的特点是:
- 它是一颗完全二叉树。事实上,该二叉堆就是由上图的完全二叉树经过调整转化而来;
- 任何一个双亲结点的值,均小于或等于左孩子和右孩子的值;
- 每条分支从根结点开始都是升序排序(如分支
1-2-3-4
)。
与最小堆相对应的是最大堆:
- 最大堆是一颗完全二叉树;
- 它的任何一个双亲结点的值,均大于或等于左孩子和右孩子的值;
- 每条分支从根结点开始都是降序排序。
最大堆的堆顶,是整棵树的最大值。我们将上图中的普通二叉树转化为最大堆,如下图:
构造二叉堆
给你一颗完全二叉树,如何调整结点,构造出一个二叉堆?下面是一颗无序的完全二叉树:
现在我们想要构造出一个最小堆,首先找到这颗完全二叉树中所有的非叶子结点(绿色标记):
我们要对每个非叶子节点进行最小堆的下沉调整。什么是最小堆的下沉调整呢?
对于某个非叶子节点,如果它的值大于其子节点中最小的那个,则将它与该子节点交换位置。这一过程表现为非叶子节点(即较大值节点)下沉一个层次,同时较小值节点则相应地上浮。需要注意的是,有时一次下沉并不足够,我们需要多次下沉,直到该节点不再大于其子节点。
为了构造最小堆,我们从最后一个非叶子节点开始,按照从右到左、从下到上的顺序进行多次下沉调整。
例如,对于值为 4
的非叶子节点,它可能在下沉到第三层后仍然大于其子节点,因此还需继续下沉,直到完全下沉到底。这样,在分支 2-4-3-1
上,节点 4
才算下沉到底。
- 对非叶子结点 7,它小于其孩子结点 10, 不用下沉;
- 对非叶子结点 3,它大于其孩子结点中较大的结点 1,结点 3 要“下沉”,和结点 1 交换。显然,结点 3 沉到底了。
- 对非叶子结点 6,它大于其孩子结点中较小的结点 5,结点 6 要下沉, 和结点 5 交换位置。显然,结点 6 沉到底了。
- 对非叶子结点 4,它大于其孩子结点中最小的结点 1,结点 4 要 “下沉”,和结点 1 交换位置。显然,结点 4 并未沉到底。
- 仍对结点 4,它大于其孩子结点中最小的结点 3,结点 4 要“下沉”, 和结点 3 交换位置。此时,结点 4 算是沉底了。
对非叶子结点 2,它大于其孩子结点中最小的结点 1,结点 2 要“下沉”,和结点 1 交换位置。显然,结点 2 算是沉到底了。
至此,我们将一颗无序的完全二叉树调整改造成了最小二叉堆,你可以检查一下,最小堆中的所有结点皆满足双亲的值小于孩子的值。并且,5 条分支上都是有序的。
构造最大堆的步骤类似,不过最大堆的下沉调整是:如果某结点小于其孩子结点中最大的那个,则交换二者位置,在图上表现为非叶子结点(即小值结点)“下沉”一个层次。通过多次下沉调整,使该结点不再小于其孩子。
下图把一个无序完全二叉树调成为最大堆:
插入结点
二叉堆是一个完全二叉树,要向其中插入结点,插入到完全二叉树的最后一个结点的下一个位置即可。
比如向下面的一个最大堆中插入结点 11,要插到最后一个结点 4 的下一个位置。当最大堆新插入一个结点 11 时,它就不再是最大堆了,因为结点 11 破坏了原堆的结构。所以,我们应当将其看作一个新的完全二叉树,然后调整新完全二叉树再次构造出最大堆。(调整过程见上)
删除结点
删除操作与插入操作相反,是删除第一个位置的元素,即删除堆顶。我们以删除上图最大堆的堆顶 11 为例。当删除堆顶 11 后,二叉堆原结构被破坏,甚至不是一颗二叉树了(变成两颗):
为了保持完全二叉树的形态,我们把最后一个结点 7 补到根结点去,顶替被删除的根结点 11。如此一来,我们又得到了一个新完全二叉树(不是二叉堆),然后我们根据这颗新完全二叉树再次构造出最大堆即可。
存储结构
因为二叉堆是一颗完全二叉树,完全二叉树适合使用顺序存储结构来实现。下图是一个最大堆,红色方框是对结点的编号,和数组下标一一对应。
链式存储结构能够清晰而形象地为我们展现出二叉堆中双亲结点和左右孩子的关系。但是数组中没有指针,只有数组下标,怎么表示双亲和孩子的关系呢?其实对于完全二叉树来说,数组下标足矣!
现假设二叉堆中双亲结点的数组下标为 parent_index
,左孩子的数组下标为 left_child_index
,右孩子的数组下标为 right_child_index
,那么它们之间有如下关系:
(一)left_child_index = 2 × parent_index + 1
(二)right_child_index = 2 × parent_index + 2
(三)parent_index = (left_child_index - 1) ÷ 2
(四)parent_index = (right_child_index - 2) ÷ 2
(五)right_child_index = left_child_index + 1
比如:结点 3 的下标为 3 ,则其左孩子 2 的下标为 2 × 3 + 1 = 7
、右孩子 1 的下标为 2 × 3 + 2 = 8
;结点 7 的下标为 4,作为右孩子,其双亲下标为 (4 - 2) ÷ 2 = 1
;
假设某结点的数组下标为 child_index
,你不知道该结点是左孩子还是右孩子,要求其双亲的下标,有
(六)parent_index = (child_index - 1) ÷ 2
比如:你不知道结点 5(下标为 5)、结点 6(下标为 6)是左孩子还是右孩子,则结点 5 和结点 6 的双亲下标分别为 (5 - 1) ÷ 2 = 2
、(6 - 1) ÷ 2 = 2
。(注意,编程语言中的整型运算,所以结果不是小数)
这里,我们使用结构体实现二叉堆:
1 |
|
在进行实际操作之前,需要初始化二叉堆,即对数组及堆长度赋值:
1 | /** |
二叉堆的具体实现
这里以构造最小堆为例。要构造一个最小堆,就得调整所有的非叶子结点。而调整的依据就是比较非叶子结点和其孩子的大小。我们约定 parent
为非叶子结点, parent_index
为其下标。child
为其孩子中较小的那个,child_index
为其下标。
child
开始默认标识左孩子,那么右孩子的下标即为 child_index + 1
。当左孩子小于等于右孩子时,child
不需要改变;当左孩子大于右孩子时,就得更新 child_index
,使child
标识右孩子。下面结合下图中值为 4 的非叶子结点为例,讲述代码如何实现。
先比较 parent
的左右孩子,左孩子较小,则 child
为左孩子,不需要更新 child_index
。
parent
和 child
各就各位,发现 parent
大于 child
,可以交换位置。在交换之前,先保存一下 parent
的值,即 parent_value = 4
:
交换位置:先把 child
的值赋给 parent
,从而达到 值1 上浮的效果:
然后更新 parent_index
和 child_index
,二者都往下走一层次:
然后将之前保存的 value
赋给现在的 parent
,从而达到 值4 下沉的效果:
一次调整完成,但对于 值4 来说,并没有结束,因为 值4 还没有沉到底。比较此时 parent
的左右孩子,发现右孩子较小,则 child
为右子树,需要更新 child_index
,使 child
标识右孩子:
现在可以交换位置了,把 child
的值赋给 parent
,达到 值3 的上浮:
然后,更新 parent_index
和 child_index
的值,二者向下走一个层次:
把 value
赋给 parent
,达到 值4 的下沉:
此时,child_index
已超过了二叉堆的长度,即 值4 已经到底了。
1 | void adjust_for_min_heap(BinaryHeap *heap, int parent_index) |
构造代码如下:
1 | /** |
插入结点
1 | /** |
删除结点
将最后一个结点移动(赋值)到堆顶,然后重新构造二叉堆。
1 | /** |
构造最大堆的本质是:将每颗子树的“大”结点上浮作为双亲,“小”结点下沉作为孩子。
构造最小堆的本质是:将每颗子树的“小”结点上浮作为双亲,“大”结点下沉作为孩子。
插入结点的本质是:插入新结点至二叉堆末尾,破坏了原二叉堆的结构,然后调整新得到的完全二叉树,重新构造二叉堆。
删除结点的本质是:删除堆顶,破坏了原完全二叉树的结构,然后使用最后一个结点,重新构造完全二叉树,再调整新得到的完全二叉树,重新构造二叉堆。
用四个字概括就是——破而后立。至于代码实现,关键在于结点的调整,把这个搞明白,剩下的就简单了。对于构造完成的二叉堆,我们将至层序遍历出来,就是优先队列的出队操作了
循环队列
循环队列是一种逻辑拓扑为环的一种队列,其中有两个指针标识很重要
front
指针指向队列中的第一个进入的元素,即将要被移除的元素。每次出队时,front
指针向后移动一格,以指向下一个元素。rear
指针指向队列中的下一个插入位置,即队列的尾部。每次插入新元素时,rear
指针会向后移动一格。
为了突出循环二字,我们将这种顺序队列画成一个圆:
循环队列的 rear 和 front 能够在队列中一圈一圈地转,像钟表的时针和分针一样。不会再出现不能利用的空间了。顺序队列的形式从“直的”变成这种可循环的之后,对于状态的判断也改变了。
空队列:队列中没有元素,如上图。
请注意,空队列的条件并不是front = rear = 0
,比如一个空队列经过 3
次入队和3
次出队操作后仍为空队列:
所以为了避免混淆,循环队列为空队列时,条件应该为front == rear
满队列:队列中没有空闲空间
上图是一个最大容量为 8
的空队列,入队 7
个元素后,队列中还剩 1
个空闲位置,如果此时我们再入队1
个元素:
此时队列中确实没有空闲空间了,但注意,此时队列满足了 rear = front
,但满足 rear = front
的队列不应该是空队列吗?这就产生误会了。
不如我们退一步海阔天空,少用一个元素,借此来消除误会。如下图,规定这样是一个满队列。
我们规定,front
出现在 rear
的下一个位置时,队列为满队列。比如在上图的满队列中,front = 3
在rear = 2
的下一个位置。所以队列为满队列的判定条件为:rear + 1 = front
,但这的条件是不准确的。
因为循环队列中的front
和 rear
都是循环使用的,就像钟表的时针一样,所以我们仅根据下标的大小来判断位置是不合理的。下面两个均是满队列,右图不满足rear + 1 = front
:
就像钟表的时针满 12
归零一样,front
和 rear
也应该满某个数后归零,这个数就是 MAXSIZE
,就是约束这个循环一周的块个数也就是队列长度。比如rear = 7
时,如果按平常做法来 ,下一步应该是rear = 8
,但在这里,我们让其归零,所以下一步应该是rear = 0
。用数学公式来表示上面的归零过程就是:rear % MAXSIZE = 0
所以满队列的判断条件应该为:(rear + 1) % MAXSIZE = front
入队操作
前面我们规定,顺序队列的队尾下标为队尾元素的下一个元素,所以直接将待入队元素放入队尾下标处,然后队尾下标加一(注意:循环队列中的加一要对 MAXSIZE 取模)当 (rear + 1) % MAXSIZE == front
时队列就满
塞入数据,队尾是不断远离队头的
弹出数据,对头是不断接近队尾的
1 | /** |
链式队列
链队列的入队操作本质是单链表的尾插法:
1 | /** * 入队操作 |
出队操作
出队操作只允许元素从队头出。将队头下标处的元素出队,然后将队头下标“加一”(对 MAXSIZE 取模)。
1 | /** |
链式队列
链队列的出队操作本质上是单链表的头删法。注意,如果出队的是队列中最后一个元素,需要在出队后,将队尾指针重新指向头结点,重新形成空队列。
1 | /** |
遍历队列
判断队列为空的是rear==front
,借助临时变量 i
,从队头下标开始逐个加一直到队尾下标结束。开始标志为:i = front
、加一操作为:i = (i + 1) % MAXSIZE
、结束标志为:i % MAXSIZE = rear
1 | /** |
如何计算顺序队列的长度。当然你可以遍历队列然后借助计数变量来存储长度,这样比较麻烦。因为顺序队列是使用数组实现的,所以顺序队列的长度我们可以直接根据下标计算出来。如果是一个非循环队列,那很简单,直接 rear - front
就是队列的长度了。
但求循环队列的长度就不能这样直接减了,因为 rear
和 front
之间的位置关系是不确定的。
左图 rear < front
,我们可以将其长度看成两部分组成:
- 下标
0
到rear
,长度为rear - 0
- 下标
MAXSIZE - 1
到rear
,长度为MAXSIZE - front
所以长度为 rear - front + MAXSIZE
。为了满足右图rear > front
的情况,如果按照上式,则此时多加了一个 MAXSIZE
,所以需要对其再对 MAXIZE
取余。所以循环队列的长度为(rear - front + MAXSIZE) % MAXSIZE
(空队列也满足)。
遍历链队列
借助指针 p 从队头元素遍历至队尾元素即可。
1 | /** |
栈
栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。栈的特殊之处在于它限制了这个线性表的插入和删除位置,它始终只在栈顶进行。
而且栈是一种具有后进先出的数据结构,又称为后进先出的线性表,简称 LIFO(Last In First Out)
结构。也就是说后存放的先取,先存放的后取,这就类似于我们要在取放在箱子底部的东西(放进去比较早的物体),我们首先要移开压在它上面的物体(放进去比较晚的物体)。
堆栈中定义了一些操作。两个最重要的是PUSH和POP
。PUSH
操作在堆栈的顶部加入一个元素。POP
操作相反,在堆栈顶部移去一个元素,并将堆栈的大小减一。
用数组实现栈的关键在于:我们可以直接使用一个数组来存储数据,并通过控制指针或索引来实现栈的先进后出(LIFO)功能。
- 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中直到子程序执行完后再将地址取出,以回到原来的程序中。
- 递归的调用:可以用来在函数调用的时候存储断点, 储存下一个指令的地址外,也将参数、区域变量等数据存入栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图形的深度优先搜索法。
1 |
|
括号配对*
利用栈来验证一个字符串中的括号是否完全配对会非常简单,因为右括号一定是和最靠近自己的一个左括号配对的,这就满足了后进先出的特性。所以我们可以直接遍历字符串,遇到左括号就入栈,遇到右括号就看看是否和当前栈顶的括号匹配,如果不匹配则不合法,如果匹配则将栈顶元素出栈,并继续循环,直到循环完整个字符串之后,如果栈为空就说明括号恰好全部配对,当前字符串是有效的。
给定一个只包括'(',')','{','}','[',']'
的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合;左括号必须以正确的顺序闭合。
1 | // 定义栈结构 |
表达式求值
算法表达式也是栈的一个经典应用场景,为了方便讲解,我们假设表达式中只有 +、-、*、/
四种符号,然后我们要对表示式 18-12/3+5*4
进行求解应该如何做呢?
其实这道题也可以利用两个栈来实现,其中一个用来保存操作数,称之为操作数栈,另一个栈用来保存运算符,称之为运算符栈。具体思路如下:
- 遍历表达式,当遇到操作数,将其压入操作数栈。
- 遇到运算符时,如果运算符栈为空,则直接将其压入运算符栈。
- 如果运算符栈不为空,那就与运算符栈顶元素进行比较:如果当前运算符优先级比栈顶运算符高,则继续将其压入运算符栈,如果当前运算符优先级比栈顶运算符低或者相等,则从操作数符栈顶取两个元素,从栈顶取出运算符进行运算,并将运算结果压入操作数栈。
- 继续将当前运算符与运算符栈顶元素比较。
- 继续按照以上步骤进行遍历,当遍历结束之后,则将当前两个栈内元素取出来进行运算即可得到最终结果。
给你一个有效的字符串表达式 s,请你实现一个基本计算器来计算并返回它的值,整数除法仅保留整数部分,s 由整数和算符 ('+', '-', '*', '/')
组成,中间由一些空格隔开。
1 | // 定义数字栈和运算符栈 |
堆
堆是一种特殊的树,广泛应用于排序,搜索,优先级队列,求中位数等场景。堆总是一棵完全二叉树。标准定义上,我们认为一颗树满足以下的两点,就是一个堆
- 一颗完全二叉树
- 每个节点的值大于等于(或小于等于)其子树中每个节点的值
根据子节点与父节点值的大小关系,可以把堆分为,
- 最大堆(也叫大根堆,大顶堆),任意父节点都比其子节点的值要大
- 最小堆(也叫小根堆,小顶堆),任意父节点都比其子节点的值要小
比如上图中, 1、2 为最大堆,3 是最小堆,4 不是堆。
堆的实现
要实现一个堆,我们可以先思考,如何存储一个堆。
树的存储方式一般有链式存储和线性存储,分别对应我们常见的链表和数组两种方式,对于完全二叉树而言,用数组来存储是非常节省存储空间的,因为不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点,所以堆我们一般也用数组来存储。
假设我们从数组下标 1
开始存储,不难发现,对于下标为 i
的任意节点,存在以下关系,
1 | // 其左子节点的索引满足 |
为什么我们要从数组下标 1 开始存储,从 0 开始不行吗?
当然可以,如果从 0 开始存储,在代码的实现上,只是计算子节点和父节点的下标的公式改变了,对于下标为 i 的任意节点,
1 | // 其左子节点的索引满足 |
那为什么我们不从下标 0 开始存储呢?我想你应该已经猜到答案了,这里与 数组下标从 0 开始计数,而不是 1 开始 有着异曲同工之妙,我们从下标 1 开始存储,每次计算子节点和父节点时,都可以减少一次加法操作,本质是为了提高代码的性能。
知道了如何存储一个堆后,我们接着来看堆都支持哪些操作?一般来说,堆有几个核心的操作,比如往堆中插入一个元素,删除堆顶元素。
堆的插入
往堆中插入一个元素后,为了保持堆的特性,我们需要对插入元素的位置进行调整,这个过程叫做堆化(heapify),以最大堆为例,
堆化的过程其实非常简单,比如上图中我们往最大堆中插入一个元素 “22”,为了保持堆的特性,只需要顺着节点所在的路径,向上与其父节点进行对比交换,直到满足大小关系即可,
1 | class Heap { |
往堆中插入数据我们解决了,如何从堆中删除数据呢?
堆的删除
堆中数据的删除我们可以先考虑删除堆顶元素。
从堆定义的第二条我们发现,堆顶元素存储的就是堆中数据的最大值或者最小值,以最大堆为例,最容易想到的是:删除堆顶元素后,把子节点中较大的元素放到堆顶,然后迭代地删除第二大节点,以此类推直到叶子节点被删除,
这种方式有没有什么问题呢?
从上图我们发现,删除后可能会出现数组空洞,而且最后堆化出来的堆并不满足完全二叉树的特性,有没有更好的办法呢?这里我们可以尝试换一种思路,先删除叶子节点(最后一个元素),把它放到堆顶(与堆顶元素交换),然后从上往下进行堆化,
因为我们移除的是数组中的最后一个元素,而在堆化的过程中,都是交换操作,不会出现数组中的空洞
,所以这种方法堆化之后的结果,肯定满足完全二叉树的特性。
1 | // 从上往下堆化 |
这样一来,删除堆顶元素就很简单了
1 | function removeMax() { |
如果我们要删除堆中的任意一个节点的元素,应该怎么做呢?
类似的,我们只需要将数组的最后一个元素与要删除的节点元素互换,然后从要删除的节点开始从上往下堆化即可,这里你可以试着实现一下。我们来讨论一下上面两个核心操作的时间复杂度。
首先,对于一个包含 n
个节点的完全二叉树,树的高度不会超过 log2n
,堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,用大 O 复杂度表示法就是 O(logn)
;我们发现插入和删除主要逻辑就是堆化,其他操作都是常数级别的
所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn)
。
堆排序
我们知道 堆排序 是时间复杂度为 O(nlogn)
的原地排序算法,具体是怎么实现的呢?
堆排序的过程大致可以分为两步,建堆和排序。
堆的构建
建堆意味着我们需要将数组原地构建成一个堆,一般有两种思路,
- 往堆中依次插入元素,我们假设起始堆中只包含一个数据,就是下标为 1 的数据,然后将下标从 2 到 n 的数据依次插入到堆中
- 从最后一个非叶子节点开始,从上往下进行堆化
第一种思路是最容易想到的,我们需要遍历整个数组然后对每个数据进行插入操作,但时间复杂度较高,为 O(nlogn)
;第二种思路不太好理解,这里我们展开一下,
前面我们提到,对于完全二叉树,根据数组存储规律,不难发现下标 n/2+1
到 n
的是叶子节点,下标 1
到 n/2
是非叶子节点,叶子节点不需要堆化,这里我们只需要对非叶子节点进行堆化就可以构建堆, 还是以最大堆为例,
我们从最后一个非叶子节点开始,从上往下进行堆化
1 | // 构建最大堆 |
我们知道每个节点堆化的时间复杂度是 O(logn)
,那 n2+1
个节点堆化的总时间复杂度是不是就是 O(nlogn)
呢?
实际上,建堆的时间复杂度是 O(n),为什么?我们来分析一下。
建堆的过程中叶子节点是不需要堆化的,所以需要堆化的节点是从倒数第二层开始,每一层我们需要比较和交换的次数,和树的高度成正比,
所以建堆的时间复杂度,就是除最后一层外,每层节点比较和交换的次数之和,
这个公式的求解非常简单,我们把公式左右都乘以 2 得到另一个公式 S2
,然后将 S1
和 S2
错位对齐求差值得到,
S
的后面部分是等比数列,带入等比数列的求和公式
前面提到树的高度 h=log2n
,代入公式S
,就能得到 S=O(n)
,所以,建堆的时间复杂度是 O(n)
。
堆排序
构建好堆后,排序就很简单了,我们发现数组中的第一个元素就是堆顶,也就是最大的元素,假设我们要从小到大对数据进行排序,应该怎么做呢?
是不是只需要把堆顶元素与最后一个元素(下标为 n 的元素)进行交换,这样最大的元素就排到了数组末尾,接着通过堆化的方法,将剩下的 n−1 个元素重新构建成堆;然后再取堆顶的元素,与倒数第二个元素(下标是 n−1 的元素)交换,一直重复这个过程,直到最后堆中只剩下标为 1 的一个元素,排序工作就完成了,
1 | // 堆排序 |
我们来分析一下堆排序的空间,时间复杂度和稳定性,
- 堆排序是原地排序吗?是,堆排序只需要存储极个别的变量,空间复杂度是
O(1)
- 堆排序的时间复杂度是多少?前面我们提到,堆排序分为建堆和排序两个过程,建堆是
O(n)
,排序是O(nlogn)
,根据加法法则,堆排序整体的时间复杂度为O(nlogn)
- 堆排序是稳定的排序算法吗?不是,排序的过程我们会将堆顶元素与最后一个元素交换,这里是有可能改变值相同数据的原始相对顺序的
Top K 问题
求 Top K 问题可以抽象为两类,静态数据集合和动态数据集合。针对静态数据,最经典的是,如何在包含 n 个数据的数组中,查找前 k 大的数据呢?
这里如果用堆来解决,思路是什么样的呢?我们可以维护一个大小为 k 的最小堆,然后顺序遍历数组,从下标为 k + 1 的元素开始,与堆顶元素进行比较,
- 如果比堆顶元素大,我们把堆顶元素删除,将这个元素插入到堆中
- 如果比堆顶元素小,则不做处理
这样数组遍历完后,堆中就是前 k 大的数据,
1 | // 交换元素 |
上面利用堆求 Top K 的时间复杂度是多少呢?我们来简单分析一下,
首先这里我们只对 k 个元素构建了最小堆,每次堆化的时间复杂度为 O(logk)
,建堆 (0,k)
和遍历数组 (k+1,n)
整体的时间复杂度为 O(n)
,所以通过上述方式求 Top K
的时间复杂度为 O(nlogk)
,其中 n
是静态数据的大小。
当然,实际的应用场景中我们可能会遇到动态数据集合,如何针对动态数据求 Top K 呢?
动态数据求 Top K 其实就是求实时 Top K,想象一下,如果我们每次都基于当前动态数据重新去计算的话,那时间复杂度就是O(nlogk)
;有没有什么办法能更高效地查询 Top K
呢?
有。实际上,我们可以一直维护一个大小为 k 的最小堆,当有数据被添加到集合中时,我们就拿它与堆顶元素进行对比,跟前面类似的,
- 如果比堆顶元素大,把堆顶元素删除,将这个元素插入到堆中
- 如果比堆顶元素小,则不做处理
这样,每次数据添加的时候,其实只做了一次常数级别的堆化处理,带来的好处是,无论任何时候查询 Top K,我们都可以在 O(1)
的时间复杂度内立即返回。
字符串
搜索引擎常用的自动补全功能就是一种字符串匹配的应用,因此我们需要理解字符串这一数据结构。字符串(串)是由零个或多个字符组成的有限序列,通常记作:s = “a₁a₂…aₙ”,其中 n 为字符串的长度,n≥0。如果 n=0,则称为空串,用 ""
表示。
需要注意的是,空格串虽然只包含一个或多个空格字符,但它与空串不同,空格串是有实际内容的
串的存储结构
在计算机中,字符串通常存储在一组地址连续的存储单元中。使用定长数组定义字符串是常见的做法,这样的数组有一个固定的最大长度,但实际字符串的长度通常小于这个最大值。为了处理这个问题,我们需要记录实际字符串的长度,有时这个长度信息存储在数组的第一个元素(索引 0)处,或者存储在最后一个元素的位置。字符串通常以 '\0'
(空字符)结尾,以标示字符串的结束。
然而,使用 '\0'
来标记字符串结束存在潜在的风险:如果不慎遗漏了 '\0'
,会导致指针越界,从而引发不可预期的错误或安全隐患。为了避免这种情况,在 C 语言中,我们通常将字符串封装到结构体中。这个结构体通常包含两个元素:
- 字符数组:用于存储字符串内容。
- 长度信息:用于记录字符串的实际长度。
定长顺序存储
采用字符数组将串中的字符序列一次连续存存储在数组中的相邻但愿中,常量串和变量串的存储结构不同,数组容量length
分半等于或者大于串长度n.
顺序存储的串具有随机存取特效,存取指定位置字符的时间复杂度为O(1)
,缺点是插入和删除元素时需要移动元素,平均移动数据量是串长度的一半,当数组容量不够时,需要重新申请一个更大的数组,并复制原来数组中的所有元素,插入和删除操作的时间复杂度为O(n)
链式存储结构
串的链式存储结构:有单字符串链表和块链表两种,但字符串链表是每个节点的数据域只包含一个字符的单链表,块链表是每个节点的数据域包含若干个字符的单链表。链式存储的串,存取指定位置字符的时间复杂度为 O(n),单字符链表虽然插入/删除操作不需要移动元素,但是占用存储空间太多,块链表的插入和删除操作需要移动元素,效率低。
字符串匹配
在进行文本编辑时候,我们经常查找和替换,在文档的指定范围内查找一个单词的位置,用另一个单词替换,替换操作的前提是查找操作,如果查找到指定单词,则确定了操作位置,可以将指定单词用另一个单词替换掉,否则不能进行替换操作,每进行一次替换操作,都需要执行一次查找操作,那么如何快速查找指定单词在文档中的位置呢,就是串的模式匹配算法需要解决的问题,
设有2个串,目标串target
和模式串 pattern
,在目标串target
中查找与模式串pattern
相等的一个子串并确定该子串的操作称为 串的模式匹配,两个子串相等指的是:长度相等且对应各个字符相同,匹配结果有两种 如果target存在pattern相等的子串,则匹配成功 获得该子串在target中的位置,否则匹配失败给出失败信息。
BF算法
BF 算法,亦即 Brute Force
暴力算法,是普通的模式匹配算法。BF 算法的思想就是将文本串 s
的第一个字符与模式串 p
的第一个字符进行匹配:
- 若相等,则继续比较
s
的第二个字符和p
的第二个字符 - 若不相等,则比较
s
的第二个字符和p
的第一个字符
依次比较下去,直到得出最后的匹配的结果。
BF 算法是一种蛮力算法,没有任何优化,就是用两层循环的比较,当字符串比较大的时候,执行效率就非常低下,不适合比较非常大的字符串。
1 |
|
KMP算法
在 KMP 算法中,当发现字符不匹配时,不会重新从头开始比较,因为之前已经匹配的部分提供了有用的信息。利用这些信息,子串可以直接移动到合适的位置继续比较,从而避免了重复操作。KMP 的时间复杂度为 O(m+n)
,即与两个字符串长度之和成线性关系。接下来我们来讨论着有用的信息是什么
- 字符串的前缀后缀
字符串匹配的过程就是模式串指针不断移动的过程,在BF算法中,通过两个指针分别维护目标串和模式串。匹配成功两个串的指针就向右移动一格。匹配失败,则模式串指针归0
,目标串的指针前进一格。记录这个前后缀的目的就是让模式串的指针不会一下就掉到0,而是采用next
数组回跳到一个大于模式串起点的位置。这个next
数组就是采用前缀后缀构成的。
对于字符串 ababc
来说,它的前缀有 [a,ab,aba,abab]
,也就是以字符串第一个字符作为开头,同时不包括最后一个字符的所有子串,同理它的后缀有 [c,bc,abc,babc]
,也就是以字符串最后一个字符作为结尾,同时不包括第一个字符的所有字串。
了解了这个,我们再来说什么是字符串的最长公共前后缀,说白了,也就是前缀和后缀这 2
个集合中的相同部分,同时取最长的那个,就是这个字符串的最长公共前后缀。显然,在这个例子中,ababc
是没有公共前后缀的。但是对于 abab
,它的前缀和后缀分别是 [a,ab,aba]
和 [b,ab,bab]
,那么它的最长公共前后缀就是 ab
。
现在,我们的目标就是取得 ababc
所有子串 [a,ab,aba,abab,ababc]
的最长公共前后缀的长度,分别保存在 next
数组中,我们只要知道最大长度即可,并不用关心串具体是什么,而我们目前通过观察即可得出 next
数组这里是 [0,0,1,2,0]
。
- next数组的作用
得到这个数组有什么用,当我们第一次碰到不匹配时(i
和 j
都等于 3 的时候)
此时i
和 j
之前的3
个字符 aba
必然完全匹配的,因为只有前面匹配成功了 j
才能走到 3,这样我们就知道了主串的后缀信息,而我们又知道 aba
的最长公共前后缀是 a
,这可以给我们一个很好的提示,主串中的 aba
的后缀和子串中的 aba
前缀有最长的公共部分 a
,这样一来,我们就没必要让重新比较了,直接将相同部分对齐就好了,也就是说让j
退回到位置 1
就可以了,而 i
保持不变。
前后缀的目的是通过比较目标串的后缀和模式串的前缀来优化匹配过程。也就是匹配失败的时候,子串的前缀位置退回到与主串相同后缀位置。
分析一下,为什么j
知道应该退回到位置 1
:
- 我们知道
j
是在位置3
不匹配的,那么j
前面的字符串我们可以知道是aba
- 前面我们已经得到了
next
数组,知道aba
的最长公共前后缀长度是1
- 也就是说,我们可以知道
i
之前1
个位置(主串的后缀)和子串开头之后1
个位置(子串的前缀)是相同的 - 进而我们可以让相同部分对齐,也就是让
j=next[j-1]
接下来,我们发现i
和j
仍然不匹配,而 j
之前的字符 a
最长公共前后缀是 0
,此时j
退到位置 0
(模式串前进一步),i
仍然保持不变。
i
和j
匹配,同时右移一格
此时i
和j
不匹配,j=next[j-1]
回退到 0
,然后我们发现 i 和 j 仍然不匹配,同时 j
已经是 0
了,那么我们就让i
往右移动一格。这里就和BF
算法一样了。
可以看到,相比于暴力解法,i
始终在前进,并没有后退(顶多保持不变),然后我们通过 next
数组来改变j
的值,使得主串的后缀和匹配串的前缀相同的位置拟合。
1 |
|
求解next
数组
最后,我们还剩下一个问题,如何求next
数组,也就是求模式字符串各个子串的最长公共前后缀长度。
我们先初始化一个和模式字符串长度相等的 next
数组,在next
数组中,第 1
位默认为 0
,因为我们规定只有一个字符的字符串没有前缀和后缀,自然公共前后缀长度只能是 0
。我们依然设定 2
个指针i
和j
,j
指向位置 0
,i
从位置 1
开始依次为 next
数组进行赋值
我们可以把这个过程依然看作是 2 个字符串的比较,j
指向的是模式字符串的前缀,而 i
指向的是模式字符串的后缀
和上面的字符串匹配一样,我们执行同样的处理:
- 当
i
和j
匹配时,i
和j
同时右移一格 - 当
i
和j
不匹配时,如果j
不在字符串开头(位置0
),就回退到上一个能匹配到的位置 - 当
i
和j
不匹配时,如果j
在字符串开头(位置 0),那么i
就右移一格
对next [1]
赋值:i
和 j
不匹配,同时j
已经是字符串开头,赋值 0
对 next [2]
赋值,i
和j
匹配,此时j
为0
,代表只有 1
个字符匹配 (j+1
),赋值 1
对 next [3]
赋值,i
和j
匹配,此时j
为1
,代表有 2
个字符匹配 (
j+1)
,赋值 2
对 next [4]
赋值,i
和 j
不匹配,此时 j
为 2
,可以得知 j
前面的字符是 ab
,而 ab
的最长公共前后缀长度就是 next[1]
,这个值我们前面已经求得了结果是 0
,所以j
回退到位置 0
,用代码表示就是 j=next[j-1]
此时 i
和j
仍然不匹配,但是j
已为0
,无法继续回退,所以直接对 next [4]
赋值为0
实际上,我们在求解模式字符串 ababc
的最长公共前后缀长度的时候,不可避免的会对它的子串进行求解,这样可以方便在不匹配时进行回退,这也是动态规划的思想,要求的结果可以用先前已经求得的结果得出。而我们本身就是要对模式字符串的各个子串进行求解,所以可谓一举两得。
1 |
|
对比一下上一段的字符串匹配代码,可以发现,2 段代码的执行逻辑几乎一模一样,不同之处只是我们在比较过程中插入了对 next
数组进行赋值的代码。
可以这样理解,在字符串匹配中,i
指向的是主串,j
指向的子串,比较的是主串和子串。而在求公共前后缀的时候,我们相当于把模式字符串拆成了前后两部分,同样是对这 2 部分进行字符串匹配,相当于自己比自己。
以上就是 KMP 算法的核心原理及实现,当然,实现方式并不是只有这一种,KMP 的实现算法多种多样,包括生成的 next
数组都会不一样.
- KMP 通过计算模式字符串自身得到 next 数组;
- 不匹配时通过 next 数组信息进行回退,而不用再从头开始比较;
- 原理就是利用模式字符串的公共前后缀信息,所以算法是奏效的。