大话数据结构读书笔记

2021-06-21 笔记数据结构 0 评论字数统计: 38.9k(字) 阅读时长: 145(分)

大话数据结构读书笔记

这是在补数据结构时候做的笔记

笔记中的引用模块代表自己的一些想法

1. 数据结构绪论

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

学科：数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科

1.4 基本概念和术语

1.4.1 数据

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

声音图像等也是可以转化为字符数据来处理的

1.4.2 数据元素

数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

1.4.4 数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集

也就是一类数据结构的的集合。个人理解这种东西都是数据而已，没有必要做详细的区分

1.4.5 数据结构

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

研究数据结构的意义就是了解待处理对象的特性和处理对象之间存在的关系，从而编写出一个好的程序

1.5 逻辑结构与物理结构

1.5.1 逻辑结构

指数据对象中数据元素之间的相互关系。

集合结构

集合结构中的数据元素除了同属一个集合外，它们之间没有其他关系。

各个数据元素是平等的，共同属性只是：同属一个集合
线性结构

线性结构中的数据元素之间是一对一关系

类似链表连起来
树形结构

树形结构中数据元素之间存在一种一对多的层次关系
图形结构

图形结构的数据元素是多对多的关系

我认为这几种结构其实是对元素之间关系的一种抽象，两个元素之间：

无关系：集合

一对一：线性

一对多：树

多对多：图

1.5.2 物理结构（存储结构）

是指数据的逻辑结构在计算机中的存储形式

存储结构应正确反映数据元素之间的逻辑关系，这是重点和难点

两种：顺序存储和链式存储

顺序存储结构

把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
链式存储结构

把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

存储关系不能反映逻辑关系，因此需要指针存放关联元素位置

1.6 抽象数据类型

1.6.1 数据类型

数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称

因为高级语言开发，不用考虑整数在计算机内部表示方式，CPU 为了加减具体实现了什么，无论什么计算机，什么语言，一般都会有整数运算，字符运算等，我们可以抽象出来

1.6.2 抽象数据类型

Abstract Data Type：是指一个数学模型及定义在该模型上的一组操作

比如整型，操作有加减乘除

比如 point，有x，y，z

抽象数据类型体现了程序设计中问题分解，抽象和信息隐藏的特性

2. 算法

2.2 数据结构与算法关系

就是相辅相成的关系

2.3 两种算法的比较

举例一个 1+2+3+…+100

可以直接用 for 循环写，但是也可以构造另一个 100+99+…+1的序列，两者相加除 2

用程序来实现就是

1
2
3

int i,sum=0,n=100;
sum = (1+n)*n/2;
printf("5d",sum);

明显这一种方法会更快，如果第一种要循环

2.4 算法定义

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作.

没有通用的算法可以解决所有问题!

2.5 算法的特性

五个基本特性:输入,输出,有穷性,确定性和可行性

2.5.1 输入输出

算法有零个或多个输入

算法有一个或多个输出

肯定会有输出,不一定有输入

很好理解,没输出的话用算法干嘛,闲的吗

2.5.2 有穷性

算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每个步骤在可接受的时间内完成

所以,死循环就不满足这个特性

有穷是实际应用中的有穷,不是数学意义上的

2.5.3 确定性

算法的每一步都有确定的含义,不会出现二义性

2.5.4 可行性

算法的每一步必须是可行的

也就是说能用,能在计算机上运行

2.6 算法设计的要求

解决问题的算法不是唯一的,但是相对好的算法对于解决问题才有帮助

2.6.1 正确性

算法的正确性: 是指算法至少应该拥有输入输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案

正确有四个层次,一般我们以第三层次作为判断算法是否正确的标准,即:

算法程序对于非法的输入数据能够得出满足规格说明的结果

2.6.2 可读性

算法的可读性: 算法设计的另一目的是为了便于阅读,理解和交流

不能追求一味地代码量少等

2.6.3 健壮性

算法的健壮性: 当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果

2.6.4 时间效率高和存储量低

算法的时间效率高和存储量低: 设计算法应该尽量满足时间效率高和存储量低的需求

人都希望花最少的钱干最大的事

2.7 算法效率的度量方法

事前分析好于事后统计

2.7.1 事后统计方法

利用计算机计时器对不同算法的程序的运行时间进行比较,从而确定算法效率的高低

缺点:

很可能写了很久发现是垃圾算法
时间比较依赖计算机的运行速度
效率高的算法在小的测试数据面前无法体现明显差异

2.7.2 事前分析估算方法

在计算机程序编制前,依据统计方法对算法进行估算

测定运行时间最可靠的方法, 就是计算对运行时间有消耗的基本操作的执行次数. 运行时间与这个技术成正比

不关心编程语言以及运行的计算机,只关心算法的话, 就不计算循环索引递增,循环终止条件,变量声明,打印结果等操作. 最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

分析一个算法运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数

输入规模为 n,随着 n 越来越大,不同算法在时间效率上的差异也就越来越大

2.8 函数的渐进增长

比如两个算法, 2n+3 和 3n+1,哪个更快?

明显只有 n=1 时第二个才更优,所以我们说整体上第一个要好过第二个

函数的渐进增长: 给定两个函数 f(n)和 g(n),如果存在一个整数 N,使得对于所有的 n>N,f(n)总是比 g(n)大,那么我们说 f(n)的增长渐进快于 g(n)

而且随着 n 的增大, +3 和+1 不影响算法变化,所以我们忽略这些加法常数.

我们再观察发现,去掉与 n 相乘的常数,结果也没有改变,所以与最高次项相乘的常数并不重要,可以将 2n²=>n²

2n²和 2n²+3n+1 比较时,发现随着 n 值越来越大,两者非常趋近

最终我们得出结论:

判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高次项)的阶数

事前估算方法的理论依据: 某个算法,随着 n 的增大,它会越来越优于某个算法,或者越来越差于某个算法.所以我们通过算法时间复杂度来估算算法时间效率

2.9 算法时间复杂度

2.9.1 算法时间复杂度

在进行算法分析时,语句总的执行次数 T(n)是关于问题规模 n 的函数,进而分析 T(n)随 n 的变化情况并确定 T(n)的数量级.算法的时间复杂度,也就是算法的时间量度,记作:

T(n) = O(f(n))

它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度.

其中 f(n)是问题规模 n 的某个函数

这是大 O()记法

一般情况下,随着 n 的增大, T(n)增长最慢的算法为最优算法

2.8 中的例子,可以是 O(n),O(1),O(n²)

n 是输入规模

2.9.2 推导大 O 阶方法

步骤:

用常数 1 取代运行时间中的所有加法常数
在修改后的运行次数中,只保留最高阶项
如果最高阶项存在且不是 1,则取出与这个项相乘的常数

得到的结果就是大 O 阶

2.9.3 常数阶

O(1)

sum = (1+n)*n/2 这个有 1 句和10 句,都是 O(1)

因为无论 n 为多少,上段只是之星 1 次和 10 次的差异,这种与问题的大小(也就是n)无关,执行时间恒定,所以 O(1)的时间复杂度,又叫常数阶

2.9.4 线性阶

要确定某个算法的阶次,常常要确定某个特定语句或整个语句集运行的次数.

分析算法的复杂度,关键要分析循环结构的运行情况

int i;
for(i=0;i<n;i++)
{
  /* 时间复杂度为O(1)的程序步骤序列*/
}

因为循环体中的代码需要执行 n 次,所以时间复杂度为 O(n)

2.9.5 对数阶

int count = 1;
while(count<n)
{
  count = count * 2;
  /* 时间复杂度为O(1)的程序步骤序列*/
}

因为每次 count*2后, 距离 n 更近了.也就是说, 有多少个 2相乘后大于 n,则会退出循环. 2的 x 次方=n得到 x=log以 2 为底,n 为真数

所以这个循环的时间复杂度为 O(logn)

2.9.6 平方阶

int i,j;
for(i=0;i<n;i++)
{
  for(j=0;j<n;j++)
  {
    /* 时间复杂度为O(1)的程序步骤序列*/
  }
}

O(n)再循环 n 次,所以为 O(n²)

如果内循环的循环次数改为 m,则为 O(m✖️n)

循环的时间复杂度等于循环体的复杂度乘以改循环运行的次数

理解大 O 推导并不难,难的是对数列的一些相关运算,这里更多的是数学知识和能力.

2.10 常见的时间复杂度

O(1)

O(log n)

O(n)

O(nlog n)

O(n²)

其他比如 O(n³)一般不去讨论

2.11 最坏情况与平均情况

查找 n 个随机数字数组中的数字,可能第一个数字就是(O(1)),也可能是最后一个(O(n))

最坏情况运行时间是一种保证,就是运行时间不会再坏了.这是最重要的需求

平均运行时间在上例中是n/2, 平均运行时间是最有意义的,因为是期望的运行时间.

对算法的分析,一种为平均时间复杂度,一种是最坏时间复杂度

一般没有特殊说明,都是最坏时间复杂度

2.12 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:

S(n) = O(f(n))

n 为问题的规模,f(n)为语句关于 n 所占存储空间的函数

2.14 结语

一台老 CPU 计算机运行 O(n)比一台速度提高100 倍的新 CPU 运行 O(n²)的程序,效率高的是老 CPU,所以说,原因就在于算法的优劣直接决定了程序运行的效率.

3. 线性表 List

3.2 定义

线性表(List): 零个或多个数据元素的有限序列

几个点:

序列: 元素是有顺序的

有限: 计算机中处理的对象都是有限的

在较复杂的线性表中,一个数据元素可以由若干个数据项组成

3.3 线性表的抽象数据类型

数据:一对一的数据元素

操作:

InitList
ListEmpty
ClearList
GetElem
LocateElem
ListInsert
ListDelete
ListLength

3.4 线性表的顺序存储结构

3.4.1 顺序存储结构定义

线性表的顺序存储结构: 指的是用一段地址连续的存储单元一次存储线性表的数据元素

3.4.1 顺序存储方式

顺序存储结构需要三个属性:

存储空间的其实位置: 数组 data, 它的存储位置就是存储空间的存储位置.
线性表的最大存储容量: 数组长度 MaxSize.
线性表的当前长度: length.

3.4.3 数组长度和线性表长度区别

线性表的长度是线性表中数据元素的个数,可变,但是小于等于数组长度

3.4.4 地址计算方法

第 i 个元素的位置y可以由第一个元素x推算得出
$$
LOC(y)=LOC(x)+(i-1)*c
$$
其中 c 是一个元素占用的存储单元个数

由此可见,可以随时算出线性表中任意位置的地址,不管第一个还是最后一个都是相同的时间,所以时间复杂度为 O(1)

3.5 顺序存储结构的插入和删除

3.5.1 获得元素操作

获取线性表的第 i 个元素,就是把数组 i-1 下标的值返回

3.5.2 插入

插入算法思路:

如果插入位置不合理,抛出异常
如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
从最后一个位置开始向前遍历到第 i 个位置,分别将他们都向后移动一个位置
将要插入元素填入位置 i
表长加1

3.5.3 删除操作

类似于上面的插入算法

删除算法思路:

如果删除位置不合理,抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
表长减 1

插入和删除的复杂度

只有插入到最后一个或者删除最后一个,时间复杂度才是 O(1),因为不需要移动元素

平均的情况,比如插入中间,移动元素次数为(n-1)/2

所以去常数和系数后得出,平均时间复杂度还是 O(n)

所以:

线性表的顺序存储结构,存取数据时间复杂度为 O(1);增删时时间复杂度都是 O(n).

也就说明,比较适合元素个数不太变化,更多为存取数据的应用

3.5.4 线性表顺序存储结构的优缺点

优点:

无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点:

插入删除操作需要移动大量元素
当线性表长度变化较大时,难以确定存储空间的容量
造成存储空间的”碎片”

3.6 线性表的链式存储结构

3.6.2 线性表链式存储结构定义

在链式结构中,除了要存数据元素信息外,还要存储它的后级元素的存储地址

因此,

为了表示每个数据元素 ai 与其直接后继数据元素ai+1 之间的逻辑关系,对数据元素 ai 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息.我们把存储数据元素的信息成为数据域,把存储直接后继位置的域成为指针域.指针域中存储的信息称作指针或链.这两部分信息组成数据元素 ai 的存储映像,成为结点 Node.

n 个节点链结成一个链表,成为线性表(a1,a2,…,an)的链式存储结构,如果链表的每个结点中只包含一个指针域,所以叫做单链表

链表中第一个结点的存储位置叫做头指针

最后一个结点指针为”空”(通常用 NULL 表示)

有时为了方便操作,会在单链表的第一个结点前附设一个结点,成为头结点. 头结点的数据域可以不存储任何信息(可以存线性表长度等公共数据), 头结点的指针域指向第一个结点的指针.

3.6.3 头指针与头结点的异同

头指针
- 是链表指向第一个结点的指针,若链表有头结点,则指向头结点
- 头指针具有标识作用,所以常常用头指针冠以链表的名字
- 不论链表是否为空,头指针均不为空.头指针是链表的必要元素
头结点
- 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放线性表的长度)
- 有了头结点,对在第一元素前插入和删除第一结点,其操作与其他结点的操作就统一了
- 头结点不一定是链表必须要素

3.6.4 线性表链式存储结构代码描述

typeof struct Node
{
  ElemType data;
  struct Node *next;
} Node;
typeof struct Node *LinkList;/*定义 LinkList*/

由这个结构定义克制,结点由存放数据元素的数据域和存放后继结点地址的指针域组成.

3.7 单链表的读取

和顺序存储结构不同的是,单链表获取第 i 个元素智能从头开始找,找到第 i 个元素位置.

因此,最坏情况下时间复杂度为 O(n)

3.8 单链表的插入与删除

3.8.1 单链表的插入

假设存储元素 e 的结点为 s,要插入到 p 和 p->next 之间:

s->next=p->next; p->next=s;

也就是让 p 的后继结点改成 s 的后继结点,再把结点 s 变成 p 的后继结点(顺序不能更换!)

3.8.2 单链表的删除

要删除结点 q,实际上就是将它的前继结点的指针绕过,指向它的后继结点即可

q=p->next; p->next=q->next;

时间复杂度

算法由两部分组成:

遍历查找第 i 个元素
插入和删除

整个算法删除和插入都是 O(n).

但是考虑从第i 个元素插入10 个元素的情况

如果是顺序存储结构,每一次插入都要移动 n-i 个元素,每次都是 O(n).

单链表,只需要第一次找到第 i 个位置的指针,O(n),接下来就是赋值移动指针,10 次, O(1)

所以:

对于插入或删除越频繁的操作,单链表效率越高

3.9 单链表的整表创建

链表是一个动态结构. 所占用空间的大小和位置是不需要预先分配划定的.

分两种:

头插法
- 插入新结点始终在第一的位置
尾插法
- 就是将之前的表尾终端结点的指针指向新结点
- 然后将最后的指针置为空

3.10 单链表的整表删除

思路:

声明一结点 p 和 q
将第一个结点赋值给 p
循环
1. 将下一结点赋值给 q
2. 释放 p
3. 将 q 赋值给 p

q 变量存在的必要: 保存下一个结点以便删除

3.11 单链表结构与顺序存储结构优缺点

存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
时间性能
- 查找
  - 顺序存储结构: O(1)
  - 单链表: O(n)
- 插入和删除
  - 顺序存储结构: O(n) 需要平均移动表长一半的元素
  - 单链表: O(1) 算出某位置的指针后,插入删除为 O(1)
- 空间性能
  - 顺序存储结构需要预分配存储空间,分大了,浪费,分小了容易溢出
  - 单链表不需要分配存储空间,只要有就可以分配,元素个数不受限制

结论

频繁查找,少插入和删除,宜采用顺序存储结构(用户注册的信息)

频繁插入删除,宜采用单链表(用户的登录信息)
元素个数变化大或未知,最好用单链表,不用考虑存储空间如果事先知道大致长度,用顺序存储结构效率高

3.12 静态链表

静态链表: 用数组来代替指针,来描述单链表

让数组的元素都是由两个数据域组成,data 和 cur.存放元素和 next 指针(该元素的后继在数组中的下标)

对数组的第一个和最后一个元素作为特殊元素,不存数据.

将未被使用的数组元素成为备用链表.

数组的第一个元素的 cur 存放备用链表的第一个结点的下标;

数组的最后一个元素的 cur 存放第一个有数值的元素的下标

3.12.1 静态链表的插入操作

先把数据放到第一个空闲的位置a,然后从头循环找到要插入的位置b,将这个元素b下标指到刚才放的位置a,将刚才放的那个元素的指针指向b 的下一个,就完事儿了,结束后修改有数值的元素下标和备用链表的下标值.

3.12.2 静态链表的删除操作

某个数据a 要删除:

将 a 的cur 指向的下标赋值给存放第一个有数值的元素的下标
将 a 的下标赋值给存放备用链表的节点的下标(也就是说这个位置成为优先空位)

3.12.3 静态链表优缺点

优点:

插入和删除时,只需要修改游标,不需要移动段素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点:

没有解决连续存储分配带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性

总的来说,静态链表其实是为了给没有指针的高级语言设计的一种能实现单链表能力的方法.理解思想即可

3.13 循环链表

循环链表: 将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表成为单循环链表,简称循环链表(circular linked list)

循环的判断条件: 原来是判断 p->next 是否为空, 现在是 p->next 不等于头结点,则循环未结束

使用尾指针

用指向终端结点的尾指针来表示循环链表,此时查找开始结点和终端节点就很方便

终端结点: rear,查找终端结点 O(1)

开始结点: rear->next->next,其时间复杂度也是 O(1)

合并

保存 A 表的头结点: p=rearA->next;
将本是指向 B 表的第一个结点(不是头结点)赋值给 rearA->next(也就是删除B 的头结点): rearA->next = rearB->next->next
将原来 A 的头结点赋值给rearB->next rearB->next =p;
释放 p;

3.14 双向链表 double linked list

双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域.

多付出的代价: 在插入和删除时,需要更改两个指针变量

插入:

将结点 s 插入 p 和p->next 之间:

s -> prior = p;
s -> next = p -> next;
p -> next -> prior = s;
p -> next = a;

先搞定 s 的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继,第四步需要最后执行以免后结点

删除:

删除结点 p:

1 2	p -> prior -> next = p -> next; p -> next -> prior = p -> prior;

3.15 总结回顾

线性表是零个或多个具有相同类型的数据元素的有限序列

两大结构:

顺序存储结构
链式存储结构

这两种结构是后面其他数据结构的基础

4. 栈与队列

4.2 栈的定义

4.2.1 栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表.

允许插入和删除的一端称为栈顶(top)

另一端称为栈底(bottom)

后进先出结构(Last In First Out) LIFO 结构

4.2.2 进栈出栈变化形式

栈没有对元素进出的时间进行限制,在不是所有元素都进栈的情况下,事先进去的元素也可以先出栈,只要保证是栈顶元素出栈就可以.所以有很多顺序

4.3 栈的抽象数据类型

ADT 栈 stack

DATA

同线性表.元素具有相同的类型,相邻元素具有前驱和后继关系

Operation

InitStack: 初始化操作,建立一个空栈
DestroyStack: 若栈存在,则销毁它
ClearStack: 将栈清空
StackEmpty: 若栈为空,返回 true,否则返回 false
GetTop: 若栈存在且非空,返回栈顶元素
Push: 若栈存在,入栈
Pop: 删除栈顶元素
StackLength: 返回栈的元素个数

endADT

4.4 栈的顺序存储结构及实现

4.4.1 栈的顺序存储结构

因为是线性表,所以是数组来实现的

下标为 0 的一端为栈底

栈的结构定义:

typeof int SElemType; /* 类型根据实际情况而定,这里假设为 int */
typedef struct
{
  SElemType data[MAXSIZE];
  int top;	/* 用于栈顶指针 */
}SqStack;

4.4.2 进栈操作

1	Status Push(SqStack S, SElemType e){ if(S->top == MAXSIZE -1) { return ERROR; } S->top++; /栈顶指针增加一*/ S->data[S->top]=e; return OK;}

4.4.3 出栈操作

1	Status Pop(SqStack S, SElemType e){ if(S->top==-1) return ERROR; e=S->data[S->top]; /将要删除的栈顶元素赋值给 e/ S->top--; /栈顶指针减少一*/ return OK;}

进栈和出栈没有涉及任何循环语句,因此时间复杂度均是 O(1)

4.5 两栈共享空间

用一个数组来存储两个栈

数组的两个端点分别为栈的底端,两个栈如果要增加元素,就是两端点向中间延伸

栈为空: 栈 1 为空就是 top1 等于-1;栈 2 为空,就是 top2 等于 n

栈满:除极端情况,就是两个栈见面之时,也就是两个指针相差 1 时,即 top1 + 1 == top2 为栈满

使用这种数据结构,通常都是当两个栈的空间需求有相反关系时.一个增长一个缩短

4.6 栈的链式存储结构及实现

4.6.1 栈的链式存储结构

简称链栈

把栈顶放在单链表的头部.(所以对于链栈来说,是不需要头结点的)

基本不存在栈满的情况.

对于空栈来说,链栈的空就是 top=NULL 的时候

4.6.2 进栈操作

// 插入元素 e 为新的栈顶元素Status Push(LinkStack *S, SElemType e){  LinkStackPtr s =(LinkStackPtr)malloc(sizeof(StackNode));  s->data=e;  s->next=s->top; // 把当前栈顶元素赋值给新结点的直接后继  S->top=s;   S->count++;  return OK;}

4.5.3 出栈操作

// 若栈不空,则删除 S 的栈顶元素,用e 返回其值,并返回 OK;否则返回 ERRORStatus Pop(LinkStack *S,SElemType *e){  LinkStackPtr p;  if(StackEmpty(*S))    return ERROR;  *e = S->top->data;  p=S->top; //将栈顶结点赋值给 p  S->top = S->top->next; //使得栈顶指针下移一位  free(p); // 释放结点 p  S->count--;  return OK;

链栈的进栈 push 和出栈 pop 都没有循环操作,时间复杂度 O(1)

对比顺序栈和链栈:

它们在时间复杂度上是一样的,均为 O(1).
对于空间性能,顺序栈需要实现确定一个固定长度,链栈没有长度问题

结论:

如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好使用链栈,反之,如果变化可控,建议使用顺序栈

4.7 栈的作用

栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题的核心.

4.8 栈的应用—递归

栈有一个很重要的作用: 在程序设计语言中实现了递归

4.8.1 斐波那契数列

1	// 斐波那契的递归函数int Fbi(int i){ if(i<2) return i == 0?0:1; return Fbi(i-1) + Fbi(i-2); //递归}int main(){ int i; for(int i = 0; i<40;i++) printf("%d",Fbi(i)); return 0;}

4.8.2 递归定义

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数

每个递归定义必须至少有一个条件,满足时递归不再执行,即不再引出自身而是返回值退出

迭代和递归的区别是: 迭代使用的是循环结构,递归使用的是选择结构.

递归能使程序的结构更清晰,更简洁,更容易让人理解,但是递归调用会建立函数的副本,会耗费大量的时间和内存.迭代则不需要反复调用函数和占用额外的内存. 所以应该视不同情况选择不同的实现

因为递归退回的顺序是它前行顺序的逆序,所以很符合栈这样的数据结构

现在的高级语言,这样的递归是不需要用户来管理这个栈的,一切都由系统代劳

4.9 栈的应用—四则运算表达式求值

4.9.1 后缀表示法定义

对于9+(3-1)*3+10/2,使用后缀表达式为:

931-3*+10 2/+

叫后缀的原因是所有的符号都在运算数字后面出现

4.9.2 后缀表达式计算结果

后缀表达式: 9 3 1-3*+10 2/+

规则: 从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号,就将处于栈顶的两个数字出栈,进行运算,运算结果进栈,知道最终获得结果

4.9.3 中缀表达式转后缀表达式

平时的标准四则运算为中缀表达式

转换规则:

从左到右遍历中缀表达式的每个数字和符号,

若是数字就输出,即成为后缀表达式的一部分;

若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(*/ > +-),则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出为止.

所以我们发现,要让计算机具有处理我们通常的标准表达式的能力, 最重要的就是两步:

将中缀表达式转化为后缀表达式(栈用来进出运算的符号)
将后缀表达式进行运算得出结果(栈用来进出运算的数字)

4.10 队列的定义

队列(queue) 是只允许在一段进行插入操作,而在另一端进行删除操作的线性表

是FIFO 的线性表. 允许插入的一端称为队尾,允许删除的一端称为对头.

4.11 队列的抽象数据类型

ADT 队列(queue)
DATA
同线性表.元素具有相同类型,相邻元素具有前驱和后驱关系
OPERATION

InitQueue: 初始化操作,建立一个空队列
DestroyQueue: 若队列存在,则销毁它
ClearQueue:将队列清空
QueueEmpty:若队列为空,则返回 true,否则返回 false
GetHead: 若队列存在且非空,返回对头元素
EnQueue:插入
DeQueue:删除对头元素
QueueLength:返回元素个数

endEDT

4.12 循环队列

栈和队列都是线性表,所以都存在顺序存储和链式存储两种方式

4.12.1 队列顺序存储的不足

如果用两个指针来指向 front 和 rear,如果一个元素入队,然而数组末尾已经占用,就会产生数组越界的错误,然而可能之前有出队列的元素造成下标小的位置空余,这种现象叫做”假溢出”

4.12.2 循环队列定义

解决假溢出的方法就是后面满了,再从头开始,也就是头尾相接的循环.

我们把这种头尾相接的循序存储结构称为循环队列

如何判断队列满?

方法一: 设置 flag
方法二:保留一个元素空间,当队列满时,数组还有一个空闲单元

重点第二种

队列满的条件: (rear+1)%QueueSize==front

取模的目的为了整合 rear 与 front 大小为一个的问题

当rear>front 时,队列长度为 rear-front

当 rear<front 时,队列长度为0+rear+QueueSize-front,为 rear-front+QueueSize.

所以通用的长度计算公式为:

(rear-front+QueueSize)%QueueSize

单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列又面临着数组可能会溢出的问题.

4.13 队列的链式存储结构及实现

其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它称为链队列

两个指针,front 和 rear. front 指向头结点,rear 指向终端结点

空队列时,都指向头结点

4.13.1 队列的链式存储结构—入队

就是在链表尾部插入结点,也就是

将新的结点赋值给原结点的后继
移动 rear 指针

4.13.2 队列的链式存储结构—出队

头结点的后继结点出队
将头结点的后继改为它后面的结点
如果除头结点只剩一个元素时,将 rear 指向头结点

4.14 总结

栈
- 顺序栈
  - 两栈共享空间
- 链栈
队列
- 顺序队列
  - 循环队列
- 链队列

5. 串

5.2 串的定义

串(string)是由零个或多个字符组成的有限序列,又名叫字符串

5.3 串的比较

串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的符号

ASCII 编码: 由 7 位二进制数表示一个字符,总共可以表示 128 个字符,后来拓展到 8 位,总共可以表示 256 个字符.

Unicode 编码:因为各种语言的文字太多而出现,比较常用的是呀 ongoing16 位的二进制数表示一个字符,这样总共可以表示约是 65 万多个字符,为了与 ASCII 兼容,前 256 个字符与 ASCII 码完全相同

对于两个不相等的串,判定大小:

给定两个串:s=”a1a2…an”, t=”b1b2…bm”,当满足以下条件之一时,s<t

n<m,且 ai=bi

例如当 s=”hap”,t=”happy”,就有 s<t,因为 t 比 s 多了两个字母
当存在某个 k<=min(m,n),使得 ai=bi(i=1,2,…,k-1),ak<bk

例如当 s=”happen”,t=”happy”,因为两串的前4 个字母均相同,而两串第 5 个字母,e 的 ASCII 为 101,y 的 ASCII 为 121,所以 s<t

5.4 串的抽象数据类型

线性表更关注的是单个元素的操作,比如查找一个元素,插入或删除一个元素,但串中更多的是查找子串位置,得到指定位置子串,替换子串等操作

5.5 串的存储结构

5.5.1 串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的. 一般使用定长数组来定义

串值的存储空间可在程序执行过程中动态分配而得. 比如在计算机中存在一个自由存储区,叫做”堆”.

5.5.2 串的链式存储结构

与线性表相似,结构中的每一个元素数据是一个字符.

一个结点可以存放一个字符,也可存放多个字符,最后一个结点若是未占满,可以用”#”或其他非串值字符值补全

串的链式存储结构除了在连接串与串操作有一定方便之外,总的来说不如顺序存储结构灵活,性能也不如顺序存储结构好

5.6 朴素的模式匹配算法

子串的定位操作通常称作串的模式匹配

简单来说,就是对主串S的每一个字符串作为子串开头,与要匹配的字符串T进行匹配,对主串做大循环,每个字符开头做 T 的长度的小循环,直到匹配成功或全部遍历完成为止.

最好的情况: O(1)

稍差一些: O(n+m). n 是主串长度,m 为要匹配的子串长度,平均是(n+m)/2次查找,时间复杂度为 O(n+m)

最坏的情况: 每次不成功的匹配都发生在串 T 的最后一个字符,

所以是O((n-m+1)*m).

这个算法非常低效

5.7 KMP 模式匹配算法

5.7.1 KMP 模式匹配算法原理

如果我们知道 T 串中首字符”a”与 T 中后面的字符均不相等(这是前提).而 T 的第二位在第一次比较的时候已经判断是相等的,所以这次的判断(S 第二位和 T 第一位对比)是可以省略的

对于在子串中有与首字符相等的字符,也可以省略一部分不必要的判断步骤

5.7.2 next 数组值推导

算法推导过程略

核心思想为主串当前位置的下标 i 不回溯,考虑 j 的值

j 值的下一值的推导结果即 next 数组

5.7.3 KMP 模式匹配算法实现

算法略

和朴素匹配算法的改动就是去掉了 i 值回溯的部分,而 get_next 函数时间复杂度为 O(m),while 循环的时间复杂度为O(n).

整个算法的循环的时间复杂度为 O(n+m),

相较于朴素匹配的 O((n-m+1)*m)来说,是好一些
但是 KMP 算法仅当模式与主串之间存在许多”部分匹配”的情况下才体现出它的优势,否则两者差异并不明显

5.7.4 KMP 模式匹配算法改进

如果 T 串的第 2,3,4,5 位置的字符都与首位的”a”相等, 那么可以用首位 next[1]的值去取代与它相等的字符后续 next[j]的值.

5.7.5 nextval 数组值推导

过程略

实际上就比如 T 的第三个字符”a”的 next 值为 1,所以与第一位的”a”比较得知它们相等,所以 nextval[3]=nextval[1]=0;

总结改进过的 KMP 算法,它是在计算出 next 值的同时,如果 a 位字符与它 next 值指向的 b 位字符相等,则该 a 位的 nextval 就指向 b 位的 nextval 值,如果不等,则该 a 位的 nextval 值就是它自己 a 位的 next 的值

5.8 总结回顾

我们在使用这些函数的时候,也要理解它们当中的原理,以便于在碰到复杂问题的时候,可以更加灵活的使用.比如 KMP 模式匹配算法

6. 树

6.2 树的定义

之前都是一对一的线性结构,一对多的情况需要树

树 Tree:

是 n(n>=0) 个结点的有限集. n=0 时称为空树.

在任意一颗非空树中:

有且仅有一个特定的称为根(root)的结点
当 n>1时,其余结点可分为 m(m>0)个互不相交的有限集 T1,T2,….,Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree).

注意:

在树的定义中也用到了树的概念
n>0时根结点是唯一的
m>0 时,子树的个数没有限制,但它们一定是互不相交的

6.2.1 结点分类

树的结点包含一个数据元素及若干指向其子树的分支.

结点拥有的子树数称为结点的度(Degree).
度为 0 的结点称为叶结点(Leaf)或终端结点; 度不为 0 的结点称为分支结点或非终端结点.
除根节点之外,分支节点也称为内部结点.
树的度是树内各结点的度的最大值.

拥有的子树数其实就是这个结点有几个分支

所以分支的最大值为树的度

6.2.2 结点间关系

结点的子树的根称为该结点的孩子(Child), 该结点称为孩子的双亲 (Parent)

同一个双亲的孩子之间为兄弟结点(Sibling)

结点的祖先是根到该结点所经分支上的所有结点

某结点为根的子树中的任一结点都称为该结点的子孙

6.2.3 数的其他相关概念

结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层.

数中结点的最大层次称为数的深度(Depth)或高度.

如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序数.

森林(Forest)是 m(m>=0) 棵互不相交的树的集合.

6.3 数的抽象数据类型

略

6.4 树的存储结构

简单的顺序存储结构是不能满足对树的实现的

不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示.

双亲表示法
孩子表示法
孩子兄弟表示法

6.4.1 双亲表示法

在每个结点中,附设一个指示器指示其双亲结点到链表中的位置.

也就是说,每个结点除了知道自己是谁之外,还知道它的双亲在哪. 所以查找双亲的时间复杂度为 O(1). 但是如果我们要知道结点的孩子是什么,只能遍历整个结构

特殊的改进: 可以添加一个长子域便于找到孩子

存储结构的设计是一个非常灵活的过程.一个存储结构设计得是否合理,取决于基于该存储结构的运算是否适合,是否方便,时间复杂度好不好等.

6.4.2 孩子表示法

每个结点有多个指针域,其中每个指针指向一棵树的根结点, 我们把这种方法叫做多重链表表示法

树的每个结点的度,也就是孩子数是不同的.两种方案:

方案一

指针域的个数就等于树的度

比如树的度为 3,指针域的个数就是 3,每个结点都有三个指针域

但是对于树种各结点的度相差很大的时候,浪费空间

方案二

每个结点指针域的个数等于该结点的度, 我们专门取一个位置来存储结点指针域的个数

克服了浪费空间的缺点,空间利用率高了,但是由于每个结点的链表是不同的结构,加上要维护结点的数值,在运算上就会带来时间上的损耗.

更好的方法? 仔细观察,为了遍历数,把每个结点放到一个顺序存储结构的数组中是合理的,单每个结点的孩子有多少是不确定的,所以再建立一个单链表

方案三

把每个结点的孩子结点排列起来,以单链表作存储结构,则 n 个结点有 n 个孩子列表,如果是叶子结点则此单链表为空. 然后 n 个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中.

需要使用两种结点结构:

孩子链表的孩子结点
- child: 存放某个结点在表头数组中的下标
- next: 指针域,用来存储指向某结点的下一个孩子结点的指针
表头数组的表头结点
- data: 存放某结点的数据信息
- firstchild 是头指针域,存放该结点的孩子链表的头指针

优点:

利于查找某个结点的孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可
遍历整个树也方便,只需要对头结点的数组循环

缺点:

无法知道某个结点的双亲,需要整棵树遍历

孩子表示法的改进:

表头数组的结点多存一个域,记录其双亲结点的下标

这种方法称为孩子双亲表示法.

6.4.3 孩子兄弟表示法

任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的. 因此我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟

结点结构由三部分组成:

data:数据域
firstchild:指针域, 存储该结点的第一个孩子结点的存储地址
rightsib:指针域,存储该结点的右兄弟结点的存储地址

优点: 查找某个结点的某个孩子方便

缺点: 找双亲不便(改进: 增加 parent 指针域)

最大好处: 将一颗复杂的树变成了一颗二叉树.这样就可以利用二叉树的特性和算法来处理这棵树了

6.5 二叉树的定义

在某个阶段都是两种结果的情形,比如开关,01,真假,对错,都适合用树状结构来建模,而这种树是一种很特殊的树状结构,叫做二叉树

二叉树(Binary Tree) 是 n (n>=0) 个结点的有限结合,该集合或者为空集(称为空二叉树), 或者由一个根节点和两棵互不相交的,分别称为根节点的左子树和右子树的二叉树组成.

6.5.1 二叉树特点

每个结点最多有两棵子树
左子树和右子树是有顺序的, 次序不能任意颠倒
即使树中某结点只有一棵子树,也要区分它是左子树还是右子树.

6.5.2 特殊二叉树

斜树

所有的结点都只有左子树的二叉树叫做左斜树

所有的结点都只有右子树的二叉树叫做右斜树

明显特点: 每一层只有一个结点,结点的个数与二叉树的深度相同

所以,线性表结构就可以理解为是树的一种极其特殊的表现形式.
满二叉树

所有的分支结点都存在左子树和右子树,并且所有叶子都在同一层上

注意: 还需要所有的叶子都在同一层上,这就做到了整棵树的平衡

特点:
1. 叶子只出现在最下一层
2. 非叶子结点的度一定是 2
3. 同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多
完全二叉树

对一棵具有 n 个节点的二叉树按层序编号,如果编号为 i (1<=i<=n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树

完全二叉树是满二叉树的子集

关键词: 按层序编号

特点:
1. 叶子只出现在最下两层
2. 最下层的叶子一定集中在左部连续位置
3. 倒数第二层,如果有叶子结点,一定都在右部连续位置
4. 如果结点度为 1,则该结点只有左孩子,即不存在只有右子树的情况
5. 同样结点数的二叉树,完全二叉树的深度最小(因为尽可能的把左边补满,把叶子留在右边)

6.6 二叉树的性质

在二叉树的第 i 层上至多有 2 的 i-1 次方个节点
深度为 k 的二叉树至多有 2 的 k 次方-1 个节点(k>=1)

其实就是把每一层装满,可以根据字节的每一位为 1 理解
对任何一颗二叉树T,如果其终端结点数为 n0,度为 2 的结点数位 n2, 则 n0 = n2 + 1

通过结点数和分支线数角度推算
具有 n 个结点的完全二叉树的深度为
$$
⌊log_2n⌋+1
$$
注意向下取整符号
如果对一棵有 n 个节点的完全二叉树 (其深度如 4) 的结点按层序编号,对任一结点 i(1<=i<=n)有:
1. 如果 i=1,则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲是结点[i/2].
2. 如果2i>n, 则结点 i 无左孩子(结点 i 为叶子结点); 否则其左孩子是结点 2i
  
  因为每下一层的编号是上一层编号的 2 倍或 2 倍+1,n 不够当然是叶子
3. 如果 2i+1>n,则结点 i 无右孩子; 否则其右孩子是结点 2i+1

6.7 二叉树的存储结构

6.7.1 二叉树顺序存储结构

二叉树是一种特殊的数,由于其特殊性,使得用顺序存储结构也能实现.

考虑完全二叉树,编号依照顺序来的,所以可以依次放入数组

考虑一般的二叉树,将其按照完全二叉树编号,只不过把不存在的结点标识出来

考虑极端情况,一棵深度为 k 的右斜树,它只有 k 个结点,却需要分配
$$
2^k -1
$$
个存储单元空间,这显然是浪费

所以: 顺序存储结构一般只用于完全二叉树

6.7.2 二叉链表

二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域. 这样的链表叫做二叉链表

data: 数据域
lchild: 指向左孩子的指针
rchild: 指向右孩子的指针

如果有需要,还可以增加一个指向双亲的指针域,那样就称之为三叉链表

6.8 遍历二叉树

二叉树的遍历(traversing binary tree) 是指从根节点触发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次

6.8.2 二叉树遍历方法

从左到右的习惯方式下,一共四种:

前序遍历

规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树

也就是先根,然后左结点,右结点
中序遍历

规则是若树为空,则空操作返回, 否则从根结点开始(注意并不是访问), 中序遍历根结点的左子树,然后是访问根节点,最后中序遍历右子树.

也就是对于每一个子树,都是先左结点,根,右结点
后序遍历

规则是若树为空,则空操作返回,否则从左到右,先叶子后结点的方式遍历访问左右子树,最后访问根节点

也就是先左右,后根
层序遍历

规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右对结点逐个访问

遍历方式有什么用? 因为对于计算机来说,它只有循环判断等方式,也就是说,只能处理线性序列,而这四种遍历方法,其实就是把树中的结点变成某种意义的线性序列.

6.8.3 前序遍历算法

二叉树定义是用递归的方式,所以遍历算法也可以采用递归

// 二叉树的前序遍历递归算法void PreOrderTraverse(BiTree T){  if(T==null)    return;  printf("%c",T->data); // 结点操作  PreOrderTraverse(T->lchild); // 先前序遍历左子树  PreOrderTraverse(T->rchild); // 最后前序遍历右子树}

理解递归函数要从栈的角度理解

6.8.4 中序遍历算法

和前序遍历算法仅仅是代码顺序的差异

// 二叉树的中序遍历递归算法
void InOrderTraverse(BiTree T)
{
  if(T==null)
    return;
  InOrderTraverse(T->lchild); // 中序遍历左子树
  printf("%c",T->data); // 结点操作
  InOrderTraverse(T->rchild); // 最后中序遍历右子树
}

6.8.5 后序遍历算法

同样

// 二叉树的后序遍历递归算法
void PostOrderTraverse(BiTree T)
{
  if(T==null)
    return;
  PostOrderTraverse(T->lchild); // 中序遍历左子树
  PostOrderTraverse(T->rchild); // 最后中序遍历右子树
  printf("%c",T->data); // 结点操作
}

6.8.6 推导遍历结果

题目 1: 已知一棵二叉树的前序遍历序列为 ABCDEF,中序遍历序列为 CBAEDF,请问后序遍历结果是多少? (CBEFDA)

题目2: 二叉树的中序序列是 ABCDEFG,后序序列是 BDCAFGE,求前序序列. (EACBDGF)

我的方法: 根据前序根最前,后序根最后的规则,将大树拆小树,小树拆小小树判定

二叉树遍历的性质:

已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树

已知前序和后序遍历,是不能确定一棵二叉树的,

原因: 前序 ABC,后序 CBA,我们只能知道 A 是根节点,B 是 A 的孩子,但是不知道 C 是 B 的左子树还是右,B 是 A 的左子树还是右

6.9 二叉树的建立

为了让每个结点确认是否有左右孩子,将二叉树中每个结点的空指针引出一个虚结点,其值为一特定值,比如”#”. 我们称这种处理后的二叉树为原二叉树的拓展二叉树

拓展二叉树可以做到一个遍历序列可以确定一棵二叉树

算法略

6.10 线索二叉树

6.10.1 线索二叉树原理

一个 n 个结点的二叉链表,一共是 2n 个指针域,n-1 条分支线数,所以存在 2n-(n-1) = n+1个空指针域,浪费了内存资源

在二叉链表,我们只能知道每个结点指向其左右孩子结点的地址,而不知道其前驱和后继(遍历结果)

所以利用空指针,存放指向结点在某种遍历次序下的前驱和后继结点的地址.

这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded Binary Tree)

我们把二叉树进行中序遍历后,将所有空指针中的 rchild,改为指向它的后继结点, 将这棵二叉树的空指针域中的 lchild,改为指向当前结点的前驱.

通过这种形式,我们可以把一棵二叉树转变成一个双向链表,这样对插入删除结点,查找结点带来方便. 对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化.

如何区分指针是指向孩子还是前驱/后驱? 每个结点增设两个标志域 ltag 和 rtag, 仅仅存放 0/1 的 boolean 型变量,内存空间小

tag为 0 时指向该结点的孩子,1 时指向前驱/后继

6.10.2 线索二叉树结构实现

二叉树线索存储结构定义:

1	typedef enum {Link,Thread} PointerTag;typedef struct BiThrNode{ TElemType data; struct BiThrNode lchild, rchild; PointerTag LTag; PointerTag RTag;} BiThrNode, *BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向其前驱或后继的线索.由于前驱和后继的信息只有在遍历该二叉树时才能得到,所以,线索化的过程就是在遍历的过程中修改空指针的过程

BiThrTree pre; // 全局变量,始终指向刚访问过的结点// 中序遍历线索化void InThreading(BiThrTree p){  if(p)  {    InThreading(p->lchild); // 递归左子树线索化    if(!p->lchild) // 没有左孩子    {      p->LTag=Thread; // 前缀线索      p->lchild=pre; // 左孩子指针指向前驱    }    if(!pre->rchild) // 没有右孩子    {      pre->RTag=Thread; // 后缀线索      pre->rchild=p; // 前驱右孩子指针指向后继(当前结点 p)    }    pre=p; // 保持 pre 指向 p 的前驱    InThreading(p->rchild); // 递归右子树线索化  }}

遍历发现其实就是操作双向链表,所以添加一个头结点,

令其 lchild 域的指针指向二叉树的根结点,其 rchild 域的指针指向中序遍历时访问的最后一个结点

令中序的第一个结点的 lchild 指针和最后一个结点的 rchild 指针均指向头结点

这样的好处: 我们既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历.

算法略

它等于一个链表的扫描,时间复杂度为 O(n)

由于它充分利用了空指针域的空间,又保证了创建一次遍历就可以终生受前驱后继信息,所以,如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构是非常不错的选择

6.11 树,森林与二叉树的转换

6.11.1 树转换为二叉树

步骤如下

加线. 在所有兄弟结点之间加一条连线
去线. 对树中每个结点,只保留它与第一个孩子的连线,删除它与其他孩子结点之间的连线.
层次调整. 以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明. 注意第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子

其实就是将树每一个结点的多个结点转换成深度

左孩子: 第一个孩子

右孩子: 兄弟

6.11.2 森林转换为二叉树

森林 = 若干棵树

把森林的每一棵树理解成兄弟

步骤如下:

把每棵树转换为二叉树
第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连起来,当所有的二叉树连起来后就得到了由森林转换来的二叉树

所以这么来看,森林中每一棵树的排位顺序也影响了最后转换结果

6.11.3 二叉树转化为数

步骤如下:

加线. 若结点的左孩子结点存在(也就是说有大儿子), 则将这个左孩子的所有 n 个右孩子结点都作为此结点的孩子. 将该结点与这些右孩子结点用线连接起来(如果有大孩子,则将大孩子的所有右孩子(原本是树结构下结点的大孩子的兄弟)连起来)
去线. 删除原二叉树中所有结点与右孩子结点的连线(因为以前是树结构下的兄弟)
层次调整

6.11.4 二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林?

看二叉树的根结点有没有右孩子,有就是森林,没有就是一棵树

树只有一个根结点,转换为二叉树,根结点也只有一个左孩子! 它的所有兄弟都作为左孩子的右结点下面了

转换步骤:

从根结点开始, 若右孩子存在,则把右孩子结点的连线删除,再查看分离后的二叉树,循环这一步,直到所有右孩子结点的连线都删除为止,得到分离的二叉树.
将每颗分离后的二叉树转换为树即可.

6.11.5 树与森林的遍历

树的遍历分为两种方式:

先根遍历. 先访问树的根结点,然后依次先根遍历根的每棵子树
后根遍历. 先访问每棵子树,最后访问根结点

森林的遍历也分为两种方式:

前序遍历:
1. 先访问森林中第一棵树的根结点
2. 依次先根遍历根的每棵子树
3. 再依次用同样的方式遍历除去第一棵树的剩余树构成的森林.
其实就是把几个树的遍历连起来
后序遍历:
1. 先访问森林中第一棵树,后根遍历每棵子树,最后访问根结点
2. 重复 1 遍历除去第一棵树的剩余树构成的森林

结论:

森林的前序遍历和二叉树的前序遍历结果相同
森林的后序遍历和二叉树的中序遍历结果相同

也就是说: 当以二叉链表作树的存储结构时,树的先根遍历和后根遍历完全可以借用二叉树的先序遍历和中序遍历的算法来实现.

也就是说,我们找到了对树和森林这种复杂问题的简单解决方法

6.12 赫夫曼树及其应用

6.12.1 赫夫曼树

最基本的压缩编码方法: 赫夫曼编码

编码中提到的特殊的二叉树称为赫夫曼树

6.12.2 赫夫曼树定义与原理

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度.

树的路径长度就是从树根到每一结点的路径长度之和

考虑到带权的结点,假设有 n 个权值构造一棵有 n 个叶子结点的二叉树.自重带权路径长度 WPL 最小的二叉树称作赫夫曼树(最优二叉树).

赫夫曼树的赫夫曼算法

根据给定的 n 个权值{w1,w2,…,wn},构成 n 棵二叉树的集合 F={T1,T2,…,Tn},其中每棵二叉树 T1中只有一个带权为 w1的根结点,其左右子树为空.
在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和.
在 F 中删除这两棵树,同时将新得到的二叉树加入 F 中
重复 2,3 步骤,知道 F只含一颗树位置. 这棵树就是赫夫曼树

6.12.3 赫夫曼编码

一般地,设需要编码的字符集为{d1,d2,…dn}, 各个字符在电文中出现的次数或频率集合为{w1,w2,…wn},以 d1,d2,…dn为叶子结点,以w1,w2,…wn作为相应叶子结点的权值来构造一棵赫夫曼树. 规定赫夫曼树的左分支代表 0,右分支代表 1,则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码,这就是赫夫曼编码.

因为在解码时,还是要用到赫夫曼树,所发送方和接收方必须要约定好同样的赫夫曼编码规则

6.13 总结

树的定义(递归)
树的存储结构:
1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法
通过孩子兄弟表示法,可以将树 -> 二叉树
二叉树:
1. 斜树
2. 满二叉树
3. 完全二叉树
二叉树的存储结构由于其特殊性使得既可以用顺序存储结构又可以用链式存储结构表示
遍历是二叉树最重要的一门学问
1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层序遍历
二叉链表有很多空指针 -> 如何构造线索二叉树
树,森林,二叉树互相转换的方法
二叉树的应用 -> 赫夫曼树和赫夫曼编码.

7. 图

7.2 图的定义

图是一种较线性表和树更加复杂的数据结构. 在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关

图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: $G(V,E)$, 其中,G 表示一个图,V 是图G 中顶点的集合,E 是图 G 中边的集合.

数据元素在线性表中叫元素,在树中叫结点,在图中叫顶点(Vertex)
图结构中,不允许没有顶点,顶点集合 V 有穷非空
线性表中,相邻的元素之间具有线性关系; 树结构中,相邻两层的结点具有层次关系; 图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的

7.2.1 各种图定义

无向边: 若顶点 vi 到 vj之间的边没有方向,则称这条边为无向边(Edge), 用无序偶对 (vi,vj) 来表示.

如果图中任意两个顶点之间的边都是无向边,则称该图为无向图 (Undirected graphs).

有向边: 若从顶点 vi 到 vj 的边有方向,则称这条边为有向边,也称为弧(Arc). 用有序偶 <vi , vj > 来表示, vi 表示弧尾 (Tail), vj 称为弧头 (Head). 如果图中任意两个顶点之间的边都是有向边, 则称该图为有向图 (Directed graphs).

无向边用小括号”()”表示,有向边用尖括号”<>”表示

若不存在顶点到其自身的边,且一条边不重复出现,则称这样的图为简单图. (本书讨论的范围)

无向图中, 如果任意两个顶点之间都存在边, 则称该图为无向完全图. 含有 n 个顶点的无向完全图有$n*(n-1)/2$ 条边.

在有向图中,如果任意两个顶点之间都存在方向互为想反的两条弧, 则称该图为有向完全图. 含有 n 个顶点的有向完全图有$n*(n-1)$ 条边.

有很少条边或弧的图称为稀疏图,反之称为稠密图. (这里稀疏和稠密都是相对的模糊的概念)

有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的树叫做权(Weight). 这些权可以表示从一个顶点到另一个顶点的距离或耗费. 这种带权的图通常称为网(Network).

如果一个图的顶点集和边集都是另一个图的子集,则称此图是另一个图的子图(Subgraph)

7.2.2 图的顶点与边间的关系

对于一个无向图,如果一个边在边集中, 则称这个边的两个顶点互为邻接点(Adjacent),即两个顶点相邻接. 边依附(Incident)于这两个顶点,或者说两个顶点相关联. 顶点v 的度(Degree)是和 v 相关联的边的数目,记为 TD(v).

边其实就是各顶点度数和的一半, 多出的一半是因为重复两次计数.

对于有向图, 一个叫邻接到顶点,一个叫邻接自顶点. 以顶点 v 为头的弧的数目称为 v 的入度(InDegree),记为 ID(v); 以 v 为尾的弧的数目称为 v 的出度(OutDegree),记为 OD(v); 顶点 v 的度为 $TD(v) = ID(v) + OD(v)$.

出度和入度都是正的

各顶点的出度和等于入度和

路径的长度是路径上的边或弧的数目

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle). 序列中顶点不重复出现的路径称为简单路径. 除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环.

7.2.3 连通图相关术语

无向图中,如果两个顶点之间有路径,则称两个顶点是连通的. 如果对于图中任意两个顶点都是连通的, 则称图是连通图(Connected Graph)

无向图中的极大连通子图称为连通分量

要是子图
子图要是连通的
连通子图含有极大顶点数
具有极大顶点数的连通子图包含依附于这些顶点的所有边

有向图G中,如果对于每一对 vi , vj 从 vi 到 vj 和从 vj 到 vi 都存在路径,则称 G 是强连通图. 有向图中的极大强连通子图称作有向图的强连通分量.

一个连通图的生成树是一个极小的连通子图, 它还有图中全部的 n 个顶点,但只有足以构成一棵树的 n - 1 条边.

如果一个图有 n 个顶点和小于 n-1条边,则是非连通图

如果它多于 n-1边条,必定构成一个环

如果一个有向图恰有一个顶点的入度为 0, 其余顶点的入度为 1, 则是一棵有向树.

一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点, 但只有足以构成若干棵不相交的有向树的弧

7.2.4 图的定义与术语总结

图按照有无方向分为无向图和有向图
- 无向图由顶点和边构成
- 有向图由顶点和弧构成. 弧有弧尾和弧头之分
图按照边或弧的多少分稀疏图和稠密图
- 如果任意两个顶点都存在边叫完全图,有向的叫有向完全图
- 若无重复的边或顶点到自身的边叫简单图
顶点有邻接点,依附的概念
- 无向图顶点的边数叫做度
- 有向图顶点分为入度和出度
图上的边或弧上带权则成为网
图中顶点间存在路径
- 两顶点存在路径则说明是连通的
- 如果路径最终回到起始点则成为环
- 当中不重复叫简单路径
- 若任意两顶点都是连通的,则图就是连通图; 有向则称强连通图
- 图中有子图,若子图极大连通则就是连通分量,有向的则称强连通分量.
有向图中连通且 n 个顶点 n-1 条边叫生成树
- 有向图中一顶点入度为 0 其余顶点入度为 1 的叫有向树.
- 一个有向图由若干棵有向树构成生成森林

7.3 图的抽象数据类型

略

7.4 图的存储结构

顺序存储结构: 无法以数据元素在内存中的物理位置来表示元素之间的关系

多重链表: 尽管可以实现图结构但是会有很多存储单元的浪费

7.4.1 邻接矩阵

顶点用一维数组可以存储, 但是边或者弧是顶点之间的关系,一维不行,那么就考虑二维数组

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图. 一个一维数组存储图中顶点信息, 一个二维数组(称为邻接矩阵)存储图中的边或弧的信息.

设图 G 有 n 个顶点,则邻接矩阵是一个 n * n 的方阵.

矩阵的对角线为 0 是因为没有顶点到自身的边, 值为 1 表示有边存在, 0 表示不存在.

无向图

无向图的边数组是一个对称矩阵

对称矩阵: 左上角到右下角的主对角线为轴,右上角的元与左下角的元全都是相等的

矩阵推断图的信息:

判定两顶点是否有边更容易
某个顶点的度,就是这个顶点 vi 在第 i 行或 i 列的元素之和.
求顶点 vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍,值为 1 就是邻接点

有向图

因为是有向图,所以矩阵并不对称

判断顶点 vi到 vj是否存在弧,只需要查找矩阵中 $arc[i][j]$ 是否为1 即可
vi的所有邻接点就是将矩阵第 i 行元素扫描一遍,查找 $arc[i][j]$ 为 1 的顶点

网图

使用 Wij 表示权值.

∞ 表示一个不可能的极限值 (不是零的原因是规避权值为 0 的情况,主对角线就是 0)

n个顶点和 e 条边的无向网图的创建,时间复杂度为$O(n+n^2+e)$, 其中对邻接矩阵的初始化耗费了$O(n^2)$的时间

7.4.2 邻接表

由于对于边数大量小于顶点的图,邻接矩阵对存储空间有极大的浪费. 我们考虑对边或弧使用链式存储的方式.

采用一种类似树的孩子表示法. 这种数组与链表相结合的存储方法成为邻接表(Adjacency List)

处理方法:

图中顶点用一个一维数组存储. 每个数据元素还需要存储指向第一个邻接点的指针,以便查找该顶点的边信息.
每个顶点vi 的所有邻接点构成一个线性表, 由于个数不定,所以用单链表, 无向图称为顶点 vi的边表,有向图则称为顶点 vi作为弧尾的出边表

对于带权值的网图, 可以在边表结点定义中再增加一个 weight 数据域,存储权值信息即可

本算法的时间复杂度对于 n 个顶点 e 条边来说,是$O(n+e)$

7.4.3 十字链表(有向图优化)

邻接表缺点: 邻接表关心了出度问题,想了解入度就必须遍历整个图; 逆邻接表解决了入度却不了解出度的情况.

十字链表(Orthogonal List): 就是把邻接表和逆邻接表结合起来的一种存储方法

重新定义顶点表结点结构:

data
firstin: 入边表头指针
firstout: 出边表头指针

重新定义边表结点结构

tailvex: 弧起点在顶点表的下标
headvex: 弧终点在顶点表中的下标
headlink: 入边表指针域,指向终点相同的下一条边
taillink: 出边表指针域., 指向起点相同的下一条边
(weight); 权值

其实就是 v0 有一条从 v1 来的话,firstin 指向 v1 的边表的那个 v1 指向 v0 的那一个, 再将这一个边结点的 headlink 指向 v0 的下一个入边

所以每个顶点的 firstin 指针开始到结束就能找到所有的入边

十字链表除了结构复杂, 创建图算法的时间复杂度是和邻接表相同的, 因此,在有向图的应用中,十字链表是非常好的数据结构模型

7.4.4 邻接多重表(无向图优化)

邻接表的问题: 如果删除(v0,v2) 这条边,需要对邻接表结构中右边表的两个结点进行删除,比较麻烦

邻接多重表结构:

ivex: 与某条边依附的两个顶点在顶点表中下标(为了方便,设置为与一旁的顶点下标相同)
ilink: 指向依附顶点 ivex 的下一条边
- ilink指向的结点的 jvex 一定要和它本身的 ivex 值相同
jvex: 与某条边依附的两个顶点在顶点表中下标
jlink: 指向依附顶点 jvex 的下一条边

不论 ilink 还是 jlink,指向的地方是结点

7.4.5 边集数组

边集数组是由两个一维元素构成. 一个是存储顶点的信息; 另一个是存储边的信息, 这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成.

要查找一个顶点的度需要扫描整个边数组,效率不高

适合对边依次进行处理的操作,不适合对顶点相关的操作

7.5 图的遍历

图的遍历 (Traversing Graph): 从图中某一顶点出发访问遍历图中其余顶点,且使每个顶点仅被访问一次.

两种遍历次序方案: 深度优先遍历和广度优先遍历

7.5.1 深度优先遍历

Depth_First_Search,简称 DFS.

其实就是一个递归,像是一棵树的前序遍历

从图中某个顶点 v 出发,访问此顶点,然后从 v 的未访问的邻接点出发深度优先遍历图,直至图中所有和 v 有路径相同的顶点都被访问到. 如果是非连通图,一次深度优先遍历后, 若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止.

一步一步来,假设每次选择最右边的走,碰见重复的后退回上一步走右边第二个.

邻接矩阵:

typedef int Boolean; //Boolean 是布尔类型,其值为 TRUE 或 FALSE
Boolean visited[MAX]; // 访问标志的数组

// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i)
{
  int j;
  visited[i] = TRUE;
  printf("%c ",G.vexs[i]); // 遍历
  for(j = 0; j < G.numBertexes; j++) // 遍历整个矩阵才能找到邻接点
    if(G.arc[i][j] == 1 && !visited[j])
      DEF(G,j);	// 对未访问过的邻接顶点递归调用
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
  int i;
  for(i = 0; i < G.numVertexes; i++)
    visited[i] = FALSE; // 初始顶点状态为未访问
  for(i = 0; i < G.numVertexes; i++)
    if(!visited[i]) // 对未访问过的顶点调用 DFS, 若是连通图,只会执行一次
      DFS(G,i);
}

图结构是邻接表的话,在递归函数中将数组换成了链表

// 邻接表的深度优先递归算法
void DFS(GraphAdjList GL, int i)
{
  EdgeNode *p;
  visited[i] = TRUE;
  pringf("%c ", GL->adjList[i].data); // 访问
  p = GL->adjList[i].firstedge; // 顶点集的第一个边
  while(p)
  {
    if(!visited[p->adjvex])
      DFS(GL,p->adjvex); // 对未访问的邻接顶点递归调用(去找第一个边的下一个边的顶点)
    p = p->next;
  }
}
// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
  int i;
  for(i = 0; i < GL->nemVertexes; i++)
    visited[i] = FALSE; // 初始顶点状态为未访问
  for(i = 0; i < GL->nemVertexes; i++)
    if(!visited[i]) // 对未访问过的顶点调用 DFS, 若是连通图, 只会执行一次
      DFS(G,i);
}

对于n 个顶点 e 条边的图来说,

邻接矩阵由于是二维数组,查找每个顶点的邻接点需要访问矩阵中所有元素,因此都需要 O(n^2^) 时间.

邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是 O(n+e).

对于有向图而言,算法上没有变化,可以通用.

7.5.2 广度优先遍历

Breadth_First_Search, 简称 BFS.

类似树的层序遍历

算法大致就是构造一个队列,先从一个结点放进去,

然后将第一个结点出队列,将其所有队列中没有的关联结点入队列

继续出队列,重复上一步,知道队列全部出来.

两种方式比较

深度优先遍历和广度优先遍历算法的时间复杂度相同

深度优先适合目标比较明确,以找到目标为主要目的的情况

广度优先适合在不断扩大遍历范围时找到相对最优解的情况

两者与算法实现无关,是方法论的问题. 是矛盾又统一的两方面

7.6 最小生成树

一个带权值的图,即网结构. 所谓的最小成本,就是 n 个顶点,用 n-1 条边把一个连通图连接起来,使得权值的和最小.

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

经典的寻找最小生成树的有两种算法,普利姆算法和克鲁斯卡尔算法

7.6.1 普利姆(Prim)算法

先构造图的邻接矩阵

然后算法略

算法定义:

假设$N = (P,{E})$ 是连通网,TE 是 N 上最小生成树中边的集合. 算法从 U={u0} , TE={} 开始.重复执行下述操作:

在所有 $u ∈ U, v ∈ V -U$ 的边 $(u,v)∈E$中找一条代价最小的边 (u0, v0) 并入集合 TE, 同时 v0 并入 U, 直至 U=V 为.

此时 TE 中必有 n-1 条边, 则$T(V,{TE})$ 为 N 的最小生成树

由算法中的嵌套循环可知算法的时间复杂度为 O(n^2^)

简单的绘图方法就是,找一个点,作为子树集合,画一个圆圈包起来, 剩下的点集到这个圆圈的距离最短的那个加入子树集合,重新画圈,反复重复.

是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的

7.6.2 克鲁斯卡尔(Kruskal)算法

K 算法直接以边为目标.

将图先转化为边集数组, 并且对他们按权值从小到大排序

算法略

定义如下:

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

此算法的 Find 函数由边数 e 决定,时间复杂度为$O(loge)$, 而外面有一个 for 循环 e 次. 所以 K 算法的时间复杂度为$O(eloge)$

对比

克鲁斯卡尔算法(K 算法)主要针对边展开,边数少效率高,对于稀疏图有很大优势

普利姆算法(P 算法)对于稠密图, 边数多的情况更好.

7.7 最短路径

非网图: 没有边上的权值,最短路径就是指两顶点之间经过的边数最少的路径;

网图: 最短路径,是指两顶点之间经过的边上的权值之和最少的路径, 并且我们称路径上的第一个顶点是源点,最后一个顶点是终点.

7.7.1 迪杰斯特拉(Dijkstra)算法

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

这个算法不是一下子就求出了两点之间的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是讲基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到想要的结果.

算法略

算法是一个嵌套

算法核心两步,一是找到某个点到源点的最近距离,二是根据这个最近距离更新这个点相邻的结点的最短距离

通过 D 算法解决了从某个源点到其余各顶点的最短路径问题.

从循环嵌套可知, 时间复杂度为 $O(n^2)$

如果要知道任意顶点到其余所有顶点的最短距离,就是将每个顶点当做源点做一次 D 算法, 就是再来一次循环, 时间复杂度就成了$O(n^3)$

7.7.2 弗洛伊德(Floyd)算法

算法略

算法的核心就是构建两个二维数组 D,P

D 代表顶点到顶点的最短路径权值和的矩阵

P 代表对应顶点的最小路径的前驱矩阵.

然后依次选择下一个中转并更新 D 和 P

建议笔算理解

三重循环,时间复杂度为 $O(n^3)$

面临需求所有顶点至所有顶点的最短路径问题时,弗洛伊德 F 算法应该是不错的选择.

7.8 拓扑排序

是无环的图的应用. 无环即图中没有回路

7.8.1 拓扑排序介绍

如果把工程比作图,某些活动肯定在某些活动之后才开始, 这样的工程图肯定是无环的有向图

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

AOV 网中不能存在回路

拓扑序列: 设 $G=(V,E)$ 是一个具有 n 个顶点的有向图,V 中的顶点序列 v1, v2, … , vn 满足若从顶点 vi 到 vj 有一条路径, 则在顶点序列中顶点 vi 必在顶点 vj 之前. 则我们称这样的顶点序列为一个拓扑序列

拓扑序列有可能不止一条

拓扑排序,其实就是对一个有向图构造拓扑序列的过程

如果此网的全部顶点都被输出,则说明它是不存在环(回路)的 AOV 网
如果输出顶点少了, 哪怕是少了一个,也说明这个网存在环(回路), 不是 AOV 网

这个少的原因书中没有描述清楚, 我的理解是:

如果是环,则这个顶点无法满足既在前又在后,所以无法放入拓扑序列, 所以最后输出的顶点肯定少.

7.8.2 拓扑排序算法

对 AOV 网进行拓扑排序的基本思路:

从 AOV 网中选择一个入度为 0 的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧, 继续重复此步骤,知道输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止

由于需要删除顶点,所以用邻接表

由于始终要找入度为 0 的点,所以顶点表结构中增加一个入度域 in; 边表不变

结构:

in: 入度的数字
data: 数据
firstedge: 边表头指针

结构代码:

typeof struct EdgeNode // 边表结点
{
  int adjvex;	// 邻接点域,存储该顶点对应的下标
  int weight; // 用于存储权值,对于非网图可以不需要
  struct EdgeNode *next; // 链域,指向下一个邻接点
}EdgeNode;

typeof struct VertexNode // 顶点表结点
{
  int in; // 顶点入度
  int data; // 顶点域, 存储顶点信息
  EdgeNode *firstedge; // 边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
  AdjList adjList;
  int numVertexes,numEdges; // 图中当前顶点数和边数
}graphAdjList,*GraphAdjList;

算法代码略

思想就是:

先初始化一个栈,

将所有入度为 0 的顶点入栈.

然后出栈栈顶元素a, 找到其连接的顶点, 并将它们的入度减少一位.

如果入度减少到 0, 入栈

删除刚刚出栈的元素a

再次循环3-5

对于一个具有 n 个顶点 e 条弧的 AOV 网来说, 初始化时候扫描顶点表,入度为 0 入栈的时间复杂度为$ O(n)$; 之后循环的时候,每个顶点进栈一次,出栈一次,入度减一一次, 共 e 次

整个算法时间复杂度为 $O(n+e)$

7.9 关键路径

拓扑排序没有解决最短路径问题.

在一个表示工程的带权有向图中, 用顶点表示事件, 用有向边表示活动, 用边上的权值表示活动的持续时间, 这种有向图的边表示活动的网, 我们称之为 AOE 网 (Activity On Edge Network)

AOE 网只有一个源点一个汇点

与 AOV 的不同: AOV 顶点表示活动, 只描述活动的先后制约. AOE 是用边表示活动的网,边上的权值表示活动持续的时间

我们把路径上各个活动所持续的时间之和称为路径长度, 从源点到汇点具有最大长度的路径叫关键路径, 在关键路径上的活动叫关键活动.

只有缩短关键路径上的关键活动时间才可以减少整个工期长度

7.9.1 关键路径算法原理

如果一个活动最早开始时间和最晚开始时间不相等,就意味着有空闲. 所以找到两者相等的,就是关键活动了,活动间的路径就是关键路径

为此,定义如下参数:

事件的最早发生时间 etv (earliest time of vertex): 即顶点 vk的最早发生时间.
事件的最晚发生时间 ltv (latest time of vertex): 即顶点 vk的最晚发生时间.
活动的最早开工时间 ete (earliest time of edge): 即弧ak的最早发生时间
活动的最晚开工时间 lte (latest time of edge): 即弧 ak 的最晚发生时间.

可以由 1 和 2 求出 3 和 4, 判断 ete[k] 和 lte[k] 是否相等来判断 ak 是否是关键活动

7.9.2 关键路径算法

将 AOE 网转化为邻接表, 与拓扑排序的邻接表结构不同在于弧链表增加了 weight 域,用来存储弧的权值

也就是顶点集合依旧有一个域存储入度

算法略

由好几个算法构成,首先修改了拓扑排序算法,拓扑排序后得到 etv, 然后算出 ltv ( ltv 的算法其实是将拓扑序列倒过来进行的), 然后通过比较 ete 和 lte 得出关键活动

妙哇!

分析整个关键路径算法,

拓扑排序时间复杂度为$O(n+e)$;

初始化 ltv 数组 $O(n)$

计算 ltv 的循环 $O(n+e)$

求 ete 和 lte 并对相同下标的它们做比较 $O(n+e)$

所以最终时间复杂度是 $O(n+e)$

7.10 总结回顾

图是最复杂的数据结构

多读几遍.就可以基本理解

图的数据结构(五种):

邻接矩阵
邻接表
边集数组
十字链表
邻接多重表

最重要的是邻接矩阵和邻接表,分别代表着边集是用数组还是链表的方式存储; 十字链表是邻接矩阵的一种升级; 邻接多重表是邻接表的升级; 边集数组更多对边的关注

具体使用什么?

稠密图,或读存数据较多,结构修改较少的图: 邻接矩阵

反之: 邻接表

遍历: 深度和广度两种

图的应用

最小生成树
- 普利姆 Prim 算法
  - 走一步看一步,逐步生成
- 克鲁斯卡尔 Kruskal 算法
  - 更有全局意识,从图中最短权值的边入手
最短路径
- 迪杰斯特拉 Dijkstra 算法
  - 强调单源顶点查找路径的方式
- 弗洛伊德 Floyd 算法
  - 利用矩阵变换, 用最清爽的代码实现了多顶点间最短路径求解的方案,原理理解有难度,算法很简洁
有向无环图
- 拓扑排序: 有效分析出一个有向图是否存在环
- 最短时间问题: 求关键路径算法

7.11 结尾语

通往牛逼的路上一路狂奔

8. 查找

8.1 开场白

搜索引擎工作原理:

我制作了一个网页
世界各地的蜘蛛会访问 (蜘蛛就是搜索引擎公司服务器上的软件)
蜘蛛抓取并复制网页,并且通过网页上的连接爬取更多的页面, 将所有信息纳入搜索引擎网站的索引数据库
当搜索时,会带着单词在索引数据库中检索所有包含关键词的网页, 根据浏览次数与关联性等算法确定网页级别,排列出顺序,呈现在网页

8.2 查找概论

需要被查的数据所在的集合,统称查找表

查找表 (Search Table) 是由同一类型的数据元素(或记录) 构成的集合.

关键字(Key) 是数据元素中某个数据项的值, 又称为键值, 用它可以标识一个数据元素. 若此关键字可以唯一地标识一个记录, 则称此关键字为主关键字 (Primary Key). 对于那些可以识别多个数据元素(或记录)的关键字,我们称为次关键字(Secondary Key)

查找 ( Searching ) 就是根据给定的某个值, 在查找表中确定一个其关键字等于给定值的数据源元素(或记录).

查找表分类:

静态查找表 Static Search Table: 只作查找操作的查找表
1. 主要操作有:
  1. 查询某个”特定的”数据元素是否在查找表中
  2. 检索某个”特定的”数据元素和各种属性
动态查找表 Dynamic Search Table: 在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素
1. 操作:
  1. 查找时插入元素
  2. 查找时删除元素

为了提高查找的效率, 我们需要专门为查找操作设置数据结构, 这种面向查找操作的数据结构称为查找结构

对于静态查找表来说,不妨用线性表结构,这样可以使用顺序查找算法, 如果对主关键字排序,则可以使用折半查找等技术高效查找

对于动态查找,会复杂些,可以考虑二叉排序树的查找技术

8.3 顺序表查找

顺序表查找 (Sequential Search) 又叫线性查找, 是最基本的查找技术, 它的查找过程是: 从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录; 如果知道最后一个(或第一个)记录,其关键字和给定值都不等时,则表中没有所查的记录,查找不成功

8.3.1 顺序表查找算法

int Sequential_Search(int *a, int n, int key)
{
  int i;
  for(i=1;i<=n;i++)
  {
    if(a[i] == key)
      return i;
  }
  return 0;
}

在数组 a(注意元素值从下标 1 开始)中查看有没有关键字 key

8.3.2 顺序表查找优化

设置一个哨兵,可以解决不需要每次让 i 与 n 作比较

int Sequential_Search2(int *a, int n, int key)
{
  int i;
  a[0]=key; // 设置 a[0] 为关键字值,哨兵
  i=n;
  while(a[i]!=key)
  {
    i--;
  }
  return i; // 返回 0 则说明查找失败
}

在总数据较多时,效率提高很大

时间复杂度为 $O(n)$

顺序查找技术在 n 很大时,查找效率极为低下

8.4 有序表查找

8.4.1 折半查找

折半查找 (Binary Search) 技术, 又称为二分查找.

它的前提是线性表中的记录必须是关键码有序(通常从小到大有序), 线性表必须采用顺序存储.

折半查找的基本思想是: 在有序表中, 取中间记录作为比较对象, 若给定值与中间记录的关键字相等,则查找成功; 若给定值小雨中间记录的关键字, 则在中间记录的左半区域继续查找; 若给定值大于中间记录的关键字,则在中间记录的右半区域查找. 不断重复上述过程,直到查找成功或失败为止

int Binary_search(int *a,int n,int key)
{
  int low,high,mid;
  low=1; //定义最低下标为记录首位
  high=n; //定义最高下标为记录末位
  while(low<=high)
  {
    mid=(low+high)/2; //折半
    if(key<a[mid])
      high=mid-1;
    else if (key>a[mid])
      low=mid+1;
    else
      return mid;
  }
  return 0;
}

折半算法的时间复杂度为 $O(logn)$

但是由于折半查找的前提是有序表顺序存储, 对于需要频繁执行插入或删除操作的数据集,维护有序的排序会有不小的开销,那就不建议使用

8.4.2 插值查找

为什么折半查找?不是折$1/4$ 或更多?

折半查找的等式为:
$$
mid=\frac {low+high} {2} = low+\frac 1 2(high-low)
$$
对于这个 1/2 进行改进
$$
mid=low+ \frac {key - a[low]} {a[high]-a[low]}(high-low)
$$
将上述折半查找的第八行更改为

mid=low+(high-low)*(key-a[low])/(a[high]-a[low]);

插值查找( Interpolation Search) 是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法,其核心在于插值的计算公式$\frac {key - a[low]} {a[high]-a[low]}$

从时间复杂度来看,也是$O(logn)$

8.4.3 斐波那契查找

首先有一个斐波那契数列数组 F

int Fibonacci_Search(int *a,int n,int key)
{
  int low,high,mid,i,k;
  low=1; // 定义最低下标为记录首位
  high=n; // 定义最高下标为记录末位
  k=0;
  while(n>F[k]-1) // 计算 n 位于斐波那契数列的位置
    k++;
  for(i=n;i<F[k]-1;i++) // 将不满的数值补全
    a[i]=a[n];
  while(low<=high)
  {
    mid=low+F[k-1]-1; // 计算当前分隔的下标
    if(key<a[mid]) // 若查找记录小于当前分隔记录
    {
      high=mid-1; // 最高下标调整到分隔下标 mid-1 处
      k=k-1; // 斐波那契数列下标减一位
    }
    else if (key>a[mid]) // 若查找记录大于当前分隔记录
    {
      low=mid+1; // 最低下标调整到分隔下标 mid+1 处
      k=k-2; // 斐波那契数列下标减两位
    }
    else
    {
      if(mid<=n)
        return mid; // 若相等说明 mid 即为查找到的位置
      else
        return n; // 若 mid>n 说明是补全数值,返回 n
    }
  }
  return 0;
}

今天和对象吵架,没怎么看进去

斐波那契算法的核心在于:

当 key=a[mid] 时,查找就成功;
当 key<a[mid] 时,新范围是第 low 个到第 mid-1 个,此时范围个数为 F[k-1]-1 个;
当 key>a[mid] 时,新范围是第 m+1个到第 high 个,此时范围个数为 F[k-2]-1 个

时间复杂度 $O(logn)$

区别

时间复杂度都是 $O(logn)$

三种有序表的查找本质上是分隔点的选择不同,各有优劣,实际开发时可根据数据的特点综合考虑.

8.5 线性索引查找

排序代价高昂,数据量海量的情况下怎么查找表? 索引

数据结构的最终目的是提高数据的处理速度

索引是为了加快查找速度而设计的一种数据结构

索引就是把一个关键字与它对应的记录相关联的过程

索引按照结构可分为

线性索引: 将索引项集合组织为线性结构,也称索引表
- 稠密索引
- 分块索引
- 倒排索引
树形索引
多级索引

8.5.1 稠密索引

稠密索引是指在线性索引中, 将数据集中的每个记录对应一个索引项.

稠密索引表的索引项一定是按照关键码有序的排列

有序就说明可以用到折半,插值,斐波那契等有序查找算法

8.5.2 分块索引

因为稠密索引项空间代价很大,为了减少索引项个数,对数据集进行分块,使分块有序,再对每一块建立一个索引项,从而减少索引项的个数

分块有序,是把数据集的记录分成了若干块,并且这些块需要满足:

块内无序, 为了减少排序开销
块间有序, 要求第二块所有记录的关键字都要大于第一块中所有记录的关键字

对于分块有序的数据集,每块对应一个索引项,这种索引方法叫分块索引. 索引项结构分三个数据项:

最大关键码, 存储每一块中的最大关键字
存储了块中的记录个数, 便于循环
用于指向块首元素的指针, 便于开始遍历

分块索引表查找步骤:

在分块索引表中查找要查关键字所在的块
根据首指针找到相应的块,并在块中顺序查找关键码

分块索引在兼顾了对细分块不需要有序的情况下,大大增加了整体查找的速度,所以普遍被用于数据库表查找等技术的应用当中

8.5.3 倒排索引

比如将几篇文章拆成英文单词(不重复)和文章编号(记录单词出现的文章号,可以是多个)

索引项的通用结构:

次关键码, 例如英文单词
记录号表, 例如文章编号

其中记录号表存储具有相同次关键字的所有记录的记录号 (可以是指向记录的指针或者是该记录的关键字). 这样的索引方法就是倒排索引 (inverted index).

称为倒排索引的原因: 由于不是由记录来确定属性值,而是由属性值来确定记录的位置

优点: 查找记录非常快

缺点: 记录号不定长

8.6 二叉排序树

普通顺序存储因为无序查找效率低

有序线性表,查找效率加快,但是插入和删除,需要耗费大量时间

假设需要对集合做查找,在我们创建此集合时就考虑用二叉树结构,而且是排好序的二叉树. 这样当对它中序遍历时,就可以得到一个有序的序列, 所以称它为二叉排序树

二叉排序树 (Binary Sort Tree), 又称为二叉查找树. 它或者是一棵空树, 或者是具有下列性质的二叉树.

若它的左子树不空, 则左子树上所有结点的值均小于它的根结构的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根节点的值;
它的左,右子树也分别为二叉排序树

这种结构利于插入和删除的实现.

8.6.1 二叉排序树查找操作

二叉树的结构

// 二叉树的二叉链表结点结构定义
typeof struct BiTNode // 结点结构
{
  int data;	// 结点数据
  struct BiTNode *lchild, *rchild;	// 左右孩子指针
}BiTNode, *BiTree

二叉排序树的查找 (递归):

// 递归查找二叉排序树中 T 是否存在 key
// 指针 f 指向 T 的双亲,其初始调用值为 NULL
// 若查找成功, 则指针 p 指向该数据元素结点,并返回 TRUE
// 否则指针 p 指向查找路径上访问的最后一个结点并返回 FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
  if(!T)
  {
    *p=f;
    return FALSE;
  }
  else if (key==T->data) // 查找成功
  {
    *p = T;
    return TRUE;
  }
  else if (key < T->data)
    return SearchBST(T->lchild,key,T,p); // 在左子树继续查找
  else
    return SearchBST(T->rchild,key,T,p); // 在右子树继续查找
}

8.6.2 二叉排序树插入操作

// 当二叉排序树 T 中不存在关键字等于 key 的数据元素时
// 插入 key 返回 TRUE,否则返回 FALSE
Status InsertBST(BiTree *T, int key)
{
  BiTree p,s; // 这个 p 最后的指向见查找代码
  if(!SearchBST(*T,key,NULL,&p))
  {
    s = (BiTree) malloc (sizeof(BiTNode));
    s->data = key;
    s->lchild = s->rchild = NULL;
    if(!p) // 是一个空树
      *T = s; // 插入 s 为新的根结点
    else if (key < p->data)
      p->lchild = s; // 插入 s 为左孩子
    else
      p->rchild = s; // 插入 s 为右孩子
    return TRUE;
  }
  else
    return FALSE;	// 树中已有关键字相同的结点
}

所以一段构建二叉排序树的代码:

int i;
int a[10] = {62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
  InsertBST(&T,a[i]);
}

8.6.3 二叉排序树删除操作

对于要删除的结点是叶子结点,或者只有左子树或只有右子树,比较好解决, 直接删除或将它的左子树或右子树整个移动到删除结点的位置即可 (独子继承父业)

但是当结点既有左子树又有右子树, 不好处理

我们将它的两个子树找出一个结点来代替它. (前驱或后继)

遍历树代码:

// 若二叉排序树 T 中存在关键字等于 key 的数据元素时,则删除该数据元素结点, 并返回 TRUE,否则返回 FALSE
Status DeleteBST(BiTree *T, int key)
{
  if(!*T) // 递归也没找到关键字等于 key 的数据元素
    return FALSE;
  else
  {
    if(key==(*T)->data) // 找到关键字等于 key 的数据元素
      return Delete(T);
    else if (key<(*T)->data)
      return DeleteBST(&(*T)->lchild,key);
    else
      return DeleteBST(&(*T)->rchild,key);
  }
}

Delete 的代码

// 从二叉排序树中删除结点 p,并重接它的左或右子树
Status Delete(BiTree *p)
{
  BiTree q,s;
  if((*p)->rchild==NULL) // 右子树空则只需重接左子树
  {
    q=*p; *p=(*p)->lchild; free(q);
  }
  else if ((*p)->lchild==NULL) // 只需重接它的左子树
  {
    q=*p; *p=(*p)->rchild; free(q);
  }
  else
  {
    q=*p; s=(*p)->lchild;
    while(s->rchild) // 转左,然后向右走到尽头(找前驱)
    {
      q=s; s=s->rchild;
    }
    (*p)->data=s->data; // s 指向被删结点的直接前驱
    if(q!=*p)
      q->rchild=s->lchild; // 重接 q 的右子树
    else
      q->lchild=s->lchild; //重接 q 的左子树
    free(s)
  }
  return TRUE;
}

q 其实就是 s 的双亲,如果 s 没有右结点就说明是前驱的原因是: 前驱是中序遍历的前一个,也就是左孩子->根->右孩子, 推断便知道, 找结点右子树的没有右孩子的将是最后一个结点

8.6.4 二叉排序树总结

二叉排序树是以链接的方式存储, 保持了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需修改链接指针即可

查找性能取决于二叉排序的性质. 但是形状是不固定的.

如果我们得到的是希望的二叉排序树, 深度与完全二叉树相同, 那么查找的时间复杂度为 $O(logn)$, 近似折半查找.

不平衡的最坏情况就是极端的斜树, 查找时间复杂度为$O(n)$, 等同于顺序查找

如何让二叉树平衡呢???

8.7 平衡二叉树( AVL 树 )

平衡二叉树(Self-Balancing Binary Search Tree), 是一种二叉排序树, 其中每个结点的左子树和右子树的高度差至多等于 1.

是一种高度平衡的二叉排序树.

我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡银子 BF(Balance Factor),那么平衡二叉树上所有结点的平衡银子只可能是-1,0和 1.

距离插入结点最近的, 且平衡因子的绝对值大于 1 的结点为根的子树, 我们称为最小不平衡子树.

插入某个点时,比较它附近的结点,计算平衡因子,最开始找到的也就是最近的结点.

8.7.1 平衡二叉树实现原理

基本思想: 每当插入一个结点, 先检查是否因插入而破坏了树的平衡性, 若是,找出最小不平衡子树. 调整, 使之称为新的平衡树.

调整:

当最小不平衡子树根结点的平衡因子 BF 大于 1, 右旋, 小于 -1 就左旋.
插入结点后, 最小不平衡子树的 BF 与它的子树的 BF 符号相反时, 就需要对结点(子树)先进行一次旋转以使得符号相同后, 再反向旋转一次才能够完成平衡操作.

算法略

8.8 多路查找树 ( B 树 )

前面讨论的数据结构,处理数据都是在内存中. 若要操作的数据集非常大, 要使用硬盘, 这样时间复杂度就会变化.

为了降低对外存设备的访问次数, 需要新的数据结构: 打破之前谈的树一个结点只能存储一个元素的限制

多路查找树( muitl-way search tree ), 其每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素. 由于是查找树, 所有元素之间存在某种特定的排序关系

四种特殊形式:

2-3 树
2-3-4 树
B 树
B+ 树

8.8.1 2-3 树

一种多路查找树: 其中的每一个结点都具有两个孩子或三个孩子(我们称它为 2 结点或 3 结点)

一个 2 结点包含一个元素和两个孩子(或没有孩子), 不能只有一个孩子; 一个 3 结点包含一大一小两个元素和三个孩子(或没有孩子). 如果某个 3 结点有孩子的话, 左子树包含小于较小元素的元素, 右子树包含大于较大元素的元素, 中间子树包含介于两元素之间的元素.

2-3 树的插入和删除很复杂, 了解还是用到了再了解吧

8.8.2 2-3-4 树

2-3-4 树就是 2-3 树的概念扩展, 包括了 4 结点的使用. 一个 4 结点包含小中大三个元素和四个孩子(或无).

插入和删除略

8.8.3 B 树

主角来了

B 树 (B-tree) 是一种平衡的多路查找树, 2-3 树和 2-3-4 树都是 B 树的特例. 结点最大的孩子数目称为 B 树的阶 (order). 因此, 2-3 树是 3 阶 B 树, 2-3-4 树是 4 阶 B 树.

一个 m 阶的 B 树具有如下属性:

如果根结点不是叶子结点, 则至少有两棵子树
每一个非根的分支结点都有 k-1 个元素和 k 个孩子, 其中$⌈m/2⌉ \le k \le m$. 每一个叶子结点 n 都有 k-1 个元素, 其中$⌈m/2⌉ \le k \le m$
所有的叶子结点都位于同一层次
所有分支结点都包含下列信息数据 $(n, A_0,K_1,A_1,K_2,A_2,…,K_n,A_n)$, 其中
- $K_i(i=1,2,…,n)$ 为关键字, 且 $K_i < K_{i+1}$
- $A_{i-1}$所指子树中所有结点的关键字均小于$K_i(i=1,2,…,n)$
- $A_n$ 所指子树中所有结点的关键字均大于$K_i(i=1,2,…,n)$

在 B 树上查找的过程是一个顺时针查找结点和在结点中查找关键字的交叉过程.

B 树的插入和删除, 方式与 2-3 和 2-3-4 树相类似, 只不过阶数可能很大.

B 树为什么能减少内外存交换数据次数?

外存如硬盘,是将所有信息分割成大小相等的页面, 每次硬盘读写都是一个或多个完整的页面, 一个硬盘一页的长度可能是 211 到 214 个字节

在一个 B 树应用中, 数据量很大,无法放入内存时, 对 B 树进行调整, 使得 B 树的阶数(或结点的元素)与硬盘存储的页面大小相匹配. 比如一棵 B 树的阶为 1001(即 1 个结点包含 1000 个关键字), 高度为 2, 那么它可以存储超过 10 亿个关键字, 我们只要让根结点持久地保留在内存中,name 查找某一个关键字只需要最多两次硬盘的读取.

8.8.4 B+ 树

对于树结构来说, 我们都可以通过中序遍历来顺序查找树中的元素, 这一切都是在内存中进行.

可是 B 树结构,我们往返于每个结点也就意味着, 我们必须得在硬盘的页面之间进行多次访问

B+树是应文件系统所需而出的一种 B 树的变形树, 严格意义上, 它已经不是之前定义的树了. 在 B 树中,每一个元素在该树中只出现一次, 有可能在叶子结点上, 也有可能在分支结点上; 而在 B+ 树中, 出现在分支结点中的元素会被当做它们在该分支结点位置的中序后继者(叶子结点)中再次列出. 另外, 每一个叶子结点都会保存一个指向后一叶子结点的指针.

根结点中的关键字在叶子结点再次列出

并且所有叶子结点都链接在一起

一棵 m 阶的 B+ 树和 m 阶的 B 树的差异在于:

有 n 棵子树的结点中包含 n 个关键字
所有的叶子结点包含全部关键字的信息, 及指向含这些关键字记录的指针, 叶子结点本身依关键字自小而大顺序链接
所有分支结点可以看成是索引, 结点中仅含有其子树中的最大(或最小)关键字

好处

随机查找,就从根结点触发,与 B 树的查找方式相同, 只不过在分支结点找到了待查找的关键字,它也只是用来索引的, 还是要到达包含此关键字的终端结点

如果需要从最小关键字进行从小到大的顺序查找,我们就可以从最左侧的叶子结点触发,不经过分支结点,直接遍历所有关键字

B+ 树的结构特别适合带有范围的查找

B+ 树的插入删除都与 B 树相似, 只不过插入和删除的元素都是在叶子结点上进行而已

8.9 散列表查找(哈希表)概述

顺序表查找都需要比较. 能否直接通过关键字得到要查找的记录内存存储位置呢?

8.9.1 散列表查找定义

我们只需要通过某个函数 f,使得存储位置=f(关键字), name 就可以通过查找关键字不需要比较就可以获得需要的记录的存储位置. 这就是散列技术.

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f,使得每个关键字 key 对应一个存储位置 f(key).

我们把这种对应关系 f 称为散列函数, 又称为哈希(Hash)函数. 采用散列技术将记录存储在一块连续的存储空间中, 这块存储空间称为散列表或哈希表(Hash table).

8.9.2 散列表查找步骤

两步

存储时,通过散列函数计算记录的散列地址, 并按此散列地址存储该记录.
查找记录时, 我们通过同样的散列函数计算记录的散列地址, 按此散列地址访问该记录.

散列技术既是一种存储方法,也是一种查找方法

散列表的记录之间不同于前几种结构,没有逻辑关系, 散列技术只与关键字有关联. 因此,散列主要是面向查找的存储结构

优点

散列技术最适合的求解问题是查找与给定值相等的记录. 简化了比较,效率大大提高

缺点

同样的关键字对应很多记录的情况,不适合散列技术

散列表也不适合范围查找

关键

如何设计一个简单,均匀,存储利用率高的散列函数?

两个关键字计算出来的地址一样时怎么解决冲突(collision)?

8.10 散列函数的构造方法

好的散列函数:

计算简单
散列地址分布均匀

8.10.1 直接定址法

直接取关键字的某个线性函数为散列地址,即
$$
f(key)=a \times key+b
$$

优点

简单,均匀,不会有冲突

缺点

需要事先知道关键字的分布情况,适合查找表较小且连续的情况. 现实中不常用

8.10.2 数字分析法

通过分析,抽取关键字中的某些数字.

比如手机号的后四位

适合事先知道关键字的分布且关键字的若干位分布均匀的情况

8.10.3 平方取中法

关键字平方取中间的几位数作为散列地址.

适合不知道关键字分布, 位数不是很大的情况

8.10.4 折叠法

将关键字从左到右分割成位数相等的几部分, 将这几部分叠加求和, 并按照散列表长,取后几位作为散列地址

适合实现不知道关键字的分布,适合关键字位数较多的情况

8.10.5 除留余数法

是最常用的构造散列函数方法

对于散列表长为 m 的散列函数公式为:
$$
f(key)=key\mod p (p\le m)
$$
mod 是取模(取余数)

很显然, 本方法的关键就在于选择合适的 p

根据前辈的经验, 若散列表表长为 m,通常 p 为小于等于表长(最好接近 m)的最小质数或不包含小于 20 质因子的合数.

8.10.6 随机数法

当关键字的长度不等时,采用这个方法构造散列函数比较合适

总结

关键字是字符串, 转化为数字来对待, 比如 ASCII 或者 Unicode

现实中,视不同情况采用不同的散列函数, 参考因素:

计算散列地址所需的时间
关键字的长度
散列表的大小
关键字的分布情况
记录查找的频率

需要综合这些因素选择散列函数

8.11 处理散列冲突的方法

如果发现使用散列函数前两个关键字$key_1 \ne key_2$, 但是却有$f(key_1)=f(key_2)$, 有冲突了,怎么解决呢?

8.11.1 开放定址法

开放定址法就是一旦发生了冲突, 就去寻找下一个空的散列地址, 只要散列表足够大, 空的散列地址总能找到, 并将记录存入

公式:
$$
f_i(key)=(f(key)+d_i)\mod m \ (d_i=1,2,3,…,m-1)
$$
也就是如果有冲突, 给散列的结果加上 1 然后再取模, 如果冲突就加上 2, 以此类推

我们把这种解决冲突的开放定址法称为线性探测法

但是这个会导致本来不是同义词却需要争夺一个地址的情况, 我们称这种现象为堆积

一种改善方法为, 不仅往后寻找地址,还往前寻找, 并且加入平方运算, 为了不让关键字都聚集在某一块区域, 这种方法称为二次探测法
$$
f_i(key)=(f(key)+d_i) \mod m \ (d_i=1^2,-1^2,2^2,-2^2,…,q^2,-q^2,q\le{m/2})
$$
另一种改善方法, 在冲突时, 对于位移量$d_i$采用随机函数计算得到, 我们称之为随机探测法

注意: 这里的随机数是伪随机数, 在查找时,用同样的随机种子, 每次得到的随机数列相同,最终能得到相同的散列地址

8.11.2 再散列函数法

事先准备多个散列函数
$$
f_i(key)=RH_i(key) (i=1,2,…,k)
$$
$RH_i$就是不同的散列函数, 每当散列冲突时,就换一个散列函数计算

8.11.3 链地址法

将所有关键字为同义词的记录存储在一个单链表中, 我们称这种表为同义词子表, 在散列表中只存储所有同义词子表的头指针, 所以如果有冲突, 也只是增加结点而已.

优点

提供了绝不会出现找不到地址的保障

缺点

带来了查找时需要遍历单链表的性能损耗

8.11.4 公共溢出区法

为所有冲突的关键字建立一个公共的溢出区来存放.

查找时, 给定值通过散列函数计算出地址后, 与就基本表的位置比对,相等则查找成功; 不相等, 去溢出表顺序查找.

适用于冲突数据较少的情况

8.12 散列表查找实现

8.12.1 散列表查找算法实现

首先定义一个散列表结构

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typeof struct
{
  int *elem; // 数据元素存储基址, 动态分配数组
  int count; // 当前数据元素个数
}HashTable;
int m=0; // 散列表表长, 全局变量

散列表初始化:

// 初始化散列表
Status InitHashTable(HashTable *H)
{
  int i;
  m=HASHSIZE;
  H->count=m;
  H->elem=(int *) malloc (m*sizeof(int));
  for(i=0;i<m;i++)
    H->elem[i]=NULLKEY;
  return OK;
}

散列函数(可随时更换算法):

// 散列函数
int Hash(int key)
{
  return key % m; // 除留余数法
}

进行插入

void InsertHash(HashTable *H, int key)
{
  int addr = Hash(key); // 求散列地址
  while (H->elem[addr] != NULLKEY) // 出现冲突
    addr = (addr+1) % m; //开放定址法线性探测
  H->elem[addr] = key; // 有空位插入
}

散列表的查找

// 散列表查找关键字
Status SearchHash(HashTable H,int key, int *addr)
{
  *addr = Hash(key); // 求散列地址
  while(H.elem[*addr] != key) // 不为空,冲突
  {
    *addr = (*addr + 1) %m; // 开放定址法线性探测
    if(H.elem[*addr] == NULLKEY || *addr == Hash(key)) // 循环回到了原点
    {
      return UNSUCCESS; //关键字不存在
    }
  }
  return SUCCESS;
}

查找与插入类似,多做一个不存在关键字的判断

8.12.2 散列表查找性能分析

如果没有冲突, 是目前各种查找中效率最高的, 时间复杂度为 $O(1)$, 这只是理想状态.

散列表的平均查找长度取决于?

散列函数是否均匀
处理冲突的方法

线性探测处理冲突可能产生堆积, 显然没有二次探测法好, 链地址法不会产生人核对及, 因而拥有更佳的平均查找性能
散列表的装填因子

装填因子是记录个数/散列表长度. 标志着散列表装满的程度

我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内, 让时间复杂度趋向 $O(1)$

虽然浪费了一定空间,但是查找效率大大提升, 总体值得

8.13 总结

查找表有静态查找表,动态查找表

对于顺序查找表, 注意设置哨兵的技巧

有序查找, 折半查找使得性能比顺序查找从$O(n)$变成了$O(logn)$, 其他的有序查找: 插值查找,斐波那契查找. 三者各有优缺点.

线性索引查找: 稠密索引, 分块索引, 倒排索引.

二叉排序树是动态查找最重要的数据结构. 为了达到最优, 最好是平衡的二叉树. 因此就需要了解平衡二叉树(AVL 树)的数据结构, 要了解如何处理平衡性的问题. 要掌握

B 树是针对内存外存之间的存取而专门设计的

B+树的设计思想

散列表是非常高效的查找数据结构, 注意散列函数的选择和处理冲突的方法

9. 排序

9.2 排序的基本概念与分类

假设含有 n 个记录的序列为${r_1,r_2,….,r_n}$, 其相应的关键字分别为${k_1,k_2,…,k_n}$, 需确定 1,2,…,n 的一种序列 $p_1,p_2,…,p_n$, 使其对应的关键字满足$k_{p1} \le k_{p2} \le … \le k_{pn}$ (非递减或非递增) 关系, 即使得序列称为一个按关键字有序的序列 ${r_{p1},r_{p2},…,r_{pn}}$, 这样的操作就成为排序.

排序的依据是关键字的大小关系, 针对不同的关键字, 可以得到不同序列

关键字可以是主关键字,也可以是次关键字, 甚至是若干数据项组合.

多个关键字的排序最终都可以转化为单个关键字的排序

9.2.1 排序的稳定性

假设$k_i=k_j(1\le i \le n, 1 \le j \le n, i \ne j)$, 且在排序前的序列中 ri 领先于 rj (即 i 小于 j). 如果排序后 ri 仍领先于 rj, 则称所用的排序方法是稳定的; 反之, 若可能使得排序后的序列中 rj 领先 ri,则称所用的排序方法是不稳定的.

意思就是关键字相等的情况下, 本来的排序顺序不变即稳定

9.2.2 内排序与外排序

根据是否全部放置内存中分类

内排序是在排序整个过程中, 待排序的所有记录全部被放置在内存中.
外排序是由于排序的记录个数太多, 不能同时放置在内存, 整个排序过程需要在内外存之间多次交换数据才能进行.

对于内排序, 性能受 3 个方面:

时间性能

高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数
辅助空间

是指除了存放待排序所占用的存储空间之外,执行算法需要的其他空间
算法的复杂性

指算法本身的复杂度, 不是指算法的时间复杂度.

按照排序过程中的主要操作, 把内排序分为:
- 插入排序
- 交换排序
- 选择排序
- 归并排序

9.2.3 排序用到的结构与函数

排序用的顺序表结构

#define MAXSIZE 10 // 用于要排序数组个数最大值
typedef struct
{
  int r[MAXSIZE+1]; // 用于存储要排序数组,r[0]用作哨兵
  int length; // 记录顺序表的长度
}SqList;

排序最常用的数组两元素的交换

// 交换 L 数组中 r 的下标为 i 和 j 的值
void swap(SqList *L, int i, int j)
{
  int temp = L->r[i];
  L->r[i] = r[j];
  L->r[j] = temp;
}

9.3 冒泡排序

9.3.1 最简单排序实现

冒泡排序(Bubble Sort) 是一种交换排序, 它的基本思想是: 两两比较相邻记录的关键字, 如果反序则交换, 知道没有反序的记录为止.

// 对顺序表 L 作交换排序(冒泡排序初级版)
void BubbleSort0(SqList *L)
{
  int i,j;
  for(i=1;i<L->length;i++)
  {
    for(j=i+1;j<=L->length;j++)
    {
      if(L->r[i]>L->r[j])
      {
        swap(L,i,j); // 交换 L->r[i] 与 L->r[j] 的值
      }
    }
  }
}

结果就是第一位置在一次循环后一定变成最小值

第二位位置在第二次循环后变成了第二小值

缺点: 效率低

9.3.2 冒泡排序算法

// 对顺序表 L 作冒泡排序
void BubbleSort(SqList *L)
{
  int i,j;
  for(i=1;i<L->length;i++){
    for(j=L->length-1;j>=i;j--) // 注意 j 是从后往前
    {
      if(L->r[j] > L->r[j+1])
      {
        swap(L,j,j+1); // 交换 L->r[j] 与 L->r[j+1] 的值
      }
    }
  }
}

注意,这里的 L->length 是下标,下标从 1 开始.

与之前的区别: 从队尾向前两两比较

正宗的冒泡的进步是:

除了第一次循环能找到最小值,还能将次小值提到很前的位置

9.3.3 冒泡排序优化

在序列已经有序的情况下,不要再继续后面的循环判断了

增加一个标记变量 flag 来改进

// 对顺序表 L 作改进冒泡排序
void BubbleSort2(SqList *L)
{
  int i,j;
  Status flag=TRUE; // 标记
  for(i=1;i<L->length && flag;i++){ // 若 flag 为 true 则退出循环
    flag=FALSE; // 初始为 FALSE
    for(j=L->length-1;j>=i;j--) // 注意 j 是从后往前
    {
      if(L->r[j]>L->r[j+1])
      {
        swap(L,j,j+1); // 交换 L->r[j] 与 L->r[j+1] 的值
        flag=TRUE; // 如果有数据交换,则 flag 为 true
      }
    }
  }
}

在 i 的循环增加了 flag 是否为 true 的判断

避免了已经有序的情况下的无意义循环判断

9.3.4 冒泡排序复杂度分析

时间复杂度为 $O(n^2)$

9.4 简单选择排序

冒泡的思想就是不停交换, 类似搞股票频繁操作.

选择排序的初步思想就是, 能不能仅仅在关键时刻出手, 也就是找到合适的关键字再做交换呢?

9.4.1 简单选择排序算法

简单选择排序法(Simple Selection Sort) 就是通过 n-i 次关键字间的比较, 从 n-i+1个记录中选出关键字最小的记录, 并和第 i 个记录交换之

// 对顺序表 L 作简单选择排序
void SelectSort(SqList *L)
{
  int i,j,min;
  for(i=1;i<L->length;i++)
  {
    min = i;	// 将当前下标定义为最小值下标
    for(j=i+1;j<=L->length;j++) // 循环之后的数据
    {
      if(L->r[min] > L->r[j]) // 如果有小于当前最小值的关键字
        min = j; // 将此关键字的下标赋值给 min
    }
    if(i!=min) // 若 min 不等于 i,则说明找到最小值,交换
      swap(L,i,min);
  }
}

其实吧, 就是减少交换次数,比较次数还是和冒泡差不多

9.4.2 简单选择排序复杂度分析

简单选择排序最大的特点就是交换移动数据次数相当少, 也就节约了相对应的时间.

比较次数: 无论最好最差的情况,其比较次数都是一样多, 第 i 趟排序需要进行 n-i 次关键字的比较, 此时需要比较$1+2+3+…+(n-1)=\frac{n(n-1)}{2}$ 次.
交换次数: 最好的时候,交换 0 次,最差,交换 n-1 次

总的时间复杂度依然为$O(n^2)$

尽管和冒泡一样,但是性能还是略优于冒泡

9.5 直接插入排序

9.5.1 直接插入排序算法

直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中, 从而得到一个新的, 记录数增 1 的有序表.

// 对顺序表 L 作直接插入排序
void InsertSort(SqList *L)
{
  int i,j;
  for(i=2;i<=L->length;i++)
  {
    if(L->r[i] < L->r[i-1]) // 需将 L->r[i] 插入有序子表
    {
      L->r[0]=L->r[i]; // 设置哨兵
      for(j=i-1;L->r[j]>L->r[0];j--)
        L->r[j+1]=L->r[j]; // 记录后移
      L->r[j+1]=L->r[0]; // 插入到正确位置
    }
  }
}

i 从 2开始的原因就是除了 r[0] 作为哨兵, r[1]已经放好位置

这个算法写的很难懂

java 的实现:

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

这个比刚才那个好懂很多

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

// 插入排序
void InsertSort(int arr[], int len){
    // 检查数据合法性
    if(arr == NULL || len <= 0){
        return;
    }
    for(int i = 1; i < len; i++){
        int tmp = arr[i];
        int j;
        for(j = i-1; j >= 0; j--){ // 在已经排序的元素序列中从后向前扫描
            //如果比tmp大把值往后移动一位
            if(arr[j] > tmp){
               arr[j+1] = arr[j];
            }
            else{
               break;
            }
        }
        arr[j+1] = tmp;
    }
}

这个也比较好理解

① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤

9.5.2 直接插入排序复杂度分析

最好的情况, 也就是要排序的表本身是有序, 这样只有比较,没有移动的记录,时间复杂度为$O(n)$

最坏的情况, 即排序表是逆序的, 需要比较$2+3+4+…+n= \frac{(n+2)(n-1)}{2}$ 次, 而记录的移动次数为$\frac{(n+4)(n-1)}{2}$

如果排序记录是随机的, 那么根据概率相同的原则, 平均比较和移动次数约为$\frac{n^2}{4}$ 次.

因此, 直接插入排序的时间复杂度为$O(n^2)$

同样的复杂度, 直接插入排序比冒泡和简单选择排序性能要好一些

算法优化改进

方法一

如果每次都是顺序查找,效率低.

思路: 每次往前查找合适的插入位置时采用二分查找(折半查找)

// 插入排序改进：二分插入排序
void BinaryInsertSort(int arr[], int len)   
{   
    int key, left, right, middle;   
    for (int i=1; i<len; i++)   
    {   
        key = a[i];   
        left = 0;   
        right = i-1;   
        while (left<=right)   
        {   
            middle = (left+right)/2;   
            if (a[middle]>key)   
                right = middle-1;   
            else   
                left = middle+1;   
        }   

        for(int j=i-1; j>=left; j--) // 找到了之后插入位置右边全部右移
        {   
            a[j+1] = a[j];   
        }   

        a[left] = key; // 插入      
    }   
}

注意要想通折半查找的跳出循环方法

方法二

分析:

插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。
插入排序在每次往前插入时只能将数据移动一位，效率比较低。

改进思路：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

这其实就是希尔排序

9.6 希尔排序

优秀排序算法的首要条件就是速度.

冒泡排序,简单选择排序,直接插入排序的时间复杂度都是$O(n^2)$

9.6.1 希尔排序原理

希尔排序(Shell Sort), 是第一批突破$O(n^2)$的算法之一

将原本有大量记录数的记录分组, 在子序列内分别进行直接插入排序, 当整个序列基本有序时, 再对全体记录做一次直接插入排序.

所谓基本有序, 就是小的关键字基本在前面, 大的基本在后面, 不大不小的基本在中间.

但是需要采取跳跃分隔的策略: 将相距某个”增量”的记录组成一个子序列, 这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序.

9.6.2 希尔排序算法

// 对顺序表 L 作希尔排序
void ShellSort(SqList *L)
{
  int i,j;
  int increment=L->length;
  do
  {
    increment=increment/3+1; // 增量序列
    for(i=increment+1;i<=L->length;i++)
    {
      if(L->r[i]<L->r[i-increment])
      {
        // 需将 L->r[i] 插入有序增量子表
        L->r[0]=L->r[i]; // 暂存在 L->r[0]
        for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment)
          L->r[j+increment]=L->r[j]; // 记录后移, 查找插入位置
        L->r[j+increment]=L->r[0]; // 插入
      }
    }
  }
  while(increment>1);
}

书上对于这个算法的解释不足, 感觉只是讲解代码.

下面这个算法比较直观

注意的点:

三层循环的条件

同时按照 gap 分组排序的理解

public class ShellSort {

  public static void main(String[] args) {
    int[] arr = {1, 4, 2, 7, 9, 8, 3, 6};
    sort(arr);
    System.out.println(Arrays.toString(arr));
  }

  public static void sort(int[] arr) {
    for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        while (j - gap >= 0 && arr[j - gap] > arr[j]) {
          swap(arr, j - gap, j);
          j -= gap;
        }
      }
    }
  }

  public static void swap(int[] arr, int a, int b) {
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
  }
}

9.6.3 希尔排序复杂度分析

究竟选什么样的增量才是最好, 目前还没有找到.

一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为 $O(n^{3/2})$

但是注意, 增量序列的最后一个增量值必须等于 1 才行.

由于记录是跳跃式的移动,希尔排序并不是一种稳定的排序方法.

因为相同的元素有可能在各自的插入排序中移动

不稳定性就是指相同元素在排序过程中被移动

9.7 堆排序

是对简单选择排序的一种改进

使用了”堆”这一种数据结构

堆是具有下列性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆; 或者每个结点的值都小于或等于其左右孩子结点的值, 称为小顶堆.

如果按照层序遍历的方式从 1 开始编号,

则结点之间满足: $k_i \ge k_{2i}$ 和 $k_i \ge k_{2i+1}$, 其中$1 \le i \le \lfloor {n/2} \rfloor$

上述是大顶堆,小顶堆同理

将大顶堆和小顶堆用层序遍历存入数组, 则一定满足上述大小的表达.

9.7.1 堆排序算法

堆排序( Heap Sort ) 就是利用堆(假设利用大顶堆) 进行排序的方法. 它的基本思想是, 将待排序的序列构造成一个大顶堆. 此时, 整个序列的最大值就是堆顶的根结点. 将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值), 然后将剩余的 n-1 个序列重新构造成一个堆, 这样就会得到 n 个元素中的次小值. 如此反复执行, 便能得到一个有序序列了.

基本思想就是在每次找到最大值的时候, 将剩下的元素也按照堆这种数据结构排列, 达成了每次修改剩下元素位置的目的.

两个问题:

如何由一个无序序列构建成一个堆?
如果在输出堆顶元素后, 调整剩余元素成为一个新的堆?

代码呈上:

// 对顺序表 L 进行堆排序
void HeapSort(SqList *L)
{
  int i;
  for(i=L->length/2; i>0; i--) // 把 L 中的 r 构建成一个大顶堆
    HeapAdjust(L,i,L->length);
  
  for(i=L->length;i>1;i--)
  {
    swap(L,1,i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
    HeapAdjust(L,1,i-1); // 将 L->r[1..i-1] 重新调整为大顶堆
  }
}

两个循环:

构建大顶堆
逐步将每个最大值的根结点与末尾元素交换,并且再调整其成为大顶堆

堆调整函数:

// 已知 L->r[s..m] 中记录的关键字除 L->r[s] 之外均满足堆的定义
// 本函数调整 L->r[s] 的关键字,使 L->r[s..m] 成为一个大顶堆
void HeapAdjust(SqList *L,int s,int m)
{
  int temp,j;
  temp=L->r[s];
  for(j=2*s;j<=m;j*=2){ // 沿关键字较大的孩子结点向下筛选
    if(j<m && L->r[j]<L->r[j+1])
      ++j;	// j为关键字中较大的记录的下标
    if(temp>=L->r[j])
      break; // rc应插入在位置 s
    L->r[s]=L->r[j];
    s=j;
  }
  L->r[s]=temp;	// 插入
}

再简单总结下堆排序的基本思路：

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

这段还是不能看书上, 直接扔代码我是真的很反感.

自己网上找了一个视频看懂了: https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=7059417364240703657

下面放上 java 代码

注意点:

完全二叉树的特点

heapify 函数的递归调用

build_heap 函数

heap_sort 函数的循环中, i 的变化

public class HeapSort {

  public static void main(String[] args) {
    int[] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int n = 6;
    heap_sort(arr, 9);
    System.out.println(Arrays.toString(arr));
  }

  private static void heap_sort(int[] arr, int n) {
    build_heap(arr, n);
    for (int i = n - 1; i >= 0; i--) {
      swap(arr, 0, i);
      heapify(arr, 0, i);
    }
  }

  private static void build_heap(int[] arr, int n) {
    int last_node = n - 1;
    int last_parent = (last_node - 1) / 2;
    for (int i = last_parent; i >= 0; i--) {
      heapify(arr, i, n);
    }
  }

  private static void heapify(int[] arr, int i, int n) {
    if (i >= n) {
      return;
    }
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int max = i;
    if (left < n && arr[left] > arr[max]) {
      max = left;
    }
    if (right < n && arr[right] > arr[max]) {
      max = right;
    }
    if (max != i) {
      swap(arr, max, i);
      heapify(arr, max, n);
    }
  }

  private static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

9.7.2 堆排序复杂度分析

堆排序主要消耗在初始构建堆和重建堆时的反复筛选上.

构建堆来说, 每次和孩子进行比较, 其实最多两次比较和互换, 因此构建堆的时间复杂度为$O(n)$

正式排序时, 第 i 次取堆顶记录重建堆需要用$O(logi)$的时间 (由完全二叉树某个结点到根结点的距离得出), 并且需要取 n-1 次堆顶记录, 因此, 重建堆的时间复杂度为$O(nlogn)$

总体的时间复杂度为$O(nlogn)$

空间复杂度上,只有一个用来交换的暂存单元.

由于记录的比较和交换是跳跃式进行,因此堆排序也是一种不稳定的排序方法

9.8 归并排序

因为堆排序用到了完全二叉树, 利用了完全二叉树的深度的特性,所以效率比较高.

有没有更直接的办法利用完全二叉树来排序呢?

将无序的数组,两两合并排序后再合并,最终获得了一个有序的数组

9.8.1 归并排序算法

归并排序(Merging Sort)的原理: 假设初始序列含有 n 个记录, 则可以看成是 n 个有序的子序列, 每个子序列的长度为 1, 然后两两归并, 得到$\lceil n/2 \rceil$ 个长度为 2 或 1 的有序子序列; 再两两归并,…, 如此重复, 直至得到一个长度为 n 的有序序列为止, 这种排序方法成为 2 路归并排序.

从这里开始书上又开始甩代码了. 懒得看. 还是去找视频看: https://www.bilibili.com/video/BV1Ax411U7Xx/?spm_id_from=333.788.recommend_more_video.0

public class MergeSort {

  public static void main(String[] args) {
    int[] arr = {6, 8, 10, 9, 4, 5, 2, 7};
    mergeSort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
  }

  private static void merge(int[] arr, int L, int M, int R) {
    int left_size = M - L;
    int right_size = R - M + 1;
    int[] left = new int[left_size];
    int[] right = new int[right_size];
    for (int i = L; i < M; i++) {
      left[i - L] = arr[i];
    }
    for (int i = M; i <= R; i++) {
      right[i - M] = arr[i];
    }

    int i = 0;
    int j = 0;
    int k = L;
    while (i < left_size && j < right_size) {
      if (left[i] <= right[j]) {
        arr[k] = left[i];
        i++;
        k++;
      } else {
        arr[k] = right[j];
        j++;
        k++;
      }
    }
    while (i < left_size) {
      arr[k] = left[i];
      i++;
      k++;
    }
    while (j < right_size) {
      arr[k] = right[j];
      j++;
      k++;
    }
  }

  private static void mergeSort(int[] arr, int L, int R) {
    if (L == R) {
      return;
    }else{
      int M = (L + R) / 2;
      mergeSort(arr, L, M);
      mergeSort(arr, M + 1, R);
      merge(arr, L, M+1, R);
    }
  }
}

注意:

边界!!!

分治法

9.8.2 归并排序复杂度分析

因为还是类似完全二叉树, 所以总的时间复杂度为$O(nlogn)$

因为需要同样数量的存储空间, 空间复杂度我$O(n+logn)$

因为两个相等的话,不会进行跳跃, 所以归并排序是一种稳定的排序算法

也就是说, 归并排序是一种比较占用内存,但却效率高且稳定的算法.

9.8.3 非递归实现归并排序

算法过程略, 但是非递归实现避免了递归时深度为$log_2n$的栈空间, 空间只是用到申请归并临时用的 TR 数组, 空间复杂度为$O(n)$

使用归并排序时,尽量考虑用非递归方法.

归并排序的优化: https://www.cnblogs.com/noKing/p/7940531.html

9.9 快速排序

希尔排序是插入排序的升级

堆排序是简单选择排序的升级

快速排序是冒泡排序的升级

9.9.1 快速排序算法

快速排序 (Quick Sort) 的基本思想是: 通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录的关键字均比另一部分记录的关键字小, 则可分别对这两部分记录进行排序, 以达到整个序列有序的目的.

public class QuickSort {

  public static void main(String[] args) {
    int[] arr = {3, 5, 7, 3, 8, 9, 6, 1, 0};
    QuickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }

  private static void QuickSort(int arr[], int L, int R) {
    if(L<R){
      int left = L, right = R;
      int pivot = arr[left];
      while (left < right) {
        while (left < right && arr[right] > pivot) {
          right--;
        }
        if (left < right) {
          arr[left] = arr[right];
          left++;
        }
        while (left < right && arr[left] < pivot) {
          left++;
        }
        if (left < right) {
          arr[right] = arr[left];
          right--;
        }
      }
      arr[left] = pivot;
      QuickSort(arr, L, left - 1);
      QuickSort(arr, left + 1, R);
    }
  }
}

快速排序函数,其实就是将选取的 pivot 值不断交换, 它也在交换中不断更改自己的位置, 直到完全满足这个要求为止.

9.9.2 快速排序复杂度分析

快速排序的时间性能取决于快速排序递归的深度, 可以用递归树来描述递归算法的执行情况.

时间复杂度推断过程很复杂, 略. 通过数学归纳法可证明, 数量级为$O(nlogn)$

空间复杂度, 主要是递归造成的栈空间的使用. 与递归树的深度有关. 空间复杂度为$O(logn)$

由于关键字比较和交换是跳跃进行,因此, 快速排序不稳定

9.9.3 快速排序优化

优化选取枢轴
优化不必要的交换
优化小数组时的排序方案
优化递归操作
了不起的排序算法

到现在为止, 快速排序算法经过多次优化后, 整体性能上, 是排序算法王者.

9.10 总结回顾

排序的稳定性
内排序与外排序
分类
- 插入排序
  - 直接插入排序
  - 希尔排序
- 交换排序
  - 冒泡排序
  - 快速排序
- 选择排序
  - 简单选择排序
  - 堆排序
- 归并排序
  - 归并排序
没有十全十美的排序算法. 即使是快速排序, 也存在排序不稳定,需要大量辅助空间,对少量数据排序无优势等不足
分类
- 简单算法
  - 冒泡
  - 简单选择
  - 直接插入
- 改进算法
  - 希尔
  - 堆
  - 归并
  - 快速
从时间复杂度来看:
- 从最好情况看, 后 3 种改进算法 > 希尔排序 >> 前三种
- 从最坏情况看, 堆排序,归并排序>快速排序>其他简单排序
  - 堆排序, 归并排序: 优等生, 发挥稳定
  - 快速排序: 天才, 发挥看心情
从空间复杂度来看:
- 归并排序强调马要跑得快,得先吃饱
- 快速排序也有空间需求
- 堆排序等都是少量索取,大量付出, 对空间要求是$O(1)$
- 如果环境非常在乎内存使用量, 选择归并和快速排序就不合适.
从稳定性来看:
- 归并排序独占鳌头
从待排序记录的个数来看:
- 待排序的个数 n 越小, 采用简单排序方法越合适.
- n 越大,采用改进排序的方法越合适
综合来说: 经过优化的快速排序是性能最好的排序算法.

9.11 结尾语

数据结构和算法对于程序员的职业人生来说,就是应该学习的知识和能够赚钱的知识的交集, 用心去掌握它, 编程之路将会是坦途.

You got a dream, you gotta protect it. People can’t do something themselves, they wanna tell you you can’t do it. If you want something, go get it. Period.

本文链接： http://yiiiqing.github.io/2021/06/21/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%AF%BB%E4%B9%A6%E7%AC%94%E8%AE%B0/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

YiqingWeb Developer

一位打工人