一篇学完：王道考研408数据结构（全）

笔记从:lengyueling.cn

PDF版本附在lengyueling.cn对应文章结尾，欢迎下载访问交流

绪论

学习数据结构

• 如何用程序代码信息化现实世界的问题

• 如何用计算机有效地处理这些信息，从而创造价值

数据结构的基本概念

什么是数据：

数据是信息的载体，是描述客观事物属性的数字、字符和所有能够输入计算机并被计算机程序识别和处理的符号的集合。数据是计算机程序处理的原材料。

现代计算机处理数据：

• 现代计算机-经常处理非数值问题

• 非数值型问题：

  • 我们关心每个人的具体信息

  • 我们也关心个人关系

数据元素：

数据元素是数据的基本单位，通常作为一个整体来考虑和处理。

数据项：

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据对象：

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

数据结构：

• 数据结构是一种或多种特定关系的数据元素的集合。

• 本课程重点关注数据元素之间的关系和这些数据元素的操作，而不关注具体的数据项内容。

数据结构的三要素

三要素：

• 逻辑结构

  • 集合结构，每个元素都属于同一个集合，没有其他关系

  • 线性结构，一对一，顺序关系

  • 树状结构，一对多

  • 图形结构，多对多

• 基本运算(增删改查)是根据某种逻辑结构和实际需要定义的。

• 如何用计算机实现物理结构(存储结构)

  • 顺序存储：在物理位置和相邻存储单元中存储逻辑相邻元素，元素之间的关系反映在存储单元的相邻关系中

  • 链式存储：在物理位置上存储逻辑上的相邻元素不能相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

  • 索引存储：在存储元素信息的同时，还有简历附加的索引表。索引表中的每个项目都成为索引项。索引项的一般形式是（关键字、地址）

  • 散列存储：根据元素的关键字直接计算元素的存储地址，也称为哈希存储

总结：

• 如果使用顺序存储，每个数据元素必须在物理上连续；如果使用非顺序存储，每个数据元素可以在物理上离散

• 数据结构会影响存储空间分配的便利性

• 数据存储结构会影响数据运算的速度

• 运算的定义是针对逻辑结构的，指出运算的功能

• 计算的实现是针对存储结构，指出计算的具体步骤

数据类型：

在这个集合中，数据类型是一组操作的总称

• 原子类型：其值不可分割的数据类型（bool、int等）

• 结构类型：其值可分解为数据类型的几个重量（struct等）

抽象数据类型（ADT）：

它定义了抽象数据组织及其相关操作ADT定义一个数据结构

算法的基本概念

算法是什么：

• 程序=数据结构 算法

• 算法（Algorithm）它是对特定问题解决步骤的描述，是指令的有限序列，每个指令表示一个或多个操作

算法的特点：

• 算法必须具有以下特征，否则不能称为算法：

• 贫穷：一种算法必须在执行贫穷步骤后结束，每一步都可以在贫穷的时间内完成。

• 确定性：算法中的每个指令都必须具有确切的含义，对于相同的输入，只能得到相同的输出。

• 可行性：算法中描述的操作可以通过有限次的基本操作执行来实现。

• 输入：算法中有零或多个输入，这些输入取决于特定对象的集合。

• 输出:一个算法有一个或多个输出，与输入有一定关系。

好算法的特点：

• 正确性：算法应能正确解决问题。

• 可读性：算法应具有良好的可读性，以帮助人们理解。

• 强度：在输入非法数据时，算法可以在不产生莫名其妙的输出结果的情况下做出适当的反应或处理。

• 高效率：

• 时间少：时间复杂度低

• 存储容量要求低存成本高，空间复杂性低

算法的时间复杂性

定义： 预估算法时间费用T(n)与问题规模n的关系（T表示“time”）

规则：

• 加法规则：T(n) = T1(n) T2(n) = O(f(n)) O(g(n)) = O(max(f(n), g(n))) （多项相加，只保留最高阶的项，且系数变为1）

• 乘法规则：T(n) = T1(n)×T2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))(保留多项相乘 ）

• 算法好坏：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)(公式:常指向幂)

• 数量级只考虑循环中最深的嵌套部分

• 最坏时间复杂度：算法在最坏情况下的时间复杂度

• 平均时间复杂性：当出现所有输入示例等概率时，算法的预期运行时间

• 最佳时间复杂度：算法的最佳时间复杂度

• 一般只考虑最坏和平均复杂度

算法的空间复杂性

定义：空间费(内存费，S(n)）与问题规模n的关系

算法原地工作： 算法所需的内存空间为常量

规则：

• 只关注与存储空间大小和问题规模相关的变量

• 加法规则、乘法规则和算法的质量与时间复杂度相同

• 大多数情况下，递归调用：空间复杂性=递归调用的深度

线性表

线性表的定义和基本操作

定义：

• 线性表(Linear List)数据类型相同n（n≥0)数据元素的有限序列，其中n为表长，当n = 0时线性表是空表

• 如果使用L命名线性表，一般表示为L = (a1, a2, … , ai, ai 1, … , an)

• a1是表头元素

• an是表尾元素

• 除了第一个元素，每个元素只有一个直接前驱

• 除了最后一个元素，每个元素都有，只有一个直接的继承

基本操作：

• InitList(&L)：初始化表。构建空线性表L，内存空间的分配。

• DestroyList(&L)：销毁操作。销毁线性表，释放线性表L占用的内存空间。

• ListInsert(&L,i,e)：插入操作。将指定元素插入表L的第一个位置e。

• ListDelete(&L,i,&e)：删除操作。删除表L中第一个位置的元素，并用e返回删除元素的值。

• LocateElem(L,e)：按值搜索操作。在表L中找到具有给定关键字值的元素。

li>

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

• Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

• PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

• Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

• 什么时候要传入参数的引用“&”： 对参数的修改结果需要“带回来”，是引用类型而不是值类型

顺序表的定义

定义：

用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

如何知道一个数据元素大小：

C语言sizeof(ElemType)

顺序表的实现-静态分配：

如果“数组”存满了怎么办：

可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的），同时如果提前初始化太多的空间而不用，又会造成资源的浪费，因此动态分配应运而生。

动态申请和释放内存空间：

• C：malloc、free函数

  • L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);

  • malloc函数返回一个指针， 空间需要强制转型为你定义的数据元素类型指针

  • malloc函数的参数，指明要分配多大的连续内存空间

• C++： new、delete关键字

顺序表的实现-动态分配：

顺序表的实现：

• 随机访问，即可以在O(1)时间内找到第i个元素。

• 存储密度高，每个结点只存储数据元素

• 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

• 插入、删除操作不方便，需要移动大量元素

顺序表的插入、删除

顺序表的基本操作-插入：

增加i的合法性判断：

顺序表的基本操作-删除：

插入和删除的时间复杂度：

• 最好时间复杂度= O(1)

• 最坏时间复杂度= O(n)

• 平均时间复杂度= O(n)

顺序表的查找

顺序表的按位查找：

• 正是如此，在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针

• 时间复杂度= O(1)

• 随机存取：由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，

顺序表的按值查找：

• 结构类型的数据元素也能用 == 比较吗：不能！（C++可以用 == 的重载来实现）

• 更好的办法：定义一个函数

• 依次对比各个分量来判断两个结构体是否相等

• 最好时间复杂度= O(1)

• 最坏时间复杂度= O(n)

• 平均时间复杂度= O(n)

单链表的定义

顺序表：

• 每个结点中只存放数据元素

• 优点：可随机存取，存储密度高

• 缺点：要求大片连续空间，改变容量不方便

单链表：

• 每个结点除了存放数据元素外，还要存储指向下一个结点的指针

• 优点：不要求大片连续空间，改变容量方便

• 缺点：不可随机存取，要耗费一定空间存放指针

定义一个单链表：

• typedef关键字：数据类型重命名

  • typedef <数据类型> <别名>

  • typedef struct LNode LNode;

  • 之后可以用LNode代替struct LNode

不带头结点的单链表：

带头结点的单链表：

区别：

• 不带头结点，写代码更麻烦

• 对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑

• 对空表和非空表的处理需要用不同的代码逻辑

• 我们一般使用的都是带头结点的单链表

单链表的插入、删除

按位序插入（带头结点）：

ListInsert(&L,i,e)：

• 插入操作，在表L中的第i个位置上插入指定元素e

• 找到第i-1个结点，将新结点插入其后

• 若带有头结点，插入更加方便，头结点可以看作“第0个”结点，直接做上面的操作即可

• 若i插在表中则与插在表头一样进行操作，可以插入成功

• 若i插在表尾则s->next为NULL（在表的定义时规定的），可以插入成功

• 若i插在表外（i>Lengh）则p指针指向NULL（While循环一直指向p->next），不能插入成功

• 最好时间复杂度= O(1)

• 最坏时间复杂度= O(n)

• 平均时间复杂度= O(n)

按位序插入（不带头结点）：

ListInsert(&L,i,e)：

• 插入操作，在表L中的第i个位置上插入指定元素e

• 不存在“第0个”结点，因此i=1时需要特殊处理

• 找到第i-1个结点，将新结点插入其后

• 若i!=1则处理方法和带头结点一模一样

• 值得注意的是int j =1而非带头结点的0（带头结点的头结点为第0个结点）

• 结论：不带头结点写代码更不方便，推荐用带头结点

指定结点的后插操作：

• 这一段代码是按位序插入中插入的那一部分代码

• 也可以直接调用InsertNextNode来执行

• 封装代码，以此提高代码复用性，让代码更容易维护

指定结点的前插操作：

• 因为仅知道指定结点的信息和后继结点的指向，因此无法直接获取到前驱结点

• 方法1：获取头结点然后再一步步找到指定结点的前驱

• 方法2：将新结点先连上指定结点p的后继，接着指定结点p连上新结点s，将p中元素复制到s中，将p中元素覆盖为要插入的元素e

（方法1）

（方法2）

按位序删除（带头结点）：

ListDelete(&L,i,&e)：

• 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。

• 找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点

指定结点的删除：

• 删除结点p，需要修改其前驱结点的next指针，和指定结点的前插操作一样

• 方法1：传入头指针，循环寻找p的前驱结点

• 方法2：偷天换日，类似于结点前插的实现

（方法2）

如果要删除的结点p是最后一个结点：

• 只能从表头开始依次寻找p的前驱，时间复杂度O(n)

• 这就体现了单链表的局限性：无法逆向检索，有时候不太方便

单链表的查找

按位查找：

• GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

• 实际上单链表的插入中找到i-1部分就是按位查找i-1个结点，如下图

• 因此查找第i个结点如下图

• 如果i=0则直接不满足j<i则指针p直接返回头结点L

• 如果i超界则当时p指向了NULL，指针p返回NULL

• 平均时间复杂度：O(n)

按值查找：

• LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

• 能找到的情况：p指向了e值对应的元素，返回该元素

• 不能找到的情况：p指向了NULL，指针p返回NULL

• 平均时间复杂度：O(n)

求表的长度：

平均时间复杂度：O(n)

单链表的建立

尾插法：

• 每次插入元素都插入到单链表的表尾

• 方法1：套用之前学过的位序插入，每次都要从头开始往后面遍历，时间复杂度为O(n^2)

• 方法2：增加一个尾指针r，每次插入都让r指向新的表尾结点，时间复杂度为O(n)

头插法：

• 每次插入元素都插入到单链表的表头

• 头插法和之前学过的单链表后插操作是一样的，可以直接套用

• L->next=NULL;可以防止野指针

总结：

• 头插法、尾插法：核心就是初始化操作、指定结点的后插操作

• 注意设置一个指向表尾结点的指针

• 头插法的重要应用：链表的逆置

双链表

为什么要要使用双链表：

• 单链表：无法逆向检索，有时候不太方便

• 双链表：可进可退，但是存储密度更低一丢丢

双链表的初始化（带头结点）：

双链表的插入：

• 小心如果p结点为最后一个结点产生的空指针问题，因此循环链表应运而生（详见后面的循环链表插入删除）

• 注意指针的修改顺序

双链表的删除：

双链表的遍历：

循环链表

循环单链表与单链表的区别：

单链表：

• 表尾结点的next指针指向NULL

• 从一个结点出发只能找到后续的各个结点

循环单链表：

• 表尾结点的next指针指向头结点

• 从一个结点出发可以找到其他任何一个结点

循环单链表初始化：

• 从头结点找到尾部，时间复杂度为O(n)

• 如果需要频繁的访问表头、表尾，可以让L指向表尾元素（插入、删除时可能需要修改L）

• 从尾部找到头部，时间复杂度为O(1)

循环双链表与双链表的区别：

双链表：

• 表头结点的prior指向NULL

• 表尾结点的next指向NULL

循环双链表：

• 表头结点的prior指向表尾结点

• 表尾结点的next指向头结点

循环双链表的初始化：

循环链表的插入：

• 对于双链表来说如果p结点为最后一个结点，因为next结点为null，p->next->prior=s会产生的空指针问题

• 循环链表规避因为最后结点的next结点为头结点因此不会发生问题

循环链表的删除：

与循环链表的插入相同。

注意点：

写代码时候注意以下几点，以此规避错误：

• 如何判空

• 如何判断结点p是否是表尾/表头元素（后向/前向遍历的实现核心）

• 如何在表头、表中、表尾插入/删除一个结点

静态链表

什么是静态链表：

• 分配一整片连续的内存空间，各个结点集中安置

• 每个结点由两部分组成：data（数据元素）和next（游标）

• 0号结点充当“头结点”，不具体存放数据

• 游标为-1表示已经到达表尾

• 游标充当“指针”，表示下个结点的存放位置，下面举一个例子：

• 每个数据元素4B，每个游标4B（每个结点共8B），设起始地址为addr，e1的存放地址为addr + 8*2（游标值）

定义静态链表：

方法1：

方法2：

基本操作：

初始化：

• 把a[0]的next设为-1

• 把其他结点的next设为一个特殊值用来表示结点空闲，如-2

插入位序为i的结点：

• 找到一个空的结点，存入数据元素（设为一个特殊值用来表示结点空闲，如-2）

• 从头结点出发找到位序为i-1的结点

• 修改新结点的next

• 修改i-1号结点的next

删除某个结点：

• 从头结点出发找到前驱结点

• 修改前驱结点的游标

• 被删除结点next设为-2

总结：

• 静态链表：用数组的方式实现的链表

• 优点：增、删操作不需要大量移动元素

• 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

• 适用场景：①不支持指针的低级语言；②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

顺序表和链表的比较

逻辑结构：

都属于线性表，都是线性结构

存储结构：

顺序表：

• 优点：支持随机存取、存储密度高

• 缺点：大片连续空间分配不方便，改变容量不方便

链表：

• 优点：离散的小空间分配方便，改变容量方便

• 缺点：不可随机存取，存储密度低

基本操作：

顺序表：

• 创建

  • 需要预分配大片连续空间。

  • 若分配空间过小，则之后不方便拓展容量；

  • 若分配空间过大，则浪费内存资源

  • 静态分配：静态数组实现，容量不可改变

  • 动态分配：动态数组（malloc、free）实现，容量可以改变但需要移动大量元素，时间代价高

• 销毁

  • 修改Length = 0

  • 静态分配：静态数组，系统自动回收空间

  • 动态分配：动态数组（malloc、free），需要手动free

• 增删

  • 插入/删除元素要将后续元素都后移/前移

  • 时间复杂度O(n)，时间开销主要来自移动元素

  • 若数据元素很大，则移动的时间代价很高

• 查

  • 按位查找：O(1)

  • 按值查找：O(n)若表内元素有序，可在O(log2n)时间内找到

链表：

• 创建

  • 只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

• 销毁

  • 依次删除各个结点（free）

• 增删

  • 插入/删除元素只需修改指针即可

  • 时间复杂度O(n)，时间开销主要来自查找目标元素

  • 查找元素的时间代价更低

• 查

  • 按位查找：O(n)

  • 按值查找：O(n)

用哪个：

• 表长难以预估、经常要增加/删除元素——链表

• 表长可预估、查询（搜索）操作较多——顺序表

开放式问题的解题思路：

问题： 请描述顺序表和链表的bla bla bla…实现线性表时，用顺序表还是链表好？

答案：

• 顺序表和链表的逻辑结构都是线性结构，都属于线性表。

• 但是二者的存储结构不同，顺序表采用顺序存储…(特点，带来的优点缺点)；链表采用链式存储…（特点、导致的优缺点）。

• 由于采用不同的存储方式实现，因此基本操作的实现效率也不同。

• 当初始化时…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个数据元素时…

栈和队列

栈的基本概念

栈的定义：

• 栈（Stack）是只允许在一端进行插入或删除操作的线性表

• 逻辑结构：与普通线性表相同

• 数据的运算：插入、删除操作有区别

• 栈顶：允许插入和删除的一端，对应元素被称为栈顶元素

• 栈底：不允许插入和删除的一端，对应元素被称为栈底元素

• 特点：后进先出Last In First Out（LIFO）

栈的基本操作：

• InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。

• DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。

• Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

• Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

• GetTop(S, &x)：读栈顶元素。若栈S非空，则用x返回栈顶元素

• StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

出栈顺序数量：

• n个不同元素进栈，出栈元素不同排列的个数为

• 上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明

栈的顺序存储结构

顺序栈的定义和初始化：

进栈操作：

出栈操作：

读取栈顶元素：

注意：也可以让栈顶指针top先指向0，每次进栈S.top++，出栈--S.top

共享栈：

• 使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生

• 两个栈共享同一片空间，0、1号栈朝着同一方向进栈

• 栈满的条件：top0 + 1 == top1

栈的链式存储结构

栈的链式存储实质：

• 进栈：头插法建立单链表，也就是对头结点的后插操作

• 出栈：单链表的删除操作，对头结点的“后删”操作

• 推荐使用不带头结点的链栈

• 创销增删查的操作参考链表

链栈的定义：

队列的基本概念

队列的定义：

• 栈（Stack）是只允许在一端进行插入或删除操作的操作受限的线性表

• 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

• 队头：允许删除的一端，对应的元素被称为队头元素

• 队尾：允许插入的一端，对应的元素被称为队尾元素

• 队列的特点：先进先出First In First Out（FIFO）

队列的基本操作：

• InitQueue(&Q)：初始化队列，构造一个空队列Q。

• DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

• EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

• DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

• GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

• QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

队列的顺序存储结构

队列的定义和初始化：

入队操作：

• 通过取余操作，只要队列不满，就可以一直利用之前已经出队了的空间，逻辑上实现了循环队列的操作

• 于是，队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front

• 代价：牺牲了一个存储单元，因为如果rear和front相同，与判空的条件相同了

出队操作：

实际上获取队头元素的值就是出队操作去掉队头指针后移的代码

判断队列已满/已空：

方案1：

• 使用前面讲的牺牲一个存储空间的方式来解决

• 初始化时rear=front=0

• 队列元素个数：(rear+MaxSize-front)%MaxSize

• 队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front

• 队空条件：Q.rear==Q.front

方案2：

• 不牺牲一个存储空间，在结构体中多建立一个变量size

• 初始化时rear=front=0；size = 0;

• 队列元素个数= size

• 插入成功size++；删除成功size--;

• 此时队满条件：size==MaxSize

• 队空条件：size == 0;

方案3：

• 不牺牲一个存储空间，在结构体中多建立一个变量tag

• 初始化时rear=front=0；tag = 0;

• 因为只有删除操作，才可能导致队空，只有插入操作，才可能导致队满因此

• 每次删除操作成功时，都令tag=0；

• 每次插入操作成功时，都令tag=1；

• 队满条件：front==rear && tag == 1

• 队空条件：front==rear && tag == 0

• 队列元素个数：(rear+MaxSize-front)%MaxSize

队列的链式存储结构

初始化（带头结点）：

初始化（不带头结点）：

入队（带头结点）：

入队（不带头结点）：

出队（带头结点）：

出队（不带头结点）：

队列满的条件：

• 顺序存储：预分配的空间耗尽时队满

• 链式存储：一般不会队满，除非内存不足

• 因此一般不用考虑队满

双端队列

定义：

• 双端队列：只允许从两端插入、两端删除的线性表

• 输入受限的双端队列：只允许从一端插入、两端删除的线性表

• 输出受限的双端队列：只允许从两端插入、一端删除的线性表

• 不管是怎么样的双端队列实际都是栈和队列的变种

考点：

• 判断输出序列合法性

• 在栈中合法的输出序列，在双端队列中必定合法

栈在括号匹配中的应用

括号匹配问题：

• 若有括号无法被匹配则出现编译错误

• 遇到左括号就入栈

• 遇到右括号，就“消耗”一个左括号

代码实现：

栈在表达式求值中的应用

算数表达式：

• 由三个部分组成：操作数、运算符、界限符

• 我们平时写的算术表达式都是中缀表达式

• 如何可以不用界限符也能无歧义地表达运算顺序

• Reverse Polish notation（逆波兰表达式=后缀表达式）

• Polish notation（波兰表达式=前缀表达式）

中缀、后缀、前缀表达式：

中缀转后缀的方法（手算）：

• 确定中缀表达式中各个运算符的运算顺序

• 选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数

• 如果还有运算符没被处理，就继续第二步

• 注意：运算顺序不唯一，因此对应的后缀表达式也不唯一

• “左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算是一致的

中缀表达式转后缀表达式（机算，用栈实现）：

• 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

• 从左到右处理各个元素，直到末尾。可能遇到三种情况：

  • 遇到操作数。直接加入后缀表达式。

  • 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。

  • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。

• 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算（手算）：

• 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数

• 注意：两个操作数的左右顺序

• 特点：最后出现的操作数先被运算，LIFO（后进先出），可以使用栈来完成这个步骤

• “左优先”原则：只要左边的运算符能先计算，就优先算左边的

后缀表达式的计算（机算，用栈实现）：

• 从左往右扫描下一个元素，直到处理完所有元素

• 若扫描到操作数则压入栈，并回到第一步；否则执行第三步

• 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步

• 注意：先出栈的是“右操作数”

• 若表达式合法，则最后栈中只会留下一个元素，就是最终结果

• 后缀表达式适用于基于栈的编程语言（stack-orientedprogramming language），如：Forth、PostScript

中缀表达式转前缀表达式（手算）：

• 确定中缀表达式中各个运算符的运算顺序

• 选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数

• 如果还有运算符没被处理，就继续第二步

• “右优先”原则：只要右边的运算符能先计算，就优先算右边的

中缀表达式的计算（机算，用栈实现）：

• 中缀表达式的计算=中缀转后缀+后缀表达式求值，两个算法的结合

• 用栈实现中缀表达式的计算：

  • 初始化两个栈，操作数栈和运算符栈

  • 若扫描到操作数，压入操作数栈

  • 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

栈在递归中的应用

函数调用的特点：

• 最后被调用的函数最先执行结束（LIFO）

• 函数调用时，需要用一个栈（函数调用栈）存储，里面包含以下信息：

  • 调用返回地址

  • 实参

  • 局部变量

• 适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

栈在递归中的应用：

• 计算正整数的阶乘n!

• 求斐波那契数列

• ......

栈在递归中过程：

• 递归调用时，函数调用栈可称为“递归工作栈”

• 每进入一层递归，就将递归调用所需信息压入栈顶

• 每退出一层递归，就从栈顶弹出相应信息

• 缺点：

  • 太多层递归可能会导致栈溢出

  • 可能包含很多重复计算

队列的应用

• 树的层次遍历

• 图的广度优先遍历

• 操作系统中的应用

  • 多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。可以用队列实现

  • CPU资源的分配

  • 打印数据缓冲区

特殊矩阵的压缩储存

一维数组的存储结构：

• 起始地址：LOC

• 各数组元素大小相同，且物理上连续存放。

• 数组元素a[i]的存放地址= LOC + i * sizeof(ElemType)

二维数组的存储结构：

• 分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存

• M行N列的二维数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址= LOC + (i*N + j) * sizeof(ElemType)

• M行N列的二维数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)

• 二维数组也有随机存储的特性

普通矩阵的存储：

• 可用二维数组存储

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

• 某些特殊矩阵可以压缩存储空间（比如对称矩阵）

对称矩阵的压缩存储：

• 若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵

• 普通存储：n*n二维数组

• 压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中

• 数组大小应为多少：(1+n)*n/2

• 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用：可以实现一个“映射”函数矩阵下标->一维数组下标

• 按行优先的原则，ai,j是第几个元素：

三角矩阵的压缩存储：

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

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

• 压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c

• 下三角矩阵，按行优先的原则，ai,j是第几个元素：

• 上三角矩阵，按行优先的原则，ai,j是第几个元素：

三对角矩阵的压缩存储：

• 三对角矩阵，又称带状矩阵：当|i - j|>1时，有ai,j = 0 （1≤ i, j ≤n）

• 压缩存储策略：按行优先（或列优先）原则，只存储带状部分

• 按行优先的原则，ai,j是第几个元素：

稀疏矩阵的压缩存储：

• 稀疏矩阵：非零元素远远少于矩阵元素的个数

• 压缩存储策略1：顺序存储——三元组<i（行），j（列），v（值）>，失去了数组随机存储的特性

• 压缩存储策略2：链式存储，十字链表法

串

串的定义和基本操作

定义：

• 串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S = ‘a1a2······an' （n ≥0）

• 其中，S是串名，单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n = 0时的串称为空串（用∅表示）。

• 有的地方用双引号（如Java、C），有的地方用单引号（如Python）

• 例如：S=”HelloWorld!”T=‘iPhone 11 Pro Max?’

• 子串：串中任意个连续的字符组成的子序列。Eg：’iPhone’，’Pro M’是串T的子串

• 主串：包含子串的串。Eg：T是子串’iPhone’的主串

• 字符在主串中的位置：字符在串中的序号。Eg：’1’在T中的位置是8(第一次出现)

• 子串在主串中的位置：子串的第一个字符在主串中的位置。Eg：’11 Pro’在T中的位置为8

• 每个空格字符占1B，不是空串

• 串的位序从1开始而不是从0开始

• 串是一种特殊的线性表，数据元素之间呈线性关系

• 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

• 串的基本操作，如增删改查等通常以子串为操作对象，因为人类的语言通常要多个字符组成的序列才有现实意义

串的基本操作：

• 假设有串T=“”，S=”iPhone 11 Pro Max?”，W=“Pro”

• StrAssign(&T,chars)：赋值操作。把串T赋值为chars。

• StrCopy(&T,S)：复制操作。由串S复制得到串T。

• StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。

• StrLength(S)：求串长。返回串S的元素个数。

• ClearString(&S)：清空操作。将S清为空串。

• DestroyString(&S)：销毁串。将串S销毁（回收存储空间）。

• Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串

• SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。

• Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。

• StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

  • 从第一个字符开始往后依次对比，先出现更大字符的串就更大

  • 长串的前缀与短串相同时，长串更大

  • 只有两个串完全相同时，才相等

字符集编码：

• 任何数据存到计算机中一定是二进制数。

• 需要确定一个字符和二进制数的对应规则这就是“编码”

• “字符集”：英文字符，ASCII字符集，中英文，Unicode字符集

• 基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16

• 注：采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符占1B即可

串的储存结构

顺序存储：

• 方案一：一个数组来储存字符，一个int变量length储存实际长度

• 方案二：数组的ch[0]来充当length，优点：字符的位序和数组下标相同

• 方案三：没有Length变量，以字符’\0’表示结尾（对应ASCII码的0），缺点：获取字符串长度需要遍历，时间复杂度高

• 方案四：数组的ch[0]废弃不用，从看开始储存字符，外加一个int变量length储存实际长度

链式存储：

推荐使用第二种方式，存储密度较高，ch数组未必一定是4个字符，也可以比4多

基本操作的实现（使用第四种方案）：

朴素模式匹配算法

字符串模式匹配：

• 在主串中找到与模式串相同的子串，并返回其所在位置。

• 子串：主串的一部分，一定存在

• 模式串：不一定能在主串中找到

• 要掌握朴素模式匹配算法、KMP算法两种方法

朴素模式匹配算法（两种实现方法）：

• 将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

• 主串长度为n，模式串长度为 m，最多对比 n-m+1 个子串

• 上节讲的index定位操作就是朴素模式匹配算法中其中一种实现方法

• 也可以使用两个指针i和j来进行匹配。若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置，即i = i - j + 2; j = 1;

• 若 j > T.length，则当前子串匹配成功，返回当前子串第一个字符的位置即i - T.length

• 设主串长度为 n，模式串长度为 m，则最坏时间复杂度 = O(n*m)，最好时间复杂度 = O(n)

KMP算法的概念

• 由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为 KMP算法

• 是对朴素模式匹配算法的优化

• 优化的原理就是减少了i指针的回溯，通过已经计算好的next指针，提高算法的整体运行效率

• next数组记录了当第几个元素匹配失败时候，j的取值例如：

  • 对于模式串 T = ‘abaabc’

  • 当第6个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=3

  • 当第5个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2

  • 当第4个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2

  • 当第3个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1

  • 当第2个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1

  • 当第1个元素匹配失败时，匹配下一个相邻子串，令 j=0, i++, j++

• next数组只和短短的模式串有关，和长长的主串无关（重要）

• 之所以只和模式串有关，是因为如果在哪里匹配失败，同时说明在这之前的部分主串和模式串是相同的

• KMP算法，最坏时间复杂度 O(m+n)，其中，求 next 数组时间复杂度 O(m)，模式匹配过程最坏时间复杂度 O(n)

• KMP算法精髓：利用好已经匹配过的模式串的信息

• 步骤：

  • 根据模式串T，求出 next 数组

• 利用next数组进行匹配（主串指针不回溯）

KMP算法之求next数组

next数组的作用：

当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配

next数组的求法：

• 任何模式串都一样，第1个字符不匹配时，只能匹配下一个子串，因此next[1]都无脑写 0（if(j==0) {i++; j++;}）

• 任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此next[2]都无脑写 1

• 每一个模式串不一样，对于第3个字符及之后的字符串，在不匹配的位置前边，划一根美丽的分界线模式串一步一步往后退，直到分界线之前“能对上”，此时 j 指向哪儿，next数组值就是多少

KMP算法之求nextval数组

定义：

nextval数组是对next数组的优化，用nextval替代next数组，减少了无意义的对比

nextval数组的求法：

• 先根据上面的方法算出next数组

• 先令nextval[1]=0

• 再根据下面代码算出后面的nextval数组

• for(int j = 2; j <= T.length; j++)
  {
      //让第next值个元素的值和当前元素比较
      if(T.ch[next[j]] == T.ch[j])
      {
          //若相等则让第next值个元素的nextval值复制给当前元素的nextval值
          nextval[j] = nextval[next[j]];
      }
      else
      {
          //若不等则让当前元素的next值赋值给当前元素的nextval值
          nextval[j] = next[j];
      }
  }

树

树的定义和基本术语

空树：

结点数为0的树

非空树的特性：

• 有且仅有一个根结点

• 没有后继的结点称为“叶子结点”（或终端结点）

• 有后继的结点称为“分支结点”（或非终端结点）

• 除了根结点外，任何一个结点都有且仅有一个前驱

• 每个结点可以有0个或多个后继

树的定义：

• 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。

• 在任意一棵非空树中应满足：

  • 有且仅有一个特定的称为根的结点。

  • 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

结点之间的关系描述：

• 什么是祖先结点？比自己深度低的结点

• 什么是子孙结点？比自己深度高的结点

• 什么是双亲结点（父结点）？自己的根结点

• 什么是孩子结点？自己作为根结点的儿子

• 什么是兄弟结点？与自己拥有相同父结点结点

• 什么是堂兄弟结点？与自己同一层的结点

• 什么是两个结点之间的路径？能从上往下前往的两个结点被称为有路径

• 什么是路径长度？经过几条边

结点、树的属性描述：

• 结点的层次（深度）：从上往下数，默认从1开始

• 结点的高度：从下往上数

• 树的高度（深度）：总共多少层

• 结点的度：有几个孩子（分支）

• 树的度：各结点的度的最大值

有序数和无序树：

• 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

• 无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

• 是否是什么，具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系

树和森林：

• 森林是m（m≥0）棵互不相交的树的集合

• 考点：树和森林的相互转换

树的性质

• 树的总结点数=树的总度数+1

• 度数为m的树和m叉树的区别

• 度为m的树第i 层至多有m^i-1 个结点（i≥1）

• m叉树第i 层至多有m^i-1 个结点（i≥1）

• 高度为h的m叉树至多有((m^h)-1)/m-1个结点

• 高度为h的m叉树至少有h 个结点

• 高度为h、度为m的树至少有h+m-1 个结点

• 具有n个结点的m叉树的最小高度为logm(n(m - 1) + 1)

• 高度最小的情况：所有结点都有m个孩子

二叉树的定义和基本术语

定义：

• 二叉树是n（n≥0）个结点的有限集合

  • 或者为空二叉树，即n = 0。

  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

• 特点：

  • 每个结点至多只有两棵子树

  • 左右子树不能颠倒（二叉树是有序树）

二叉树的五种状态：

• 空二叉树

• 只有左子树

• 只有右子树

• 只有根结点

• 左右子树都有

几个特殊的二叉树：

• 满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树

  • 特点：

    • 只有最后一层有叶子结点

    • 不存在度为1 的结点

    • 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）

• 完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树

  • 特点：

    • 只有最后两层可能有叶子结点

    • 最多只有一个度为1的结点

    • 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）

    • i≤ n/2 为分支结点， i> n/2 为叶子结点

    • 如果某结点只有一个孩子，那么一定是左孩子

• 是满二叉树一定是完全二叉树，是完全二叉树不一定是满二叉树

• 二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

  • 左子树上所有结点的关键字均小于根结点的关键字

  • 右子树上所有结点的关键字均大于根结点的关键字

  • 左子树和右子树又各是一棵二叉排序树