数据结构复习(8)——查找
顺序查找
- 无序
(1). ASL成功=(n+1)/2;
(2). ASL失败=n+1。 - 有序
(1). ASL成功=(n+1)/2;
(2). ASL失败=n/2+n/(n+1)。(失败结点有n+1个)
折半查找=二分查找（有序）
- 代码演示：
- ASL成功= log2的(n+1)+1;
- ASL失败=(h层失败结点的个数*h)/总结点个数。
分块查找（块内无序块间有序）
B树、B+树
B与B+树的增删参考： https://segmentfault.com/a/1190000020416577
散列查找
-
散列函数、散列表、冲突的定义
-
构造散列函数的方法：
-
解决冲突的方法：
(1). 开放地址法：(2). 不能随便删除数，因为别的数需要依靠其找到，可以添加一个删除标记，但是要记得定期维护。
(3). 拉链法：
(6). 平均查找长度-坑位