8小结

南山隐士 2022年07月31日 37 0

本单元介绍了查找的相关概念以及在不同数据结构下的查找算法,包括:顺序查找、折半查找、分块查找、二叉树排序查找、散列(哈希)查找等。

主要知识点归纳如下:

1.查找表是同一类型的记录构成的集合,查找就是给定一个确定的值,在查找表中确定一个记录,其关键字等于给定值的操作。

2.顺序查找的查找表为线性表,存储结构为顺序表。若查找表长度为n,它的平均查找长度为(n+1)/2,查找方法是顺序比较。

3.折半查找要求查找表为有序的线性表,存储结构为有序的顺序表,它的时间复杂度为O(log2n)。查找方法是逐次取中、比较、确定新查找区间。描述折半查找过程的二叉树称为折半查找的判定树,通过它能容易得到查找某元素的比较次数和等概率条件下成功查找的平均查找长度,构造判定树的方法是逐次取序列和子序列中间记录的下标。

4.本书中二叉排序树是用递归定义的方式给出的,3个条件缺一不可。查找表用二叉排序树表示的方法是按照定义逐个插入,在二叉排序树上查找时逐次用待查值与根或子树的根进行比较,确定查找范围(子表)。对二叉排序树进行中序遍历可以得到一个有序序列。

5.散列查找的原理是在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系。实现方法是通过哈希函数、哈希表。本单元只要求了解散列查找的原理、相关概念和利用哈希函数构造哈希表的方法,并了解用链地址法和开放地址法解决冲突的原理。

Last Updated: 2022/07/31 23:24:57
9.1 排序的基本概念 8.4 哈希表及其查找