基础数据结构归档

这里是一些基础数据结构知识点的整理,有基本概念,线性表,链表,树,图,哈希表等。该部分内容是曾在2018年和2019年发布的。

当前博客显示的发布时间非真实时间,而是这些内容在当时发布时的最后发布时间。

数据结构的基本概念

利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时,实际需要处理的元素一般会有很多,而这些大量的数据都要存放在计算机中。因此,大量的数据元素在计算机中如何组织,提高数据处理的效率,并且尽量节省存储空间,是进行数据处理的关键问题。

数据结构主要研究和讨论以下三个方面的问题,目的是提高数据据处理的效率。所谓提高效率主要体现在两个方面:一是提高数据处理的速度,二是尽量节省数据处理过程中所站的计算机存储空间。

1.数据的逻辑结构

2.数据的存储结构

3.对各种数据结构的运算

简单来说,数据结构是指相互有关联的数据元素的集合。数据元素具有广泛的含义,一般来说,现实世界中客观存在的一切个体都可以作为数据元素。

数据的逻辑结构

对于一个给定的数据结构,它应该包含表示数据元素的信息,以及表示各个数据间的前后关系。这里数据间的前后关系是指的它们的逻辑关系,而与它们在计算机中存储的物理位置无关。所以,数据的逻辑结构一般有两个要素,一是数据元素的集合,二是它们之间的逻辑关系。

举个例子,对于图这种数据结构,通常我们用G来表示一个图,一张图通常由两个集合构成,一个是点集V,另一个是边集E。则这个图就可以表示成:

G = {V,E}

要注意,对于一些复杂的数据结构,它的数据元素也可以是一种数据结构。

数据的存储结构

前面说到,一个数据结构中的各个数据元素在计算机存储空间中的位置关系与逻辑关系是极有可能不相同的。实际上,数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。在数据的存储结构中,不仅要存放各种数据元素的信息,还需要存放各种数据元素间的前后关系。

线性结构和非线性结构

通常的,我们根据数据结构中各个元素之间的前后关系的复杂程度,一般将数据结构分成两大类型:线性结构和非线性结构。

如果一个非空的数据结构满足有且只有一个根节点,并且每一个节点最多只有一个前驱或者后继,那么这样的数据结构我们称之为线性结构,有的资料或文献中也称作“线性表”。在线性结构中各个数据元素之间的前后关系都是比较简单的。需要特别说明的是,在一个线性结构中插入或删除任何一个节点后应该还是线性结构,不满足该特性的数据结构也不是线性结构。比如下图所展示的数据结构,就不是一个线性数据结构。

不满足线性数据结构定义或特性的,统称为非线性数据结构。

非线性数据结构要比线性数据结构复杂得多,因为它通常会包含更多的前后关系。线性结构与非线性结构都可以是空的数据结构。

线性表

一种最简单并且最常用的数据结构。它由一组数据元素构成。数据元素既可以是简单的,又可以是复杂的。比如矩阵,我们可以把矩阵理解为一个线性表,其中每一行/每一列的数据就可以作为一个数据元素。在这种复杂的线性表中,由若干数据项组成的数据元素称之为记录。总的来说,线性表是一个具有n个元素的一个有限序列。它满足线性数据结构的性质,也就是对于任何一个结点,只会有最多一个前驱和一个后继。

数据元素在线性表中的位置只取决于它们自己的序号,而 不一定 取决于它们的物理位置。此外,一个非空的线性表有如下的结构特征:

1.有且只有一个根结点,它没有前驱。

2.有且只有一个尾结点,它没有后继。

3.中间的结点有且只有一个前驱和后继。

在线性表中,结点的个数n代表线性表的长度。当n = 0时,称为空表。

线性表的顺序存储结构

这是最简单的存放线性表的方法。它也被称为顺序分配。

线性表的顺序存储结构具有以下两个基本特点:

1.所占存储空间是连续的。

2.各数据元素在存储空间中是按照逻辑顺序依次存放的。

如果采用了线性表的顺序存储结构,那么对于某个元素,它的前驱和后继在存储空间(物理位置)中是紧邻的。对于顺序存储结构,如果各个数据元素所占的存储空间相等,那么查找元素是比较方便的。(其实大多数情况下这个条件是满足的)

对,其实就是一维数组……

在顺序存储结构中,线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。这句话怎么解释呢?我们可以想一想,一维数组在硬件里是怎么存储的?

借助这张图来了解是比较直观的。

实际上,头结点所对应的地址称作为首地址,后续的结点地址是连续的,那么自然就会产生一个相对于首地址的位置差值,这个差值我一般称之为“偏移量”。也就是说,在这样的线性表中,每个数据元素都可以用“首地址+偏移量”来表示。

但是要注意的是,上图中的每一个值都只占一个字节,所以地址会按照1,2,3,……这样的顺序来变化。实际上,如果每一个数据元素占k个字节的话,偏移量也是按照k的倍数来变化的。

对于一个线性表,它的操作一般有如下几种:

1. 在指定位置插入新元素
2. 删除指定位置的元素
3. 查找某个元素
4. 排序
5. 分解线性表
6. 合并线性表
7. 复制线性表
8. 逆转线性表

计算机二级考察插入和删除操作。

线性表的插入操作

刚才说到,顺序存储结构的线性表可以用一维数组来表示,那么这个问题其实就是如何在一个一维数组中插入一个元素的问题。

通常的,在定义一维数组时,数组的长度要比实际用到的长度要长一些。如果长度太短,会导致存储空间不够而无法进行操作,但是长度太长的话又会造成浪费。具体要开多大,自己掂量着来。

插入操作大致的分三步。

1. 找到要插的位置
2. 让后面的元素全部后挪一位,腾出空来
3. 插♂ 进去

特殊的,如果要在线性表的末尾插入元素,那么直接第三步就好。

不难看出,在大多数情况下,进行插入操作都要进行元素的移动。一般的,如果要在i位置插入一个元素,那么第i个元素(包括他本身)以及之后的元素都要做对应的移动。在平均情况下,要在线性表中插入一个元素,需要移动大约一半的元素。这个效率其实是很低的,尤其是在线性表比较大的时候。

此外要注意,当存储空间已满,整个数组的所有位置都存放了数据时,插入操作无法进行。该操作一定要在编写代码时体现出来。

移动操作是倒着来的。即先从尾结点开始,向后移动一个偏移量,之后尾结点之前的每一个元素都要向后移动一个偏移量,一直到插入位置为止。

最后,在腾出来的空位上插入新元素,线性表长度+1。

线性表的删除操作

删除操作也是三步。

1. 找到要删除的位置
2. 该位置之后的元素全部前移一位(本质上是一种复制后的覆盖)
3. 多余的尾结点清空

特殊的,如果要在线性表的末尾删除元素,那么直接清空尾结点就好。

该操作的效率也比较低,道理同上。

此外,当线性表为空表时,不能进行删除操作,如果试图删除一个不存在的结点,也是不可以的。

一定注意不要忘了第三步,清空尾结点。清空的同时线性表长度-1。

总结

对于顺序存储结构的线性表,其优点在于定义方便,易于操作,但是缺点也是很明显的,插入和删除操作的效率很低。

那么它适用于什么情况呢?

对于数据量小的问题,或者是元素不经常变动的问题来说,使用顺序存储结构的线性表是比较简单的。如果数据量大,并且元素还要经常变动,那么可以考虑使用链式存储结构的线性表(链表)。

之前介绍的线性表的顺序存储结构具有一定的不足之处。比如插入或删除元素的效率较低,同时,它的大小是固定的,在操作时需要注意空间的限制。今天要介绍的链表就能很好的解决这些问题。

链表

链表这种数据结构其实也是一种线性表,但它并不是顺序存储结构,而是一种链式存储结构。

链式存储结构的基本单元称为结点。每一个存储单元都可以存放若干数据。

在链式存储结构中,通常要求每个结点包括两个信息。一是数据域,记录该结点的数据, 二是指针域,用来存放指向下一个结点或者前一个结点的指针。

之前我们说到,顺序存储结构要求地址必须是连续的,但是链式存储结构不需要。它们之间由指针域连接在一起,所以存储空间可以不连续(也就是说可以是连续的,这点一定注意)。

链式存储结构既可以用来表示线性结构,也可以用来表示非线性结构。在使用链式存储结构存储比较复杂的数据结构时,它的指针域的个数要稍微多一些。

线性链表

顾名思义,这就是线性表的链式存储结构。其实我们通常说“链表”,指的就是这个。

线性链表与链表在特性上是相似的。在存储链表时,计算机会将一个结点分成两部分:一部分用来存储数据元素的值,另一部分存储指向下一个结点的指针,或者,下一个数据元素的存储序号。

画一下示意图:

在线性链表中,使用一个专门的指针HEAD指向链表中第一个数据元素的结点(注意并不是指向数据域)。

尾指针不指向任何位置,可以设为NULL或者0。

对于线性链表,可以从头指针开始,沿着各个结点的指针扫描到链表中的所有结点。

其实完全可以给出一个思路。使用for循环来遍历整个链表,循环的初值是头结点,边界是还存在下一个结点,每循环一层,就沿着指针域跑到下一个结点。循环体输出当前结点数据域的信息即可。

这种链表也叫做单向链表,它只能找到后继而不能找到前驱(或者只能找到前驱而不能找到后继),如果想要找到它的前驱,必须再次从头结点进行寻找。

所以为了弥补这个缺点,人们开发出了双向链表。

双向链表的每一个结点具有两个指针域,一个指向前驱一个指向后继。

图中L指的是左指针域 R指的是右指针域,D指的是数据域。

链式栈

其实就是把顺序存储的栈变成链式存储的栈。

对栈的操作都在头结点上进行。在实际的应用中,带链的栈可以收集计算机存储空间中所有空闲的存储结点。这种链式栈称为可利用栈。由于可利用栈连接了计算机存储空间中所有的空闲结点,因此,当计算机系统或者用户程序需要存储结点时,就可以从中取出栈顶结点。同样,释放一个结点时将返回栈顶。随着其他线性链表的插入与删除,可利用栈处于动态变化之中。即可利用栈经常要进行退栈与入栈操作。

对于一个链式栈,它的基本操作和普通栈是差不多的。

1.初始化。建立一个空栈。

2.入栈。在栈顶插入一个新结点。它分为两步。

第一步,将新节点的指针域指向原头结点。

第二步,头指针上移至新结点。栈长度+1。

3.出栈。也是分两步。

第一步,头指针指向第二个结点。

第二步,第一个结点的指针域指向空。

4.读栈顶元素

很简单,因为头指针就直接指向栈顶,所以只需要访问头指针所指的结点即可。

链式队列

和链式栈类似。队首是头结点,队尾是尾结点。

图我就不画了,和链式栈是一样的,只不过头结点指针变成了队首指针,尾结点加一个队尾指针即可。

链式队列的操作也和通常队列几乎一样。

1.初始化队列。

2.入队。在队尾添加一个新结点就好。

第一步,原尾结点的空指针改为指向新结点。

第二步,新节点的指针域指向空。(如果原来就是空的那就不需要这一步)

3.出队。与出栈相同。

线性链表的基本运算

线性链表的基本运算有很多,比如插入、删除、合并、分解、逆转、复制、排序、查找等。这里主要说一下查找,插入和删除。

1.查找元素

这是删除和插入的基础。因为在链表中,要想在中间插入或删除中间的某个元素,必须要先通过遍历找到它们的位置。

遍历整个列表,在每个结点看值是多少,有就返回已找到,已经到头都找不着就返回没找到。

2.删除元素

思路和上文所述是一致的,遍历一遍整个链表,每次遍历到某个结点,就通过它的指针域看一下下一个结点的数据域是啥,如果是我要删除的元素,那么,我就把当前结点的指针域指向当前指针域指向的结点的指针域指向的下一个结点,然后把要删除的结点的指针域设为空即可。

(有点晕是吧……慢慢捋一下

当前结点是我要删除的结点的前驱结点。我要删除我的后继,我就要把我的后继“孤立”起来。那么我分两步去做这件事。第一步,我要把我的指针域连到跳过这个要删除的结点的位置,也就是我后继的后继。可是我是无法访问我的后继的后继的,我只能通过我的后继去访问我的后继。我有一个通向我后继的指针,当我到达我的后继时,我会再通过我的后继的指针域找到我后继的后继,这个指向我后继的后继的指针域我就找到了,我就可以把我的指针域连在上面。那么我后继的指针怎么处理呢?孤立啊,指向空位置就好。

3.插入元素

我们默认是插入到某结点之后。这个就比较简单了。首先遍历找到这个结点,然后让新结点的指针域指向它的后继,最后让这个结点的指针域指向新结点。

为什么不能先让这个结点的指针域指向新结点呢?

先指过去你的后继不就全没了吗……你还怎么连后边的结点啊……

总结一下,对于链式结构的插入和删除,只需要改变指针域,而不需要移动数据元素。这一点就比线性结构优秀很多。另外,对于删除后被孤立的结点,我们不应让它浪费掉,应该把它送回可利用栈。

循环链表

其实刚才所说的链表还存在一个问题。对于空结点和头结点的插入和删除操作,没法通过循环实现,必须加特判。而且,线性单链表的访问不是自由的,必须从头结点开始,如果想要从中间的结点开始遍历整个链表,可能比较麻烦。这时候,循环链表就可以解决这个问题。

实现很简单。尾结点原本是指空的,只需要指向头结点就可以。

(PS:栈与队列可以配合https://www.cnblogs.com/OIerShawnZhou/p/7277322.html食用)

栈也是线性表的一种。它是一种特殊的线性表。它限定在一段插入或删除。你可以把栈形象地理解为一个任何有底无盖的容器,我们每次对栈进行操作都是在顶部进行。对于这个“容器”,它的顶部我们称之为栈顶,它的底部我们称之为栈底。不难得出一个性质,对于栈顶元素,它总是最后一个被插入,总是最先被删除。我们一般把栈的插入操作叫做入栈,相应的,删除操作叫做出栈(有的也叫退栈)。

栈是按照先进后出(FILO)的原则组织数据的,因此,栈也被称作“先进后出”表或者“后进先出”表。

通常的,我们用一个指针top来表示栈顶的位置。

栈在系统中的用途

举一个简化后的例子好了。比如说一个嵌套调用的程序,计算机怎么处理呢?

先看一下(伪)代码示意:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//...  

int main{
//do something.
f1();
//f1返回后会到达这里,记录返回点地址为A
//do something.
}
void f1(){
//do something.
f2();
//f2返回后会到达这里,记录返回点地址为B
//do something.
return;
}
void f2(){
//do something.
f3();
//f3返回后会到达这里,记录返回点地址为C
//do something.
return;
}
void f3(){
//do something.
f4();
//f4返回后会到达这里,记录返回点地址为D
//do something.
return;
}
void f4(){
//do something.
return;
}

计算机在执行这样的程序的时候,要一层一层地调用函数。而且还要做到进得去,出的来。这就需要一个辅助性的工具来帮助计算机记住进去了哪个函数,从这个函数出来要去哪。

此时,计算机就会使用线性表。它会这样做:

1. 开始执行程序前,计算机申请了一个空表。
2. 当发生函数调用时,计算机会找到它的返回点地址,并且塞到那个线性表的最后面。
3. 当程序从某个子程序返回时,计算机会从线性表中把最后插进去的返回点地址取出,并使用该地址。

模拟一下线性表的工作过程:

1. 一开始是空表[]
2. 进入main函数,遇到了f1,表变成了[A]
3. 进入f1,遇到了f2,表变成了[B]
4. 进入f2,遇到了f3,表变成了[ABC]
5. 进入f3,遇到了f4,表变成了[ABCD]
6. f4执行完毕,要退回f3,f3在哪啊?线性表告诉他,从f4出去要去D位置,于是线性表把D取出来给程序使用,表变成了[ABC]
7. 和上一步一样,从f3出去要到C位置,于是线性表把C取出来。表变成了[AB]
8. 同理,表变成了[A]
9. 程序执行完毕,表又空了[]

这便是一个最简单的栈。

栈的运算

和线性表一样,在程序设计中,我们也是要使用一维数组设定一个栈,同时要设定一个指针来表示栈顶。

其实有些时候,这里所谓的“指针”,可以不使用真正的指针而是使用一个变量代替,该变量所代表的值即为数组下标,该下标所标注的位置就是栈顶。

1.入栈

之前有说到,入栈运算是指的在栈顶位置插入一个新元素。

首先判断栈满,即判断线性表最后一个位置的指针和栈顶指针是否重合。如果重合,那么说明栈的存储空间已满,是无法进行入栈操作的。

如果栈不满,则栈顶指针上移,入栈。

2.出栈

首先判断栈空,如果栈顶指针与数组头指针重合(或者说,为0),此时是空栈,出栈操作没有意义。

然后(该操作可选)读栈顶元素,并用来做一些其他的事情。

最后栈顶指针-1。

3.访问栈顶元素

仍然需要先判断栈空。如果非空,则返回栈顶元素。这个操作不会删除栈顶元素。

队列

和排队处理任务时那样,大家都在一条线上等待,早来的早处理。在计算机系统中,如果计算机只能同时做一件事,那么当有多件事需要处理时,其他待做的事情就要“排队等候”。操作系统也会使用一种特殊的线性表来处理这样的排队事件。

这种特殊的线性表就是队列。它允许在一段进行插入,但是删除是在另一端。允许插入的一端称作队尾。(不是队头,一想就明白)允许删除的一端
称作队头。显然,在队列中,最先进来的元素一定是最先出去的,所以它是一种先进先出(FIFO)的线性表。

队列的运算

和栈差不多,入队,出队,读队首。我们假设数组是从左往右走的。

1.入队

首先判断队列有没有满。这里说“队列满”是比较特殊的,它是指队尾指针到达数组尽头。如果不满,则队尾指针+1,入队。

2.出队

队首指针+1即可,读队首操作也是可选的。

3.访问队首元素

先判断队空,再访问即可。

这里为什么说队列满是特殊的呢?实际上,这里的满是指队尾已到达数组尽头,但是队首可能并不在数组的开始位置,也就是说,这个数组可能是有一部分的空闲的,但此时仍然不能进行入队操作,这是通常队列的一个缺点。

所以,为了解决这个缺点,人们开发出了循环队列。

循环队列

与通常队列很相似,这也是实际应用比较广泛的一种队列,它的空间使用效率较高。

对于循环队列,当队尾已经到达数组尽头而又接收到入队指令时,它会判断队首之前是不是还有空位置,如果有,那么队尾就会跑到数组的前面,形成一个逻辑上的圈。

在循环队列中,队尾指针指向队列中的队尾元素,队首指针指向队首元素的前一个位置。

每进行一次入队运算,队尾指针+1,如果队尾指针=数组长度+1时,让队尾变成0。出队运算也是这样的。

不难得出,循环队列满的时候会有队首指针=队尾指针,但是队空时也满足这个性质。为了区别时队满还是队空,我们有时候会设置一个标记flag,它为0时表示队空,1表示非空。

不难得出,队空满足条件flag = 0。

队满满足条件flag = 1并且队首指针 = 队尾指针

入队运算分三步。

1.首先判断队列是否为满。当flag = 1并且队尾指针 = 队首指针时,说明队列满,不可以入队。若不满,进入第2步。

2.队尾指针+1,并判断是不是需要变换队尾指针。

3.新元素入队,flag变成1。

出队运算也分三步。如果同时需要取队首元素则是4步。

1.判断队空。如果flag = 0则队空,出队操作无意义。

2.队首指针+1,并判断是不是需要变换队首指针。

3.(可选)返回队首指针所指的元素,可以用来做其他事情。

4.判断出队后队列是否变为空。如果此时队首指针=队尾指针,则说明队列已空,把flag设成0。

树与二叉树

在介绍二叉树之前,先介绍一下树是什么。

它是一种一对多的数据结构,对于每一个结点,它只可能有一个前驱或者没有前驱,但是后继可以有一个也可以有多个,当然也可以没有后继。画出来比较像一棵倒长的树。

(图片来自网络)

可以看出,它具有很明显的层次关系。在描述各个结点之间的关系时,我们常用一些血缘关系中的术语。

对于一个结点,我们称它的前驱结点为它的父结点。对于最上面的那个没有父结点的结点,我们称之为树的根结点。对于一个结点,它的所有后继都是它的儿子,也就是子结点。

在一棵树中,一个结点所拥有的后继的个数称为该结点的度。这棵树中所有结点的最大的度称为这棵树的度。换句话说,如果一个结点的度数为n,那么就表示这个结点具有n个子结点。在树中,除根结点外,每一个结点都有一个唯一的分支指向它。由此不难得出,树中的结点数等于所有结点的度数+1。

树是按照一定的原则进行分层的。根结点在第一层,同一层上所有结点的子结点都在下一层。其中最底部的结点(叶节点)的层数是最深的。

二叉树

一种非常常用也非常有名的数据结构。树结构的术语完全适用于二叉树。

对于一棵二叉树,有且只有一个根节点,并且每一个结点最多有两棵子树,分别称为左子树和右子树。所以,二叉树中每一个结点的最大的度为2。当一个结点没有任何后继时,它是叶结点。

(图片来自网络)

二叉树的基本性质

1. 在二叉树的第k层上,最多有2k-1(k≥1)个结点。
2. 深度为m的二叉树最多有2m-1个结点。
3. 在任意一棵二叉树中,度为0的结点总是比度为2的结点多1个。
4. 具有n个结点的二叉树,它的深度至少是[log2n]+1。其中[log2n]是指的是log2n的整数部分。

完全二叉树与满二叉树

这是两种特殊形式的二叉树。

对于满二叉树,每一层上的结点都会达到它的最大值。也就是说,在第k层,一定有2k-1个结点。深度为m的满二叉树具有2m-1个结点。

完全二叉树只有一点不同。完全二叉树可以在最后一层的最右边缺少一些结点。对于完全二叉树来说,叶结点只有可能在层次最深的两层出现。

所以,满二叉树也算是一种特殊的完全二叉树。但是完全二叉树不一定是满二叉树。

完全二叉树还具有的性质:

具有n个结点的完全二叉树的深度为[log2n]+1。

如果设一个完全二叉树具有n个结点,从根节点开始,按层序用自然数进行编号,那么对于这些编号还具有以下结论:

1. 如果k=1,则这个结点是根节点。如果k>1,那么它的父节点编号是[k/2]。
2. 如果2k≤n,则编号为k的结点的左儿子的编号是2k,否则就没有左子结点。(由于完全二叉树的定义,当一个结点没有左子结点时,一定没有右子结点)
3. 如果2k+1≤n,则编号为k的子结点的右子结点的编号为2k+1,否则该子结点没有右子结点。

根据这些性质,如果按照从上到下,从左到右的顺序给一个完全二叉树进行编号,那么就很容易确定各个结点之间的编号关系。

二叉树的链式存储结构

和线性链表很类似。对于每个结点要设立两个指针域,一个指向左儿子,一个指向右儿子,如果它没有对应的儿子结点就指空。

要设立头指针指向二叉树的根节点。

二叉树的遍历

所谓二叉树的遍历,即是指不重复地访问二叉树中的所有结点。

由于二叉树是一种非线性结构,因此,对二叉树的遍历要比遍历线性表复杂得多。在遍历到二叉树的某个结点后,要面临两个选择:向左走和向右走。也就是说,遍历二叉树的方法实际上是确定访问各个结点的顺序,以便于不重不漏的访问到所有结点。

通常我们使用三种遍历方法。它们分别是前序遍历,中序遍历和后序遍历。

1. 前序遍历

所谓前序遍历,其实就是先访问根节点,再访问左子树,最后访问右子树。这是一个递归的过程,在每一个子树也要重复这样的过程。

比如还是用这张图来说一下:

如果二叉树为空则返回,否则先根,再左,最后右。

首先遍历根结点是A,然后是左子树BDEH,然后是右子树CFG。对于左子树再执行一样的操作,遍历出根节点是B,左子树D,右子树EH。对于左子树再执行一样的操作,遍历出左子树是空,右子树是空。对于左子树再执行一样的操作。发现是空,返回。对于右子树再执行一样的操作,发现是空,返回。此时返回到D,对于右子树再执行一样的操作,遍历出根节点是E,左子树是H,右子树是空。对于左子树再执行一样的操作,根节点是H,左右为空,然后去H的左子树,发现是空的,返回,右也是空的,返回。这样以A为根整个的左子树访问完毕,再考虑右子树。右子树根节点是C,左子树是F,右子树是G,F和G没有后继。

这样遍历出一个序列,该序列是ABDEHCFG,它叫做二叉树的前序序列。

2. 中序遍历

中序遍历是指的先访问左子树,再访问根节点,再访问右子树。它也是一个递归的过程。

从A出发,A是根节点,BDEH是左子树。CFG是右子树。去左子树,B是根节点,D是左子树,EH是右子树。去左子树,根节点是D,左右子树为空,去左子树,空,返回,去根节点,是D,去右子树,空,返回。访问完左子树到达根节点B,访问右子树EH。根节点是E,左子树是H,右子树空。访问左子树H,左子树为空,根节点是H,右子树空。访问完左子树,访问根节点E,右子树空。访问根节点A,访问右子树CFG,左子树是F,根节点是C,右子树是G。先访问F,F的左子树为空,右子树为空,再访问根节点C,最后是右子树G,左右子树为空。

这样遍历出一个序列,该序列是DBHEAFCG,它叫做二叉树的中序序列。

3. 后序遍历

后序遍历先访问左子树,再访问右子树,最后是根节点。

从A出发,左子树BDEH,右子树CFG。先遍历左子树,左子树是D,右子树是EH,根节点是B,遍历到D,左右子树为空,回到右子树,左子树是H,右子树空,根节点是E,访问H,再访问E。最后是根节点B。然后是右子树CFG,左子树是F,右子树是G,根节点是C,左子树根节点是F,没有左右子树,右子树根节点是G,没有左右子树。最后是根节点C。然后右子树遍历完毕,最后就是总的根节点A。

这样遍历出一个序列,该序列是DHEBFGCA,它叫做二叉树的后序序列。

直接给出结论,如果知道某二叉树的前序序列和中序序列,那么可以唯一地恢复该二叉树。同样,只要知道后序序列和中序序列也可以唯一地恢复该二叉树,但是只知道前序序列和后序序列是不可以唯一地恢复该二叉树的。

比较绕,要多消化一下。

线索二叉树

为什么要学习这个*东西呢?先来想想二叉树的那三个遍历方法吧。

二叉树的遍历是很多人比较熟悉的,实际上,二叉树的遍历操作就是一个把非线性结构变成线性结构的过程。在线性序列中,每个结点有一个唯一的前驱和唯一的后继(头和尾这种就是有一个没有的)。在这个过程中,我们通过降维打击把树变成了线性表,这破坏了树的结构。有没有一种方法可以做到不进行降维打击也能存储前驱和后继的信息?

其实前驱和后继的信息只需要遍历就能得到的,还是那句话,查询次数多了总有你T的时候。所以还得想个靠谱的办法。

这看起来也许很简单,我在每个结点都保存一个前驱和后继的信息不就可以了?

嗯这确实可以,本题结束。

此时恰巧一位强迫症的路人经过,他会发现这个结构存储密度特别低,然后感觉非常不适。这是因为什么呢?有结论表明,有n个结点的二叉链表必然存在n+1个空链域。那么问题来了,这n+1个空链域能不能利用起来呢?

啊当然这么问的话肯定是能利用的起来是吧

实际上,考虑利用这些空链域来存放遍历后结点的前驱和后继信息,这就是线索二叉树构成的思想。采用既可以指示其前驱又可以指示后继的双向链接结构的二叉树被称为线索二叉树。

等等,双向链接结构?二叉链表一般是单向的,这意味着只能通过祖先访问子孙。既然要能够查找前驱,这肯定是不足够的。既然链表可以双向,那二叉链表为什么不可以?这是完全没问题的嘛。

假如这样规定:若结点有左子树,则其lchild表示左孩子,否则令其指示其前驱,若结点有右子树,则其rchild表示右孩子,否则令其指示其后继。同时为了避免混淆(lchild,rchild虽然指示了区域,但是并不知道到底指示的是什么),还需要增加ltag和rtag这两个字段,其中值为0时表示指示孩子,值为1时表示指示前驱或后继。

typedef struct BiThrNode {  
    TElemType data; // TElemType是抽象数据类型啦,它是什么都可以的  
    BiThrNode *lchild, *rchild;  
    int ltag, rtag;  
}BiThrNode, *BiThrTree;  

以这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表。其中指向结点前驱和后继的指针称为线索。使用此结点构筑的二叉链表(二叉树)就叫做线索二叉树。对二叉树以某种次序使其变为线索二叉树的过程叫做二叉树的线索化。

MacOoQ.png

Macjij.png

MacvJs.png

线索二叉树的构造

由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历时才能得到,因此线索化的过程即为在遍历的过程中修改空指针的过程。显然,对二叉树按照不同的遍历次序进行线索化得到的线索二叉树是不同的。

为了记下遍历过程中访问结点的先后关系,附设一个指针pre始终指向刚刚访问过的结点,指针p指向当前访问的结点,由此记录下遍历过程中的访问先后关系。

以结点p为根的子树中序线索化

1. 如果p非空,左子树递归线索化。
2. 如果p的lchild为空,则给p加上左线索,ltag置为1,p的左孩子指针指向pre(前驱),否则将p的ltag置为0.
3. 如果pre的rchild为空,则给pre加上右线索,rtag置为1,pre的右孩子指针指向p(后继),否则将pre的rtag置为0.
4. 将pre指向刚访问过的结点p,即`pre = p;`

void InThreading(BiThrTree p) {  
    if (p) {  
        InThreading(p->lchild);  
        if (!p->lchild) {  
            p->ltag = 1;  
            p->lchild = pre;  
        }  
    }  
    else {  
        p->ltag = 0;  
    }  
    if (!pre->rchild) {  
        pre->rtag = 1;  
        pre->rchild = p;  
    }  
    else {  
        p->rtag = 0;  
    }  
    pre = p;  
    InThreading(p->rchild);  
}  
/*  
pre是全局变量,初始化时其右孩子指针为空,便于在树的最左点开始建立线索  
*/  

带头结点的二叉树中序线索化

void InOrderThreading(BiThrTree &thrt, BiThrTree T) {  
    thrt = new BiThrNode;  
    thrt->ltag = 0;  
    thrt->rtag = 1;  
    thrt->rchild = thrt;  
    if (!T)  
        thrt->lchild = thrt;  
    else {  
        thrt->lchild = T;  
        pre = thrt;  
        InThreading(T);  
        pre->rchild=Thrt;  
        pre->rtag = 1;  
        thrt->rchild=pre;  
    }  
}  
/*  
pre仍然是全局变量。首先建立头结点,头结点有左孩子,若树非空,则其左孩子为树根,头结点的右孩子指针为右线索。初始化时右指针指向自己,若树为空,则左指针也指向自己。  
头结点的左孩子指向根,pre初值指向头结点。然后调用中序线索化的算法,算法结束后,pre为最右结点,pre的右线索指向头结点。  
*/  

线索二叉树的遍历

现在我们已经构造好了线索二叉树。好了,现在好像是可以不通过降维打击也能方便查到某个结点的前驱和后继了。

在中序线索二叉树中查找

1. 查找前驱的方法:

* 若`p->ltag == 1`,则p的左链指示其前驱
* 若`p->ltag == 0`,则说明p有左子树,结点的前驱是遍历左子树时最后访问的一个结点(左子树中最右下的结点)。

2. 查找后继的方法:

* 若`p->rtag == 1`,则p的右链指示其后继
* 若`p->rtag == 0`,则说明p有右子树。根据中序遍历的规律可知,结点的后继应该是遍历其右子树时访问的第一个结点,即右子树中最左下的结点。

遍历中序线索二叉树

首先指针p指向根结点,p为非空树或遍历未结束时,循环执行下面的操作:沿左孩子向下,到达最左下结点*p,它是中序的第一个结点;访问*p;沿右线索反复查找当前结点*p的后继结点并访问后继结点,直至右线索为0或者遍历结束;转向p的右子树。

void InOrderTraverse_Thr(BiThrTree T) {  
    p = T->rchild;  
    while (p != T) {  
        while (p->ltag == 0)  
            p = p->lchild;  
        cout << p->data;  
        while (p->rtag == 1 && p->rchild != T) {  
            p = p->rchild;  
            cout << p->data;  
        }  
        p = p->rchild;  
    }  
}  

遍历线索二叉树的时间复杂度为O(n),空间复杂度为O(1),这是因为线索二叉树的遍历不需要使用栈来递归操作。

B-树

数据结构课程设计用,简单学一下,不过好像有点难。。?

我想我需要纠正一下这个数据结构的名称,此前我一直称它为B树,但有些教程把它叫做B-树或者B_树,其实它们都是一样的。

B-树的基本概念

B-树中所有结点中孩子结点个数的最大值成为B-树的阶,通常用m表示,从查找效率考虑,一般要求m>=3。一棵m阶B-树,或者是一棵空树,需要满足下面的特性:

  • 树中每个结点至多有 m 棵子树,每个结点最多有m个分支(子树),而最少分支数要看是否为根节点。
  • 除根之外的所有非终端结点至少有两棵子树;根非叶节点至少有ceil(m/2)个分支。(ceil代表向上取整)
  • 所有的非终端结点中包含下列信息数据:(n,A0,K1,A1,K2,A2,…,Kn,An);

其中n为该结点中关键字的个数;ki为该结点的关键字且满足ki < ki+1;Ai为该结点的孩子结点指针,且满足Ai所指结点上的关键字 > Ki 且 <
Ki+1,A0所指结点上的关键字小于K1,An所指结点上的关键字 > Kn

  • 结点内各关键字互不相等且按从小到大排列,如果一个结点有n-1个关键组,那么该结点有n个分支。
  • 叶子结点处于同一层;可以用空指针表示,是查找失败到达的位置。

简单来说,B树的阶是人为定义的,假如有一个4阶的B树,则除了叶结点都是NULL外,其他的结点最多保存3个信息和4个连接域,而且这是互相关联的。如果要保存2个信息则必须是3个连接域,保存1个信息则必须是2个连接域。B树本身也就是一种二叉排序树,所以也适用二叉排序树的一些性质。

下图展示了一个4阶的B树。解释一下每个结点,最左边的数字代表的是这个结点的元素个数,4阶的话元素个数最多是3。对于只有1个元素的结点,应该有2个连接域,对于只有2个元素的结点应该有3个连接域,3个元素的结点应该有4个连接域,多个元素存在的情况下应该保持有序。

由于B-树具有分支多层数少的特点,使得它更多应用在数据库系统中。将大型数据库文件存储在硬盘上,为了减少访问次数,就可以使用B-树。它的检索效率很不错。

B树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在B树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度;

B-树的查找操作

以上图为例,演示一下查找的过程。B树的查找是二叉排序树的扩展,区别在于二叉排序树是二路查找,而B树是多路查找。

又因为B树某结点内部元素是有序的,在结点内查找时可以二分查找来提升速度(确信

假如我们要查找53和20,在查找53的时候,先从根结点开始,比较大小,如果比根大则去右子树,否则去左子树。(二叉排序树性质)

重点来了,现在到了43和78的结点,查找的53要比43大,所以是不会到达39的结点的。然后对比78,如果比78大的话则肯定去了99所在的结点,不过我们查找的53在43和78之间,所以会进47
53 64的结点,此时再从左到右进行查找,就可以找到53。

如果要查找20,首先从根节点往左子树出发,发现18,然后往右子树出发,右子树发现27,往左子树出发,发现NULL,表示查找失败,这个B树里没有20。

叶子结点不保存任何信息,如果某次查找跑到了叶子结点,则表示查找失败。

B树的标准的查找规则如下,假设查找key:

1. 先让key与根结点中的关键字比较,如果key等于K[i](K[]为结点内的关键字数组),则查找成功
2. 若key < K[1],则到A[0]所指示的子树中进行继续查找(A[]为结点内的指针数组),这里要注意B-树中每个结点的内部结构。
3. 若key > K[n],则到A[n]所指示的子树中继续查找。
4. 若K[i] < key < K[i+1],则沿着指针A[I]所指示的子树继续查找。
5. 如果最后遇到空指针,则证明查找不成功。

B-树的插入与构筑操作

B-树也是从空树开始,不断插入新的数据元素构筑的。但是B-
树构建的过程与前面的二叉排序树和AVL树不同,B-树在插入新的数据元素时并不是每次都向树中插入新的结点。因为对于m阶的B-
树来说,在定义中规定所有的非终端结点(终端结点即叶结点,关键字个数为0)包含关键字个数范围是[ceil(m / 2) - 1, m - 1],所以在插入新的数据元素时,首先向最底层的某个非终端结点中添加,如果该结点中的关键字个数没有超过m-1,则直接插入成功,否则还需要继续对该结点进行处理。

对于关键字的插入,需要找到插入为位置。在B-
树的查找过程中,当遇到空指针时,则证明查找不成功,同时也找到了插入位置,即根据空指针可以确定在最底层非叶节点中的插入位置。由此可见,B树的结点插入总是在终端结点上。但是,在插入过程中有可能会破坏B-
树的特征,比如一个4阶的B-树出现了一个结点保存4个数据+5个连接域的情况,这种情况就需要一个“裂开”操作,即拆分结点。

假设有关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15},以此构筑一棵5阶B-树,过程如下。

确定结点中关键字个数的范围

由于要求5阶,则关键字个数的范围为2-4。

2是怎么算出来的?因为根非叶节点至少有ceil(m/2)个分支,所以5阶的话最少要有3个分支,3个分支则必定有2条关键字。

4是怎么算出来的?因为是5阶,所以每个结点最多有5个连接域,所以最多有4个关键字。

确定根节点

由于根节点可以最多容纳4个信息,则根节点应该是下图这样:

插入后续节点 拆分操作

当准备插入11时,11是不可以再插入到根节点了,因为这样关键字的个数变成了5,超出了范围,此时需要进行拆分操作。

拆分时需要取关键字数组的中间位置,这里由于11的加入,关键字的个数会变成5,取中间位置应该是3而不是2。我们让k[3] =
6作为一个新的根节点,6左右的关键字分别做成两个结点,作为新结点的两个分支。此时变成了这样。

新关键字总是插在叶子结点上。当插入4 8 13后,树变成了:

插入关键字10需要插在8和11之间,此时又会出现需要拆分的情况,拆分时需要把10放入根节点,并把10左右的关键字拆成两个新结点连在根节点上。

(图我不画了,太麻烦了QAQ)

按照上述步骤,插入过程中不超范围就直接插,超出范围就让它裂开,最后它会变成这样:

(手画了个,将就着看吧x)

需要注意一个事,插入最后一个关键字15,15应该插入在14之后,此时会出现关键字个数超出范围的情况,则需要拆分,13并入根节点,13并入根节点后,根节点超出范围,需要再次拆分,10作为新的根节点,并将10左右的关键字做成两个新节点连接到新的根节点。这种插入一个关键字后出现多次拆分的情况称为连锁反应。

B-树的删除

对于删除,我们需要先找到待删除的关键字,但是直接的删除是不可以的,因为这有可能会破坏B-
树的特性。比如旧关键字删除之后结点的个数不再满足定义,此时需要做出一些调整。可能需要向其兄弟结点借一些关键字或者和其孩子结点进行关键字的交换,也可能需要进行结点的合并,其中,和当前结点的孩子进行关键字交换的操作可以保证删除操作总是发生在终端结点上。

删除关键字8和16,关键字8在终端结点上,并且删除后所在结点关键字个数不会超出限制,所以可以直接删除。关键字16不在终端结点上,但是可以用17覆盖16,然后把原来的17删除掉。这里便是与孩子结点进行关键字交换的操作。这里不能用15和16进行关键字交换,因为这样会导致15所在结点中关键字的个数小于2。

删除关键字15,15虽然也在终端结点上,但是不能直接删除,因为删除后当前结点中关键字的个数小于2,这样不满足5阶B树的定义。此时需要向其兄弟结点借关键字,显然应该向其右兄弟来借关键字,因为左兄弟的关键字个数已经是下限2。借关键字不能直接将18移到15所在的结点上,因为这样会使得15所在的结点上出现比17大的关键字,所以正确的借法应该是先用17覆盖15,再用18覆盖原来的17,最后删除原来的18。

删除关键字4,4在终端结点上,但是此时4所在的结点的关键字个数已经到下限,需要借关键字。不过可以看到其左右兄弟结点已经没有多余的关键字可借。所以就需要进行关键字的合并。可以先将关键字4删除,然后将关键字5、6、7、9进行合并作为一个结点链接在关键字3右边的指针上,也可以将关键字1、2、3、5合并作为一个结点链接在关键字6左边的指针上。但是这样单纯的合并后仍然不可以,因为会出现非根的双分支结点(我就不画图了这个),这样需要继续进行合并。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <iostream>  
#include <string>
#include <cstdlib>
using namespace std;

struct Index {
string id;
int loc;
};

//B-Tree 结点
class BTreeNode {
protected:
//string *keys;//存储关键字的数据
Index* keys;
int t; //最小度 (决定了key的数量范围)
BTreeNode** C; //存储孩子结点的数组
int n; //现在key的个数
bool leaf; //如果这个结点是一个叶子 则为TRUE , 否则 为FALSE
public:
BTreeNode(int _t, bool _leaf);
void traverse(); //遍历以该结点为根的子树中所有结点
BTreeNode* search(Index k);//在以该节点为根的子树中查找键为k的结点

void insertNonFull(Index k);
void splitChild(int i, BTreeNode* y);

friend class BTree;
};

class BTree {
protected:
BTreeNode* root; //根节点的指针
int t; //最小度
public:
BTree(int _t) {
root = NULL; t = _t;
}
void traverse() {
if (root != NULL) root->traverse();
}
BTreeNode* search(Index k) {
if (root == NULL) return NULL;
else return root->search(k);
}
void insert(Index _k);
};

BTreeNode::BTreeNode(int _t, bool _leaf) {
t = _t;
leaf = _leaf;
keys = new Index[2 * t - 1]; //一个结点key最多有2*t-1个
C = new BTreeNode * [2 * t]; //一个结点孩子最多有2*t个
n = 0; //新建结点当前key的数量为0
}

void BTreeNode::traverse() {
// 有n个key和n+1个子key,遍历n个key
// 还有前n个子key
int i;
for (i = 0; i < n; ++i) {
// 如果这不是叶节点,在打印key[i]之前先遍历以C[i]为根的子树
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i].id;
}
// 打印最后一个子树的根
if (leaf == false)
C[i]->traverse();
}

BTreeNode* BTreeNode::search(Index k) {
// 找到第一个大于等于k的key
int i = 0;
while (i < n && k.id > keys[i].id)
i++;
//如果找到的key值等于k,则返回此结点
if (keys[i].id == k.id)
return this;
// 如果这里没有找到key而这里是一个叶节点
if (leaf == true)
return NULL;
// 去找一个适当的子树继续查询
return C[i]->search(k);
}

void BTree::insert(Index k) {
//如果树为空
if (root == NULL) {
root = new BTreeNode(t, true);
root->keys[0] = k; //插入 key
root->n = 1; //更新当前root结点的key的个数为1
}
else {//树不为空
// 如果树的根结点已满,则树的高度会增加
if (root->n == 2 * t - 1) {
BTreeNode* s = new BTreeNode(t, false);
// 旧的根结点成为新的根节点的孩子
s->C[0] = root;
// 拆分旧根结点并将一个key移动到新根结点上
s->splitChild(0, root);
// 新的根节点现在有了两个子结点。现在决定两个子结点中的哪一个会有新的key
int i = 0;
if (s->keys[0].id < k.id)
++i;
s->C[i]->insertNonFull(k);
//改变根节点
root = s;
}
else
root->insertNonFull(k);
}
}

// 在此结点中插入新key
// 假设在调用这个函数时,结点必须是非满的
void BTreeNode::insertNonFull(Index k) {
//将index初始化为最右边元素的索引
int i = n - 1;

// 如果这是一个叶节点
if (leaf == true) {
// 下面的循环做两件事
// a) 查找要插入新key的未知
// b) 将所有较大的key移动到前方一个位置
while (i >= 0 && keys[i].id > k.id) {
keys[i + 1] = keys[i];
i--;
}
// 在找到的位置插入新的key
keys[i + 1] = k;
n = n + 1;
}
else { // 如果这个结点不是叶节点
// 找到将拥有新key的子结点
while (i >= 0 && keys[i].id > k.id)
i--;

// 查看找到的子元素是否已满
if (C[i + 1]->n == 2 * t - 1) {
// 如果某个子结点已满,则需要对子结点进行拆分
// 机翻:如果孩子吃饱了,就把它切开(草 我裂开了
splitChild(i + 1, C[i + 1]);

// 执行拆分操作后,C[i]中间的key会上升一级,并且C[i]会一分为二
// 看看哪一个会得到新key
if (keys[i + 1].id < k.id)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

// 分割此结点的子结点y
// 注意,当调用这个函数时,y必须是满的
void BTreeNode::splitChild(int i, BTreeNode* y) {
// 创建一个将要存储y结点的t-1个key的新结点
BTreeNode* z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;

// 复制y中最后t-1个key到z
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

// 复制y中最后t的子结点到z
if (y->leaf == false) {
for (int j = 0; j < t; ++j)
z->C[j] = y->C[j + t];
}

// 减少y中的key数量
y->n = t - 1;

// 因为这个结点将有一个新的子结点,所以要给新的子结点开辟空间
for (int j = n; j >= i + 1; --j)
C[j + 1] = C[j];

// 将新的子结点链接到此结点
C[i + 1] = z;

// 一个y的key将会移动到这个结点,找到新key的位置并将所有较大的key移动一个位置。
for (int j = n - 1; j >= i; --j)
keys[j + 1] = keys[j];

// 将y中间的key复制到这个结点
keys[i] = y->keys[t - 1];

// 此结点中的键数量增加1
n++;
}

int main() {
BTree t(3);
t.insert({ "10",1 });
t.insert({ "20",2 });
t.insert({ "5",3 });
t.insert({ "6",4 });
t.insert({ "12",5 });
t.insert({ "30",6 });
t.insert({ "7",7 });
t.insert({ "17",8 });

t.traverse();
cout << endl;
Index k = { "20",2 };
if (t.search(k) != NULL)
cout << "exist" << endl;
else
cout << "not exist" << endl;
}

参考资料

B-树及其基本操作(插入和删除)详解 http://data.biancheng.net/view/60.html

B-树(B树)详解 https://www.jianshu.com/p/7dedb7ebe033

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了 https://zhuanlan.zhihu.com/p/27700617

代码是我同学给的,我把里面的注释给翻译了一下

哈希与哈希表

曾经也是学过的东西,现在重新学一遍。其实就是通过一个人为制造的函数H,把一些比较大的数字或者字符串转化成能直接通过变量或者数组下标表示的东西,这个函数就是哈希函数。通过哈希函数转化得到的数值一般称之为哈希值。通过哈希值可以快速查找和匹配。

字符串哈希

用来解决子串类问题。一个比较常见的问题是寻找长度为n的主串上出现了多少次长度为m的子串,这类问题可以使用kmp解决,也可以使用字符串哈希解决。但是如果是这种问题:从主串中每次选取两个子串,问是否匹配(可能相当大),此时便只能使用字符串哈希。

具体操作?哈希函数并不是一个具体的函数,它是可以进行人为定义的,任何一种可以离散化的方法都可以作为一个哈希函数使用。一个比较简单直观的方法是取余法,令hash(k)
= k % m,m代表哈希表的大小,取决于你的空间。m越小哈希冲突概率越大, m越大空间开销越大,所以m的值要合理分配。

1
2
3
4
5
6
7
8
9
10
int hash(string s) {  
int seed = (随便一个数);
int m = HASH_SIZE;
int Hash = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
Hash = (Hash * seed + x[i] - '0') % m;
}
return Hash;
}

这样可以在O(n)的复杂度内完成哈希操作。但是这样做缺点是明显的,极有可能哈希冲突,也就是不同的串得到了相同的哈希值,这样可能会导致错误。解决哈希冲突的方法有多种,这里介绍双哈希。其实就是把哈希函数再写一遍,这次换一个不同的种子,只有两个哈希值都相等才能断定两个字符串相等。实际证明这个方法实用性不错。

下面介绍一下滚动哈希的优化技巧。选取两个合适的互质常数b和h(b < h),假设有字符串C = c1c2…cm,那么定义哈希函数Hash(C) =
(c1bm-1+c2bm-2+…+cmb0) % h

正常的数字是十进制的,这里相当于把字符串C看成一个b进制的“数”,用b做基数。这一过程是递推计算的,设Hash(C,k)为前k个字符构成的字符串的哈希值,则有H(C,k+1)
= H(C,k) × b + ck+1 (暂不考虑取模)

通常,题目要求的是判断主串的一段字符与另一个字符串是否匹配,即判断字符串C = c1c2…cm从k+1位置的长度n的子串C’ =
ck+1ck+2…ck+n的哈希值与另一匹配字符串S = s1s2…sn的哈希值是否相等,于是有Hash(C’) = Hash(C,k+n) -
Hash(C,k) × bn

(代码有问题,debug中)

哈希表

哈希表是一种高效的数据结构,它的优点同字符串哈希一样,查找的算法时间效率几乎就是常数,同时也很容易实现,多产生的代价仅仅是消耗较多内存。

假设现在有一个线性表A(1,75,324,1353,43,91,40),用n代表元素个数,存储它很简单,只需要一个一维数组。但是这样的数据结构为查找带来了麻烦。如果是顺序存放还好说,我们可以使用二分查找,但是大部分情况下序列是无序的,我们只能使用线性复杂度的算法进行查找。但当n非常大时,速度依然会变得很慢。

我们考虑使用“桶”,开一个特殊的数组,其下标最大值为序列A中的最大值,也就是有一个数组b[1354](C/C++中数组从0开始,长度为n的话最大值到n-1,这里应该是1354而不是1353),然后我们令A中的所有元素都在这个b数组里“对号入座”,将数值作为下标,值只有0和1两种(其实不拘泥于这两个数,只是比较常用,只要能区分“有”和“没有”就可以),这样根据这个“桶”来进行查找,时间复杂度变成了常数。但这样仍然会存在一个问题,数组下标并不能很大,这样对于大数据来说仍然是不太合适的。并且这样会造成很大的空间浪费。不过我们可以采用哈希技术,为每个数设置一个哈希值。人为构造哈希函数Hash(x)
= x % 123,这样所有的数都变成了0到122之间的数,空间变小了很多。

实际上,这样做仍然存在问题。单纯的进行取模操作会导致大量的数据经过哈希操作后有重复,这就是哈希冲突。那么在查询时就有概率出现错误。哈希表与字符串哈希有所不同,有时题目的测试数据足够大,导致无论如何选择哈希函数都无法避免冲突,而且为了避免冲突去刻意构造一个复杂的哈希函数也得不偿失。这里我们的做法是使用链表。当发生冲突时把这个值挂在链表的下一个结点上,这样虽然查找时的复杂度不是严格的O(1),但是期望仍然是O(1),实际复杂度取决于链表长度,也就是冲突的程度。

假设以6为模数,哈希表应该是类似于下面这样:

(实际上,实际使用的模数一般要比6大得多,而且一般都是质数,这里仅是举例)

显然,如何构造哈希函数是决定哈希表查找效率的关键。因为只要哈希值的分布足够平均,链表查找的复杂度就会变小。下面是三种比较常用的哈希函数构造方法,

1.取余法

选择一个适当的正整数m,用原数据对m取模的结果作为哈希值,也就是Hash(x) = x %
m,这个方法应用是比较广泛的,使用率也比较高。这个方法的关键在于如何选取合适的m,一般是选择一个比较大的质数,这里给出一个从网上找的常用取模质数表,可供参考:

61, 83, 113, 151, 211, 281, 379, 509, 683, 911 / 一千以下

1217, 1627, 2179, 2909, 3881, 6907, 9209, /一万以下

12281, 16381, 21841, 29123, 38833, 51787, 69061, 92083, /十万以下

122777, 163729, 218357, 291143, 388211, 517619, 690163, 999983, /百万以下

1226959, 1635947, 2181271, 2908361, 3877817, 5170427, 6893911, 9191891,
/千万以下

12255871, 16341163, 21788233, 29050993, 38734667, 51646229,68861641,
91815541,/一亿以下

1e9+7 和 1e9+9 //十亿左右

122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411,/十亿以下

1222827239,1610612741, 3221225473ul, 4294967291ul /十亿以上

一般来说,如果m的约数越多,造成冲突的概率就会越大,所以尽量选择质数。

2.乘积取整法

用值乘以一个在(0,1)中的实数A(最好是无理数,(√5 -
1)/2是一个实际效果很不错的数),这样能得到一个(0,k)之间的实数,取其小数部分再乘以哈希表的大小M,再向下取整,然后得到在哈希表中的位置。

这个听起来就挺麻烦的(摊)

3.基数转换法

类似于字符串哈希使用的方法:将值看成是另一种进制的数,然后把它转化成十进制数,然后用取余法。一般取大于10的数作为转换基数,并且最好和原来进制的10互质。比如将一个十进制数强行看作是13进制,然后按照进制转换规则转成10进制,就得到一个值。

听起来也好麻烦。。。

事实上,哈希函数的构造方法有很多,并没有硬性规定,能避免冲突就可以。

取余法代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>  
#include <cstdio>
#define maxn 500000
#define m 999983
using namespace std;

int tot, adj[maxn], nxt[maxn], num[maxn];
int top, stk[maxn];

void init() {
//初始化哈希表,在多组数据时用来清空哈希表
//用一个栈存储出现过的哈希值,每次只要把出现过的哈希值的链表清零就可以,节省时间
tot = 0;
while (top) {
adj[stk[top--]] = 0;
}
}

void insert(int key) {
//使用取余法进行插入
int h = key % m;
for (int e = adj[h]; e; e = nxt[e]) {
if (num[e] == key)
return; //遍历链表如果已经出现过这个值就没必要再存一遍
}
if (!adj[h]) // 如果能走到这里说明这个值没存过,要进行存储,把第一次出现的哈希值入栈
stk[++top] = h;
nxt[++tot] = adj[h];
adj[h] = tot;
num[tot] = key; //用类似于建立邻接表的方式建立链表,存储下所有哈希值等于h的数字
}

bool query(int key) {
//查询操作
//先求哈希值再遍历链表,查找到则表示存在
int h = key % h;
for (int e = adj[h]; e; e = nxt[e]) {
if (num[e] == key)
return true;
}
return false;
}
int main() {
//此处请自由发挥
return 0;
}

树状数组

一种时间复杂度为log级别的数据结构,支持单点维护和求区间和。树状数组可以在大数据下快速计算区间和以及维护最大值最小值。

lowbit操作:

1
2
3
int lowbit(int m) {
return m&(-m);//位运算
}

求前缀区间和:

1
2
3
4
5
6
7
8
int sumele(int n){
int sum = 0;
while (n>0){
sum += c[n];
n -= lowbit(n);
}
return sum;
}

单点更新:

1
2
3
4
5
6
void update(int i,int val){
while (i<=n){
c[i] += val;
i += lowbit(i);
}
}

它只是一种维护的手段,实质上还是求区间和。

并查集

本能反应是想到一个菊花型的结构。

这其实是用路径压缩形成的一种很特殊的树形结构,每棵树的根节点都是一个代表元素。

并查集初始化时,集合的每个元素都是自己是自己的代表元素,所以

1
2
for (int i=1;i<=n;i++)
father[i] = i;

用它就可以初始化一个并查集。

合并集合很简单,把一棵树上的根节点变成另一棵树上的子结点就好。

1
2
3
4
5
void merge(int x,int y){
x = find(x);
y = find(y);
father[y] = x;
}

并查集的路径压缩的查找祖先方法。

1
2
3
4
5
6
int find(int x){
if (father[x] == x)
return father[x];
father[x] = find(father[x]);//如果当前节点的father并不是代表元素,那就递归地更新老祖宗
return father[x];//返回老祖宗
}

判断两个元素是否在同一集合:

1
2
3
4
5
6
7
8
bool check(int x,int y){
x = find(x);
y = find(y);
if (x==y)
return true;
else
return false;
}

图论

图的基本概念

图是一种多对多的数据结构,通俗的来讲,有一些点,点和点之间由各种边相连,就是一个图。精准的定义:图是一种这样的数据结构,假如把图记作G,则有G =
(V,E),V是图上的点构成的集合,E是点与点之间的关系构成的集合,即边集合。可以看出,图其实是由两个集合构成的数据结构。

简单来区分的话,图分为有向图和无向图。有向图的边是有方向的,如果有A→B,则并不一定有B→A。但如果是无向图,则当A和B之间存在边时,一定是A↔B,即当A能走到B时,B也能走到A。

方便起见,引入一些基本术语:

结点的度:无向图中与结点相连的边的数目,称为结点的度。

结点的入度:在有向图中,以这个结点为终点的有向边的数目。

结点的出度:在有向图中,以这个结点为起点的有向边的数目。

权值:边的“费用”,可以形象地理解为边的长度。

连通:如果图中结点U,V之间存在一条从U通过若干条边、点到达V的通路,则称U、V 是连通的。

回路:起点和终点相同的路径,称为回路,或“环”。

完全图:一个n 阶的完全无向图含有n×(n-1)/2 条边;一个n 阶的完> > 全有向图含有n×(n-1)条边;

稠密图:一个边数接近完全图的图。

稀疏图:一个边数远远少于完全图的图。

需要注意,只有有向图才存在入度和出度的概念,在无向图中只有度而没有入度和出度。

图的存储结构

一般有两种实现方式,一种是邻接矩阵,另一种是邻接表。邻接邻接,相邻连接,连者为邻,互利互通。这个名字还是不难理解的。

邻接矩阵比较适合理解图的结构,具有直观,好写的优点。

定义二维数组G[][],对任意的G[i][j],代表从点i到点j的边的权值。如果该图的边无权,则只需要定义成0-1型就好。对于无向图,满足G[i][j] =
G[j][i]。如果i与j之间不存在边,则定义为INF或者-1。(INF:infinity,即无穷,无限大,一般为2147483647,即int范围的最大值)

举例:

它们所对应的邻接矩阵如下:

建立邻接矩阵的代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>  
#define maxn 2333
#define INF 2147483647
using namespace std;

int g[maxn][maxn];
int n, m;
int edgeNum;
int from, to, dis;
int main() {
cin >> n >> m >> edgeNum;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[i][j] = INF;
}
}
//初始化邻接矩阵,初始全部为INF表示全都不连通
for (int i = 1; i <= edgeNum; i++) {
cin >> from >> to >> dis;
g[from][to] = dis;
g[to][from] = dis; // 如果是有向图,这个语句就不能有
}
//此处请自由发挥
return 0;
}

快速初始化的方法:使用ctsdlib里面的memset函数对数组进行初始化,使用memset(g, 0x7f,
sizeof(g))可以把数组全都初始化成一个很大的数,memset(g, 0, sizeof(g))全部初始化为0,memset(g, 0xaf,
sizeof(g))初始化为一个很小的数。

然而,实际应用中邻接表使用的并不是很广泛,反而是邻接表使用较为广泛。

前置知识:链表的使用

邻接表存储法又叫图的链式存储法,它的原理是根据图上的每一个结点建立一个链表,在图上这个点每连接一个其他点,就把这个点的编号塞到链表后面,这样一个点与其连接的所有点就连成了一条链,将一张图上所有点的这个链弄出来排在一起,成为一个表状结构,就是邻接表。

举例:

这里只说下图A吧,B和C类似。对于V1,它连接V2,V3,V4,那么以V1为首的链表后面连接的结点就是V2,V3,V4(顺序不一定非得是这个,顺序只能表明先连的哪个点后连的哪个点。)对于V2,连接V1和V4和V3,对于V3,连接V2和V1,对于V4,连接V1和V2。画出图来大概是这样:

建立邻接表需要使用到结构体,它记录边的信息,一般是记录起止点和权值。然后开一个该结构体类型的数组代表的就是边集。你问点集怎么表示?点集不用表示。(想一想,为什么)

然后我们需要一个head数组,对于任意的head[i],代表的是以i点开头的链表的“位置”,这个位置是虚拟的,也正是这个数组模拟链表的关键所在。初学者在这里比较难以理解,简单来讲这可以用来代替链表的“指针域”进行存储。进行加边操作的时候需要对边数进行计数,from对应的是head[from],因为一个点为首的只有一条链表,这一步是找到这个链表的头,然后是to对to,dis对dis,最后更新一下head[from]为当前边数即可。严格来讲这个理解可能并不是很严谨,如果想深入理解可以查阅其他资料,或者选择基于实用主义,不求甚解。

建立邻接表的代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>  
#define maxn 2333
using namespace std;
struct Edge {
int from, to, dis;
};
Edge edge[maxn];

int head[maxn], from, to, dis;
int totEdge = 0;
int n, m;

void addEdge(int from, int to, int dis) {
edge[++totEdge].from = head[from];
edge[totEdge].to = to;
edge[totEdge].dis = dis;
head[from] = totEdge;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> from >> to >> dis;
addEdge(from, to, dis);
}
//此处请自由发挥
return 0;
}

最短路

引入带权图和无权图的概念。对于边有权值的图我们叫做带权图,否则叫做无权图。边的权值可以理解为两点之间的距离,或者移动的代价,花费等等。一张图中可能会有很多带有权值的路径把点连接起来,对于图的最短路,分为单源最短路和多源最短路。单源最短路指的是从一点出发到达图中某点的最短路径,多源最短路指的是任意两点之间的最短路。解决最短路径的算法有很多,但是每种算法都有一定的适用范围。

多源最短路:Floyed算法

多适用于邻接矩阵,时间复杂度O(n³),适用负边权

令dis[u][v]表示从u到v的最短路径长度,w[u][v]表示连接u,v边的长度。

首先初始化所有的dis,如果对于任意u,v有边相连则dis[u][v] = w[u][v],如果没有则dis[u][v] = INF。

算法过程:

for (int k = 1; k <= n; k++) { //这层循环必须放在最外面  
    for (int i = 1; i <= n; i++) {  
        for (int j = 1; j <= n; j++) {  
            if (dis[i][j] > dis[i][k] + dis[k][j])  
                dis[i][j] = dis[i][k] + dis[k][j];  
        }  
    }  
}  

嗯,浑身上下散发着动态规划的味道。这的确是个动态规划,三层循环,第一层循环中间点k,第二第三层循环起点终点i、j,算法的思想很容易理解:如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离,那么就用这个更短的路径长度来更新原先点i到点j的距离。

假设现在有一无向图。有一条从点1到点2的带权边为6,有一条从点1到点3的带权边为2,有一条从点3到点2的带权边为1,可以知道dis[1][2] =
6,dis[1][3] = 2,dis[2][3] =
1,这是初状态。因为dis[1][3]+dis[3][2]<dis[1][2],所以就用dis[1][3]+dis[3][2]来更新原先1到2的距离。如果两者之间有最短路径的话,就会更新成最短路径的长度。

变形:

for (int k = 1; k <= n; k++) { //这层循环必须放在最外面  
    for (int i = 1; i <= n; i++) {  
        for (int j = 1; j <= n; j++) {  
             dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);  
        }  
    }  
}  

如果是一个没有边权的图,把相连的两点间的距离设为dis[i][j]=true,不相连的两点设为dis[i][j]=false,用这个办法可以判断一张图中的两点是否相连。

单源最短路:Dijkstra算法

多适用于邻接表,时间复杂度O(n2)(未经优化),O((n+m)logm)(加入堆优化),不适用负边权

也就是所谓的迪杰斯特拉算法。它是基于一个贪心的思想。从起点V0开始,每次新扩展一个距离最短的点,然后再以这个点为中间点去更新起点到其他所有点的距离。它无法处理边权有负的情况。由于所有的边权都是正,所以不会存在一个距离更短的没有扩展过的点。也就是说每次扩展都要保证路径是当前最短,所以当前这个点到起点的距离永远不会再被改变一次,从而保证算法的正确性。

设起点为s,dis[v]表示从s到v的最短路径,pre[v]为v的前驱节点,用来输出路径。首先初始化:dis[v]=∞(v≠s); dis[s]=0;
pre[s]=0;

然后是伪代码:

for (i = 1 to n) {
    在没有被访问过的点中找一个顶点u使得dis[u]是最小的
    u标记为已确定最短路径
    for 与u相连的每个未确定最短路径的顶点v
        if (dis[u]+w[u][v] < dis[v]) {
            dis[v] = dis[u] + w[u][v];
            pre[v] = u;
        }
}

算法结束后,dis[v]为s到v的最短距离;pre[v]为v的前驱节点,用来输出路径。如果不需要pre数组的话可以不加。

这里为什么只给出了伪代码?因为实际使用的Dijkstra大多是优化之后的算法。

(以下文字摘自信息学奥赛一本通课件)

算法思想:从起点到一个点的最短路径一定会经过至少一个“中转点”(例如下图1到5的最短路径,中转点是2。特殊地,我们认为起点1也是一个“中转点”)。显而易见,如果我们想求出起点到一个点的最短路径,那我们必然要先求出中转点的最短路径(例如我们必须先求出点2
的最短路径后,才能求出从起点到5的最短路径)。换句话说,如果起点1到某一点V0的最短路径要经过中转点Vi,那么中转点Vi一定是先于V0被确定了最短路径的点。

我们把点分为两类,一类是已确定最短路径的点,称为“白点”,另一类是未确定最短路径的点,称为“蓝点”。如果我们要求出一个点的最短路径,就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。

Dijkstra的算法思想,就是一开始将起点到起点的距离标记为0,而后进行n次循环,每次找出一个到起点距离dis[u]最短的点u,将它从蓝点变为白点。随后枚举所有的蓝点vi,如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话,这将它作为vi的“更短路径”dis[vi](此时还不确定是不是vi的最短路径)。

就这样,我们每找到一个白点,就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点,故每一个终点一定能够被它的最后一个中转点所修改,而求得最短路径。

模拟这个过程,算法开始时,作为起点的dis[1] = 0,其他的点dis[i] = INF。

第一轮循环找到dis[1]最小,将1变成白点。对所有的蓝点做出修改,使得dis[2]=2,dis[3]=4,dis[4]=7。

第二轮循环找到dis[2]最小,将2变成白点。对所有的蓝点做出修改,使得dis[3]=3,dis[5]=4。这时dis[2],dis[3],dis[4]被它的最后一个中转点1修改为了最短路径。

第三轮循环找到dis[3]最小,将3变成白点。对所有的蓝点做出修改,使得dis[4]=4。发现以3为中转不能修改5,说明3不是5的最后一个中转点。这时dis[3],dis[5]被它们的最后一个中转点2修改为了最短路径。

接下来的两轮循环将4、5也变成白点。N轮循环结束后,所有的点的最短路径即能求出。这时dis[4]也被它的最后一个中转点3修改为了最短路径。

Dijkstra无法处理边权为负的情况。 比如下图这样的图:

2到3的边权值为-4,显然从起点1到3的最短路径是-2(1→2→3),但是dijskstra在第二轮循环开始时会找到当前dis[i]最小的点3,并标记它为白点。这时的dis[3]=1,然而1却不是从起点到点3的最短路径。因为3已被标记为白点,最短路径值dis[3]不会再被修改了,所以我们在边权存在负数的情况下得到了错误的答案。

堆优化:使用堆来优化查找操作。

堆优化之后的Dijkstra:(陈年老代码了,代码风格与现在略有不同)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>  
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
#define INF 2147483647
using namespace std;
int n,m,s,head[50010],cnt;
ll dis[10010];
bool used[10010];
struct Edge{
int to,from,dis;
}edge[500010];

void add_edge(int u,int v,int dis){
edge[cnt].to=v;
edge[cnt].from=head[u];
edge[cnt].dis=dis;
head[u]=cnt++;
}
typedef pair<int,int> P;
void dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > q;
fill(dis,dis+n+1,INF);
fill(used,used+n+1,false);
dis[s]=0;
q.push(P(0,s));
while(!q.empty()){
P p=q.top();q.pop();
int u=p.second;
if(used[u]) continue;
used[u]=true;
int pp=head[u];
while(pp!=-1){
int v=edge[pp].to;
if(!used[v]&&dis[v]>dis[u]+edge[pp].dis){
dis[v]=dis[u]+edge[pp].dis;
q.push(P(dis[v],v));
}
pp=edge[pp].from;
}
}
}
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v,d);
}
dijkstra(s);
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
}

单源最短路:Bellman-Ford算法

(经过队列优化后的中国叫法是SPFA),多适用于邻接表,时间复杂度O(NE)(未经优化,N为点数,E为边数),O(kE)(k是常数,加入队列优化),适用负边权

同样是用来计算从一个点到其他所有点的最短路径的算法,也是一种单源最短路径算法。能够处理存在负边权的情况,但无法处理存在负权回路的情况。经过改造后的SPFA算法是笔者最喜欢也是最常用,同时也是最容易被卡的最短路算法。

(以下文字摘自信息学奥赛一本通课件)

设s为起点,dis[v]即为s到v的最短距离,pre[v]为v前驱。w[j]是边j的长度,且j连接u、v。初始化:dis[s]=0,dis[v]=∞(v≠s),pre[s]=0

1
2
3
4
5
6
for (i = 1; i <= n-1; i++)
for (j = 1; j <= E; j++) //注意要枚举所有边,不能枚举点。
if (dis[u]+w[j]<dis[v]) { //u、v分别是这条边连接的两个点。
dis[v] =dis[u] + w[j];
pre[v] = u;
}

Bellman-Ford算法的思想很简单。一开始认为起点是白点(dis[1]=0),每一次都枚举所有的边,必然会有一些边,连接着白点和蓝点。因此每次都能用所有的白点去修改所有的蓝点,每次循环也必然会有至少一个蓝点变成白点。在下面这个简单的模拟中能看到白点的“蔓延”情况。

虽然Bellman-
Ford算法可以求出存在负边权情况下的最短路径,却无法解决存在负权回路的情况。负权回路指一个环,这个环上所有的权值都为负,也可以理解成是指边权之和为负数的一条回路。如果图中出现负环会发生什么?

负权回路是指边权之和为负数的一条回路,上图中②-④-⑤-③-
②这条回路的边权之和为-3。在有负权回路的情况下,从1到6的最短路径是多少?答案是无穷小,因为我们可以绕这条负权回路走无数圈,每走一圈路径值就减去3,最终达到无穷小。
所以说存在负权回路的图无法求出最短路径,Bellman-Ford算法可以在有负权回路的情况下输出错误提示。
如果在Bellman-Ford算法的两重循环完成后,还是存在某条边使得:dis[u]+w<dis[v],则存在负权回路:

for 每条边(u,v) 
    if (dis[u]+w<dis[v])  
        return false

优化:SPFA算法

SPFA算法在国际上通称为“经过队列优化的Bellman-Ford算法”,仅在中国流行SPFA这种名字。

设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路估计值对u点所指向的结点v进行松弛操作。如果v点的最短路估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断地从队列中取出结点来进行松弛操作,直到队列为空。这个算法保证只要最短路存在,SPFA算法必定能求出最小值。SPFA算法同样可以判断负环。额外设立一个inq数组,某个点入队的次数超过n次时,可以判断负环存在并且提前退出。

这个算法,简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法。

SPFA
在形式上和广度优先搜索非常类似,不同的是广度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是说一个点修改过其它的点之后,过了一段时间可能会获得更短的路径,于是再次用来修改其它的点,这样反复进行下去。
算法时间复杂度:O(kE),E是边数。K是常数,平均值为2。

SPFA代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>  
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 5000015
#define INF 2147483647
#define ms(x) memset(x,0,sizeof(x));
using namespace std;
struct Edge{
long long int from,to,dis;
};
Edge edge[maxn];
long long int n,m,s,u,v,d;
long long int head[maxn];
long long int dis[maxn];
bool inq[maxn];
long long int cnt = 0;
void add_edge(long long int from,long long int to,long long int dis){
edge[++cnt].from = head[from];
edge[cnt].to = to;
edge[cnt].dis = dis;
head[from] = cnt;
}

void spfa(void){
queue<long long int> q;
q.push(s);
ms(inq);
inq[s] = true;
for (int i=1;i<=n;i++)
dis[i] = INF;
dis[s] = 0;
while (!q.empty()){
long long int u = q.front();
q.pop();
inq[s] = false;
for (int i=head[u];i!=0;i=edge[i].from){
long long int v = edge[i].to;
long long int w = edge[i].dis;
if (dis[u]+w < dis[v]){
dis[v] = w+ dis[u];
if (!inq[v]){
q.push(v);
inq[v] = true;
}
}
}
}

}

int main(){
cin >> n >> m >> s;
for (int i=1;i<=m;i++){
cin >> u >> v >> d;
add_edge(u,v,d);
}
spfa();
for (int i=1;i<=n;i++)
cout << dis[i] << " ";
return 0;
}

该算法的速度非常之快,但当该算法运行在稠密图或者人为构造的网格图上,该算法的复杂度极有可能退化成O(NE)。

最小生成树(MST)

生成树的定义:在一个有n个点的无向图中,取其中n-1条边,连接所有的顶点,得到一个子图,这个子图便是原图的一个生成树。

为什么说子图是树?实际上,树是图的一种特殊形态。这里便扩充了一下图的定义:

图G是树当且仅当下面的任意一个条件成立:

1.G有n-1条边,不存在环

2.G有n-1条边,连通

3.G的任意两点之间只有唯一的简单路径。

4.G连通,但任意删除一条边后就不再连通。

引入最小生成树的概念:在一个带权的无向连通图中,各边权和最小的一棵生成树即为原图的最小生成树。

最小边原则:图中权值最小的边(如果唯一)一定在最小生成树上。

图的最小生成树的唯一性定理:对于一个图G,如果图中的边权值互不相同,则图中的最小生成树一定是唯一的,反之则不然。

最小生成树用来解决类似于使用最小代价用n-1条边连接n个点的问题。比如架设快速道路或者架设网线要求花费最少。

Prim算法 时间复杂度O(n²)

(以下文字摘自信息学奥赛一本通课件)

Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想:白点代表已经进入最小生成树的点,蓝点代表未进入最小生成树的点。

算法描述:

以1为起点生成最小生成树,min[v]表示蓝点v与白点相连的最小边权。

MST表示最小生成树的权值之和。

a)初始化:min[v]= ∞(v≠1); min[1]=0;MST=0;
b)for (i = 1; i<= n; i++)
1.寻找min[u]最小的蓝点u。
2.将u标记为白点
3.MST+=min[u]
4.for 与白点u相连的所有蓝点v  
    if (w[u][v]<min[v]) 
        min[v]=w[u][v];
c)算法结束: MST即为最小生成树的权值之和

算法分析&思想讲解:

Prim算法每次循环都将一个蓝点u变为白点,并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边,最后得到的一定是最小生成树。

算法证明:

①当只取了一个点K时(边集为空),一定存在一个MST,包含当前的点集和边集。

②假设存在一个MST包含当前的点集和边集。当前点集为S,剩下的点集为S’。设跨越S-S’的最小代价的边为(u,v)。

反证法:假设取的是跨越S-S’的某边(u’,v’),删除(u’,v’)加入(u,v),S和S’分别连通,且S-S’通过(u,v)也能连通,这样会得到一个更小权值的MST,所以新加入的边一定是代价最小的边(u,v)。

Q.E.D

Kruskal算法

时间复杂度O(ElogE)(E为边数)

前置知识:并查集

Kruskal(克鲁斯卡尔)算法是一种巧妙利用并查集来求最小生成树的算法。我们把无向图中相互连通的一些点称为处于同一个连通块中。Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。

算法描述:

初始化并查集。father[x]=x。
tot=0
将所有边用快排从小到大排序。
计数器 k=0;
for (i=1; i<=M; i++)      //循环所有已从小到大排序的边
  if  这是一条u,v不属于同一集合的边(u,v){ (因为已经排序,所以必为最小),
     ①合并u,v所在的集合,相当于把边(u,v)加入最小生成树。
     ②tot=tot+W(u,v)
      ③k++
      ④如果k=n-1,说明最小生成树已经生成,则break; 
  }
结束,tot即为最小生成树的总权值之和。

Kruskal在初始时认为所有的点都是孤立的。然后它枚举所有边(已按边权排好序),枚举到某边的时候会判断这条边连接的两点是否在同一集合里,如果不是则说明这条边一定在最小生成树里,则加入这一条边。一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的边,所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合,最后n个点一定会合并成一个集合。通过这样的策略,Kruskal算法就能得到一棵有n-1条边,连接着n个点的最小生成树。

Kruskal模板:

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#define maxn 5005  
#define maxm 200005  
using namespace std;  
struct Edge{  
    int from,to,dis;  
    bool operator <(const Edge &rhs)const{  
        return dis < rhs.dis;  
    }  
};  
Edge edge[maxm];  
int father[maxm];  
int n,m;  
int totedge = 0;  
int k = 0;  
int ans = 0;  
inline int read(){  
    int num = 0;  
    char c;  
    bool flag = false;  
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');  
    if (c == '-')  
        flag = true;  
    else  
        num = c - '0';  
    while (isdigit(c = getchar()))  
        num = num * 10 + c - '0';  
    return (flag ? -1 : 1) * num;  
}      
void init(){  
    for (register int i=1;i<=m;i++)  
        father[i] = i;  
}  
int find(int x){  
    if (father[x] == x)  
        return father[x];  
    father[x] = find(father[x]);  
    return father[x];  
}  

void merge(int x,int y){  
    father[find(x)]  = find(y);  
}  

int main(){  
    n = read();m = read();  
    for (register int i=1;i<=m;i++){  
        edge[i].from = read();  
        edge[i].to = read();  
        edge[i].dis = read();  
    }  
    sort(edge+1,edge+m+1);  
    init();  
    while (totedge < n-1){  
        if (find(edge[++k].from) != find(edge[k].to)){  
            ans += edge[k].dis;  
            merge(edge[k].from,edge[k].to);  
            totedge++;  
        }  
    }  
    printf("%d\n",ans);  
    return 0;  
}  

拓扑排序

啥叫拓扑?百度百科这样说:

拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。拓扑英文名是Topology,直译是地志学,最早指研究地形、地貌相类似的有关学科。几何拓扑学是十九世纪形成的一门数学分支,它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现的一些孤立的问题,在后来的拓扑学的形成中占着重要的地位。

简单来讲,拓扑研究的是图形的位置关系。而拓扑排序也就是指对一张有向无环图的所有点的次序进行排序,最后得到一个序列,而这个排序的规则便就是按照相连的先后顺序进行排序,这个排序就叫做拓扑排序。更简单的说,拓扑排序是把一个图变成一个序列。做成的这个序列就叫做拓扑序列。

引入新概念。

有向无环图(DAG):在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。

对拓扑排序的讨论均是建立在有向无环图上的。所以本栏目里面所说的图,如果不加特殊注明,均指有向无环图。构造拓扑序列可以帮助我们合理安排一个工程的进度,由DAG构造拓扑序列具有很高的实际应用价值。

举个最简单的例子,游戏的技能树就是一个很简单的有向无环图(之前说到,树也是图的一种)。假设有这么一个设定:所有的后续技能学习都需要一些前置技能的要求,也就是说如果你要学习一个新技能,必须要满足之前的某些技能是掌握的。那么对这个技能树进行拓扑排序,得到的就是一个拓扑序列,它代表着你先学了什么后学了什么。

而构造拓扑排序算法很简单。假如使用邻接表,需要稍稍改动一下加边函数,在里面统计一下某个点的入度,比如from a to
b的一条边,一旦成立,b的入度就会+1。这样建图后我们可以得到一个数组,里面保存着各个点的入度信息。

然后我们扫描一下这个数组,寻找入度为0的点(如果保证原图是DAG,则这样的点一定存在)。把所有入度为0的点压入一个队列(不要只找到一个就结束这个操作,因为在DAG里可能存在多个入度为0的点)。

然后我们用一个while(!q.empty())控制循环。每次从队首取出一个结点(并且将这个结点弹出),这是当前遍历到的结点,将它输出(这里的输出并不是说非得要输出,因为题和题不一样,这里也有可能是其他操作,或者说是保存起来方便下一步操作),然后遍历所有与这个点连接的点(直接邻接表遍历操作就可以),把扫描到的点都入度-1,如果-1后入度变成了0,说明这应该是下一步要进行遍历的结点,就把这个结点入队。重复操作,直到队空为止,最后生成的序列就是拓扑序列。

比如说这个图,首先找到入度为0的点是只有A,把A入队。取队头是A,输出,弹出,然后遍历队头A的连接点,先找到B,入度-1后是0,入队,找到C,入度-1后是0,入队,D也是这样。一遍找完了,再回到开头取找队头,取队头是B,输出,弹出,然后遍历队头B的连接点,找到E,入度-1后变成2,不入队。找完B了找下一个队头是C,遍历C的连接点,找到E,入度-1后变成1。然后是D,这里再进行一步减入度的操作E的入度就变成了0,这里E就可以入队了。最后就是E。这样它的拓扑序列就是ABCDE。

Tips:使用队列那里并不强求,其实使用栈也是可以的。这也就意味着,一个DAG的拓扑序列可能不是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>  
#include <cstdio>
#include <queue>
#define maxn 23333
using namespace std;
struct Edge {
int from, to, dis;
};
Edge edge[maxn];
int n, m, s, u, v, d;
int inDegree[maxn];
int tot = 0;
int head[maxn];

void addEdge(int from, int to, int dis) {
edge[++tot].from = head[from];
edge[tot].to = to;
edge[tot].dis = dis;
head[from] = tot;
inDegree[to]++; // update in-degree
}

void output(int u) {
cout << u << " ";
}

void topoSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0)
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
output(u);
for (int i = head[u]; i; i = edge[i].from) {
int v = edge[i].to;
inDegree[v]--;
if (inDegree[v] == 0)
q.push(v);
}
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> d;
addEdge(u, v, d);
}
topoSort();
system("pause");
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 Shawn Zhou
  • Hexo 框架强力驱动 | 主题 - Ayer
  • 访问人数: | 浏览次数:

感谢打赏~

支付宝
微信