数据结构与算法笔记
b站课程笔记，笼统学习，如有必要可再次快速寻找对应视频内容
b站视频链接：https://www.bilibili.com/video/BV1Ws411T7Qk?from=search&seid=6943615033604970213
基础
时间复杂度：O记
重复n次，就记作O(n)，两个n次循环的嵌套复杂度为O(n^2) 只看最高次项
空间复杂度较为少用
线性表
抽象数据类型（P8）
标记方式
ADT 抽象数据名
Data
数据元素间逻辑关系
Operation
操作
endADT
线性表
ADT 线性表 list
Data
除了首位和末位，其余所有数据都有且仅有一个前驱或后驱元素。数据元素之间一一对应
Operation
操作
endADT
两种储存结构：顺序存储，链式存储
优缺点：顺序存储不需要额外定义元素间的逻辑，但在插入删除元素是时间杂度是O(n)
链式存储结构存储2个元素（指针，数据），术语是指针域，数据域，该元素称为节点（Node）
静态链表
–cursor游标，指向下一个节点的下标
循环链表
–尾指针(rear)指向头指针
-特征，优势：便于修改合并循环单链表（只需要修改rear node的指向即可）
-判断是否有环：异步指针，p每次走1步，内循环q走n步（n += 1），没有环的情况下不会出现p=q
约瑟夫问题
栈
RPN 逆波兰法，4+(1+3)*(2-5)表示为4 1 3 + 2 5 – * +
其原理是遇到数字就入栈，遇到运算符先弹出栈顶前两个元素运算再将运算结果入栈。
队列
通过队头front 和 队尾rear两个指针实现前出后入只需调整指针，降低时间杂度。
为防止出现队尾假溢出，发明了循环队列：
如果front rear指针指向同一位置时，即表示数据已空
字符串匹配：
BF & KMP 算法
BF – Brute Force, 匹配S和T的每一位
KMP – 避免回溯，通过模式串决定，而非目标串。
前缀集prefix，从前往后一个个取。后缀集suffix-从前往后一个个删除
注意suffix和prefix不是对称关系，而是严格按照相等元素个数+1作为该位失配的k值（即指向的字符位）
和 BF不同，KMP算法通过指定某一位失配时的匹配位来避免重复搜索。具体编程实现还没有尝试。
树：
概念篇：
拥有子树的个数称为Degree, Degree=0,该节点为Leaf叶节点/终端节点。其余节点称为中间节点/内部节点。子节点Child。同级节点Siblings
同级不相关的树的集合为Forest。
子树顺序不可替换为有序树，可替换为无序树。
数据结构篇
双亲表示，孩子表示法等
孩子双亲表示法：
树整体用数列结构，孩子用链表，父母节点则在数列内表示
二叉树(Binary Tree)
各节点的child<=2, 可以存在n=0。固有五种形态：空，根，左，右，双
左右子树有区分，有序。只有一个节点也需要区分左右子树。
特殊二叉树：
- 斜二叉树（Every child is either left or right）
- 满二叉树(All parent has 2 children) 所有leaf都出现最后一层
- 完全二叉树：所有leaf都出现在最后两层，如果只有一个child, must be left.
- 代码 [lchild | data | rchild]
树的遍历方法：
前序遍历，中序，后序遍历，层序遍历。
大致理解：
前序遍历就是按照从root 到 leaf 的总体顺序，先完全走完left child,再走 right child
中序遍历是从leaf到root，让所有的 parent都被child夹在中间
后序和层序则还未深入研究。
上述两项理解主要基于对树的建立和线索二叉树的建立总结得到。
二叉树的建立与遍历-P48
- VS coding演示。
- 通过左右节点为空判断是否为叶节点。
- 利用递归快速建立和遍历树。
二叉树与树、森林间的转换
根节点有RightChild的二叉树可以转换为森林，否则只能为树
Huffman编码
根据使用频率生成WPL（Weighted Path Length）最小的树，用于高效分类
其原理就是让出现频率较高的样本位于更浅的叶节点中
图论
邻接表-矩阵形式表达节点间的连接
当连接（弧）上有权值时，形成网络。
入值 出值
十字邻接表：startVex, endVex, inWeight, outWeight
起点、终点、接入值、接出值
优势，可以快速读出接入和接出总数。
图的搜索
主要分为 DFS (Depth First Search)深度优先搜索和BFS (Breadth First Search)广度优先搜索
DFS (Depth First Search)
包含动画实现，类似逐行搜非零的元素对应的列号，前往（首个非零行号）列
如遇到全部都检索过，则回退。
直至回退后所有元素都已遍历过，即回到0，DFS结束。
BFS (Breadth First Search)
从任意点开始，以队列方式储存数据
输入A，A出列，同时A的子节点BF从队尾入列，如有已经遍历过的节点，则不再入队
重复这一过程，即可实现逐个遍历。
最小生成树
普利姆（Prim）算法
P63:18:00动画演示
选择最小的值，不是很理解，较难
克鲁斯卡尔算法
针对边展开
P64 17:14
按节点开始遍历，用parent矩阵储存每条边的起始节点，当n!=m是判断新建连线的终点不等于已有边的起点（不形成闭环，即树的思想）
parent List中每个元素的index基本对应起节点的编号。
两种生成算法的使用
prim针对顶点，适用于节点多边少稠密矩阵
kruscal针对边，适用节点少边多的稀疏矩阵
最短路径算法-Dijistra Floryd
Dijistra
分为三个数组，分别记录当前路径权值和、前驱节点，是否遍历。每次找出令当前权值和最小的路径组合。
Floryd
记录所有路径信息，D矩阵存储权值和，P矩阵储存前驱节点号。
其优势是可以批量优化所有节点间的最短路径。
拓扑排序-路径规划
AOV Net (Action on Vertex)顶点网络
有向图不可以存在回路。
拓扑序列：有向图生成
关键线路
AOE(Activity on Edge)键线网络
每个节点进行2次嵌套的循环
外循环遍历节点，内循环遍历与当前节点相邻的前置节点
计算得到的最早开始和最晚开始时间之差（也就是可调整的时间）
查找算法
分类
- 静态查找-链表
- 动态查找-伴随添加和删除-二叉排序树或hash表查找？
顺序查找
顺序查找需要2次判断O(2n)，设置a0=item，这样只需要一个判断，即 if a[0]!=item O(n)
插值查找
在二分法思路上，根据k到max的距离调整下一次分隔的比例，O(log_{2} {n})
线性索引
重组列表、倒序列表（以文章为内容，单词为索引）