数据结构-邓俊辉

@[toc]

去重

讲解
主要思想:先排序,然后找到不同的元素就将其放到前列

斐波那契查找

在常系数意义上要优于二分查找
拓展:符合语义要求的二分查找版本C

改进版冒泡排序

解析
前半部分(绿色)其实并不一定是无序的,而我们在冒泡的过程中其实已经”隐式”地检查过了.如果之前的冒泡没有交换过,证明前面的已经是有序的了.

继续改进
每次都记录下最后一次逆序对的位置,这样就可以不必对没有逆序的元素进行遍历,最好情况下可以到达O(n).

中缀表达式转逆波兰表达式(RPN)

逆波兰表达式无括号,从头到尾计算

括号引理

记录下dfs搜索过程的时间标签的作用

AVL树3+4重构

下面的代码似乎有点错误:

伸展树

利用了局部性原理,经过长时间的调整,常被访问的节点会靠近树根位置.

Tanjarn双层调整改进算法

B-树

分裂操作如果向上传播至根,那么B树木高度+1,这也是使得B树可以长高的唯一操作.

红黑树

散列函数的设计

为什么是平方取中?

平方试探

视频证明

提高装填因子

优先级队列

完全二叉树实现:根节点即最大元素

常系数改进:不用每次都swap,先将最后一个节点备份,逐渐向上比较,每次只下移父节点,最后直接替换即可

蛮力建堆:

改进:自下而上的下滤

深度和高度作为指标明明应该很接近,为什么在渐进的意义上会有这样的差别?
越底层,节点数量越多.

堆排序:

堆合并:

以上方法并没有利用到A和B两个堆原本的偏序信息.

左式堆:

右侧链:

左式堆实例:
视频实例

插入即是合并

删除亦是合并

串

蛮力为何低效?
只看原字符串,针对原字符串的每个字符,在最坏情况下,都需要和模式串的每个字符进行比对.

不变性:

KMP算法:

next[]数组:

选取最大的那个t,t越大,j-t越小,意味着越安全,可以避免回溯(暂未理解),也即跃过的部分确实是不必尝试匹配的.
视频讲解

j<0也表示上一次失配的位置即首位置.

构造next[]数组:
递推公式:

效率精确估计:

KMP再改进:
下一个进行匹配的至少不应该和原来一样,针对下面的案例,即至少不能再是0.

注意第二行0下面都变成了-1.
BM算法:坏字符
更多地关注教训,加速失败,让更大的教训更早地出现.

后面的字符可以排除更多的对齐位置.

视频讲解

BC表:

但模式串中可能有多个’X’,那么要选用哪个’X’呢?
此时应该巧选其一,避免回溯.选择shift位移量相对较小的,即选用最后的那个’X’.
那如果模式串中没有’X’呢?
此时应将模式串完整地移过这个位置.(第四行,利用通配哨兵字符)

如果最后一个’X’的秩过大导致shift为负数,此时应该怎么办?
直接+1.

最好性能:

最坏性能:
视频讲解
坏字符’1’的替代者’0’的最后位置太靠后,导致shifit为负数,因而只能整体移动一个位置.

改进:
GS:好后缀

产生gs[]表:

性能比较: