第9章_查找讲述.ppt

第9章 查找 9.1 查找的概念 查找(Search):也称检索，即根据给定的某个值，在查找表中确定一个其关键字等于给定值的第一条记录(元素)或全部记录。若表中存在这样的记录，则查找成功，通常要求返回该记录存储位置；若不存在这样的记录，表明查找失败，返回特定值。 9.2 顺序表查找 顺序表(Sequential List)：指集合或线性表的顺序存储结构。 本章讨论中，设顺序表采用一维数组A表示，其元素类型为ElemType，它含有关键字域key和其它一些数据域，并设定A的大小为整型常量MaxSize，数组的元素个数为n，n应小于等于MaxSize。 typedef struct { KeyType key; … } ElemType; 9.2.1 顺序查找 顺序查找(Sequential Search)又称线性查找，它是一种最简单最基本查找方法。 思路：从顺序表的一端开始，依次将每个元素关键字同给定值K进行比较，若某个元素关键字等于K，则查找成功，返回该元素所在下标，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败，反回特定值(常用-1表示)。 其算法如下： 9.2.2 二分查找 二分查找(Binary Search)又称折半查找。作为二分查找对象的表必须是顺序存储的有序表（默认为升序）。 查找过程：首先取整个有序表A[0]～A[n-1]的中点元素A[mid](mid=? (n-1)/2?)的关键字与K比较 例：以二分查找方法从长度为10的有序表中查找一个元素的ASL为 9.3 索引查找 9.3.1 索引的概念 索引查找(Index Search)又称分级查找。计算机中为索引查找建立一张主表和各级索引表。 索引存储的基本思想是：首先把一个线性表(主表)按一定的函数关系划分成若干逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后可采用顺序或链接方式存储索引表和子表。 9.3.2 索引查找算法 索引查找是在索引表和主表上进行的查找，其过程是：先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定对应子表在主表中开始位置和长度，再根据给定关键字K2，在对应子表中查找出关键字等于K2的结点。 分块查找(Blocking Search)：属于索引查找，它要求主表中每个子表之间递增(递减)有序，并且索引表中每个索引项的索引值域用来存储对应块中最大关键字。 9.4 散列查找 9.4.1 散列的概念（Hash） 在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位置，我们将h(K)函数称为散列函数或哈希函数。h(K)的值称为散列地址或哈希地址。使用的数组空间是集合或线性表进行散列存储的地址空间，被称之为散列表(Hash List)或哈希表。 在散列表上进行查找时，首先根据给定的关键字K，用与散列存储时使用的同一散列函数h(K)计算出散列地址，然后按此地址从散列表中取出对应的元素。 9.4.2 散列函数 构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。 常用构造散列函数方法： 直接定址法 除留余数法 数字分析法 平方取中法 折叠法 9.4.3 处理冲突的方法 开放定址法 线性探查法 平方探查法 双散列函数探查法 链接法 m阶B_树的高度h为： log m (N +1) ? h ? 1+log ?m / 2? ( (N +1) / 2 ) B-树插入 在B-树上插入一个数据元素首先要检索出关键字的正确插入位置，然后再进行插入。在B-树中插入新元素不是添加新的叶子结点，而是需要先判断该结点是否已有m-1个键字，若不是m-1个关键字，则按关键字（设为k）的大小有序地插入到适当的位置，否则，由于结点的关键字个数为m，超过了结点所规定的范围，需要进行结点的“分裂”。 例如，对一组关键字（25，80，40，45，56，75，85，20），从3阶的空的B-树开始，依次插入关键字。其具体过程如图8.19（a）到（k）图。 3.对线性表进行二分查找时，要求线性表必须 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，结点按关键字有序排列 D. 以链接方式存储，结点按关键字有序排列 4.用二分查找表的元素的速度比用顺序法 A.必须快 B.必须慢 C.相等 D.不确定 5.若要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找方法是 A. 顺序查找