电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.7.2 查找（二）

电量寄貅状学学 软件技术基础 3.7.2查找算洁（二) 主讲教师：刘民岷 ■ 航空航天学院 软件技术基础课程组

软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

分块查找 分块查找又称索引顺序查找，这是顺序查找的一种改进方 法。 方法描述：将n个数据元素“按块有序”划分为m块(m≤n。每一块 中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任 一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任 一元素又都必须小于第3块中的任一元素，.…。每个块中元素不一 定是有序的。 11 93014 3550 6555 86707867 30 65 86 电子科技大学刘民岷 查找算法 2

电子科技大学 刘民岷 查找算法 2 • 分块查找又称索引顺序查找，这是顺序查找的一种改进方 法。 • 方法描述：将n个数据元素“按块有序”划分为m块(m  n)。每一块 中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任 一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任 一元素又都必须小于第3块中的任一元素，……。每个块中元素不一 定是有序的。 11 9 30 14 35 50 65 55 86 70 78 67 30 65 86

4、分块查找（续） 查找过程： 一先选取各块中的最大关键字构成一个索引表； 一查找分两个步骤： >先对索引表进行二分查找或顺序查找，以确定待查记录在哪一 块中 >在已确定的块中用顺序法进行查找 119 3014 35506555867078 67 30 65 86 电子科技大学刘民岷 查找算法 3

电子科技大学 刘民岷 查找算法 3 11 9 30 14 35 50 65 55 86 70 78 67 30 65 86 • 查找过程： – 先选取各块中的最大关键字构成一个索引表； – 查找分两个步骤： ➢先对索引表进行二分查找或顺序查找，以确定待查记录在哪一 块中； ➢在已确定的块中用顺序法进行查找

树表查找 前三种查找方法各有千秋。二分法查找效率高，顺序法可 以采用链表存储结构，操作灵活。 但最好是既有二分法的高效率，又有链表灵活性的查找方法。 二叉排序树实际上就是将数据元素组织成二叉树形式，以 达到与二分法相同的查找效率，而又具有链表的插入、删 除操作的灵活性。 。1 根据二叉排序树的定义，在二叉排序树中，左子树上所有 结点的关键字都小于根结点的关键字；右子树上所有结点 的关键字都大于根结点的关键字。 电子科技大学刘民岷 查找算法 4

电子科技大学 刘民岷 查找算法 4 • 前三种查找方法各有千秋。二分法查找效率高，顺序法可 以采用链表存储结构，操作灵活。 但最好是既有二分法的高效率，又有链表灵活性的查找方法。 • 二叉排序树实际上就是将数据元素组织成二叉树形式，以 达到与二分法相同的查找效率，而又具有链表的插入、删 除操作的灵活性。 • 根据二叉排序树的定义，在二叉排序树中，左子树上所有 结点的关键字都小于根结点的关键字；右子树上所有结点 的关键字都大于根结点的关键字

树表查找（续） 5.1二叉排序树查找基本思想 当二叉排序树不空时，首先将给定值k与根结点的关键字进行 比较，若相等则查找成功； 若给定值k小于根结点的关键字，则下一次与左子树的根结点 的关键字进行比较，否则与右子树的根结点的关键字进行比较 。如此递归地进行下去直到某一次比较相等，查找成功。 5.2二叉排序树查找算法 :oooos:bsnode *bs_search(bsnode *t,keytype k) 00006:{ 00007: bsnode *s; 00008: if(t==NULL) 00009: 00010: printf("empty tree"); 00011: return(t); 00012: 00013: s=t; 00014: if((s->data).key==k) 00015: 00016: printf("searching sucess"); 00017: return(s); 00018: 00019: else if((s->data).key>k)//searching Left Tree 00020: return(bs_search(s->LC,k)); 00021: else //searching Right Tree 00022: return(bs_search(s->RC,k)); 00023:} 电子科技大学刘民岷 查找算法 5

电子科技大学 刘民岷 查找算法 5 5.1 二叉排序树查找基本思想 • 当二叉排序树不空时，首先将给定值k与根结点的关键字进行 比较，若相等则查找成功； • 若给定值k小于根结点的关键字，则下一次与左子树的根结点 的关键字进行比较，否则与右子树的根结点的关键字进行比较 。如此递归地进行下去直到某一次比较相等，查找成功。 5.2 二叉排序树查找算法

哈希查找 哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方 法都是把查找建立在比较的基础上，而哈希查找则是通过将关键字换算 为存储地址的方法进行查找的，换算时使用的函数称为哈希函数。 ● 哈希查找是一种快速查找方法。 哈希表由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上 ，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对 数据元素的快速检索。 哈希函数哈希表中元素是由哈希函数确定的。将数据元素的关键字K作 为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为 该元素的存储地址。表示为： Addr=H (key) ·建立哈希函数的原则 均匀性H(key)的值均匀分布在哈希表中； 简单 以提高地址计算的速度。 电子科技大学刘民岷 查找算法 6

电子科技大学 刘民岷 查找算法 6 • 哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方 法都是把查找建立在比较的基础上，而哈希查找则是通过将关键字换算 为存储地址的方法进行查找的，换算时使用的函数称为哈希函数。 • 哈希查找是一种快速查找方法。 • 哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上 ，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对 数据元素的快速检索。 • 哈希函数 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作 为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为 该元素的存储地址。表示为： Addr = H（key） • 建立哈希函数的原则 – 均匀性 H（key）的值均匀分布在哈希表中； – 简单 以提高地址计算的速度

哈希查找（续）一一 地址冲突问题 在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址 的现象称为冲突。 即关键字K1≠K2,但哈希函数值H(K1)=H(K2) >均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解 决；也即必须寻找下一个可用地址。 > 处理冲突有两种方法： ·开放地址法一发生地址冲突后，求解下一个地址 链地址法一当发生地址冲突后，将所有函数值相同的记录连成一个单链表。 电子科技大学刘民岷 查找算法 7

电子科技大学 刘民岷 查找算法 7 ➢ 在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址 的现象称为冲突。 即关键字K1  K2， 但哈希函数值 H(K1)= H(K2) ➢ 均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解 决；也即必须寻找下一个可用地址。 ➢ 处理冲突有两种方法： ▪ 开放地址法－发生地址冲突后，求解下一个地址 ▪ 链地址法－当发生地址冲突后,将所有函数值相同的记录连成一个单链表