查找和内部排序

《查找和内部排序》由会员分享，可在线阅读，更多相关《查找和内部排序（78页珍藏版）》请在金锄头文库上搜索。

1、数据结构考研辅导-第四讲查找和排序,1 查 找,1.1 查找的基本概念,1.2 顺序查找和折半查找,1.3 B-树,1.4 计算式查找法哈希法,查 找,1.1 查找的基本概念,列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。,关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。,主关键字：如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。,查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。,在查找算法中要

2、用到三类参量，即： 查找对象K（找什么） 查找范围L（在哪找） 查找的结果（K在L中的位置） 其中、 为输入参量，在函数中不可缺少。 为输出参量，可用函数返回值表示。,平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。,对于长度为n的列表，查找成功时的平均查找长度为：,其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。,1.2 基于线性表的查找法,具有顺序查找法、折半查找法和分块查找法三种,1.2.1 顺序查找法,顺序查找法的特点是：用所给关键字与线性表中各元素的关键

3、字逐个比较，直到成功或失败。,存储结构：,顺序结构,链式结构,顺序结构有关数据类型的定义：,#define LIST_SIZE 20 typedef struct KeyType key;OtherType other_data; RecordType; typedef struct RecordType rLIST_SIZE+1; /* r0为工作单元 */int length; RecordList;,设置监视哨的顺序查找算法,int SeqSearch（RecordList l, KeyType k） /*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否

4、则为0*/ l.r0.key=k; i=l.length;while (l.ri.key!=k) i-;return（i）; ,其中l.r0为监视哨，可以起到防止越界的作用。,不设置监视哨的顺序查找算法,int SeqSearch（RecordList l, KeyType k） /*不用监视哨法，在顺序表中查找关键字等于k的元素*/ i=l.length;while (i=1 ,循环条件i=1判断查找是否越界。,用平均查找长度分析顺序查找算法的性能。,假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序

5、查找算法的平均查找长度为：,时间复杂度为O(n),1.2.2 折半查找法（二分法查找法）,条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。,基本过程：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,例如用折半查找法查找10、50的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。,用折半查找法查

6、找12的过程为：,用折半查找法查找50的过程：,折半查找的算法如下：,int BinSrch （SqList l, KeyType k）/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/ low=1 ; high=l.length; /*置区间初值*/while ( low=high)mid=(low+high) / 2;if (k=l.rmid. key) return（mid）;/*找到待查元素*/else if (kl.rmid. key) high=mid-1;/*未找到，则继续在前半区间进行查找*/else low=mid+1; /*继续在后半区间

7、进行查找*/return (0); ,用平均查找长度分析折半查找算法的性能,折半查找成功时的平均查找长度为：,优点：比较次数少，查找速度快，平均性能好。 缺点：要求待查的表为有序表，且插入、删除困难。时间复杂度为O(log2n),1.3 B-树 要了解二叉排序树的概念,1. m路查找树（ m叉排序树）,定义：一棵m路查找树，或者是一棵空树，或者是满足如下性质的树：,1)结点最多有m棵子树，m-1个关键字，其他结点最少有m/2个孩子结点其结构如下：,其中n为关键字个数，Pi为指向子树根结点的指针，0in，Ki为关键字，1in,2）KiK i+1，1in-1,3）子树Pi中的所有关键字均大于Ki、

8、小于Ki+1，1in-1,4）子树P0中的关键字均小于K1，而子树Pn中的所有关键字均大于Kn,5）子树Pi也是m路查找树，0in。,从定义可以看出，对任一关键字Ki而言，Pi-1相当于其“左子树”，P i相当于其“右子树”，1in 。 如下图示(一棵3路查找树),2. B_树及其查找,一棵B树是一棵平衡的m路查找树，它或者是空树，或者是满足如下性质的树：,（1）树中每个结点最多有m棵子树； （2）根结点至少有两棵子树； （3）除根结点之外的所有非叶结点至少 m/2 有棵子树； （4）所有叶结点出现在同一层上，并且不含信息，通常称为失败结点。失败结点为虚结点，在B树中并不存在，指向它们的指针为

9、空指针。引入失败结点是为了便于分析B树的查找性能。,二.B-树的插入 在B-树上插入关键码是在最底层的某个非终端结点中添加一个关键码。添加分两种情况： 1. 若添加后结点上关键码个数小于等于m-1，则插入; 2若添加后，该结点上关键码个数为m个，因而使该结点的子树超过了m棵，这与B-树定义不符，所以要进行调整，即结点的“分裂”。结点的“分裂”方法为：关键码加入结点后，将结点中的关键码分成三部分，使得前后两部分关键码个数均大于等于m/2，而中间部分只有一个结点。前后两部分成为两个结点，中间的一个结点将其插入到父结点中。若插入父结点而使父结点中关键码个数为m个，则父结点继续分裂，直到插入某个父结点

10、，其关键码个数小于m。可见，B-树是从底向上生长的。,一棵三阶B-树上的插入,三.B_树的删除分两种情况：1. 删除最底层结点中关键码(1) 若结点中关键码个数大于m/2 1，直接删去。(2) 若结点中关键码个数等于m/2 1，删除后结点中关键码个数小于m/2 1，不满足B-树定义，需调整。也有两种情况：a) 被删关键字所在结点含有m/2 1个，其兄弟 m/2 1也就是将兄弟中的最大(左兄弟)或最小(右兄弟)的关键字上移到双亲中，而将双亲中小于或大于且紧靠该上移关键字的关键字下移至被删关键字的结点中 见板书b)被删关键字和其兄弟的关键字数目均为m/2 1。假设它有右兄弟，右兄弟地址由双亲f所指

11、，则删除该关键字后将剩余的指针和关键字加上双亲指针一起合并到他的兄弟中,B+树（了解）B+树是应文件系统所需而产生的一种B-树的变形树。一棵m阶的B+树和m阶的B-树的差异在于：有n棵子树的结点中含有n个关键码；所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。 通常在B+树上有两个头指针，一个指向根结点，另一个指向关键码最小的叶子结点 。因此，可以对B+树进行两种查找运算：一种是从最小关键码起顺序查找，另一种是根结点开始，进行随机查找。,在

12、B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。,1.4 计算式查找法哈希法,哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表 。,哈希法的基本思想： 首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存

13、取元素的目的。,1.4.2 处理冲突的方法（四种）,1.开放定址法 （再散列法 ）,基本思想：当关键字key的哈希地址p= H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)% m i=1，2，n 其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：,l线性探测再散列, di=1，2，3，m-1，其特点是：冲突发生时，顺序查看表中下一单元，直

14、到找出一个空单元或查遍全表。,l二次探测再散列，di=12,-12,22,-22,k2,-k2 ( k=m/2 ) ，其特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。,l伪随机探测再散列, di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，(如i=(i+p)% m），并给定一个随机数做起点。,关键码集为 47，7，29，11，16，92，22，8，3，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，建表如下：,47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的；Hash(29)=7，哈希地址上冲突，需寻找下一个空的

15、哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由H1找到空的哈希地址的；,而Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+1) mod 11=4 仍然冲突；H2=(Hash(3)+2) mod 11=5 仍然冲突；H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，

16、可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。,2. 二次探测法Hi=(Hash(key)di) mod m其中：Hash(key)为哈希函数m为哈希表长度，m要求是某个4k+3的质数(k是整数)di 为增量序列 12，-12，22，-22，q2，-q2且q (1/2)*(m-1),关键码集为 47，7，29，11，16，92，22，8，3，用二次探测法处理冲突，建表如下：,对关键码寻找空的哈希地址只有3这个关键码与上例不同，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+12) mod 11=4 仍然冲突；H2=(Hash(3)-12) mod 11=2 找到空的哈希地址，存入。,2.再哈希法,这种方法是同时构造多个不同的哈希函数：Hi=RH1（key） i=1，2，k 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key），直到冲突不再产生。,