数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第九章 查找

第九章 查找,数据结构,第九章 查找,第八章 查找,知 识 点 查找的基本概念 三种基本查找方法：顺序查找、二分查找和分块查找 哈希表查找,要 求 熟练掌握以下内容： 三种基本查找方法的基本思想和算法 散列法基本思想、散列函数的常用构造方法及解决冲突方法,第八章目录,9.1 查找的基本概念 9.2 基本查找方法 9.3 哈希表查找 9.4 应用举例及分析 小 结 习题与练习,9.1 查找的基本概念,查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。,对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。 查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。,返回,9.2.1 顺序查找,顺序查找(Sequential search)也称为线性查找，是采用线性表作为数据的存储结构，对数据在表中存放的先后次序没有任何要求。 顺序查找是最简单的查找方法，它的基本思想是：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。,顺序查找的线性表定义如下： #define MAXITEM 100 /*最多项数*/ struct element keytype key; Elemtype data; ; typedef struct sqlistMAXITEM; 这里keytype和ElemType可以是任何相应的数据类型，如int、float或char等，在算法中我们规定它们缺省是int类型。,顺序查找算法,int sequsearch (sqlist r, int k, n) /*n为线性表r中元素个数*/ i=1 while (ri.key!=k ,顺序查找算法分析,此函数的主要运算时间是用于循环语句逐单元进行比较判断ri.key是否等于k，因此顺序查找的速度较慢，最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。 顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。,9.2.2 二分查找,二分查找(Birary search)也称为折半查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。 设n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。 采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标 。,比较结果有三种可能： 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； 如果rm.key=k，查找成功，m所指的记录就是查找到的数据。,重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。 二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围了缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(logn)，对于较大的n显然较顺序查找速度快得多。,二分查找算法,int binsearch(sqlist r,int k,n) int i,low=1,high=n,m,find=0; /*low和high分别表示查找范围的起始单元下标和终止单元下标，find为查找成功的标志变量*/ while (lowrm.key),二分查找算法续,low=m+1; else i=m; find=1; if (!find) i=0; return(i); ,9.2.3 分块查找,分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。 分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。 还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表按关键字值的递增顺序排列。,分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。 例如线性表中关键字为:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如图8.1所示。,图9.1 线性表与索引表,索引表的定义,struct indexterm keytype key; int low,high; ; typedef struct indexterm indexMAXITEM; 这里的keytype可以是任何相应的数据类型，如int、float、或char等，在算法中，我们规定keytype缺省是int类型。,分块查找算法,int blksearch (sqlist r,index idx,int k,bn) /*bn为块的个数*/ int i,high=bn,low=1,mid,j,find=0; while (lowidxmid.key) low=mid+1;,分块查找算法续,else find=1; if(find=1) i=idxmid.low; j=idxmid.high; else if (lowbn) /*k小于索引表内最大值*/,分块查找算法续, i=idxlow.low; j=idxlow.high; while (ij) i=0; return(i); ,返回,9.4.1 散列法,散列法就是也称为哈希查找(Hashed search)或杂凑法。 散列法的核心思想是将每个记录的地址与该记录的关键字之间建立某种函数关系，可直接由关键字查找到该记录，根据关键字求存储地址的函数称为散列函数，又称为哈希函数（Hashed Function），按散列存储方式构造的动态表又称散列表(hashed table)。,设有关键字为1，3，7，12，15的五个记录，定义一个散列函数为： h(k)=(k mod m)+1 式中k为关键字，mod表示除法取余数的运算，m为一项规定的整数。 假设在此我们取m=7，则按这五个关键字计算出的函数值为： h(1)=2,h(3)=4,h(7)=1,h(12)=6,h(15)=2,图9.7 散列法,可能由不同的关键字计算出相同的散列函数值来，例如此例中h(1)和h(15)都等于2，也就是遇到了不同记录占用同一地址单元的情况，这种情况称为发生了冲突（collision）。,散列是一种重要的存储方法，又是一种查找方法。 应用散列法存储记录的过程是对每个记录的关键字进行散列函数的运算，计算出该记录存储的地址，并将记录存入此地址中。 查找一个记录的过程与存储记录的过程一样，就是对待查找记录的关键字进行计算，得到地址，并到此地址中查找记录是否存在。,9.4.2 散列函数构造方法,1. 直接定址法：直接取关键字本身或者关键字加上一个常数作为散列地址。 2. 数字分析法：又称为数字选择法。适用于所有关键字事先都知道，并且关键字的位数比散列地址的位数多的情况，在这种情况下，可将各个关键字列出，分析它们的每一位数字，舍去各关键字取值比较集中的位，仅保留取值比较分散的位作为散列地址。,数字分析法例子,3. 除留余数法：这是一种最简单也最常用的构造散列函数的方法，前面介绍的散列函数： h(k)=(k mod m)+1 就是采用这种方法。这种方法关键在于m的选择，选定m值后就可以决定存储地址的数目了。 4. 折叠法：折叠法是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。,9.4.3 处理冲突的方法,1. 开放地址法：开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。 开放地址法又称为闭散列表处理冲突的方法。散列表按结构形式可分成开散列表和闭散列表，闭散列表的结构是一个向量,也就是一维数组，表中记录按关键字经散列函数运算所得的地址直接存入数组中。 当在闭散列表上发生冲突时，必须按某种方法在散列表中形成一个探查地址序列，沿着这个探查地址序列在数组中逐个查找，直到碰到无冲突的位置为止，并放入记录。,形成探查地址序列最简单的方法是线性探测法，设散列函数为H，闭散列表一维数组的容量为m，对关键字k，计算出的地址为d=H(k)。 线性探测法的基本思想是沿着散列表顺序向后探查，直至找到开放地址为止，如到达表末端仍未找到开放地址，则将表看成是循环的，返回到表的首端再向后找，只要尚有开放地址最终总可以找到。 线性探测法对应的探查地址序列为d+1，d+2，m,1,d-1。探查地址序列对应的计算公式为：di=(H(K)+i) mod m (1im-1),例如，已知一组关键字k1k5，已计算出各关键字的散列函数值为： H(k1)=3, H(k2)=5, H(k3)=1, H(k4)=3, H(k5)=3， 总记录个数为5，开辟的一维数组长度可以比实际用的存储单元多一些，取m=8。,图9.8 开放地址的线性探测,二次探测法,二次探测法的基本思想是：生成的探查地址序列不是连续的，而是跳跃式的。二次探测法对应的探查地址序列的计算公式为： di = (H(k)+i) mod m 其中i=12，-12，22，-22­,j2，-j2，(jm/2)。,图9.9 开放地址的二次探测,2. 链接表法：又称为开散列表处理冲突的方法。 设散列函数为H(k)，函数值范围为0m-1，开散列表的结构可以设计成一个由m个指针域构成的指针数组Tm，初始状态都是空指针。其中每一个分量对应一个单链表的头指针，凡散列地址为i的记录都插入到头指针为Ti的链表中。每一个这样的单链表称为一个同义词表。链接表法解决冲突的方式，就是将所有关键字为同义词的记录链接在同一个单链表中。 例如前面的例子改用链接表法如图9.10所示。,图9.10 链接表法,9.4.4 散列法的查找运算,散列表的目的主要是用于快速查找。 在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。假设给定的值为k，根据建表时设定的散列函数H，计算出散列地址H(k)，如果表中该地址单元为空，则查找失败；否则将该地址中的关键字值与给定值k比较，如果相等则查找成功，否则按建表时设定的处理冲突的