软件技术基础第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）/2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。对确定的缩小区域再按二分公式，重复上述步骤；最后，得到结果：要么，查找成功，要么，查找失败。存储结构用一维数组存放。,第 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.htypedef 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 5 6 7 8,取67，计算 H（67）=3，冲突，解决冲突，得出：,第 47 页,哈希查找,哈希查找的过程和建立哈希表的过程是一致的。设哈希表为HST0M-1，哈希函数取H（key），解决冲突的方法为R（x），则哈希查找步骤为：Step1 对给定k值，计算哈希地址 Di=H（k）；若HSTi为空，则查找失败；若HSTi=k，则查找成功；否则，执行step2（处理冲突）。Step2 重复计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到HSTDk为空，或HSTDk=k为止。若HSTDk=K，则查找成功，否则查找失败。,第 48 页,查找举例,以上述哈希表为例。哈希函数为H(key)=key MOD 8,设有数列22,41,53,46,30,13,1,67,用线性探测法解决冲突,建立的哈希的表为:,0 1 2 3 4 5 6 7 8,比较次数：3 1 6 3 2 1 1 2,22,41,53,46,30,13,1,67,平均查找长度ASL=(3+1+6+3+2+1+1+2)=查找key=67 比较两次找到,查找成功;查找key=21 比较8次找不到,查找失败。,第 49 页,链地址法处理冲突,以上述数列为例，产生的哈希表为：,1234567,41,1,46,13,30,22,53,67,H(22)=H(46)=H(30)=6,H(53)=H(13)=5,H(67)=3,H(41)=H(1)=1,平均查找长度ASL=(1+1+1+1+2+2+2+3)=,第 50 页,思考题,1：长度为12的按关键字有序的查找表采用顺序组织方式，若采用二分查找法，则在等概的情况下，查找失败时的ASL值为？查找成功时的ASL值？答案：成功时：37/12；失败时：49/132、哈希表平均ASL的计算,