数据结构课件查找-精选课件(公开).ppt

第九章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 查找的基本概念 查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。 对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。 查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。 查找表操作及分类 操作： (1)查询某个“特定的”数据元素是否在查找表中； (2)某个“特定的”数据元素的各种属性； (3)在查找表中插入一个数据元素； (4)从查找表中删去某个数据元素。 分类： 若对查找表只作(1)和(2)两种操作，则称此类查找表为静态查找表。 若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。 9.1 静态查找表 抽象数据类型静态查找表的定义： ADT StaticSearchTable{ 数据对象D: D是具有相同属性的数据 元素的集合。 数据关系R:数据元素同属一个集合。 基本操作P: Create(ST,n); Destroy(ST); Search(ST,key);Traverse(ST,Visit()); } ADT StaticSearchTable 一、顺序查找 顺序查找的基本思想是： 从线性表的一端开始，依次将扫描到得结点关键字和给定值K相比较。若当前扫描到得结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 顺序查找的存储结构要求： 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作为存储结构时，扫描必须从第一个结点开始），顺序查找对数据在表中存放的先后次序没有任何要求。 顺序查找的线性表定义如下： typedef struct { ElemType *elem; int length; }; （2）算法的实现： 讨论① 顺序查找算法分析 顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。 二、有序表的查找(折半查找) 折半查找(Birary search)也称为二分查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。 设n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。 采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标： 比较结果有三种可能： ⑴ 如果r[m].keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； ⑵ 如果r[m].keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； ⑶ 如果r[m].key=k，查找成功，m所指的记录就是查找到的数据。 重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。 二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(log2n)，对于较大的n显然较顺序查找速度快得多。 二分查找的性能分析 具体例子(11个元素) 查找过程可用判定树 描述 查找成功时进行比较的 关键字个数最多不超过 树的深度?log2n? +1 当n较大时，平均查找长度为 ASLbs= log2( n+1) –1 三、静态树表的查找 当有序表中各记录的查找概率相