第七章总结

tulensa 2020-06-28

一、基本概念:

1、  列表:待搜索的数据集合。

2、  关键字:要查找的那个数据。

3、  查找:一种算法过程。

二、基于线性表的查找:

1、  顺序查找:

(1)思想:逐个比较,直到找到或者查找失败。

(2)时间复杂度:T(n) = O(n)。

(3)空间复杂度:S(n) = O(n)。

第七章总结

2、  折半查找:

(1)思想:又称二分查找,对于已经按照一定顺序排列好的列表,每次都用关键字和中间的元素对比,然后判断是在前部分还是后部分还是就是中间的元素,然后继续用关键字和中间的元素对比。

第七章总结

3、  分块查找:

(1)思想:把无序的列表分成若干子块(子表),然后建立一个索引表,记录每个子块中的某个关键字(最大的数或是最小的数),然后用关键字和这个索引表进行对比。该索引表还存储子块的起始位置,所以可以使用折半查找或者顺序查找确定关键字所在的子块位置。进入子块后,使用顺序查找查找。

(1)思想:二叉排序树:①若它的左子树非空,则左子树上所有节点的值均小于它的根节点的值;②若它的右子树非空,则右子树上所有结点的值均大于(或大于等于)它的根节点的值;③它的左、右子树也分别为二叉排序树。查找的时候,中序遍历二叉树,得到一个递增有序序列。查找思路类似于折半查找。

4 . 平衡二叉排序树:

(1)思想:首先它也是二叉排序树,但是还要具有如下性质:①左子树和右子树的深度之差的绝对值小于等于1;②左子树和右子树也是平衡二叉树。

5.  哈希查找:

(1)思想:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为H(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=H(k),从而达到按关键字直接存取元素的目的。难点在于处理冲突的方式:①开放定址法②再哈希法③链地址法④建立公共溢出区。

相关推荐