数据结构

第一章 (三要素、算法、复杂度)

基本概念和术语

什么是数据？

数据元素和数据项

个人理解：数据元素和数据项都是相对而言的，例如对于一个银行系统（它的数据元素就是每个客户，而每个客户又有自己独特的信息，这些信息即为数据项），当然图片的例子，信息(数据项)有时候也可以再进行分隔（eg:地址信息还可以细分为省、市、区），这个称为组合项

数据结构、数据对象

数据类型、抽象数据类型

数据类型

抽象数据类型

一个数学模型+定义该模型上的一系列操作，包含了数据对象、逻辑结构、操作，但是不涉及存储实现，只描述怎么做

ADT只是一个抽象的概念，这个抽象概念中你可以随便定义数据对象，随便定义函数，具体实现有c中的结构体，java，c++中的类，但是它属于一种更加抽象的概念，属于类、结构体…的上层概念

数据结构三要素

逻辑结构

物理结构(存储结构)

逻辑结构不能决定物理结构，任何一种逻辑结构都可以使用任意物理结构进行存储

数据的存储结构会影响存储空间分配的方便程度和对数据运算的速度

存储结构实现了数据结构的定义，同时也确定了逻辑结构及其关系

顺序存储

物理顺序和逻辑顺序是相同的

链式存储

使用指针来表示元素之间的逻辑关系，指针和数据元素一起存储(例如:图中数据元素所占的单元格不是单一表示数据元素了，而是表示一个节点[节点包括数据域和指针域{数据域存放数据元素，指针域存放指针}])

索引存储

索引表和数据元素是单独存储的

散列存储(hash存储)

哈希表和数据元素也是单独存储的

操作与运算

算法基本概念

算法的定义

算法的五个特征

算法的有穷性

这里的算法指的是按照特定程序生成某段输出的过程(一个抽象的概念，例如我切水果，切的这个过程就是算法)，而程序所指的是产生输出的指令集

算法的确定性

这里例子中的取随机数也是满足确定性的，因为输出的范围是确定的

可行性

输入

输出

只要造成了数据的改变，都算作算法的输出，即算法的输出至少为1

“好”算法的性质

正确性

可读性

健壮性

高效率和低存储

算法效率度量(时间复杂度)

如何计算

1. 是否可以忽略表达式的常数部分

当n足够大时，即可使用同阶O来表示T(n)的最高次数，从而忽略常数部分

大O表示法的作用是：忽略n的影响即n趋于无穷大，观察算法的效率。**忽略硬件、语言、常数等细节，描述算法运行时间（或内存占用）随数据规模增长的变化趋势，从而比较不同算法的“增长速度”，选出在数据规模大时依然高效的算法。**即关注增长的速度(增长率)

2. 如果代码有很多行，需要每一行计算运行次数吗？

   

   只需要考虑最深处循环的语句次数与n的关系

常用技巧

加法原则

乘法原则

常见渐进时间复杂度

三种时间复杂度

例子如下：

算法效率度量(空间复杂度)

程序运行时内存需求

空间复杂度计算

例子1(原地工作复杂度)：

例子2:

递归函数带来的空间开销

如果没有其他输入干扰项，其空间复杂度=递归调用深度

这里每次申请长度为n的数组，最后累加即为O(n2)

第二章(线性表)

线性表的定义和基本操作

基本定义

当使用单一的序列时即可使用线性表进行定义，例如：排名、日程表

基本操作

• 对于&的解释：获取变量的地址，从而实现在函数内部对变量的内存指向进行修改，如下

  

线性表的顺序存储

顺序表的定义

顺序表的概念

例子：数组(数组的地址就是首元素的地址，即首地址)

实现方式

静态分配

在C++中静态分配之后，数组的长度就被固定住了(超出了没有办法、分配太大又造成了内存浪费)，所以就根据需求引出了下面的动态分配

动态分配

由于这里数组没有直接定义长度(eg:data[length])，而是使用了一个指针，所以动态分配即是让这个数组指针指向一块内存即可，如果需要增加数组长度，即指向新的数组即可，例子如下：

基本特性

这里的随机访问，是指访问任意一个元素所需的时间复杂度都是一样的。这个“随机”体现在：你可以直接跳到表中第 i 个元素的位置，不需要从第一个元素开始挨个找过去。个人理解：命名为任意访问可能更好一点

顺序表的插入和删除、查找

插入

具体的实现步骤：由于数组不支持动态插入，插入一个元素，只能将插入位置(包括该位置的元素)整体向后移一位，由于从前往后移动无法获取后一位的值，所以采取从最后一位开始后移，即从后往前后移一位，具体实现例子如下：

• 时间复杂度计算：

  

删除

由于需要将删除的值返回，可以采取在删除函数的形参部分加上&获取传入参数的地址进行获取删除值，也可以采取将删除的值返回赋值给变量。删除流程：跟增加不同的是：将删除位置的下一位从前往后依次前移一位即可。具体实现如下：

• 时间复杂度计算：

  

查找

按位查找

• 为什么按位查找可以直接查找到地址？

  

  因为顺序表是顺序存储，知道了数组首地址，即可计算出位数地址(首地址+查找位数*数据类型字节长度),所以顺序表的按位查找时间复杂度为O(1){只用一个计算公式即可得地址}

按值查找

• return返回的是顺序表的位序，而不是数组的下标，所以这里返回i+1

• 编程结构体使用==进行比较时错误的，但是做题使用==比较结构体不影响

• 时间复杂度：

  

线性表的链式存储

单链表

单链表的定义

代码实现

LinkList即代表LNode型的指针(头指针代表指向了一个单链表)，定义LinkList的作用是为了区分头指针和节点指针

• 这里简单讲一下为什么指针类型是自定义的结构体类型即LNode类型，因为指针的定义即是指向一个定义的数据类型内存地址(例如：int *p代表这个指针指向int类型的内存地址，LNode * next代表指向LNode类型的内存地址)

两种实现

不带头节点链表

主要是为了定义一个为空的单链表，也是为了说明LinkList的作用

带头节点链表

这里带头节点和不带头节点的单链表在初始化init时候都是传入&L,是因为都需要需改值，不带头节点是因为要将头指针指向null(防止野指针),带头结点链表即需要将头指针指向单链表的头节点的数据域(头节点的数据域不存值，或者只放辅助数据如：表名、表长….)

• 这里头节点和不带头节点的差别：主要是在头插法和删除时候的时候链表是否为空的判断

  • 不带头节点的链表：

    • 情况1：链表为空（L == NULL）。你需要让 L 指向新节点。
    • 情况2：链表不为空。你需要让新节点的 next 指向原来的第一个节点，然后让 L 指向新节点。
    • 代码中必须写 if 判断，区分这两种情况。

    带头节点的链表：

    • 头节点永远存在，即使链表为空，也有一个头节点（L 指向它，它的 next = NULL）。
    • 在第一个位置插入：无论链表是否为空，操作都一样——让新节点的 next 指向 L->next，然后让 L->next 指向新节点。
    • 不需要任何 if 判断，代码统一。

  • 同样的问题也出现在删除操作中：

    • 不带头节点的链表：删除第一个节点时，你需要把头指针指向第二个节点。如果删除后链表变空，头指针要设为 NULL。又要写 if。
    • 带头节点的链表：删除第一个数据节点就是 L->next = L->next->next。删除后即使链表变空，头节点依然存在（L->next = NULL）。代码完全统一。

  总结：头节点是用一个节点的空间开销，换来永远不需要写 if (head == NULL) 这种边界判断。

单链表的建立

尾插法

这里第一步是初始化一个带有头节点的单链表

这里简单说一下循环，第一次循环：首先申请了LNode类型的内存并且用LNode型的s指针指向该内存，s的数据域被赋值为x，将r指向s(这时的r是指头节点,即这时头节点指向第一个首元节点)，然后将s赋值为r(即r为首元节点的指针了).第二次循环：还是申请一块内存为s，s数据域赋值为x，将r指向s(这时的r已经是首元节点的指针了，即首元节点指向第二个节点)，将s赋值为r(即r为第二个节点的指针),依次类推…..

时间复杂度为O(n)，有多少个节点就执行多少次循环

头插法

这里我也简单地说一下循环,第一次循环：首先申请了LNode类型的内存并且用LNode型的s指针指向该内存，s的数据域被赋值为x，s的指针域被赋值为头节点的指针域(即s指向头节点的指向节点)，L的指针域指向s(即头节点指向s)。第二次循环，其实一点区别也没有，也是s先指向头节点的指向节点，然后头节点指向s。依次类推…..

这里也体现出了，头节点的作用，如果你没有头节点，你需要判断该单链表是否为空(有头节点时，就算单链表为空，头节点也是指向null，插入的s也是指向null，无需判断单链表是否为空),空则s指向null，非空则指向头指针指向节点

头插法可以将尾插法的顺序逆置：(第一个是尾插法，第二个是头插法)

单链表的查找和求表长

按位查找

简单讲一下循环：首先这里的i是指位序，不是数组下标，p首先是指的头节点，然后p指向下一个节点，j++，即j就代表了第几个节点，最后一次循环，即i=5时，p指向null。

时间复杂度为O(n)

• 按位添加即在按位查找之后使用尾插法即可

  

按值查找

循环：从第一个节点开始查找，并将数据域的值进行比较，如果不等于则接着往下查找，等于的话即返回值即可。

如果失败的话，时间复杂度一定是O(n)

求表长

循环：即下一个不为null，则长度加1，从头节点开始

时间复杂度为O(n).

单链表的插入和删除

按位序查找(带头结点)

循环:其实就是求表长的算法，将指针移动到位序-1的位置，然后使用尾插法插入即可

尾插法插入：将插入的指针s，s的数据域赋值，s指向位序-1的指针域，即s指向位序，然后再将位序-1的指针域指向s即可

按位序查找(不带头结点)

多了一个头节点的判定，需要变动头指针的指向

指定节点后插

指定节点前插

这个前插是首先将插入节点后插到指定节点后，然后再将指定节点与后插入节点的值进行互换，从而达到实现前插的目的。这个算法的好处是他的时间复杂度只有O(1)。

如果才用遍历法进行前插的话，需要找到插入节点，然后在插入节点的前驱进行后插法，但是这个就涉及到遍历链表了，时间复杂度为O(n).

按位序删除

删除的话需要两个指针，一个指针用来查找位序，一个指针用来标记删除的节点，和查找位序一样，首先找到位序节点的前驱，将删除节点指针标记删除节点，获取删除节点的值，然后将前驱指向删除节点的后继，删除节点释放即可。

删除指定节点P

这个和前插法的O(1)算法是一样的，也是采用值覆盖的方法。算法是首先将一个指针指向删除节点的后继，然后将后继赋值给删除节点，并且将指针域也赋值给后继节点，即这时就有两个删除节点的后继，然后将指向删除节点的后继删除，即完成了后继对删除节点的覆盖，从而完成了删除。这种算法的好处也是只用O(1)的时间复杂度。

但是如果是删除最后一个节点，没有删除节点的后继用于覆盖，那么只能采取按位序查找进行删除的办法了。这个时间复杂度就是O(n)了。

双链表

简单来说：双链表就是在单链表的基础上使节点有前后两个指针域，分别指向节点的前驱和后继，方便进行逆序的一系列操作

初始化

插入

• 如果p是最后一个节点，即删除p后继节点的前驱指向操作
• 使用后插法的好处就是不用考虑头节点的问题

删除

如果p是最后一个节点，即不用考虑后继节点的前驱指向问题

销毁双链表的操作，就是循环删除头节点的后继节点

遍历

循环链表

循环链表就是在单链表的尾节点添加一个指针域，使其指向头节点。

循环单链表

单链表如果要查找一个节点的前驱，就需要从头节点开始重新查找，这样的时间复杂度是O(n)

循环单链表的好处就是，从一个节点出发可以找到其他任何一个节点

• 循环单链表插入表尾节点时，可以使头指针指向表尾。可以让头指针指向插入节点，并将刚才的表尾指向头指针指向节点，最后将头节点指向刚才的表尾即可。

  

循环双链表

循环双链表就是将双链表的头节点的前驱指向尾节点，将为节点的后继指向头节点。

• 结构定义

  

• 插入

  和双链表的插入操作不同的地方在于末尾的插入操作需要将尾节点的后继指针指向头节点即可

  

• 删除

  也是考虑尾节点的情况

  

静态链表

简单来说就是顺序存储实现的链表。适用场合：不支持指针的语言。数据量固定不变的场景。例如：磁盘容量的定义

什么是静态链表

静态链表的定义

基本操作

初始化：

增删改查：

顺序表与链表的比较

物理结构/存储结构

运算/基本操作

创建

销毁

增加/删除

修改/查找

选择合适的结构

第三章(栈和队列)

栈的基本概念

栈是只允许在一端进行插入或删除的线性表

栈的定义

栈的基本操作

常见问题(出栈有多少种)

这里的进栈顺序必须是唯一的，否则公式无法成立.多种出栈主要是因为出栈没有被规定，例如：当我入栈a,b时，我马上出栈，即得到b,a，如果我入栈a、b、c时马上出栈，即得到c、b、a，即不同了。

顺序栈的实现

顺序栈的定义

初始化

top指针始终指向栈顶元素，例如:栈空时，top==-1，栈满时,top==MaxSize-1

入栈

先动指针，再赋值

出栈

先取指，再动指针

读栈顶

共享栈

简单来说：两个栈将出口互相对着(嘴对嘴)。top0这个栈是从右往左入栈，top1这个栈是从左往右入栈

如果栈顶指针不指向-1

栈顶指针始终指向栈顶元素的下一个位置，栈空：top==0,栈满：top==MaxSize即如下操作

进栈：

先赋值，再进行栈顶指针+1

出栈：

先进行栈顶指针-1，再进行取值

链式栈的实现

链式栈的定义

进栈

链式栈的进栈操作等同于单链表的头插法

出栈

使用的是单链表种覆盖删除的操作，删除的是首元节点

栈调用函数

首先这个题目，如果要讨论执行顺序，那么就是如图所示的:f(5)->f(3)……

在程序执行时，每次函数调用都会在系统栈上压入一个栈帧（Stack Frame）。当函数返回时，栈帧弹出。

我下面讨论的是系统栈的压入过程:

首先是参数f(5)
系统栈压入f(5)
	-f(5)计算,第一个得到f(3)
系统栈压入f(3),栈中有(从栈底开始):f(5)、f(3)
	-f(3)计算,return 2,
系统栈弹出f(3),栈中有(从栈底开始):f(5)
系统栈压入f(1),栈中有(从栈底开始):f(5)、f(1)
	-f(1)计算,return 2,
系统栈弹出f(1),栈中有(从栈底开始):f(5)
系统栈弹出f(5),return 4,栈中有(从栈底开始):null

后面的那个栈调用差不多

队列的基本概念

队列只允许在一端进行插入，另外一端进行删除的线性表

队列的定义

队列的基本操作

队列的顺序存储

定义

基本操作

初始化

这里判空不添加判断条件：是否为0，是为了后面的循环队列考虑。

在循环队列中，可能由于队列的不断出队导致front不断++，最终与rear重合，并且不在0这个位置上。

入队

front指控制队头元素，rear控制队尾元素+1，但是如果出队了几个元素，如图，队尾指针就无法指向队尾元素+1了，所以我们采用循环队列的方式，将rear指针用取余的方式重新指向队头。所以大部分都讨论循环队列了。

循环队列

循环队列判断已满的条件是：rear的下一个位置如果是front，即判断为满，但是会牺牲一个存储单元。

循环队列入队

循环队列是逻辑上的环状，不是物理存储上面

循环队列的初始化和判空都与普通的队列相同

循环队列出队

这里强调一下，front也是采用对MaxSize取余的方法进行移动的，因为front本身也是在这个循环队列中

循环队列(区分队空队满)

方案一(这个最常见的要注意一下,front指向队头元素,rear指向队尾元素的下一个元素,在判断队满的情况时,要牺牲一个存储单位):

方案二：

方案三：

当tag=0时，说明刚才进行的是删除操作，判断队空还是队满的情况就是队空(不可能删除成队满)

当tag=1时，说明刚才进行的是插入操作，判断队空还是队满的情况就是队满(不可能插入成队空)

不同的情况

情况1(rear指向队尾元素的下一个位置，front指向队头元素),也是我们最常用的模式：

这里判空直接就是rear=front，因为我们判满时牺牲一个单位进行的,所以判空不需要再额外判断。

情况2(rear指向队尾元素，front指向队头元素)

这里的长度计算要将MaxSize+1

情况三(rear指向队尾元素，front指向队头元素的前一个位置)

情况四(rear指向队尾的下一个元素，front指向队头的前一个元素)：

这里长度计算要MaxSize-1

链式队列的实现

定义

基本操作

初始化

带头节点

不带头节点

入队

带头结点

不带头节点

出队

带头节点

不带头节点

双端队列

双端队列本质上就是背靠背的两个栈

在输入或者输出受限时，可以看成一个栈和一个队列的集合体。，双端序列的输出种类大于栈和队列的输出种类，栈和队列能输出的，双端序列可以输出，栈和队列无法输出的双端序列也可以输出

栈和队列的应用

栈在括号匹配中的应用

就是使用栈来解决括号匹配的问题，凡是遇到左括号就入栈，遇到栈顶元素与之匹配的右括号就出栈

• 可能出现的情况：
  • 成功：剩下空栈
  • 失败：孤单左括号、孤单右括号、左右括号不匹配

栈在表达式求值中的应用

三种算术表达式

这里的op就表示为运算符

后缀表达式相关问题

中缀转后缀

方案一(机械识别方法，也是基本方法)：

从左往右识别表达式：
遇到运算数则直接加入后缀表达式：a
遇到预算符则加入表达式，并且弹出大于或等于其优先级的运算符，若碰到"("则停止出栈，符号栈：+
遇到运算数则直接加入后缀表达式：ab
栈中没有大于或等于*的优先级，入栈，符号栈：+*
遇到"("直接入栈，如果遇到")"，则弹出所有运算符，直到"("为止，括号本身不进入后缀表达式，符号栈:+*(
遇到运算数则直接加入后缀表达式：abc
遇到-号，弹出运算符直到"("或栈空,符号栈中栈顶元素为"(",即直接入栈，符号栈：+*(-
遇到运算数则直接加入后缀表达式：abcd
遇到")"，出栈所有元素加入后缀表达式，直到"(",括号本身不进入后缀表达式，后缀表达式:abcd-，符号栈:+* 注意:")"不入栈
遇到-,出栈大于等于其优先级加入后缀表达式:abcd-*+，符号栈：-
遇到运算数则直接加入后缀表达式：abcd-*+e
遇到/,出栈大于等于其优先级加入后缀表达式:abcd-*+e，符号栈：-/
遇到运算数则直接加入后缀表达式：abcd-*+ef
最后将符号栈中的运算符依次弹出并加入后缀表达式:abcd-*+ef/-

方案二(选择题可以使用，不需要求解符号栈中的具体元素时):

中缀表达式计算法:
找到优先级最高的,(),里面的表达式为c-d,中缀转后缀:cd-
从左往右看表达式,cd-看成一个整体,b*cd-,中缀转后缀:bcd-*
从左往右看表达式,bcd-*看成一个整体,a+bcd-*,中缀转后缀:abcd-*+
从左往右看表达式,abcd-*+看成一个整体,e/f看成一个整体,中缀转后缀:ef/,两个整体一减abcd-*+-ef/,中缀转后缀:abcd-*+ef/-


第一步：找优先级最高的（处理括号）
整个表达式中，(c-d) 的优先级最高。
把它单独拿出来转成后缀：cd-。
打包：此时，我们可以把 cd- 看作一个新的整体，假设叫它 X。原表达式就变成了 a+b*X-e/f。
第二步：找次高优先级（处理乘除）
在剩下的表达式里，b*X（即 b*(c-d)）优先级最高。
把它转成后缀：bX*，还原回去就是 bcd-*。
打包：把 bcd-* 看作一个新的整体，假设叫它 Y。原表达式变成了 a+Y-e/f。
第三步：处理同级优先级（处理加减，注意结合性）
现在剩下 a+Y 和 e/f。
先算左边的加法 a+Y（因为加减法从左往右算）：转成后缀是 aY+，还原就是 abcd-*+。
打包：把 abcd-*+ 看作整体 Z。此时表达式变成了 Z-e/f。
再算右边的除法 e/f：转成后缀是 ef/。表达式变成了 Z-ef/。
第四步：最后收尾
最后只剩下一个减法：Z 减去 ef/。
转成后缀：Zef/-。
把 Z 还原，最终结果就是：abcd-*+ef/-

后缀表达式求值（后缀转中缀）

从左到右识别表达式：
遇到a运算数直接入栈,运算数栈：a
遇到b运算数直接入栈,运算数栈：ab
遇到+运算符,则将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b
遇到c运算数直接入栈,运算数栈：a+b c
遇到d运算数直接入栈,运算数栈：a+b cd
遇到*运算符,则将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b c*d
遇到e运算数直接入栈,运算数栈：a+b c*d e
遇到/运算符,则将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b c*d/e
遇到-运算符,则将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b-c*d/e
遇到f运算数直接入栈,运算数栈：a+b-c*d/e f
遇到-运算符,则将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b-c*d/e+f

中缀表达式求值(计算机)

运算符栈和操作数栈与前面的中缀转后缀以及后缀表达式的算法一样,如下：
遇到a运算数直接入栈,运算数栈：a
遇到+运算符直接入栈,运算符栈：+
遇到b运算数直接入栈,运算数栈：ab
遇到-，因为+优先级等于-,所以将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b,运算符栈：-
遇到c运算数直接入栈,运算数栈：a+b c,运算符栈：-
遇到*运算符直接入栈,运算符栈：-*
遇到d运算数直接入栈,运算数栈：a+b c d,运算符栈：-*
遇到/，因为*优先级等于/,所以将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b c*d,又因为-优先级小于/，所以直接入栈了，运算符栈：-/
遇到e运算数直接入栈,运算数栈：a+b c*d e,运算符栈：-/
遇到+，因为/优先级大于+,所以将S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b c*d/e,又因为-优先级等于+，运算数栈：a+b-c*d/e,运算符：+
遇到f运算数，因为到了末尾：即直接计算了：S1(栈顶前一个元素) OP(运算符) S2(栈顶元素),将计算结果入栈,运算数栈:a+b-c*d/e+f

其他方案(最快)

画树法(运算符当作根节点或者子根节点)：
最后算的-号当作根节点，右边则是除法，按照除法顺序画出左右节点
左边则是加法,加法的左右画出左右节点
接下来是乘法，乘法的左右画出左右节点
最后是-法,减法的左右画出左右节点

按照先序遍历即可得到前缀表达式
按照后序遍历即可得到后缀表达式

栈在递归中的运用

在递归调用函数的时候可以看成一个栈存储，特点：最后执行的函数最先存储

斐波那契数列画成二叉树可以看成一个斜三角，而这个斜三角的节点个数小于一个正三角
正三角的算法为2的h次方相加
即斜三角的节点个数小于2的n次方，由于O(n)表示为增长速率，可以将常数忽略掉，即Tn可以近似看为2的n次方

队列的应用

先了解队列会在后面应用广泛，没有深讲。

树的遍历

图的遍历

操作系统

数组的定义和存储

定义

存储

二维数组：

特殊矩阵的压缩存储

普通矩阵

对称矩阵

下三角存储：

上三角存储：

如果更换了下标表示，公式失效，所以主要还是研究数组到k的映射关系

三角矩阵

下三角存储：

上三角存储：

三对角矩阵

稀疏矩阵

三元组首行存储行数、列数、元素的个数

三元组的元素失去了随机存取的特性

当矩阵存储所消耗资源远远大于三元组存储资源的话，才会选择使用三元组进行存储

第四章(串)

串的基本概念

串的定义

空串是任何主串的子串

基本操作

ASCII码表：

串的存储结构

顺序存储

string有多种存储方式，最常用是最后一种，废弃第0位，用最后一位来表示数组的长度，优点就是数组下标与位序相等，并且变量length的值可以存储的更大。

链式存储

三种存储方式的对比

基本操作

求子串SubString：

求串在主串第一次出现位置Index

这里循环判定是验证，子串在主串是否长度足够，例如：1234、1234567,子串最后验证的位置是4这个位置，到了5这个位置再进行匹配时没有意义的，长度不够

串的比较Compare：

逆置递归算法

主要思想是从an-1与an倒置,设这个整体为b1，再将an-2与b1倒置，再将an-3与b2倒置，依次类推

串的模式匹配

简单来说就是在主串(目标串)中查找子串(模式串)是否存在，有点类似我们前面学习Index函数

简单(朴素)模型匹配算法

最基础的就是我们前面字符串用于查找子串匹配的Index算法

使用一个辅助变量k,用于记录i(主串匹配的位置)的位序

不使用辅助变量k,而是使用i-j+2记录当前匹配的首位置(就是使用当前匹配减去已经匹配的子串长度)

时间复杂度

最好情况:匹配成功:第一个就是我们匹配的模式串(即时间复杂度为子串长度)

最好情况:匹配失败:就是我们前面Index算法的while循环,用于检测是否到达最后匹配位置(主串长度-子串长度+1)

最坏情况:匹配成功:每一个都要匹配子串的长度次，直到最后一次匹配才匹配成功(最后匹配位置乘以子串长度)

最坏情况:匹配失败:每一个都要匹配子串的长度次，并且匹配失败(最后匹配位置乘以子串长度)

KMP算法

KMP算法的出现是因为简单模型匹配算法的主串指针在比较时，总需要回溯，从而导致时间复杂度过高。

算法思路:在一次比较后，不再移动主串指针，而是利用部分匹配结果，直接将子串指针跳转到next数组指向位置，然后再进行匹配,如果再次匹配成功,则移动主串指针,否则还是将子串指针进行循环匹配。

next数组求法:

例题求下图的next数组：

next数组第一位默认为0
第二位的前缀为0(因为最后一个字符,就没有字符了),后缀也为0(除去第一个字符,也没字符了),那么公共前后缀则为0,最大前后缀也为0,那么next数组第二位则为0+1=1
第三位的前缀为a,后缀也为b,那么公共前后缀则为0,最大前后缀也为0,那么next数组第二位则为0+1=1
第四位的前缀为a ab,后缀也为a ba,那么公共前后缀则为a,最大前后缀也为1,那么next数组第二位则为1+1=2
第五位的前缀为a ab aba,后缀也为a aa baa,那么公共前后缀则为a,最大前后缀也为1,那么next数组第二位则为1+1=2
第五位的前缀为a ab aba abaab,后缀也为b ab aab baab,那么公共前后缀则为ab,最大前后缀也为2,那么next数组第二位则为2+1=3

• 为什么next数组可以不移动主串指针,而直接使用子串指针跳转就可以进行模式匹配？
  • 因为next的数组求解是通过公共前后缀得到的,例如第六位的跳转位置是3,是因为12的ab=45的ab,所以12的ab模式匹配是无意义的,在前一次的模式匹配就已经匹配45的12了。+1是因为这里是从1开始的，后面有从0开始的next数组就不需要+1了。
  • 这里就是从0开始的next数组，求解方式没有变，但是省略了+1

时间复杂度

KMP算法比简单模式匹配算法的效率要搞一个n倍。求next数组O(m),模式匹配最坏情况所需时间复杂度O(n)最坏时间复杂度:O(m+n)

KMP算法优化

KMP算法优化本质上是next数组优化，举例:如下图所示，假设到12的位置匹配失败，按照next的数组，在下一次匹配，子串指针则要跳转到位序6进行匹配，但是位序6和位序12都是a，所以这个注定匹配失败属于无效匹配，还需要跳转子串指针，跳转到位序4再进行匹配。那我们为什么不开始就写一个nextval数组存放最好的跳转位序呢，这就是KMP优化算法.

第五章(树)

树的定义和基本术语

基本概念

基本术语

有序树的定义即为从左到右是有次序的，例如根节点为爷爷，则从左到右即为大儿子、二儿子…..

树的性质

如下图所示：节点最多按照性质4，3叉树应为13个节点，这是在每一个层级都满配的情况下，但是如果第三层级没有三个孩子节点，则会多一个高度，及树的高度为4或更高，所以最小高度就是满足性质4的最小高度。

二叉树的基本概念

特殊二叉树

满二叉树

完全二叉树

左边为完全二叉树,右边不是的，因为K没有对应上，应该为E的孩子节点

二叉排序树

平衡二叉树

平衡二叉树的前提是二叉排序树，这里定义中的深度之差是指一个节点的左右高度差，以左边树为例：以30节点为例，左边的高度是3，右边的高度是2，即这里的高度差是1

二叉树的基本性质

n个节点可以构造多少种二叉树？采用栈的出栈种类公式，如下图：

n0这里指的是叶子节点，总结即为叶子几点总比二分支节点多一个

完全二叉树的基本性质

这里求节点的位序的方法和满二叉树是一样的，如果节点为i，则左孩子则为2i，右孩子则为2i+1，父节点为i/2，性质见下图，该性质只适用于满二叉树或者完全二叉树

叶子节点大于n/2，否则即为分支节点

即树如果为偶数叶子节点，则整体即为奇数个节点，度为1的节点就是0个，树如果为奇数的叶子节点，则整体为偶数个节点，度为1的节点就是1个(就是单独出来的那个叶子节点的父节点),度为2的节点始终为叶子节点-1即可

二叉树的存储结构

顺序存储

由于二叉树的顺序存储需要存储完全二叉树或者满二叉树才能存储其逻辑结构，所以其消耗的资源是巨大的，且最坏情况就是存储满二叉树的情况就是2的h次方-1个节点进行存储

链式存储

普通链式存储的二叉树，无法像顺序存储那样的直接使用公式找到父节点，只能通过根节点重新遍历寻找父节点

• 三叉链表:二叉树中的双链表，多了一个指向父节点的指针

  

二叉树的遍历

二叉树的递归遍历

左：left(L)；右:right(R);根:D，规定得三种遍历方式，一直是左在右前面，例如：先序:DLR，中序：LDR,后序：LRD，这里的先中后指的是根节点的位置

先序遍历

1. 递归写法(调用自身，然后在函数里面先传参左子树，再传参右子树)

2. 非递归写法

按照先序遍历的算法写循环(核心思想是对每一个节点都进行先序遍历即根左右)，首先判断节点是否存在，如果节点存在则访问并入栈，入栈再赋值为左节点，依次循环，到最后的叶子节点，赋值为左节点，但是为空，则出栈栈顶元素，在这个出栈算法里面必须将p指向出栈元素否则后面无法有效赋值，并赋值为其右节点，判断是否存在，存在则入栈进行左遍历，不存在则接着出栈。依然按照上述循环，到最终的叶子节点再进行出栈，最后先序遍历所有元素。

中序遍历

1. 依然按照递归定义写代码(中序遍历，首先传入左子树，然后访问根节点，左后传参右子树)

2. 非递归写法

这里先序和中序的不同的点就在于访问函数的不同，先序遍历是首先访问根节点，所以在节点存在时即可进行访问，但是中序遍历是首先访问左子树节点，所以到叶子节点(即p为空时),这时说明没有左子树了，即可访问当前节点也就是当前子树的根节点。所以整体算法和先序遍历类似。注意：visit函数改变了位置即可

后序遍历

这是二叉树里面使用最多的算法

1. 递归写法(依然按照算法进行，首先传参左子树，任何传参右子树，最后访问根节点)

2. 非递归写法

这个算法和前面的不同在于根节点是最后存储的，所以必须要先访问兄弟节点，这里就需要多一个指针用来记录右子树已经遍历。前面依然是正常的左遍历，到最后的叶子节点代码开始不同，这时左子树为空，但是要先遍历右子树，如果右子树这时也为空，才能进行访问函数，并且弹出节点(核心思想依然是我们的对每一个节点都进行后序遍历),依然判断右子树是否存在，如果不为空，说明当前子树的右子树存在，那么赋值为右子树，重新进行左遍历。这里需要注意的是，由于我们是在判断为空时，才进行弹出栈顶元素，所以在这之前，指针指向的还是空(即该节点的左子树),但是我们需要对该节点的右子树进行遍历，所以在判断为空之后，就需要读取栈顶指针，但是不弹出，即(GetTop函数),用于遍历右子树。当最后弹出元素时，指针指向的为弹出元素即说明该节点已经完成了后序遍历，接下来就需要对该节点的兄弟节点进后序遍历了，所以指针需要指向栈顶元素，所以将p赋值为空，即进入else范围。在该节点的右子树也已经遍历完成之后，则需要存储根节点，则需要一个指针记录了刚才已经进行右子树遍历，则添加一个指针，在弹出的时候，将p赋值为该指针r。如果这时该节点的右子树等于r说明右子树已经遍历，则直接进入子else范围进行弹出并访问操作。

总结：(相较于先序和中序遍历多出了GetTop函数和多出了一个指针，多出了p被赋值为空，多出了右子树判断)

GetTop：对于已经左遍历完的节点进行遍历右子树。

r指针:用于记录该节点的右子树是否已经遍历，若已经遍历则可访问根节点

p被赋值为空：用于将p指向栈顶元素进行遍历右子树

右子树判断：通过观察右子树是否存在和已经是否遍历

递归遍历的应用

1. 求二叉树的高度

求高度的应用可以分为两类:

1. 二叉树为空则高度为0
2. 二叉树不为空，则为左子树和右子树的max加根节点的高度即(max{h左，h右}+1)

2. 求二叉树的叶子节点数

求叶子节点数的应用可以分为3类：

1. 二叉树为空则叶子节点数为0
2. 二叉树只有根节点则叶子节点数为1
3. 二叉树不仅有根节点，则叶子节点数为左子树的叶子节点数+右节点的叶子节点数

二叉树的层次遍历

根节点入队，根节点出队，如果有左右孩子，则左右孩子分别入队，然后循环即可。

遍历序列构造二叉树

遍历序列中必须要有中序遍历才能构造二叉树，主要是根据根节点来构造的

三种遍历的关系

先序遍历:根节点在开头，中序遍历根节点在中间，后序遍历根节点在末尾，层次遍历：根节点子在开头

线索二叉树

线索二叉树的概念

前驱和后继的查找采用常规方法就是使用双指针，但是有许多缺点，所以就引出了线索二叉树

线索二叉树的作用

线索二叉树的存储结构

只有空指针域才可以进行线索化

三种线索二叉树

即为三种遍历方式的二叉树，先序遍历、中序遍历、后序遍历。线索化就是先将遍历序列写出来，然后进行空指针域线索化即可。

二叉树的线索化(代码实现)

中序线索化

先序线索化

递归函数里面添加if判断是为了防止死循环，防止叶子节点顺着它的空指针域线索化重新指向父节点，重新线索化

后序线索化

查找前驱后继

中序二叉树的后继

中序二叉树的前驱

先序二叉树的后继

先序二叉树的前驱

后序二叉树的后继

后序二叉树的前驱

树的存储结构

双亲表示法(顺序存储)

1. 存储一般树：

2. 存储森林

孩子表示法(顺序+链式存储)

1. 存储树

数组第一列中表示双亲位置可以取消掉，这样就是一个单纯的孩子表示法。当然就会有图示缺点，查找父节点不方便

2. 存储森林

孩子兄弟表示法(链式存储)

1. 存储树

左指针指向左孩子节点，右指针指向右兄弟节点

2. 存储森林

树、森林与二叉树之间的相互转化

树与二叉树相互转化

树转换为二叉树还是我们之前使用的孩子兄弟表示法

二叉树转换为树

森林与二叉树相互转化

森林转换为二叉树，就是孩子兄弟表示法中将森林转为二叉树

二叉树转换为森林

树、森林的遍历

树的遍历

先根遍历

先根遍历，就是依次遍历子节点，例如图示的先根遍历结果为:ABEFCDG

树的先根遍历与该树转换为二叉树的先序遍历结果相同

后根遍历

树的后根遍历与该树转换为二叉树的中序遍历结果相同

层序遍历

森林的遍历

先序遍历

森林的先序遍历就是对每一棵树做先根遍历

中序遍历

森林的中序遍历就是对每一棵树做后根遍历

森林转换为二叉树性质

由于森林中的叶子节点代表没有孩子，转为二叉树即为没有左孩子

哈夫曼树和哈夫曼编码

带权路径长度概念

哈夫曼树的定义

哈夫曼树也可以是大于二叉树的，但也是求解其中的带权路径最小

哈夫曼树的构造

哈夫曼编码

哈夫曼编码的应用

首先获取每个节点的哈夫曼编码

并查集

逻辑结构：集合

数组中的每个元素的值即为当前节点父节点的数组下标,例如：K的父节点是E,下标为4，即k的值为4

并查集的基本操作

1. Find – “查”操作：

   确定一个指定元素所属集合

2. Union – “并”操作：

   将两个不相交的集合合并为一个

并查集的代码实现

1. 初始化

2. 基本操作

并查集的优化

union优化

find优化

优化总结

第六章(图)

图的基本概念

有向图

无向图

简单图

在考研408的考试中，暂且只考虑简单图，不考虑多重图

有/无向完全图

1. 基本概念

2. 有/无向图的度

路径

连/强连通图

连通图针对无向图，强连通图针对有向图

连/强连通分量

子图

点选择的子集必须要和边选择的子集要能构成图，才能成为子图

生成树

生成森林

带权图

稀疏/稠密图

有向树

补充概念

n个顶点的图，若|E|>n-1，边集大于n-1，两个顶点确定一条边，该边集大于n-1，说明每一个点都有边相连，则一定会有回路

无向完全图，需要n(n-1)/2条边，以五个顶点为例，第一个点4条边，第二个点3条边，，，，最后求和

有向完全图，需要n(n-1)条边，以四个顶点为力，第一个点3条边，第二个点3条边，，，，最后求和

无向图边数的两倍等于各顶点度数的总和。

无向图G有n个顶点：

​ – 连通图：每两个顶点都可以”到达”,则构成最少边的情况就是所有顶点构成一个回路-1条边(因为没有方向，不需要构成回路)，即最少n-1条边

​ – 非连通图：除去一个顶点外，其他所有顶点构成一个完全图(任意两个顶点之间可以直达{无向完全图的构成为n(n-1)/2边}),则构成了最多边的情况，这时再将n-1带入完全图公式即为((n-1)(n-2)/2)，例如五个顶点即如下：

有向图G有n个顶点

​ – 强连通图：每两个顶点都可以”到达”,这个和连通图不同的地方在于他是有方向的，所以需要构成回路，即最少n条边

​ – 非强连通图：即图示结果，也是除外一个点进行有向完全图{n(n-1)}，将n-1带入公式即{(n-2)(n-1)}，加上构成完全图的所有点到除外点的一条边(n-1)，这时即为非强连通图的最多边即为：{(n-2)(n-1)+n-1}

图的邻接矩阵存储

邻接矩阵

1. 无向图邻接矩阵

2. 有向图的邻接矩阵

有向图的邻接矩阵和无向图一样，如果是按照从行到列进行排序，观察点与点之间是否有出度即可。没有无向图的对称矩阵特性

3. 无向带权图的邻接矩阵

该带权图的邻接矩阵和无向图的邻接矩阵一样，只是在无向图的邻接矩阵上对应的位置加上边的权值。特性依然保留是对称矩阵

4. 有向图带权图的邻接矩阵

邻接矩阵的特点

图的邻接表法存储

无向图的邻接表

有向图的邻接表

由于图的邻接表的入度和出度的顺序无法确定，所以邻接表不是唯一的(有向图、无向图一样)

邻接表的性质

这里的时间复杂度问题：
随便给你一个目标顶点 j，你能不能在 O(1) 的时间内知道 i 和 j 之间有没有边？
对于邻接矩阵来说，直接查找matrix[i][j] 的值是 0 还是 1 就可以了。时间复杂度为O(1)
对于邻接表来说，由于邻接表只能存储相邻边的信息，最坏的情况即是i 和几乎所有点都相连，但 j 是最后一个（或者压根没连）你需要把这条链表遍历完。链表的长度在最坏情况下是 n-1，所以时间复杂度是 O(n)

图的十字链表法和邻接多重表法

有向图的十字链表

无向图的邻接多重表

十字链表和多重邻接表的性质

图的基本操作(*)

图的遍历

图的广度优先遍历(BFS)

广度优先与树的层次遍历很像，都是从一个节点(顶点)开始，依次访问该点的孩子节点(邻接顶点)

图示广度优先遍历示例：
2
1 6
6 5
5 3 7
3 7
7 4
4 8
依次出队4、8遍历结束

算法实现

1. 连通图

2. 非连通图

使用一个循环来检测该数组的值是否为true，循环内部进行BFS算法即可

性能分析

1. 邻接矩阵

2. 邻接表

3. 空间复杂度分析

广度优先生成树

将广度优先遍历，使用层次遍历将树画出来

图的深度优先遍历(DFS)

算法实现

1. 连通图

2. 非连通图

性能分析

1. 邻接矩阵

2. 邻接表

3. 空间复杂度分析

深度优先生成树

补充知识

图的应用

最小生成树

总结：

PRIM算法

算法思想：
从一个顶点开始选择权值最小的一条边，再将该边连接的顶点加入树中(并将该电加入顶点集中)，再从顶点集中选择一条权值最小的边
顶点集{4},选择权值为1的边
顶点集{4,1},选择权值为4的边
顶点集{4,1,3}(这里选择3/6都可以),选择权值为2的边
顶点集{4,1,3,6},选择权值为5的边(按照生成树的概念，不能形成环路,所以没有选择(6,4)这条边)
顶点集{4,1,3,6,2},选择权值为3的边
顶点集{4,1,3,6,2,5},最后把生成树的图画出来即可

Kruskal算法

算法思想：
首先要将所有边都去掉,这时就只剩顶点了,然后选取权值最小的边连接连通分量(将所有点都连接)即可
选择权值为1的边，顶点集{1,4}
选择权值为2的边，顶点集{1,4}，{3,6}
选择权值为3的边，顶点集{1,4}，{3,6}，{2,5}
选择权值为4的边连接连通分量，顶点集{1,4,3,6}，{2,5}
选择权值为5的边连接连通分量，顶点集{1,4,3,6,2,5}

两种算法效率分析

破圈法(*)

最短路径问题1

单源最短路径

BFS算法(无权图)

Dijkstra算法(带权图、无权图)

算法思想：从一个顶点开始，不断的更新dist(最短路径)和path(前驱顶点)数组，以至最后所有顶点都加入顶点集

• 局限性:Dijkstra算法不适用于带负权值的图

各顶点间的最短路径

Floyd算法(带权图、无权图)

算法思想：
计算每个顶点经过其他顶点，最短路径是否会改变，如果改变即更新邻接矩阵和前驱节点矩阵
1.计算最开始的邻接矩阵和前驱节点矩阵,记为A(-1)和path(-1)
2.然后计算各点经过v0时的邻接矩阵,记为A(0),v1经过v0到达v2，v2经过v0到达v1最短路径是否改变,若改变则更新邻接矩阵A(-1)和前驱节点矩阵path(-1)
3.然后计算各点经过v0,v1时的邻接矩阵,记为A(1),v0经过v1到达v2，v2经过v1到达v0最短路径是否改变,若改变则更新邻接矩阵A(0)和前驱节点矩阵path(0)
4.然后计算各点经过v0,v1,v2时的邻接矩阵,记为A(2),v0经过v2到达v1，v1经过v2到达v0最短路径是否改变,若改变则更新邻接矩阵A(1)和前驱节点矩阵path(1)

最短路径各算法比较

最短路径问题2

有向无环图描述表达式

问题如下：

首先画出该表达式的二叉树形态(采用的是求后缀表达式的画树法)使用画树法求后缀表达式

最后将重复的部分用根节点直接指向即可(则最少需要五个节点)

拓扑排序

图上的有向图得到的拓扑排序如下：

正向拓扑排序

逆向拓扑排序

图上的有向图得到的拓扑排序如下：

关键路径

AOE网

定义法

上面这个方法求关键路径叫定义法

定义法思路:
由于AOE网上面的顶点需要该顶点的所有入度完成，才能进行该点事件的开始
如上图所示AOE网的关键路径求解：
v1到v3,v3有两个入度,一个a1,一个a3,但是a3完成需要v2完成,v2完成需要a2完成,a2<a1,所以先走a2这条路,从a2走到a7到达v3,即路径长度为8
v3到v4只有一条路，直接8+1=9即可，即关键路径为a2,a3,a4
该路径具有最大路径长度即为关键路径，也是最短能完成事件的时间，即9为关键路径长度

图表法

1. 求所有事件的最早发生时间

求该点(前驱的点+边权值)的最大值

2. 求所有事件的最迟发生时间

求该点(后继节点的权值-边权值)的最小值

3. 求所有活动的最早发生时间

活动的最早发生时间等于其事件的最早发生时间

4. 求所有活动的最迟发生时间

活动的最晚发生时间等于其终点事件的最晚发生时间-该活动的持续时间(边的权值)

5. 求所有活动的时间余量

所有活动的最迟发生时间-所有活动的最早发生时间,所得到的时间余量如果为0即为关键路径，关键路径所经过的顶点即为关键节点

关键路径的性质

第七章(查找)

第八章(排序)