软件技术基础第03章查找.ppt

第 1 页,思考问题,数据存放在计算机中如何查找？ 查找方法有所不同吗？不同方法的查找效率有区别吗？ 基本的查找方式有几种？,第 2 页,教学目标,了解有关查找的 基本概念 查找的主要算法,第 3 页,教学要求,通过本单元的学习，了解、掌握有关查找的： 基本概念 查找、平均查找长度 主要查找算法 顺序查找、折半查找、分块查找 哈希查找,第 4 页,本单元涉及的内容,第3章 3.1 基本的查找技术 3.2 哈希表技术,第 5 页,一、基本概念,查找 查找表 静态查找 动态查找 平均查找长度,第 6 页,查找,查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。 查找表 是一组待查数据元素的集合。 静态查找 是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。 动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。,第 7 页,平均查找长度,平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。 它是用来评价一个算法好坏的一个依据。 对含有n个数据元素的查找表，查找成功时的平均查找长度为：,其中：Pi 为查找表中第i个数据元素的概率，且,Ci为查找到第i个数据元素时需进行比较的次数。 显然，Ci随查找过程及DS的不同而各异。,第 8 页,基本的查找技术,顺序查找 折半查找 分块查找,第 9 页,1.顺序查找,算法思想： 最古老的算法。从第1个元素到最后1个元素，逐个进行比较。 查找表的存储结构 既适用于顺序存储结构 也适用于链式存储结构 算法描述 算法讨论,第 10 页,算法描述,查找操作步骤： step1 从第1个元素开始查找； step2 用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。,第 11 页,顺序查找算法,seq_search(int *item ,n , key ) int i=0 ; while ( i n ,第 12 页,顺序查找算法（改进算法）,seq_search_adv(int *item ,n , key ) int i=0 ; itemn=key ; /* 设置哨兵 */ while ( itemi!= key ) i+; /* 查找key */ if ( i n ) /* 如果 i = n，没找到 */ printf(“查找成功 !n”); return (i); else printf(“查找失败 !n”); return (-1); 注: 设置哨兵目的在于免去查找过程中每一步都要检测整个表是否查完 顺序查找算法中,执行频率最高的是while语句,改进后,可以节省近一半的时间,第 13 页,顺序查找算法主程序,#include “stdio.h” #define n 7 main() int key,loc=0; int a10=43,15,21,37,2,5,82; printf(“Input key:”); scanf(“%d”, ,第 14 页,算法讨论,平均查找长度ASL在等概率的情况下,平均查找长度ASL在等概率的情况下,优点: 对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求；当序列中的记录“基本有序”或N值较小时，是较好的算法； 缺点： ASL较长 讨论：能否减少比较次数，以提高效率。,例如，,二分法等,第 15 页,2.折半查找,算法思想： 将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 即通过一次比较，将查找区间缩小一半。 二分查找的先决条件是查找表中的数据元素必须有序。,第 16 页,算法描述,算法步骤： step1 首先确定整个查找区间的中间位置， mid = （ left + right ）/ 2 step2 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功； 若大于，则在后半区域继续进行二分查找； 若小于，则在前半区域继续进行二分查找。 对确定的缩小区域再按二分公式，重复上述步骤； 最后，得到结果： 要么，查找成功， 要么，查找失败。 存储结构 用一维数组存放。,第 17 页,折半查找算法举例,对给定数列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关键字值为30的数据元素。,第二次： 23，28，30，32，50 ,mid1= （1+10）/2 = 5,mid2 = （6+10） /2 = 8,第 18 页,折半查找算法,bin_search ( item , n ,key ) int *item, n, key; int left ,right , mid; left=0; right = n-1; while ( left right ) mid = ( left + right )/2 ; /* 计算中点位置 */ if ( key itemmid) left = mid + 1; /* 待查区间在右部 */ else printf ( “ Successful searchn”); return mid ; /* 查找成功 */ printf( “ Search failure n”); return -1; /* 查找失败 */ ,第 19 页,折半查找算法的主程序,#define “stdio.h” int num; main( ) int res, key ; int s10=1,3,5,7,9,11,13，15，17，19，21，23; res=b_search(s,12,7); if(res0) printf(“res=%d , num=%dn“,res+1,num); else printf(“search failuren”); ,第 20 页,算法分析,优点: ASL log2n;即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。 缺点：因要求有序，所以对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不大便利。 考虑： 能否一次比较抛弃更多的部分（即一次比较，使查找范围缩得更小），以达到提高效率的目的； ？,把两种方法（顺序查找和二分查找）结合起来，即取顺序查找简单和二分查找高效之所长，来达到提高效率的目的？,第 21 页,3.分块查找,分块查找又称索引顺序查找，这是顺序查找的一种改进方法。 方法描述： 将n个数据元素“按块有序”划分为m块（m n）。 每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，。每个块中元素不一定是有序的。,第 22 页,分块查找算法描述,step1 先选取各块中的最大关键字构成一个索引表； step2 查找分两个部分： 先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中； 在已确定的块中用顺序法进行查找。,第 23 页,分块查找举例,有数列如下： 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 按“块有序”分三块:(22,12,13,9,8),(33,42,44,38,24), (48,60,58,74,47)。选取每块中最大的关键字组成索引表22,44,74,查找关键字值为60的元素。 用二分法，确定在索引表中的位置为 mid=2，key值60与a2比较，60a2,取第3个块;在第3块中用顺序法查找,比较两次,就可以找出60的元素来。,第 24 页,索引表结构定义,#include “stdio.h“ typedef struct int key; /* 块最大值 */ int link; /* 指向块入口地址 */ index;,第 25 页,index_seq_search.c子函数,index_seq_search(index ls,int s,int m,int key,int l) int i,j; i=0; while(ilsi.key) i+; /* 确定在哪块查找 */ if(i=m) printf(“ Searching failuren“); return(-1); else /* 否则，查找成功处理 */,第 26 页,分块查找子函数（续）, j=lsi.link; /* 块入口地址 */ while (key !=sj /* 结束 */,第 27 页,分块查找主函数,main() index ls5= 14,0,34,5 ,66,10,85,15,100,20 ; int a=8,4,3,2,14, 34,20,17,28,29 ,58,61,59,66,48, 81,80,79,83,69,89,100,96,86,87; int i,j=0,key; for(i=0;i25;i+) if (j=0) printf(“ “); if (j=5) printf(“ “); j=0; printf(“ “); printf(“%4d“,ai); j+; printf(“ n“); printf(“Enter key: “); scanf(“%d“, ,第 28 页,算法讨论,设索引表使用二分法，则有： ASL log2（n/S +1）+ S/2 其中：n为表长，S为块长（假设各块长度相等）。 优点： 插入、删除操作方便；只要找到对应的块，在块中任意位置操作均可。 缺点： 索引表增加了辅助存储空间。 注： 索引表在数据库系统中广泛使用。 还有什么方法吗？,树表查找,第 29 页,二、哈希（hash）表技术,哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方法都是把查找建立在比较的基础上，而哈希查找则是通过计算存储地址的方法进行查找的。 计算是计算机的特点之一，因此，建立在计算基础上的哈希查找是一种快速查找方法。,第 30 页,哈希查找的基本概念,哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对数据元素的快速检索。 哈希函数 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为： Addr = H（key） 建立哈希函数的原则 均匀性 H（key）的值均匀分布在哈希表中； 简单 以提高地址计算的速度。,第 31 页,哈希函数常用的构造方法,数字分析法 平方取中法 折叠法 除留余数法（求模取余法） 直接定址法,第 32 页,数字分析法,当关键字的位数比存储区地址码位数多时，可合理选择关键字的某几位组成的哈希地址。 选取的原则：尽量避免计算出的地址有冲突。 举例：学校的电话号码是7位十进制数，学校的程控交换机是3000门。但经分析不难得出： 0XXX 266 8XXX 9XXX 前3位是相同的，第4位分别为“0、8、9”，这样一来，正好可以表示3000个不同的电话号码。 H（KEY）= Right（telnum，4）,第 33 页,平方取中法,取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不知道关键字的全部情况，取其中的哪几位也不一定合适，在这种情况下，取一个数平方后的中间几位数作哈希地址。取的位数由表长决定。 例如，3288，平方后是“10810944”，取后4位为哈希地址，即“0944”。,第 34 页,折叠法,将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 关键字位数很多，且每一位上数字分布大致均匀时，可采用折叠法。 举例：某资料室藏书近万册。采用国际标准图书编号（ISBN），每个编号10位十进制数字。可用折叠法构造一个4位数的哈希函数。 例如： 书号为： 0 - 4 4 2 - 2 0 5 8 6 - 4 5 8 6 4 4 2 2 0 H（key）= 0088 0 4,+）,1 0 0 8 8,第 35 页,除留余数法（求模取余法）,取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。 H（key） = key MOD p 这是一种最简单，也是最常用的构造哈希函数的方法。 举例，32834872 ，哈希表长为4位十进制数。 P值可取小于9999的数，例如，取5000； H（KEY）= 32834872 MOD 5000 = 4872 由经验得知：通常选p为小于哈希表长的最大素数。,第 36 页,直接定址法,取关键字或关键字的某个线性函数值为哈希地址，即： H（key） = key H（key） = a * key + b （a，b为常数） 例如： 在1100岁的人口统计表中，年龄作为关键字，哈希函数取关键字本身。 再如： 解放后出生人口统计表中，年份作为关键字，哈希函数取为： H（key）= key +（ -1948）,第 37 页,选择哈希函数的标准,哈希函数计算所需要的时间 关键字的长度 哈希表的长度 关键字的分布情况 记录的查找频率,第 38 页,冲突及冲突处理,在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1 K2， 但哈希函数值 H（K1）= H（K2）。 均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。 处理冲突是建立哈希表过程中不可缺少的一部分。 处理冲突有两种方法： 开放地址法 链地址法,第 39 页,处理冲突 - 开放地址法,当发生地址冲突后，求解下一个地址用 Hi =( H（key）+di） MOD m i=1,2,k(k m-1) 其中: H(key)为哈希函数,m为哈希表长度,di为增量序列。增量序列的不同取法，又构成不同的开放地址法。 线性探测再散列 di=1,2,m-1 二次探测再散列,di=12 , -12, 22, -22, ,+k2, -k2(k m/2),第 40 页,处理冲突 - 链地址法,当发生地址冲突后,将所有函数值相同的记录连成一个单链表。,第 41 页,哈希查找操作步骤,用给定的哈希函数构造哈希表 根据选择的冲突处理方法解决地址冲突 在哈希表的基础上执行哈希查找,第 42 页,建立哈希表,建立哈希表操作步骤： step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。,第 43 页,举例,对给定数列 22,41,53,46,30,13,1,67 ,建立哈希表。表长取9,即08。哈希函数设定为: H(key) = key MOD 8 ,用线性探测解决冲突 Hi=(H(key)+di) MOD m ,di=1,2,m-1。 取22，计算H（22）=6，该地址空，可用；,0 1 2 3 4 5 6 7 8,22,22,0 1 2 3 4 5 6 7 8,41,比较次数： 1 1,取41，计算H（41）=1，该地址空，可用；,第 44 页,举例（续一）,取53，计算 H（53）= 5，该地址空，可用；,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,0 1 2 3 4 5 6 7 8,比较次数： 1 1 1,比较次数： 1 1 1 2,取46，计算 H（46）= 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8 = 7，该地址空，可用；,第 45 页,举例（续二）,取30，计算 H（30）= 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8 = 7， 该地址冲突，再用线性探测法计算下一个可用地址；Hi=0，地址空，可用；,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,0 1 2 3 4 5 6 7 8,比较次数： 3 1 1 1 2,比较次数： 3 1 6 1 1 2,46,30,30,13,取13，计算 H（13）= 5，依法解决冲突，得出：,第 46 页,举例（续三）,取1，计算 H（1）= 1，该地址冲突，解决冲突可得：,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,46,30,30,13,比较次数： 3 1 6 3 1 1 2,1,13,1,67,比较次数： 3 1 6 3 2 1 1 2,0 1 2 3 4