复习（9）14章以前的内容

一下子就从14跳到12了……也不知道为什么

image.png
image.png
image.png
image.png
image.png
image.png

这里涉及到了一个转换，也就是对于堆中元素的删除（因为这个删除实际上是pop，所以必定是对于堆顶元素进行操作的），其实就是从最后一个元素开始行走，在行走的过程中 一定会涉及到每一层元素的交换和遍历，这样就可以将对应的元素都更换过来

image.png
image.png
个人理解：其实大根堆的初始化并不是初始化，顶多可以说是是将一个已经存在了的数组进行“堆化”，方法是，对于每个有节点的元素，从最后一个个往前开始遍历，进行符合大根堆规律的调整，最后必定能够形成大根堆
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

这里说一下自己的理解，也就是对于一个二叉树节点来说，最基础的元素就是root，当我们需要对这个二叉树进行遍历的时候，任何时候都不仅仅是遍历而已，需要一个操作，这个操作必然是对于一个二叉树节点的单位而言的，所以我们需要对总的遍历函数（参数为一种操作）传一个函数的参数，这个函数应该对某个节点实现某个功能，这个函数穿进去之后就被设置成为是private中的visit的具体形式，而之后public会调用private中的函数来实现具体的遍历，具体内容是从root开始，进行遍历，并且在遍历（递归实现）的每一层，都会调用被穿进去的函数来使用，实现功能。
public中的遍历的参数——函数
函数传进去变为private的函数的具体的值
public中的遍历的主体——调用private中的遍历
private中的遍历的参数——root节点
private中的实现——递归，并且调用visit

image.png
image.png
image.png
image.png
image.png
简单来说就是左子树都是孩子，右子树都是同辈儿
image.png
image.png
image.png
image.png
跳表和散列表
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

这个算法的意思就是，对于每一个将要判别是否可行的点来说，必须是将其对应的相邻的点也检查过，如果存在，证明这个点可行，压进去，对临界点进行操作，如果不存在，那么就不能存，直接返回，返回之后的点其实就是自己作为二临界点尝试过的点，同样的，在判别临界点是否满足这种条件的时候，也需要对其的邻接点进行判别，如果没有就不能入，返回已经被压入的当前点，否则的话就压入，继续判别其邻接点。

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
这个算法的精髓就在于，在我们想要将一个t转置为b的时候，首先要做的，应该是将t中每一列的非零个数计算出来，t中的列对应b中的行，再经过每一行的叠加能够求出对应的b中每一行应该有多少个数，然后对于t中的每个元素进行遍历，将行列转换过来之后，对应地找到b中已经计算出来的每一个起始点，然后将整体值作为一个term节点跟对应的序列一起插入进去，循环下来，b就是t的转置，也要注意b其实是作为一个函数的引用参数存在的，也就是说是借用调用函数地形式实现了将结果赋予的目的
image.png
迭代器是作为一个类地成员所使用的，声明类型和名字，指向特定的方向。
image.png
image.png
image.png
image.png
这里要注意，因为传进去的链表和头结点是要被复制的，所以对于当前的对象来说，只是单纯地使用后者的指针是不行的，当前对象中的所有的节点都必须是自己所建立出来的
image.png
image.png
image.png
image.png
image.png
image.png
image.png
内在逻辑其实就是，首先因为iteratoe是一个定义在类内的东西，所以它能够访问类内的数据成员，但是其实并没有访问，然后我们在类内加了一个对应的汗水，这个函数的功能是能够将对应的节点赋予给这个迭代器，而迭代器中有一个跟节点一模一样的指针，这个指针能够通过初始化函数来进行初始化地赋值，然后就被这个外部调用的函数给进行赋值了，进行赋值之后就可以进行遍历和比较，都是通过重定义运算符号来实现的
image.png
image.png
image.png
image.png
image.png
image.png
image.png
概括一下就是，首先每个元素是北褚村在一个链表中的，然后我们需要建立一个多个元素组成的链表数组，随后不断从这个链表中取出元素，每个元素都是含有成绩、姓名的结构体，通过分数的定义将其连接在不同箱子的后面，之后再将这个元素从中删除，在箱子完成之后，再依次按照次序将每个节点从箱子中取出来并且连接在对应的原节点后面
image.png
image.png
最后一步实际上完成的是将下一个节点连接上来，然后将对应的指针也转移过去，这里一定要区分开来指针和具体节点的区别
image.png
逻辑就是，y是通过其来进行连接的中间点，然后，只要遍历到的点非控股，如果是第一个，那么就直接进行连接，然后令y直接成为最后一个，也就是顶部的部分——这里有个逻辑就是其实往往底部是开始的地方
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
将较小的一个并查集开始遍历，遍历之后，将对应的并查集标记置为后者，
最后一个是最精髓的，要首先将k所指的指向b所指向的，然后是将b指向开头，如果直接将k放在开头就不可以
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
直到找到一个较大的数儿才能执行插入