软基课件第二章查找

1、NO：1第二章 常用数据结构及其运算一、查找的基本概念2.7 查找 关键字1）主关键字：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。2）次关键字：用来标识若干记录的数据项称为次关键字。 查找给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。 NO：2第二章 常用数据结构及其运算2.7 查找 平均查找长度由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即统计意

2、义上的数学期望值来评估查找算法，称为平均查找长度（ASL）：其中，n是文件中记录的个数，Pi是查找第i个记录的查找概率，通常我们认为每个记录的查找概率相等，即Pi=1/n；Ci是找到第i个记录时所经历的比较次数。NO：3第二章 常用数据结构及其运算二、线性查找2.7 查找线性查找又称顺序查找，是一种最简单的查找方法。 基本思想从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。NO：4第二章 常用数据结构及其运算2.7 查找 算法描述int SeqSearch(int r,int n,int k)rn.key=k; i

3、=0;while (ri.key!=k) i+;return(i);说明：若返回n表明查找不成功。链式存储结构： p=h-next; while (p!=NULL) & (p-key!=k) p=p-next; return p;NO：5第二章 常用数据结构及其运算2.7 查找 性能分析等概率情况下，Pi=1/n，Ci=i，所以：NO：6第二章 常用数据结构及其运算三、对分查找2.7 查找又称折半查找，是对有序表进行的一种查找。 基本思想先找到“中间记录”，比较其关键字，如果关键字与给定值K相等，则查找成功；如果关键字x小于给定值K，则说明被查找记录必在前半区间内；反之则在后半区间内。这样把搜

4、索区间缩小了一半，继续进行查找。NO：7第二章 常用数据结构及其运算2.7 查找 算法描述int BinSearch(int r,int n,int k)int low=0，hig=n-1;while (low=hig)mid=(low+hig)/2;if (k=rmid) return(1);if (krmid) low=mid+1;return(0);请看例子：5 13 17 42 46 55 70 94low mid higk=555 13 17 42 46 55 70 94 low mid hig5 13 17 42 46 55 70 94low mid hig5 13 17 42 4

5、6 55 70 94hig low5 13 17 42 46 55 70 94low mid higk=125 13 17 42 46 55 70 94low mid hig查找成功查找失败NO：8第二章 常用数据结构及其运算2.7 查找 性能分析1）对分查找的判定树：在查找过程中，各记录的比较次数与待查记录在文件中的相对位置有关，我们把比较次数相同的记录关键字放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为判定树。如上图：429455704613175序列：5,13,17,42,46,55,70,94的判定树NO：9第二章 常用数据结构及其运算2.7 查找 借助对分查找判定树，很容

6、易求得对分查找的平均查找长度。 对分查找的过程恰是走了一条从根结点到被查记录所在结点的一条路径。它与关键字的比较次数即为该结点所在的层次数。判定数是一棵接近满二叉树，对于满二叉树的结点n与深度h满足 n=2h-1(判定树 n2h-1),取h=log2(n+1),第k层上结点个数最多为2k-1429455704613175NO：10等概率下的平均查找长度为：第二章 常用数据结构及其运算2.7 查找可以用归纳法证明:NO：11第二章 常用数据结构及其运算2.7 查找 对分查找的优点是平均查找长度小，缺点是要求表中的元素按关键字排序。在n很小时(ndata) return(1); if (kdata

7、) q=p; p=p-lchild; if (kp-data) q=p; p=p-rchild; s=GetNode(); if (!s) return(0);s-data=k; s-lchild=s-rchild=NULL;if (t=NULL) p=s;else if (kdata) q-lchild=s; else q-rchild=s;return(0);NO：17第二章 常用数据结构及其运算2.7 查找如果二叉排序树已经存在，只是进行查找，则算法可写成：int BstSearch(NODE *t,int k) if (t)if (k=p-data) return(1);if (kda

8、ta) BstSearch(t-lchild,k);if (kp-data) BstSearch(t-rchild,k); else return(0);NO：18 性能分析1）相同的记录，由于插入的先后次序不同，所以生成的二叉排序树也不同，而且平均查找长度也可能不同。如图所示：第二章 常用数据结构及其运算2.7 查找2038032176548（20, 8, 6, 17, 54, 32, 3, 80）ASL=(1*1+2*2+4*3+4*1)/8=2.65432802086173（54, 32, 20, 8, 17, 6, 80, 3）ASL=(1+2*2+3+4+5*2+6)/8=3.5NO

9、：19第二章 常用数据结构及其运算2.7 查找在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。 最坏情况下，二叉排序树是通过把有序表的n个结点依次插入生成，所得到的二叉排序树蜕化为一棵深度为n的单支树，平均查找长度和单链表的顺序查找相同，为(n+1)/2 最好情况下，生成的二叉排序树比较匀称，得到与二分查找判定树相似的二叉排序树，平均查找长度约为 log2nNO：20第二章 常用数据结构及其运算六、哈希表技术及其查找2.7 查找 哈希表1）基本思想：通过对给定值作某种运算，直接求得关键字等于给定值的记录的位置。2）概念：设关键字key与存储位置间的对应关系为H(key)，若用一维数组

10、来存放文件，则H(key)即为数组的下标。我们称函数H为哈希(Hash)函数，H(key)为哈希地址（或散列地址），这个一维数组称为哈希表。NO：21第二章 常用数据结构及其运算2.7 查找3）有关问题： 哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较。 为提高查找效率，哈希表的空间m要比记录个数n大，定义a=n/m为装填系数（有时也叫装填因子），实际应用中一般取：0.650.85。 为求得哈希地址，有时须对关键字进行算术或逻辑运算，若关键字为非数值型，NO：22第二章 常用数据结构及其运算2.7 查找可先转化为数值，称为关键字的内部码。而且求得的哈希地址的值域必须在哈希表

11、长的范围内。 若某个哈希函数对不同的关键字得到相同的哈希地址，这种现象称为冲突，这些关键字称为同义词。实际应用中，冲突一般不可避免，应寻找解决冲突的方法。所以，运用哈希技术进行查找，要解决两个问题：哈希函数的构造和解决冲突。NO：23第二章 常用数据结构及其运算2.7 查找 构造哈希函数的几种方法1）数字分析法：适合静态数据，关键字已知,分析数字的分布，删除不均匀的数字，再根据存储空间的大小决定数字的数目。例如有7个学生的学号为： No.123456789 542422241542813678542228171542389671542541577542885376542193552分析知：第1

12、, 2, 3位分布太不均匀，删去；第8位出现的7太多，删去。设存储空间为1000，则可取第4, 6, 7位作为关键字的存储地址，分别为：422，836，281，396，515，853，135太集中NO：24第二章 常用数据结构及其运算2.7 查找2）平方取中法：先将关键字平方(扩大差别)，再选取其中几位作为哈希地址。例如有一组关键字为：(0100,1100,1200,1160,2060,2061,2163,2261,2262)设存储空间为1000，将关键字平方后再取第2,3,4位构成哈希地址为：(010,210,440,345,243,247,678,112,116)。3）除留余数法：对关键字

13、取模（余数）作为哈希地址，即：H(key)=key % p其中p必须是小于或等于表长的质数。NO：25第二章 常用数据结构及其运算2.7 查找4）折叠法：将关键字分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。折叠时有两种方法：移位折叠和边界折叠。如关键字值为：12320324111220，分为5段：123,203,241,112,20，两种折叠法分别如下：123 123203 302241 241112 211 20 20 879 897字段左靠齐后相加偶数字段倒排后相加NO：26第二章 常用数据结构及其运算2.7 查找 解决冲突的方法1）线性探测再散列设线性表的空间

14、为Tm，哈希函数为H(key)，冲突时求另一个记录的地址公式为：dj+1=(d1+j) % m (j=1,2,s,s1)其中d1=H(key)。 线性探测再散列是把哈希表作为一个环状空间，当冲突发生时，以线性方式从下一个哈希表地址开始探测，直到查到一个空的存储地址，将NO：27第二章 常用数据结构及其运算2.7 查找数据存入。若找完一个循环还没有找到空间，则表示地址已满。查找算法如下：LineSearch(T,k,m)i=H(k); j=i;while (Tj.key!=k & Tj.key!=0)j=(j+1)%m;if (j=i) 表满；return(-1);return(j);若Tj.k

15、ey=0表示此地址为空。说明：这种方法易造成关键字聚集，增加查找时间。NO：28第二章 常用数据结构及其运算2.7 查找2）平方探测再散列本方法是用来改善线性探测的缺点，避免相近的关键字聚集在一块。冲突时求地址公式为：3）随机探测再散列本方法是用一组预先给定的随机数求冲突时求地址，公式为： d2j=(d1+j2) % m (j=1,2,s,s1) d2j+1=(d1-j2) % mNO：29第二章 常用数据结构及其运算2.7 查找dj=(d1+Rj) % m (j=1,2,.,s,s1)其中Rj为一组随机数列。下面看一个例子：设有一组关键字为：(13,29,01,23,44,55,20,84,

16、27,68,11,10,79,14)n=14，选取a=0.75, 则哈希表长m=19，哈希表为T0.18，用除留余数法构造哈希函数，选质数p=17，分别用三种方法解决冲突。其中随机数序列为：3,16,55,44,.NO：30第二章 常用数据结构及其运算2.7 查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18K=13，addr=13%17=13，填入13K=29，addr=29%17=12，填入29K=01，addr=01%17=1，填入01K=23，addr=23%17=6，填入23K=44，addr=44%17=10，填入44K=55，addr

17、=55%17=4，填入55K=20，addr=20%17=3，填入20K=84，addr=84%17=16，填入84K=27，addr=27%17=10，冲突 addr=10+1=11， 填入27K=68，addr=68%17=0，填入68K=11，addr=11%17=11，冲突 addr=11+1=12， 冲突 addr=11+2=13， 冲突 addr=11+3=14， 填入11K=10，addr=10%17=10，冲突 addr=10+1=11， 冲突 addr=10+2=12， 冲突 addr=10+3=13， 冲突 addr=10+4=14， 冲突 addr=10+5=15， 填入

18、10K=79，addr=79%17=11，冲突 addr=11+1=12， 冲突 addr=11+2=13， 冲突 addr=11+3=14， 冲突 addr=11+4=15， 冲突 addr=11+5=16， 冲突 addr=11+6=17， 填入79K=14，addr=14%17=14，冲突 addr=14+1=15， 冲突 addr=14+2=16， 冲突 addr=14+3=17， 冲突 addr=14+4=18， 填入14线性探测：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)线性Hash表的填入是不顾后效的，平均查找长度不依赖于表长，而是跟表的填满率有关。同理可用其它两种方法解决，只不过公式不同。NO：31第二章 常用数据结构及其运算2.7 查找4）链地址法若哈希表为T0.m-1，设置一个由m个指针分量组成的一维数组ST0.m-1，凡哈希地址为i的记录都插入到头指针为STi的链表中。链地址法是个动态结构，所以更适合在造表之前无法确定记录个数的情况。NO：32第二章 常用数据结构及其运算2.7 查找查找算法如下：ChnSearch(ST,m,k)i=H(k); p=STi;while (p & p-data!=k) p=p-next;r