教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net.

Presentation on theme: "教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net."— Presentation transcript:

1 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net
计算机软件技术基础 教 师：曾晓东 电 话： E_mail:

2 6.1 查找 一、概念和术语 二、顺序表查找 三、散列查找 四、各种查找算法的比较 计算机软件技术基础 查找与排序

3 6.1 查找 访问与查找都是数据结构中的重要操作，访问数据结构中数据元素的访问算法都是与具体数据结构的特性紧密相关的。
如根据下标访问数组中的数据元素，沿指针指向访问线性链表中的结点、遍历一棵二叉树等。在这一节中，我们将讨论各种查找算法，并对查找算法进行分析。 计算机软件技术基础 查找与排序

4 一、概念和术语 记录(record)：它是由若干个数据项(或称为域)组成的数据元素，它和结点、顶点的意义完全相同。
文件(file)：它是由若干记录组成的集合，即含有若干记录的表称为文件。 关键字 1）主关键字：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。 2）次关键字：用来标识若干记录的数据项称为次关键字。 计算机软件技术基础 查找与排序

5 一、概念和术语 查找 给定一个值K，在含有n个记录的文件中进行查找，寻找一个关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。 动态查找与静态查找 查找的同时对表作修改操作的表称为动态查找表，否则称之为静态查找表。 计算机软件技术基础 查找与排序

6 一、概念和术语 平均查找长度 由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即统计意义上的数学期望值来评估查找算法，称为平均查找长度（ASL）： 其中，n是文件中记录的个数，Pi是查找第i个记录的查找概率，通常我们认为每个记录的查找概率相等，即Pi=1/n；Ci是找到第i个记录时所经历的比较次数。 计算机软件技术基础 查找与排序

7 二、顺序表查找 1、顺序查找 顺序查找又称线性查找，是一种最简单的查找方法。 1）基本思想
从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。 2）算法描述 结点的类型定义 typedef struct{ keywordtype key; datatype elemdata; }elemtype; 顺序表的类型定义 const int MAXSIZE=100; typedef struct{ struct elemtype data[MAXSIZE]; int length; } listtype 计算机软件技术基础 查找与排序

8 二、顺序表查找 int sqlistsearch(listtype *a,keywordtype k){
int i; a->data[a->length] = k; // 设置监视哨 for(i=0;a->data[i].key!=k;i++); if(i == a->length) return(-1); // 查找不成功 else return(i); // 查找成功 } 3)性能分析 等概率情况下，Pi=1/n，Ci=i，所以： 计算机软件技术基础 查找与排序

9 二、顺序表查找 2、折半查找 又称对分查找，是对有序表进行的一种查找。 1)基本思想 先找到“中间记录”，比较其关键字，
如果关键字与给定值K相等，则查找成功； 如果关键字x小于给定值K，则说明被查找记录必在前半区间内； 反之则在后半区间内。这样把查找区间缩小了一半，继续进行查找。 计算机软件技术基础 查找与排序

10 二、顺序表查找 low mid hig k=55 low mid hig k=12 low mid hig low mid hig hig low 查找成功 查找失败 计算机软件技术基础 查找与排序

11 low mid hig k=55 low mid hig k=12 二、顺序表查找 low mid hig 2)算法描述 int BinSearch(listtype *a,int k) { /*在有序顺序表a中查找关键字k，若成功则返回记录号，否则返回-1*/ int mid,low=0，high=a->length-1; while(low <= high){ mid = (low+high)/2; if(k == a->data[mid].key) return(mid); if(k < a->data[mid].key) high=mid-1; if(k > a->data[mid].key) low =mid+1; } return(-1); } low mid hig low mid hig hig low 查找成功 查找失败 计算机软件技术基础 查找与排序

12 42 94 55 70 46 13 17 5 序列：5,13,17,42,46,55,70,94的判定树 二、顺序表查找 3)性能分析 对分查找的判定树：在查找过程中，各记录的比较次数与待查记录在文件中的相对位置有关，我们把比较次数相同的记录关键字放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为判定树。 等概率下的平均查找长度为： 计算机软件技术基础 查找与排序

13 二、顺序表查找 3、分块查找 1）概念 分块查找又称索引顺序查找，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字。而每一块中的关键字则不一定有序。 2）基本思想 先将各块中的最大关键字构成一个递增有序的索引表，查找分两步： ① 对索引表对分或顺序查找,以确定所在块。 ② 在所在块中进行顺序查找。 计算机软件技术基础 查找与排序

14 二、顺序表查找 图例 第1块 第2块 第3块 索引表 最大关键字 起始地址 计算机软件技术基础 查找与排序

15 二、顺序表查找 3)算法分析 分块查找的平均查找次数包括两部分 查找索引表(Lb) 在块中查找(Lw) ASL = Lb+Lw
设共有n个记录，分成b块，每块有s个记录，则b=n/s 设在索引表和块中都进行顺序查找，则 ASL = (b/2+s/2) = (n/s+s)/2 + 1 当b=s=sqrt(n)时，ASL最小，为sqrt(n)+1 其查找效率界于折半查找和顺序查找之间 计算机软件技术基础 查找与排序

16 三、散列查找 1、散列表 又称哈希表 1）基本思想：通过对给定值作某种运算，直接求得关键字等于给定值的记录的位置。
2）概念：设关键字key与存储位置间的对应关系为H(key)，若用一维数组来存放文件，则H(key)即为数组的下标。我们称函数H为哈希(Hash)函数，H(key)为哈希地址（或散列地址），这个一维数组称为哈希表。 计算机软件技术基础 查找与排序

17 三、散列查找 3）有关问题 ① 哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较。
② 为提高查找效率，哈希表的空间m要比记录个数n大，定义a=n/m为装填系数(有时也叫装填因子)，实际应用中一般取：0.65～0.85。 计算机软件技术基础 查找与排序

18 三、散列查找 ③ 为求得哈希地址，有时须对关键字进行算术或逻辑运算，若关键字为非数值型，可先转化为数值，称为关键字的内部码。而且求得的哈希地址的值域必须在哈希表长的范围内。 ④ 若某个哈希函数对不同的关键字得到相同的哈希地址，这种现象称为冲突，这些关键字称为同义词。实际应用中，冲突一般不可避免，应寻找解决冲突的方法。 所以，运用哈希技术进行查找，要解决两个问题：哈希函数的构造和解决冲突。 计算机软件技术基础 查找与排序

19 三、散列查找 2、构造散列函数 构造散列函数的原则 散列函数应是简单的，能在较短的时间内计算出结果。
散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许m 个地址时, 其值域必须在 0 到 m-1 之间。 散列函数计算出来的地址应能均匀分布在整个地址空间中 。 计算机软件技术基础 查找与排序

20 三、散列查找 1）折叠移位法 将关键字分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。
折叠时有两种方法：移位折叠和边界折叠。如关键字值为： ，分为5段：123,203,241,112,20，两种折叠法分别如下： —— —— 计算机软件技术基础 查找与排序

21 三、散列查找 2) 平方取中法 先将关键字平方，再选取其中几位作为哈希地址。例如有一组关键字为：
(0100,1100,1200,1160,2060,2061,2163,2261,2262) 设存储空间为1000,将关键字平方后再取第2,3,4位构成哈希地址为： (010,210,440,345,243,247,678,112,116)。 计算机软件技术基础 查找与排序

22 三、散列查找 3) 除留余数法 对关键字取模（余数）作为哈希地址，即：H(key)=key % p。
如果将m取为某个偶数，则奇数关键字值被转换为奇地址，偶数关键字值被转换成偶地址。显然，这很容易造成散列冲突。另外，如果用较小的质数或含有小质数因子的合数作为除数m，也会导致散列地址不均匀的结果。为了获得比较均匀的地址分布，最好选择—个较大的质数作为除数。 计算机软件技术基础 查找与排序

23 三、散列查找 注意：经验证明模数m取为超过20的质因子的合数，散列地址分布将比较均匀。
也可以使用此方法，作附加处理，将散列地址限制在一个范围内。 如允许的地址空间限制在000—499之间，则将H % 500即可。 计算机软件技术基础 查找与排序

24 三、散列查找 4）数字分析法 适合静态数据，关键字已知,分析数字的分布，删除不均匀的数字，再根据存储空间的大小决定数字的数目。例如有7个学生的学号为： 分析知：第1, 2, 3位分布太不均匀，删去；第8位出现的7太多，删去。设存储空间为1000，则可取第4, 6, 7位作为关键字的存储地址，分别为： 422，836，281，396，515，853，135 计算机软件技术基础 查找与排序

25 三、散列查找 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况, 它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。 计算机软件技术基础 查找与排序

26 三、散列查找 3、处理散列冲突 所谓散列冲突(conflict)就是两个不相同的关键字值被转换成同—个散列地址的现象。 1）线性探测
设性线表的空间为T[m]，哈希函数为H(key)，冲突时求另一个记录的地址公式为： dj+1=(d1+j) % m (j=1,2,…,s,s≥1) 其中d1=H(key)。 计算机软件技术基础 查找与排序

27 1）线性探测 线性探测再散列是把哈希表作为一个环状空间，当冲突发生时，以线性方式从下一个哈希表地址开始探测，直到查到一个空的存储地址，将数据存入。 若找完一个循环还没有找到空间，则表示地址已满。 计算机软件技术基础 查找与排序

28 三、散列查找 设有一组关键字为： (13,29,01,23,44,55,20,84,27,68,11,10,79,14) n=14，选取a=0.75, 则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，采用线性探测法处理冲突 01 20 79 23 44 84 27 29 68 11 13 10 14 55 K=10 H(K)=10%19=10 冲突 Add=10+1=11 冲突 Add=11+1=12 冲突 Add=12+1=13 冲突 Add=13+1=14 填入 K=01 H(K)=1%19=1 填入 K=29 H(K)=29%19=10 填入 K=79 H(K)=79%19=3 填入 K=14 H(K)=14%19=14 冲突 Add=14+1=15 填入 K=13 H(K)=13%19=13 填入 K=20 H(K)=20%19=1 冲突 Add=1+1=2 填入 K=11 H(K)=11%19=11 冲突 Add=11+1=12 填入 K=23 H(K)=23%19=4 填入 K=84 H(K)=84%19=8 填入 K=27 H(K)=27%19=8 冲突 Add=8+1=9 填入 K=55 H(K)=55%19=16 填入 K=44 H(K)=44%19=6 填入 K=68 H(K)=68%19=11 填入 平均查找长度： ASL=总比较次数/记录个数； 采用不同的解决冲突方法，ASL也可能不同。 对此例，平均查找长度为 ASL=( )/14=22/14 计算机软件技术基础 查找与排序

29 若hash[j].key=0表示此地址为空。
三、散列查找 查找算法如下： int linearprobing(elemtype hash[],int n,int k){ /*hash:哈希表;n:哈希表的表长；k：关键字*/ i=H(k);/*计算地址*/ j=i;/*线性探测位置*/ while(hash[j].key!=k && hash[j].key!=0){ j=(j+1)%n; if(j==i){return(-1); //表满 } } return(j); } 若hash[j].key=0表示此地址为空。 缺点：线性探测方法容易产生“记录群集”, 不同探查序列的关键码占据可用的空位, 为寻找某一关键码需要经历不同的探查序列, 导致查找时间增加。 计算机软件技术基础 查找与排序

30 三、散列查找 2)随机探测 线性探测产生群集的主要原因是：每次都探测邻接的下一步个位置，即探测步长不变，如果按不同的步长探测，则可减少群集现象。 本方法是用一组预先给定的随机数在冲突时求地址，公式为： dj=(d1+Rj) % m (j=1,2,...,s,s≥1) 其中Rj为一组随机数列。 计算机软件技术基础 查找与排序

31 2)随机探测 设有一组关键字为： (13,29,01,23,44,55,20,84,27,68,11,10,79,14) n=14，选取a=0.75, 则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，用随机探测法解决冲突。其中随机数序列为：23,2,19,14,3,16,55,44,… 计算机软件技术基础 查找与排序

32 三、散列查找 关键字：(13,29,01,23,44,55,20,84,27,68,11,10,79,14) 01 79 23 20 44 84 29 68 27 13 10 11 55 14 K=10 H(K)=10%19=10 冲突 Add=(10+23)%19=14填入 K=29 H(K)=29%19=10 填入 K=13 H(K)=13%19=13 填入 K=79 H(K)=79%19=3 填入 K=14 H(K)=14%19=14 冲突 Add=(14+23)%19=18填入 K=11 H(K)=11%19=11 冲突 Add=(11+23)%19=15填入 K=01 H(K)=01%19=01 填入 K=55 H(K)=55%19=17 填入 K=20 H(K)=20%19=1 冲突 Add=(1+23)%19=5 填入 K=84 H(K)=84%19=8 填入 K=44 H(K)=44%19=6 填入 K=23 H(K)=23%19=4 填入 K=27 H(K)=27%19=8 冲突 Add=(8+23)%19=12 填入 K=68 H(K)=68%19=11 填入 对此例，平均查找长度为 ASL=( )/14=19/14 明显比采用线性探测法处理冲突为优 计算机软件技术基础 查找与排序

33 若hash[add].key=0表示此地址为空。
三、散列查找 查找算法如下： int randomprobing(elemtype hash[],int rnd[],int n,int k){ /*hash:哈希表;rnd:随机数列；n:哈希表的表长；k：关键字*/ i=H(k);/*计算地址*/ j=0;/*随机数列位置*/ add=i; /*随机探测位置*/ while(hash[add].key!=k && hash[add].key!=0){ add=(i+rnd[j])%n; j++; } return(j); } 缺点：处理表满不方便。 若hash[add].key=0表示此地址为空。 计算机软件技术基础 查找与排序

34 三、散列查找 线性探测及随机探测的缺点： 不能真正删除表中已有表项。删除表项会影响其他表项的查找。若把关键码为68的表项真正删除, 以后在查找关键码为11的表项时就查不下去, 会错误地判断表中没有关键码为 11的表项。 若想删除一个表项, 只能给它做一个删除标记, 进行逻辑删除, 不能把它真正删去。 逻辑删除的副作用是：在执行多次删除后, 表面上看起来散列表很满, 实际上有许多位置没有利用。 当然，也可以物理删除表项，不过，需要将表项后面的各项前移 计算机软件技术基础 查找与排序

35 三、散列查找 3）链地址法 适用于记录内容变动较大的散列表
若哈希表为T[0..m-1]，设置一个由m个指针分量组成的一维数组ST[0..m-1]，凡哈希地址为i的记录都插入到头指针为ST[i]的链表（称为散列链表或桶，哈希地址相同的元素称为同义词）中。 链地址法是个动态结构，所以更适合在造表之前无法确定记录个数的情况。 计算机软件技术基础 查找与排序

36 3）链地址法 散列链表的结点定义与普通单链表一致，只是其elemtype域包含两个域：
keywordtype(关键词)和datatype(数据)， 其定义与前面的Hast表的结点定义类似 计算机软件技术基础 查找与排序

37 三、散列查找 查找算法如下： node * hashlinkSearch(node *ST[],int m,keywordtype k) {
/*ST:散列链表的头指针数组；m:哈希表长度；k：关键词*/ i=H(k);/*取哈希地址*/ p=ST[i];/*散列链表的头指针*/ while (p && p->key!=k) p=p->next; return(p); } 返回值p为指向查找元素的地址，若p=NULL，说明表中无此元素，可将其插入到哈希表中。 计算机软件技术基础 查找与排序

38 三、散列查找 示例：给出一组表项关键码 { Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly }。散列函数为：Hash (x)＝ord (x)－ord ('A')。 用它计算可得： Hash(Burke) = 1 Hash(Ekers) = 4 Hash(Broad) = 1 Hash(Blum) = 1 Hash(Attlee) = 0 Hash(Hecht) = 7 Hash(Alton) = 0 Hash(Ederly) = 4 散列表为 T[0..25]，m = 26。 计算机软件技术基础 查找与排序

39 三、散列查找 Attlee Alton Burke Broad Blum Ekers Ederly Hecht 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8 9 Attlee Alton Burke Broad Blum Ekers Ederly Hecht 计算机软件技术基础 查找与排序

40 三、散列查找 通常，每个桶中的同义词子表都很短，设有n 个关键码通过某一个散列函数，存放到散列表中的 m 个桶中。那么每一个桶中的同义词子表的平均长度为 n / m。以查找平均长度为 n / m 的同义词子表代替了查找长度为 n 的顺序表，查找速度快得多。 装填因子： 应用链地址法处理冲突, 需要增设链接指针, 似乎增加了存储开销。事实上, 由于线性探测和随机探测法都必须保持大量的空闲空间以确保查找效率，如随机探测法要求装填因子  0.5，而表项所占空间又比指针大得多，所以使用链地址法反而比线性探测法和随机探测法节省存储空间。 计算机软件技术基础 查找与排序

41 三、散列查找 ASL=总比较次数/记录个数；采用不同的解决冲突方法，平均查找长度也可能不同。
4）性能分析 ASL=总比较次数/记录个数；采用不同的解决冲突方法，平均查找长度也可能不同。 与线性查找、对分查找相比，ASL较小。但最坏情况的查找性能较差 平均查找长度是装填系数a的函数。适当选择a的值是很关键的。 计算机软件技术基础 查找与排序

42 4）性能分析 散列表的装填因子  表明了表中的装满程度。越大, 说明表越满, 再插入新元素时发生冲突的可能性就越大。
散列表的查找性能, 即平均查找长度依赖于散列表的装填因子, 不直接依赖于 n 或 m。 不论表的长度有多大, 我们总能选择一个合适的装填因子, 以把平均查找长度限制在一定范围内。 计算机软件技术基础 查找与排序

43 三、散列查找 用不同的方法溢出处理冲突时散列表的平均查找长度如图所示。 计算机软件技术基础 查找与排序

44 四、不同查找算法的比较 1.顺序查找 2.折半查找 3.分块查找 4.散列查找 查找效率低 对记录结构无要求，可在链表、顺序表上查找
查找效率高 只能在有序的顺序表上查找，不适用记录多变的表 3.分块查找 查找效率界于顺序查找和折半查找之间 对记录结构的要求也界于顺序查找和折半查找之间， 较适合大型文件的查找 4.散列查找 查找性能与文件中的记录数无关，只与其装填因子相关 最坏情况的查找性能不佳 计算机软件技术基础 查找与排序

45 小结 1、理解基本概念：关键字、ASL（平均查找次数） 2、掌握：线性查找、折半查找、哈希查找 3、了解：分块查找 计算机软件技术基础
查找与排序