由于查找运算的使用频率很高解读课件.ppt

1、 由于查找运算的使用频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。在一些实时查询系统中尤其如此。因此，本章将系统地讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。一般，假定被查找的对象是由一组结点组成的一般，假定被查找的对象是由一组结点组成的表表(Table)或文件，而每个结点则由若干个数据或文件，而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该项组成。并假设每个结点都有一个能惟一标识该结点的关键字。结点的关键字。查找查找(Searching)的定义是：给定一个值的定义是：给定一

2、个值K，在在含有含有n个结点的表中找出关键字等于给定值个结点的表中找出关键字等于给定值K的结的结点。若找到，则查找成功，返回该结点的信息或点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关该结点在表中的位置；否则查找失败，返回相关的指示信息。的指示信息。1.动态查找表和静态查找表 若在查找的同时对表做修改操作(如插入和删除)，则相应的表称之为动态查找表。否则称之为静态查找表。2.内查找和外查找和排序类似，查找也有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。查找运算的主要操作是关键字的比较，所以

3、通常把查找过程中对关键字需要执行的 平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。（平均查找长度 ASL(Average Search Length)定义为：niiicpASL1n是结点的个数；Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即 pl=p2=pn=1/nci是找到第i个结点所需进行的比较次数。typedef int KeyType；/KeyType应由用户定义 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，

4、则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。（1）类型说明 typedef struct KeyType key；InfoType otherinfo；/此类型依赖于应用 NodeType；typedef NodeType SeqListn+1；/0号单元用作哨兵 int SeqSearch(Seqlist R，KeyType K)/在顺序表R1.n中顺序查找关键字为K的结点，/成功时返回找到的结点位置，失败时返回0 int i；R0.key=K;for(i=n；Ri.key!=K;i-)；/从表后往前

5、找 return i；/若i为0，表示查找失败，否则Ri是要找的结点 /SeqSearch 1 2 3+.+n=(1+n)/2约等于表长的一半找不到？n+11528329766145iiiiiii算法中监视哨算法中监视哨R0的作用的作用 为了在for循环中省去判定防止下标越界的条件i1，从而节省比较的时间。成功时的顺序查找的平均查找长度：成功时的顺序查找的平均查找长度：在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为 (n+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。若K值不在表中，则须进行n+1次比较之后才能确定查找失败。算法简单，但效率不高。1、二

6、分查找、二分查找(BinarySearch)二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。low high mid=(low+high)/2if(amid=k)表示找到121619 22 25 33 40 48 52 65 70 83lmhmlhmh二分查找的基本思想是:(设Rlow.high是当前的查找区间）（1）首先确定该区间的中点位置：mid=(high+low)/2;（2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二

7、分查找，具体方法如下：若Rmid.keyK，则由表的有序性可知Rmid.n.keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R1.mid-1中，故新的查找区间是左子表R1.mid-1。类似地，若Rmid.keyK，则要查找的K必在mid的右子表Rmid+1.n中，即新的查找区间是右子表Rmid+1.n。下一次查找是针对新的查找区间进行的。int BinSearch(SeqList R，KeyType K)/在有序表R1.n中进行二分查找，成功时返回结点的位置，失败时返回零 int low=1，high=n，mid；/置当前查找区间上、下界的初值 whil

8、e(lowK)high=mid-1;/继续在Rlow.mid-1中查找 else low=mid+1；/继续在Rmid+1.high中查找 return 0；/当lowhigh时表示查找区间为空，查找失败 /BinSeareh ASL=log2(n+1)n=10000条记录;ASL=5000次 log210000=1551218213545507890012345678432313234 2、分块查找的基本思想、分块查找的基本思想分块查找的基本思想是：（1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。（2）然后在已确定的块中进行顺序查找 由于块内无序，只能

9、用顺序查找。l s l/s(l/s+1)/2+(s+1)/2 y=(l/x+x)/2+120 0840 41260 119182820343043475452131315232533334555lls （1）平均查找长度ASL分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。以二分查找来确定块，分块查找成功时的平均查找长度 ASLblk=ASLbn+ASLsqlg(b+1)-1+(s+1)/2lg(n/s+1)+s/2以顺序查找确定块，分块查找成功时的平均查找长度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)动态查找 二叉排序树(Bi

10、nary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。由BST性质可得：（1）二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。（2）二叉排序树中，各结点关键字是惟一的。346573184232p=NULLf typed

11、ef int KeyType；/假定关键字类型为整数typedef struct node /结点类型 KeyType key；/关键字项 InfoType otherinfo；/其它数据域，InfoType视应用情况而定，下面不处理它 struct node*lchild，*rchild；/左右孩子指针 BSTNode；typedef BSTNode*BSTree；/BSTree是二叉排序树的类型 BSTree InsertBST(BSTree*Tptr，KeyType key)/若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回 BSTNode*f，*p=*TPtr；/p的初

12、值指向根结点 while(p)/查找插入位置 if(p-key=key)return p；/树中已有key，无须插入 f=p；/f保存当前查找的结点 p=(keykey)?p-lchild：p-rchild；/若keykey，则在左子树中查找，否则在右子树中查找 /endwhile p=(BSTNode*)malloc(sizeof(BSTNode)；p-key=key；p-lchild=p-rchild=NULL；/生成新结点 if(*TPtr=NULL)/原树为空 *Tptr=p；/新插入的结点为新的根 else/原树非空时将新结点关p作为关f的左孩子或右孩子插入 if(keykey)f-

13、lchild=p；else f-rchild=p；return NULL /InsertBST BSTree InsertBST(BSTree*root,int key)BSTree q;BSTree studTree;q=InsertBST(&studTree,23);if(q=NULL)printf(“插入成功n”);else printf(“该同学已经存在”);printf(“%d”,p-key,34235678289167822328345667788291log2n退化二叉树 Hash(哈希查找）1、散列表、散列表 设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)

14、的关键字集合记为K（|K|比|U|小得多）。散列方法是使用函数h将U映射到表T0.m-1的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。其中：h：U0，1，2，m-1，通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。T为散列表(Hash Table)。h(Ki)(KiU)是关键字为Ki结点存储地址(亦称散列值或散列地址)。将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)有10个学生记录，他

15、们的学号为 8780001 8780002 8780003 8780004 8780005 8780006 8780007 8780008 8780009 8780010 要存放在一个10个元素的一维数组里，如何存放，取出来比较方便01012342656067298942单元序号=学号-87800018780009 有10个，他们的学号为 8780001 8780002 8780003 8780004 8780005 8780006 8780007 8780008 8780009 8780010 要存放在一个一维数组里，如何存放，取出来比较方便 暂定：27日（星期日上午）307，303，305

16、，207。有10个，他们的学号为 01 06 13 17 26 29 40 20 60 56 h(k)=19%20 要存放在一个一维数组里，如何存放，取出来比较方便 一维数组只有7个元素怎么办？（1）冲突 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。【例】上图中的k2k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。找一个比较好的Hash函数 一个碰撞机机率尽可能少，碰撞肯定会发生。尽可能分散如何解决碰撞 最理想的解决冲突的方法是安全避免冲突。要做到

17、这一点必须满足两个条件：其一是|U|m其二是选择合适的散列函数。这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。通常情况下，h是一个压缩映像。虽然|K|m，但|U|m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填人的结点数，则将=n/m定义为散列表的装填因子(Load Factor)。越大，表越满，冲突的机会也越大。通常取1。1、散列函数的选择有两条标准：简单和均、散列函数

18、的选择有两条标准：简单和均匀。匀。简单指散列函数的计算简单快速；均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集0，1，m-1上，以使冲突最小化。为简单起见，假定关键字是定义在自然数集合上。具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。1 2 3 4 5 1 4 9 16 25【例】将一组关键字(0100，0110，1010，1001，0111)平方后得 (0010000，0

19、012100，1020100，1002001，0012321)若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。相应的散列函数用C实现很简单：int Hash(int key)/假设key是4位整数 key*=key；key/=100；/先求平方值，后去掉末尾的两位数 return key1000；/取中间三位数作为散列地址返回 该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=keym 该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数 取m大于表长的最小质数 表长

20、10 m=11 m=17【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，等均互为同义词。该方法包括两个步骤：首先用关键字key乘上某个常数A(0A1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：该方法最大的优点是选取m不再像除余法那样关键。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 该函数的C代码为：int Hash(int key)double

21、 d=key*A；/不妨设A和m已有定义 return(int)(m*(d-(int)d)；/(int)表示强制转换后面的表达式为整数 23(32)2512(15)选择一个随机函数，取关键字的随机函数值为它的散列地址，即 h(key)=random(key)其中random为伪随机函数，但要保证函数值是在0到m-1之间。通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T0.m-1中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T0.m-1中。（1）开放地址法解决冲突的方法 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。