数据结构
数据结构
  绪论
    时间复杂度、空间复杂度
      注意递归的时间与空间复杂度
    算法特征
      有穷性、确定性、可行性、输入、输出
  线性表
    顺序表
      存储物理地址空间连续
      静态分配与动态分配
    单链表
      带头节点与不带头节点
      头插法建立的单链表是逆置的
    循环单链表
    循环双链表
    静态链表
      类似FAT表，需要连续的存储区
  栈、队列和数组
    栈
      n个元素入栈，出栈不同数量为卡特兰数
      顺序栈
      链栈
        入栈出栈操作都在表头进行
      共享栈
        高地址与低地址共享使用
    队列
      顺序队列
      循环队列
        判断队空或队满方法
          牺牲一个单元创造两种状态
          新增size表示长度
          设置tag区分队满还是空
      链式存储
      双端队列
    栈和队列的应用
      栈
        前中后缀表达式
        波兰表达式为前缀，逆波兰表达式为后缀
        函数递归调用
        括号匹配
      队列
        层次遍历
        缓冲区
    数组
      对称矩阵
      上/下三角矩阵
      三对角矩阵
      稀疏矩阵
        十字链表
        三元组
          行数、列数，非零元素个数
  串
    kmp的next数组，kmp复杂度O(m+n)
    nextval数组
  树与二叉树
    树的概念
      度为m：只要有一个节点有m个孩子
      路径长度：两个节点之间经过边的个数
      总节点N=N0+N1+····Nm=1+N1+2*N2+····+m*Nm
    二叉树
      n0=n2+1
n=n0+n1+n2
        n1=0或n1=1。n0+n2=2*n2+1
总节点为奇偶看度为1的节点数
      特殊二叉树
        完全二叉树
          最后一个分支节点n/2。
          度为1的节点最多只有一个
        正则二叉树
          只有度为0和2的节点
      存储方法
        顺序存储
        链式存储
      遍历
        先序
        中序
        后序
        层序
      线索二叉树
        利用n+1个空指针指向前驱和后继
        增加ltag与rtag标记记录指针是前驱/后继还是左/右孩子
        先序线索二叉树
          无法找前驱
        中序线索二叉树
        后序线索二叉树
          无法找后继
    树和森林
      存储结构
        双亲表示法
          指向父节点
          需要连续空间
        孩子表示法
          指向孩子节点
        孩子兄弟表示法(二叉树表示法)
          左指针指向孩子，右指针指向兄弟
      树森林与二叉树的转换
        利用孩子兄弟表示法
        孩子作为左指针，兄弟为右指针
      树与森林的遍历
        树的遍历
          先根
            与对应二叉树先序遍历相同
          后根
            与对应二叉树中序遍历相同
        森林的遍历
          先序
            与对应二叉树先序遍历相同
          中序
            与对应二叉树中序遍历相同
    树与二叉树的应用
      哈夫曼树
        节点带权路径长度
          根到节点的长度乘以节点的权值
        树的带权路径长度WPL
          所有叶子结点的路径长度
        前缀编码
      并查集
        使用双亲表示法数组
          根节点的值是集合元素数量的相反数
        优化：将短树并入高树.路径压缩
  图
    图的定义
      简单图：无重复的边。没有自环
      路径长度：路径上边的数目。
n个点有大于n-1条边必有环
      无向图
        连通图：任意两个节点都有路径
        连通分量：极大连通子图
      有向图
        强连通图
        强连通分量
      完全图：任意两个节点都有边
    图的存储
      领接矩阵
        适合稠密图
      邻接表
        无向图：O(|V|+2|E|)。有向图：O(|V|+|E|)
        适合稀疏图
      十字链表
        适合有向图
        O(|V|+|E|)
      邻接多重表
        适合无向图
        O(|V|+|E|)
    图的遍历
      广度优先搜索BFS
        广度优先生成树只有领接矩阵的表示法唯一
        需要辅助队列
      深度优先搜索DFS
        需要递归工作栈
    图的应用
      最小生成树
        Prime
          O(|V|^2)
          适合稠密图
        Kruskal
          O(|E|log2|E|)
          适合顶点多，边稀疏图
      最短路
        Dijkstra迪杰斯特拉
          不适合负权图
          O(|V^2|)
        Floyd弗洛伊德
          O(|V|^3)
          不适合有负权回路
          每次循环表示以该节点为中转的最小边
      有向无环图描述表达式
      拓扑排序(AOV网)
        邻接矩阵：O(|V|^2)
邻接表：O(|V|+|E|)
      关键路径(AOE网)
        邻接矩阵：O(|V|^2)
邻接表：O(|V|+|E|)
        事件最早发生时间Ve(k)
        事件最迟发生时间Vl(k)
        活动最早发生时间e(i)
        活动最迟发生时间l(i)
        时间余量d(i)=l(i)-e(i)
  查找
    查找的基本概念
      静态与动态查找表
        静态查找表：只有查询
        动态查找表：动态插入或删除
      平均查找长度ASL
        成功
        不成功
    顺序查找与折半查找
      顺序查找
        查找成功：(n+1)/2
        查找不成功
          有序表：n/2+n/(n+1)
          无序表：n+1
      折半查找
        查找判定树一定是平衡二叉树
        具体平均查找长度画出查找判定树分析
          计算失败时只需计算内部节点
      分块查找
        索引表有序，sqrt(n)为最适合分块长度
    树形查找
      二叉排序树(BST)
        查找
        插入
        删除
      平衡二叉树(AVL)
        插入：每次调整最小不平衡子树
          LL，RR，RL，LR旋转
        删除
          同二叉排序树，删除后需要调整，不平衡不断向上传递
        最少节点N_h=N_(h-1)+N_(h-2)+1
        最多即满二叉树
      红黑树
    B树与B+树
      B树
        绝对平衡
        m阶B树
          每个节点最多有m个子树，m-1个关键字
          非根节点有(m+1)/2颗子树(m+1)/2-1个关键字
          树的高度
        插入
          注意分裂，在最底层中插入
        删除
          非终端节点拿 前驱或后继 代替，然后转化为对 前驱或后继 的删除
          注意合并
          若左右可借，则借左右节点关键字
      B+树
        m个子树，m个关键字
        至少(m+1)/2个关键字
        只有叶子结点有记录，查询需要查到最底部
        B+树有两个指针：一个根节点，一个顺序最小节点
    Hash表
      散列函数
        直接定址法
        除留余数法
        数字分析法
        平方取中法
      冲突处理
        开放地址
          线性探测法
          平方探测法(二次探测)
            0，1，-1，4，-4.....
          双散列法
          伪随机序列法
        拉链法
      删除：对元素逻辑删除。删除后冲突时要继续往后查找
      装填因子：记录数/散列表长度
      查找成功与失败
        成功ASL要除以元素数量
        失败ASL要除以散列表散列函数取值个数
        查找失败：查遍全表或找到一个空闲单元
  排序
    插入排序
      直接插入排序
        稳定
        最好O(n)，最坏O(n^2)
      折半插入排序
        稳定
        O(n^2)
        减少了元素比较次数，但比较次数与初始状态无关
      希尔排序
        不断缩小增量，在子表中排序
        不稳定
        仅适合顺序存储的线性表
        最坏O(n^2)
    交换排序
      冒泡排序
        稳定
        排序完成后若已经有序，还需排序一次才能确定有序
        最好O(n)，最坏O(n^2)
      快速排序
        不稳定
        时间最好O(nlogn)，元素基本有序时最坏O(n^2)
空间平均O(logn)，最坏O(n)
    选择排序
      简单选择排序
        不稳定
        O(n^2)
        元素的移动次数最少，比较次数稳定为n*(n-1)/2
      堆排序
        不稳定
        建堆时间为O(n)，时间为O(nlogn)
        应用：堆排序和优先队列
        初始化堆时，从n/2（就是分支节点）的节点开始调整，交换大小元素。
        插入元素时，放入最后一个位置，然后调整
        输出堆顶元素后，将最后一个元素与堆顶交换，然后调整
        ⚠️有两个子节点时，要对比两次。
只有一个子节点时，只要比一次
    归并，基数，计数
      归并排序
        稳定
        空间O(n)，时间O(nlogn)
        适合顺序存储与链式存储
        n个元素k路归并时，归并趟数=log_k(n)
      基数排序
        稳定
        需要O(r)的空间，即辅助队列
        不需要比较，与序列的初始状态无关
      计数排序
        稳定
    外部排序
      减少I/O方法
        增大归并路数
        减少归并段数量
      外部排序时间=内部排序时间+外存I/O时间+内部归并时间
      败者树
        树高不包括冠军节点
        归并路数变多，比较次数变多
        减少了为了选取最小值元素的比较次数
        比较次数为log_2(k)，向上取整
      置换选择排序(生成初始归并段)
        平均长度为工作区大小两倍
      最佳归并树
        类似哈夫曼树
        若节点不够则加几个值为0的虚段
  判断环路
    BFS可判断有向图
    DFS可判断有向图与无向图
    拓扑排序可判断有向图
  同一个图领接矩阵法的DFS与BFS序列唯一
而领接表得到的不唯一
静态分配：一开始就分配所有空间
动态分配：空间满了就开辟更大的空间，将所有元素拷贝到大空间去
注意队头与队尾指针初始情况、队空情况、队满情况
若已知中序，知道其他任意一种序列即可确定一棵二叉树
二叉搜索树中序遍历为递增序列
没有一个编码是另一个编码的前缀
一个边只存一份
注意查找失败的平均查找长度与查找成功有所不同
分析问题最好画出查找判定树
1.无左右子树直接删除
2.只有一个子树，删去后子树接上来
3.有两个子树，删去后拿前驱/后继来顶替，目标变为删去前驱/后继节点
从下往上找
从左到右有序
(m+1)/2为m/2上取整
最高就是根节点有一个关键字，其他节点有(m+1)/2-1个关键字
最矮就是每个节点都m-1个关键字
注意取余，到达表尾要从表头重新开始
查找成功相关因素：散列函数，处理冲突的方法，散列表的装填因子。
失败：处理冲突的方法（核心因素），散列函数的均匀性，散列表的装填因子
int Partition(int A[], int low, int high) {
int pivot = A[low]; //以第一个为基准
while (low < high) {
while (low < high && A[high] >= pivot)--high;
A[low] = A[high];
while (low < high && A[low] <= pivot)++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[], int low, int high) { //快速排序
if (low < high) {
int pivotpos = Partition(A, low, high);//将序列以基准位置平均分成两份
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos + 1, high);
}
}
每次选择最小的元素交换到前面去
可视为一颗完全二叉树
两个字节点时两个孩子节点先比较，然后再和当前节点比较，若满足条件就交换
只有一个子节点时，直接和当前节点比较。
将前后相邻的有序表合并为一个子表2，4，8。。。。
记录比当前元素小的数量，记数量为n，则n就是当前元素的位置
思想为归并排序
内部排序用来生成初始归并段
归并路数太多容易占用内存空间
工作区满后，选择最小值与当前归并段最后一个比较，满足条件就加入后面，否则就选择次小值.......
若最大值都比归并段最后一个小，就再加一个归并段。