数据结构之查找课件.ppt

1、数据结构,第八章 查找,第八章 查找,知 识 点 查找的基本概念 三种基本查找方法：顺序查找、二分查找和分块查找 树型查找的基本概念和查找算法 散列法、散列函数冲突的基本概念和解决冲突方法 难 点 二叉排序树查找 平衡树及平衡树的调整,要 求 熟练掌握以下内容： 三种基本查找方法的基本思想和算法 二叉排序树查找的基本思想和算法 散列法基本思想、散列函数的常用构造方法及解决冲突方法 了解以下内容： 平衡树及平衡树的调整 B-树查找,第八章目录,8.1 查找的基本概念 8.2 基本查找方法 8.3 树型查找 8.4 散列法 8.5 应用举例及分析 小 结 习题与练习,8.1 查找的基本概念,查找又

2、称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。,对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。 查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通

3、常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。,返回,8.2 线性表的查找,1。顺序查找(Sequential search) 基本思想：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。,顺序查找的线性表定义如下： Typedef struct rectype keytype key; itemtype item1 rectype;,顺序查找算法,int sequsearch (r, n, k) /*R1

4、N中存放N个元素*/ r0.key=k; i=n; while (ri.key!=k) i-; return(i); ,顺序查找算法分析,监视哨的作用 最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。 顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。,2.折半查找,折半查找又称二分查找(Birary search)。 假设记录在查找表R1n中按关键字排列有序。首先用k与查找表中间元

5、素的关键字比较，。,比较结果有三种可能： 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； 如果rm.key=k，查找成功，m所指的记录就是查找到的数据。,重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。,例：从下列序列中查找K=21的

6、记录,5 13 19 21 37 56 64 75 80 88 92,int binsearch(r, n, k) /*记录存储在r1n中 int low=1，hig=n， mid; while (low=hig) mid=(low+high)/2; if (rmid.key=k) return(mid); else if (rmid.keyk) low=mid+1; else hig=mid-1; return(0); ,折半查找的分析 折半查找的判定树 平均查找长度 ASL= log2(n+1)-1 查找成功时的最大查找长度为折半查找判定树的深度log2n +1， 查找不成功时的最大查找长

7、度也为折半查找判定树的深度log2n +1。,3.有序表的其它查找方法,斐波那契查找方法 插值查找法,8.2.3 分块查找,分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。 分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。 还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表按关键字值的递增顺序排列。,分块查找的算法分两步进行，首先确所查找的

8、结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。 例如线性表中关键字为:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如图8.1所示。,图8.1 线性表与索引表,索引表的定义,struct indexterm keytype key; int low, high; ; typedef struct indexterm indexMAXITEM; 这里的keytype可以是任何相应的数据类型，如

9、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 (lowidxmid.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.h

10、igh; while (ij) i=0; return(i); ,返回,分块查找的分析,设有n个的记录，均匀地分成b块，每块含有s个记录，即b=n/s，又设每个记录的查找概率相等，则每块的查找概率为1/b，块中每个记录的查找概率为1/s， 若用顺序查找确定记录所在的块，则分块查找的平均查找长度为 ASLsucc=（b+1）/2+（s+1）/2 =（n/s+s）/2 + 1 若用折半查找确定记录所在的块，则分块查找的平均查找长度为 ASLsucc log2（n/s+1）+ s/2,顺序查找、折半查找、分块查找的比较,顺序查找对查找表无任何要求，既适用无序表，又适用有序表，查找成功的平均查找长度为

11、(n+1)/2，时间复杂度为O(n)； 折半查找要求表中元素必须按关键字有序，其平均查找长度为近似(log2(n+1)-1)，时间复杂度为O(log2n)； 分块查找每块内的元素可以无序，但要求块与块之间必须有序，并建立索引表。,8.3 二叉排序树(BST) 二叉排序树或是一棵空树,或是具有下列性质的树: 若左子树非空, 则左子树上的所有结点都小于其根结点的值; 若右子树非空, 则右子树上的所有结点都大于其根结点的值; 左,右子树也都是一棵二叉排序树. 例,结点定义如下： Typedef struct node keytype key; itemtype others; struct node

12、 *lchild, *rchild; BSTree,8.3.1 二叉排序树查找,基本思想：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右子树继续查找。,树型查找是一种递归的查找过程。 在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下：,递归函数如下 btree search (BSTree *b, int k) if (b=NULL) return (NULL); else if(b-data=k) return (b); if(kdata)

13、 return (search (b-left, k); else return (search (b-right,k); ,非递归算法,btree treesearch (BSTree *b, int k) BSTree *p; p=b; while(p!=NULL); if (p-data=k) return (p); else if (kdata) p=p-left; else p=p-right; return (NULL); ,二叉排序树查找分析,树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与

14、二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。 为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。,图8.2 两个二叉排序树,在二叉排序树上插入结点,基本思想,插入结点的非递归算法,Void insertbst(BSTree *tptr,*s) /*tptr指向根 /*s指向要插入的结点 s-lchild=s-rchild=null; If (tptr=null) tptr=

15、s; return; else, p=tptr; While(p!=null) if (p-key=s-key) return; /*无需插入 q=p; /*q记录p的父亲 if (s-key key) /*寻找要插入的位置 p=p-lchild; else p=p-rchild; If ( s-keykey) /*至此,q指向的是 q-lchild=s; /*要插入结点s的父 else q-rchild=s; /*结点 ,在二叉排序树上删除结点,在二叉排序树中删除一个结点后，要使剩余的结点仍为二叉排序树。 设被删除的结点为P, 且P为F的左儿子（若为右儿子时，道理相同）。 P无儿子 删除P,

16、 修改有关指针 f-lchild=null,2. P只有一个儿子 设P只有左儿子Pl(或右儿子Pr), 只要令Pl （或Pr ）成为F的左儿子即可。 F-lchild=p-lchild 或 F-lchild=p-rchild,3. P有两个儿子时，有两种方法。设P的前驱为S. （1）令P的左子树成为F的左子树，P的右子树成为S的右子树。 F-lchild=p-lchild; r=p-rchild; /*r为临时变量 S=f-lchild; While(s-rchild != null) s=s-rchild; S=r; /*使P的右子树成为S的右子树,（2）使P的前驱S代替P,然后删除S. 若

17、S有左儿子，则用S的左儿子代替S的位置。 设Q为S的父亲。,q=p; S=p-lchild; While(s-rchild != null) q=s; S=s-rchild; /*找P左子树最右下方的结点S P-key=s-key; If (q!=p) q-rchild=s-lchild; Else q-lchild=s-lchild; /*当Q=P时，S即为P的左儿子，此时把S的左儿子作为P的左儿子,8.3.2 平衡树,平衡树(Balanced tree)也称为AVL树，是由阿德尔森维尔斯基和兰迪斯(Adelson-velskii and landis)于1962年首先提出的。 这是一种附加

18、了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（Balance factor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或-1，即任一结点的左、右子树高度之差不超过1。 如图8.3所示，图中数字为该结点的平衡因子。,平衡树,平衡二叉树,不平衡二叉树,假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加1，我们可能会遇到以下三种情况： (1) 如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0,插入新结点后将使平衡因子变成+1，但仍符合平衡树的条件，不必对其加以调整； 如果原来hlhr，即

19、原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡树的限制条件，需对其加以调整； 如果原来hlhr，即原来此结点的平衡因子等于-1，插入新结点后将使平衡因子变成0，平衡更加改善，不必加以调整。,如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加1，则也会遇到与之相对应的三种情况。 以图8.4所示的树为例，设原已有关键字为51，29，72，11和46这五个结点，原树符合平衡树条件，图中各结点旁所标数字为该结点的平衡因子。,图8.4 平衡树插入结点,插入新结点破坏了平衡树条件的情况分为两类，仍以向左子树插入新结点为例，这两类情况分别如图8.5（a）和(c

20、)所示。 图中矩形表示子树，矩形的高度表示子树的高度，带阴影线的方形则表示插入新结点后造成的子树高度加1，各结点旁所标数字为该结点的平衡因子。,图8.5 平衡树的调整,平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。 平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。 在插入新结点时，当确定了新结点应插入的位置后，需向回寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修

21、改。,8.3.3 B-树,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。 所有的叶子结点都在同一层上，并且不带任何信息.,图8.6 一棵4阶B-树,返回,1. B-树的查找 例,2. B-树的插入

22、 基本思想：在B-树中插入一个关键字K时，要先找到关键字K应插入的结点P。 若结点P中的关键字数小于m/2 -1 时，插入即可，否则，要把P分裂成两个结点 P 和 P。 分裂方法：把旧结点P中的关键字和要插入的关键字K按大小顺序分成三部分：中间部分只有一个关键字，左右部分的关键字数量相等或只差一个关键字。中间的关键字上移到父结点中，左右部分为两个新的结点 P 和 P 。 例：,3. B-树的删除 若删除的关键字在树的内部结点中，则可以和它的前驱（或后继）交换，再删除其前驱（或后继）。 所以，只讨论如何从末端结点中删除关键字的问题。 分三种情况： （1) 若该结点的关键字个数 大于m/2 -1

23、时，直接删除即可。 例：,(2) 若该结点的关键字个数 等于m/2 -1 ， 但左兄弟（或右兄弟）结点的关键字数大于m/2 -1 ，则可把左兄弟（右兄弟）中的最大的（最小的）关键字移至父结点中，将父结点中的有关关键字下移至该结点中。 例：,(3). 若该结点的关键字数、左兄弟（或右兄弟）结点的关键字数 都 等于m/2 -1 ，则要把该结点的左兄弟（或右兄弟）和其父结点中的有关关键字合并成一个新的结点。 例 ：,B+树 定义： 1. 若结点中有n棵子树，就有n个关键字； 2. 所有叶子结点中包含了全部关键字的信 息, 及指向下一个叶子结点的指针, 且叶子 结点中的关键字按大小排列； 3. 所有内

24、部结点可以看成索引部分，其中 仅含有子树中最大（小）的关键字. 例：,8.4.1 散列法,散列法就是也称为哈希查找(Hashed search)或杂凑法。 散列法的基本思想是将每个记录的地址与该记录的关键字之间建立某种函数关系，可直接由关键字查找到该记录，根据关键字求存储地址的函数称为散列函数，又称为哈希函数（Hashed Function），按散列存储方式构造的动态表又称散列表(hashed table)。,设有关键字为1，3，7，12，定义一个散列函数为： h(k)=k mod p 其中 k 为关键字， mod 取余数， p 为一整数。 若取 p=7，则 h(1)=1, h(3)=3, h

25、(7)=0, h(12)=5，,可能有不同的关键字计算出相同的函数值。 例如，h(1)=1，(15)=1 也就是不同记录占用同一地址单元，这种情况称为发生了冲突（collision）。 若 KiKj,但 H(Ki)=H(Kj),则称Ki和 Kj为同义词。 装填因子：记录数/表的长度,0,1,2,3,4,5,6,散列是一种重要的存储方法，又是一种查找方法。 应用散列法存储记录的过程是对每个记录的关键字进行散列函数的运算，计算出该记录存储的地址，并将记录存入此地址中。 查找一个记录的过程与存储记录的过程一样，就是对待查找记录的关键字进行计算，得到地址，并到此地址中查找记录是否存在。,8.4.2 散

26、列函数构造方法,1. 直接定址法：直接取关键字本身或者关键 字加上一个常数作为散列地址。 H(K)=K H(K)= a*K + b 2. 数字分析法：又称为数字选择法。适用于所有关键字事先都知道，并且关键字的位数比散列地址的位数多的情况，在这种情况下，可将各个关键字列出，分析它们的每一位数字，舍去各关键字取值比较集中的位，仅保留取值比较分散的位作为散列地址。,数字分析法例子,3.折叠法：折叠法是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。,4. 除留余数法：这是一种最简单也最常用的构造散列函数的方法，如 h(k) = k mod p （pm) m: 存放记录的表长 p :一般地,P应选则小于散列表长度的质数.,8.4.3 处理冲突的方法,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. 链地址法 把同