1、第八章 查找第八章 查找知 识 点查找的基本概念三种基本查找方法：顺序查找、二分查找和分块查找树型查找的基本概念和查找算法散列法、散列函数冲突的基本概念和解决冲突方法难 点二叉排序树查找平衡树及平衡树的调整第八章 查找要 求 熟练掌握以下内容：三种基本查找方法的基本思想和算法二叉排序树查找的基本思想和算法散列法基本思想、散列函数的常用构造方法及解决冲突方法 了解以下内容：平衡树及平衡树的调整B-树查找 第八章 查找8.1 查找的基本概念8.2 基本查找方法8.3 树型查找8.4 散列法8.5 应用举例及分析小 结习题与练习第八章 查找查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找
2、出相应的记录的操作。在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。第八章 查找对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为
3、衡量查找算法好坏的依据。返回第八章 查找 1。顺序查找(Sequential search)基本思想：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。第八章 查找顺序查找的线性表定义如下：Typedef struct rectype keytype key;itemtype item1 rectype;第八章 查找int sequsearch(r,n,k)/*n为线性表r中元素个数*/r0.key=k;i=n;while(ri.ke
4、y!=k)i-;return(i);第八章 查找此函数的主要运算时间是用于循环语句逐单元进行比较判断ri.key是否等于k，因此顺序查找的速度较慢，最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。第八章 查找折半查找又称二分查找(Birary search)，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。设
5、n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标 。2/)1(nm第八章 查找比较结果有三种可能：如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找；如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找；如果rm.key=k，查找成功，m所指的记录就是查找到的数据。第八章 查找重复
6、上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围了缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(logn)，对于较大的n显然较顺序查找速度快得多。第八章 查找5 13 19 21 37 56 64 75 80 88 92 第八章 查找int binsearch(r,n,k)int low=1，hig=n，mid;while(low=hig)mid=(low+high)/2;if(
7、rmid.key=k)return(mid);else if(rmid.keyk)low=mid+1;else hig=mid-1;return(0);第八章 查找斐波那契查找方法插值查找法第八章 查找分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。
8、索引表按关键字值的递增顺序排列。第八章 查找分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。例如线性表中关键字为:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如图8.1所示。第八章 查找 索引表 22 60 82 1 5 9 13 4 8 12 16 44 9 22 12 14 35 42 44 38 48 60 58 47 78 80 77 82 1
9、 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 线 性 表 第八章 查找struct indexterm keytype key;int low,high;typedef struct indexterm indexMAXITEM;这里的keytype可以是任何相应的数据类型，如int、float、或char等，在算法中，我们规定keytype缺省是int类型。第八章 查找int blksearch(sqlist r,index idx,int k,bn)/*bn为块的个数*/int i,j,mid,low=1,high=bn,find=0;while(low=hi
10、gh&!find)/*二分查找索引表*/mid=(low+high)/2;if(kidxmid.key)low=mid+1;else find=1;第八章 查找if(find=1)i=idxmid.low;j=idxmid.high;else if(lowbn)/*k小于索引表内最大值*/第八章 查找 i=idxlow.low;j=idxlow.high;while(ij)i=0;return(i);返回第八章 查找二叉排序树(BST):二叉排序树或是一棵空树,或是具有下列性质的树:1.若左子树非空,则左子树上的所有结点都小于其根结点的值;2.若右子树非空,则右子树上的所有结点都大于其根结点的
11、值;3.左,右子树也都是一棵二叉排序树.例第八章 查找 基本思想：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右子树继续查找。第八章 查找树型查找是一种递归的查找过程。在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下：第八章 查找递归函数如下btree*search(btree*b,int k)if(b=NULL)return(NULL);else if(b-data=k)return(b);if(kdata)return(search(b-
12、left,k);else return(search(b-right,k);第八章 查找btree*treesearch(btree*b,int k)btree*p;p=b;while(p!=NULL);if(p-data=k)return(p);else if(kdata)p=p-left;else p=p-right;return(NULL);第八章 查找在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到所查找结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到某个终端叶子结点的路径。与二分查找类似，和关键字比较的次数不超过二叉排序树的深度。但是，含有n个结点的
13、二叉树不是唯一的，由于对其结点插入的先后次序不同，所构成的二叉树的形态和深度也可能不同。例如，图8.2是按不同插入次序得到的两个二叉排序树。第八章 查找 45 24 53 12 37 100 12 45 24 100 53 37 在查找失败的情况下，在这二个树上所进行的关键字比较次数分别为3和6次。第八章 查找树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。为了保证
14、树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。第八章 查找基本思想第八章 查找Void insertbst(*tptr,*s)/*tptr指向根 /*s指向要插入的结点 s-lchild=s-rchild=null;If(tptr=null)tptr=s;return;else 第八章 查找 p=tptr;While(p!=null)if(p-key=s-key)return;/*无需插入 q=p;/*q记录p的父亲 if(s-key key)/*寻找要插入的位置 p=p-
15、lchild;else p=p-rchild;If(s-keykey)/*至此,q指向的是 q-lchild=s;/*要插入结点s的父 else q-rchild=s;/*结点 第八章 查找平衡树(Balanced tree)也称为AVL树，是由阿德尔森维尔斯基和兰迪斯(Adelson-velskii and landis)于1962年首先提出的。这是一种附加了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（Balance factor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或-1，即任一结点的左、右子树高度之差不超过1。如图
16、8.3所示，图中数字为该结点的平衡因子。第八章 查找平衡二叉树 1 1 1 1 0 0 0 -1 2 0 0 1 0 不平衡二叉树不平衡二叉树 第八章 查找假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加1，我们可能会遇到以下三种情况：(1)如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0,插入新结点后将使平衡因子变成+1，但仍符合平衡树的条件，不必对其加以调整；如果原来hlhr，即原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡树的限制条件，需对其加以调整；如果原来hlhr，即原来此结点的平衡因子等于-1，插入新结点后
17、将使平衡因子变成0，平衡更加改善，不必加以调整。第八章 查找如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加1，则也会遇到与之相对应的三种情况。以图8.4所示的树为例，设原已有关键字为51，29，72，11和46这五个结点，原树符合平衡树条件，图中各结点旁所标数字为该结点的平衡因子。第八章 查找 11 0 29 72 51 46 5+1 0 0 0 21 33 49 64 83 第八章 查找插入新结点破坏了平衡树条件的情况分为两类，仍以向左子树插入新结点为例，这两类情况分别如图8.5（a）和(c)所示。图中矩形表示子树，矩形的高度表示子树的高度，带阴影线的方形则表示插入新
18、结点后造成的子树高度加1，各结点旁所标数字为该结点的平衡因子。第八章 查找 AR BL BR(a)A+2+2 B BL AL AR(b)B A (BR)第八章 查找 BL AR CL CR C(c)+2-1 A B+1 AL AR BR R(CR)BL(CL)A B(d)C 第八章 查找平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。在插入新结点时，当确定了新结点应插入的位置后，需向回寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最
19、低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。第八章 查找B-树的定义：一棵m（m3）阶的B-树，或者为空树，或者是满足如下条件的m叉树：1.如果树非空，则根至少有1个关键字.2.除根结点外，每个结点中的关键字为 m/2-1 m-1.第八章 查找3.结点中含有以下内容：n,A0,K1,A1,K2,Kn,An 其中，n为关键字个数 Ki是关键字，Ai是指向子树的指针。关键字是递增的,即 Ki Ki+1,且Ai所指子树中所有结点的关键字均小于Ki+1，Ai+1所指子树中所有结点的关键字均大于Ki+1。所有的叶子结点都在同一层
20、上同一层上，并且不带任何信息.第八章 查找 2 40 55 61 1 16 1 9 1 28 1 36 1 66 1 32 3 42 a b h c d e f g t 64 返回第八章 查找1.B-树的查找 例 第八章 查找2.B-树的插入 基本思想基本思想：在B-树中插入一个关键字K时，要先找到关键字K应插入的结点P。若结点P中的关键字数小于m/2-1 时，插入即可，否则，要把P分裂成两个结点 P 和 P。分裂方法分裂方法：把旧结点P中的关键字和要插入的关键字K按大小顺序分成三部分：中间部分只有一个关键字，左右部分的关键字数量相等或只差一个关键字。中间的关键字上移到父结点中，左右部分为两个
21、新的结点 P 和 P。例：第八章 查找3.B-树的删除 若删除的关键字在树的内部结点中，则可以和它的前驱（或后继）交换，再删除其前驱（或后继）。所以，只讨论如何从末端结点中删除关键字的问题。分三种情况：（1)若该结点的关键字个数 大于大于m/2-1 时，直接删除即可。例：第八章 查找(2)若该结点的关键字个数 等于等于m/2-1，但左兄弟（或右兄弟）结点的关键字数大于m/2-1，则可把左兄弟（右兄弟）中的最大的（最小的）关键字移至父结点中，将父结点中的有关关键字下移至该结点中。例：第八章 查找(3).若该结点的关键字数、左兄弟（或右兄弟）结点的关键字数 都 等于等于m/2-1，则要把该结点的左
22、兄弟（或右兄弟）和其父结点中的有关关键字合并成一个新的结点。例：第八章 查找B+树 定义：1.若结点中有n棵子树，就有n个关键字；2.所有叶子结点中包含了全部关键字的信 息,及指向下一个叶子结点的指针,且叶子 结点中的关键字按大小排列；3.所有内部结点可以看成索引部分，其中 仅含有子树中最大（小）的关键字.例：第八章 查找散列法就是也称为哈希查找(Hashed search)或杂凑法。散列法的核心思想是将每个记录的地址与该记录的关键字之间建立某种函数关系，可直接由关键字查找到该记录，根据关键字求存储地址的函数称为散列函数，又称为哈希函数（Hashed Function），按散列存储方式构造的动
23、态表又称散列表(hashed table)。第八章 查找设有关键字为1，3，7，12，1，定义一个散列函数为：h(k)=k mod p 其中 k 为关键字，mod 取余数，p 为一整数。若取 p=7，则 h(1)=2,h(3)=4,h(7)=1,h(12)=6 第八章 查找可能有不同的关键字计算出相同的函数值。例如，h(1)=2，(15)=2 也就是不同记录占用同一地址单元，这种情况称为发生了冲突冲突（collision）。若 KiKj,但 H(Ki)=H(Kj),则称Ki和 Kj为同义词同义词。713120123456第八章 查找散列是一种重要的存储方法，又是一种查找方法。应用散列法存储记录
24、的过程是对每个记录的关键字进行散列函数的运算，计算出该记录存储的地址，并将记录存入此地址中。查找一个记录的过程与存储记录的过程一样，就是对待查找记录的关键字进行计算，得到地址，并到此地址中查找记录是否存在。第八章 查找1.直接定址法：直接取关键字本身或者关键 字加上一个常数作为散列地址。H(K)=K H(K)=a*K+b2.数字分析法：又称为数字选择法。适用于所有关键字事先都知道，并且关键字的位数比散列地址的位数多的情况，在这种情况下，可将各个关键字列出，分析它们的每一位数字，舍去各关键字取值比较集中的位，仅保留取值比较分散的位作为散列地址。第八章 查找 1 2 3 4 5 6 7 8 9 0
25、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3 1 1 9 9 8 6 7 6 8 1 2 9 3 4 4 4 1 1 1 6 3 2 5 2 4 4 4 3 3 3 3 5 1 0 9 3 4 1 6 7 8 9 5 3 6 0 9 位：第八章 查找3.折叠法：折叠法是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。第八章 查找4.除留余数法：这是一种最简单也最常用的构造散列函数的方法，如 h(k)=k mod p（pm)m:存放记录的表长 p 的选择很重要，若选择的不
26、好，可能产生太多的冲突。一般地,P应选则小于散列表长度的质数，或不包括小于20的质因数的合数。第八章 查找1.开放地址法：当插入的记录时，计算出来的地址已被其它记录占用时，要寻找其它尚未占用的单元。Hi(K)=(H(k)+di)%m (i=1,2,m)其中：H(k)为哈希函数 m为表长 di增量序列 di有两种选择方法：di=1,2,n (线性探测法)di=12,-12,22,-22,32,-32,k2 (km/2）（二次探测法)第八章 查找例：2.链地址法 把同义词都放在一个链表中。例：第八章 查找8.4.4 散列表的运算第八章 查找查找顺序查找二分查找分块查找树型查找平衡树散列法处理冲突的
27、方法开放地址法链接表法返回第八章 查找一、基础知识题1.解释下列名词(1)查找 (2)树型查找 (3)平衡因子(4)散列函数 (5)冲突2.设有序表为a,b,c,d,e,f,g，请分别画出对给定值f,g和h进行拆半查找的过程。3.试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种查找法对长度为n的表的等概率查找长度是多少？第八章 查找4.设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素15,27,50,73,49,61,37,60，试画出采用二次探测法处理冲突的散列表。5.线性表的关键字集合为113,12,180,138,92,67,94,134,2
28、52,6,70,323,60，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构。6.设关键字集合为27,49,79,5,37,1,56,65,83，散列函数为：H（k）=k mod 7，散列表长度m=10，起始地址为0，分别用线性探测和链接表法来解决冲突。试画出对应的散列表。第八章 查找二、算法设计题1.从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找。2.如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。第八章 查找3.试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。4.设给定的散列表存储空间为H1m，每个单元可存放一个记录，Hi(1im)的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突方法为线性探测法，编写一个函数将某记录R填入到散列表H中。返回
