数据结构思维导图

线性表、队列、栈

集合、树、图

Q·front=（Q·front+1）%MaxSize

掌握KMP算法的滑动

前缀匹配，next数组

度为2的树至少有3个结点，而二叉树为空

度为2的有序树若只有一个孩子就无须确定左右次序。二叉树无论孩子是否为2都要确定次序

平衡二叉树

从结点中选取最小的两个结点构造树，轮流...

n 个结点能构造出n-1 个结点，所以哈夫曼树结点总数为2n-1

没有一个编码是另一个编码的前缀

选择距离最近的顶点连起来

时间复杂度O(V²)

按权值递增的顺序选择合适的边

单源最短路径

每一轮加入一个路径最短的结点

从原始邻接矩阵改

时间复杂度O(V³)

ve()事件(顶点)最早发生时间

vl()事件最晚发生时间

e(i)活动(边)最早开始时间

v()最晚开始时间

查找成功，平均查找长度: (n+1)/2

不成功，n+1

成功，(n+1)/2

不成功，n/2+n/(n+1)

比较次数不会超过树的高度

n个非叶子结点，n+1个叶子结点（失败结点）

查找成功平均查找长度：（1x1+2x2+3x2²+…+hx2⁽ʰ⁻¹⁾）/n =log（n+1）-1

兄弟够借，父子换位

兄弟不够，父子合并(若父结点只有一个关键词，合并后无父结点，要重新调整)

开放定址法

拉链法（不会聚集）

H（key）=key%p p取不大于表长m最接近m的质数

最坏比较次数n（n-1）/2

步长d=n/2,

最坏比较次数n（n-1）/2，移动次数3n（n-1）/2

比较次数与初始状态无关，始终是（n-1）n/2次

定义：大根堆：L（i）≥L(2i)且L(i)≥L(2i+1)

①建堆：从┗n/2┛~1为根的子树进行筛选 ②输出堆顶元素，将堆的最后一个元素放在堆顶，向下筛选

当初始归并段不足以构成一个严格k叉树时，需添加长度为0的“虚段”

（n0-1）%（k-1）=0时，可以构成k叉树

（n0-1）%（k-1）=u时，说明有u个多余，要加上k-u-1个虚段