数据结构 查找

null第九章 查找第九章 查找查找——也叫检索，是根据给定的某个值，在中确定一个关键字等于给定值的或数据元素 关键字——是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~null9.1 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 算法描述Ch7_1.c64监视哨比较次数=5比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1null顺序查找方法的ASL对查找概率不等的查找表，先对查找概率进行排序优点：算法简单，适用面广 缺点：平均查找长度较大。null9.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若kr[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败null算法描述Ch7_2.cnullnull描述折半查找过程的判定树及查找21的过程null算法评价 判定树：描述查找过程的二叉树叫~ 有n个结点的判定树的深度为log2n+1 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 折半查找的ASL当n值较大时（n>50)，有次近似结果）null9.3 分块查找（索引顺序表的查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 算法描述Ch7_3.cnull最大关键字起始地址null分块查找方法评价nullnull二叉排序树（Binary Sorting Tree），它或者是一棵空树，或者是一棵具有如下特征的非空二叉树： 若它的左子树非空，则左子树上所有结点的关键字均 小于根结点的关键字； 若它的右子树非空，则右子树上所有结点的关键字均 大于等于根结点的关键字； 左、右子树本身又都是一棵二叉排序树。 9.3 .1二叉排序树查找一、概念null struct node { int key; //代表关键字 … struct node *lch,*rch; //代表左、右孩子 };二、二叉排序树的数据类型描述 和第六章类似，可以用一个二叉链表来描述一棵二叉 排序树，具体为：null三、二叉排序树上的查找 1 . 二叉排序树的查找思想 若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。 2 . 二叉排序树查找的算法实现nullNODE * search(int k, NODE *root) //在以root为根指针的二叉排序树中查找关键值为k的结点 {NODE *p; p=root; while(p!= =NULL) { if (p->key= =k) return(p); //查找成功 else if (p->key>k) p=p->lch ; //进入左子树查找 else p=p->rch ; //进入右子树查找 } return(NULL); } null五、二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。null一、平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。9.3 .1平衡二叉树查找 若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。 我们希望二叉排序树都是AVL树，因为它的深度和log2n是同数量级的，则平均查找长度也和log2n同数量级null二、非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。 1 . R型 的处理(单向右型) 如图1所示，在A的左孩子B上插入一个左孩子结点C，使A的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子)null2 . LR型的处理(左右型) 如图2所示，在A的左孩子B上插入一个右孩子C，使的A的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将C变到B与A 之间，使之成为LL型，然后按第1种情形LL型处理。null3 . L型的处理(单向左型) 如图3所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点C成为B的右子树。null4 . RL型的处理(右左型) 如图4所示，在A的右孩子B上插入一个左孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将C变到A与B之间，使之成为RR型，然后按第3种情形RR型处理。null例1：给定一个关键字序列4,5,7,2 ,1,3,6，试生成一棵平衡二叉树。 分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图。nullnull三、平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。 null例2：对例1给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。 分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图1，得到的二叉排序树见图2。 null从图2的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。 从图1的平衡二叉树可知，查找6需2次，平均查找长度 ASL=(1+2+2+3+3+3+3) /7=17/7≈2.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。 null 例3 给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树)，并求出每一种查找的成功平均查找长度。顺序查找的顺序表（一维数组）如图3所示， 从图3 可以得到顺序查找的成功平均查找长度为： ASL=(1+2+3+4+5+6+7+8)/8=4.5；null二分查找的判定树（中序序列为从小到大排列的有序序列）如图4所示， 从图4可以得到二分查找的成功平均查找长度为： ASL=(1+2*2+3*4+4)/8=2.625；null二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图 5(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图5(b)所示。 从图5(a)可以得到二叉排序树查找的成功平均查找长度为： ASL=(1+2*2+3*2+4+5*2)/8=3.125； 从图5(b)可以得到平衡二叉树的成功平均查找长度为： ASL=(1+2*2+3*3+4*2)/8=2.75；null9.3.2 B-树和B+树 B-树 一、B-树的基本概念  1.定义  一棵m阶的B-树,或为空树,或为满足下列特性的m叉树: (l)所有的非终端结点的结构如下: 其中,①k1,k2,...,kn为n个按从小到大顺序排列的关键字; ②p0,pl,p2,...,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1≤i≤n-1)所指向子树中的所有关键字的值均大于ki且小于ki+1; ③n(n≤m-1)为键值的个数,即子树个数为(n+l)。 (2)树中每个结点至多有m棵子树。 (3)除非根结点为叶子结点,否则至少有两棵子树。 (4)除根之外的所有非终端结点至少有┌m/2┐棵子树。 (5)所有叶子结点在同一个层次上,且不含有任何信息。 null2. 说明 (1)对于非根结点的所有分支结点,n的取值范围为 ┌m/2┐-1≤n≤m-1。 (2)对于根结点,n的取值范围为1≤n≤m－1。 (3)对于叶子结点,其子树均为空树(即没有子结点),又规定不含有任何信息:所,可以把它看作不在树中的外部结点。 (4)B-树的阶m可以事先任意指定,一旦指定后,就固定不变。  图1是一棵由10个键值生成的四阶B_树的示意图,该树共有四层,所有叶子点均在第四层上。 nullatbcdfgeh图1 B-树null二、B-树的查找 1.查找方法   由B-树的定义可知,在B-树上进行查找的过程与二叉排序树的查找类似。根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。若有k=ki,则查找成功,根据相应的指针即可取得记录:否则,若k在ki和ki+1之间,取指针pi所指的结点,重复这个查找过程,直到在某结点中查找成功,或在某结点处出现pi 为空,查找失败 .例如，在图1所示B_树中查找关键字80和38。nullatbcdfgeh图1 B-树null2.性能分析 可以证明,在含有N个关键字的B-树上进行查找时，从根结点到待查找关键字，所在路径上涉及的结点数不超过 h≤1+log┌m/2┐(N+1)/2 当m=4、N=211-1=2047时，h<=11 null三、B-树的插入   在B-树中插入一个键值k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个键值。且要使插入的结点中的键值字个数≤m－1,否则将涉及到结点的“分裂"问

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

。null1.插入方法  （1）首先要经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。 （2）对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字个数不超过(m-l),直接把键值插就行了;否则需要把结点分裂成两个。 （3）分裂的做法是,取一新结点,把原结点上的键和k按升序排序后,从中间位置(即┌m/2┐之处)把键值(不包括中间位置的键值)成两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父亲结点中。如果父结点的键值个数也超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。 null3阶B树，结点中的关键字个数不会超过2null(c2) 插入38后的 B_树（分裂后）要分裂null(d2) 插入20后的 B_树(d1) 插入20后的 B_树null(d2) 插入20后的 B_树30 50(d3) 插入20后的 B_树null四、B-树的删除   B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的键值个数≥┌m/2┐,否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。 null1、被删关键字所在结点中关键字数目不小于┌m/2┐则只需从该结点删去该关键字ki和相应指针pi，树的其他部分不变 2、被删关键字所在结点的关键字数目等于┌m/2┐-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于┌m/2┐-1，则需将其兄弟结点中最小（最大）的关键字上移至双亲结点中，将双亲结点中小于（大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点。null3、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均小于┌m/2┐-1.假设该结点有右兄弟，且右兄弟结点地址由双亲结点中的指针pi所指，则在删去关键字之后，它所在结点中剩余的关键字和指针加上双亲结点中的关键字ki一起，合并到pi所指结点中。（若没有右兄弟，则合并到左兄弟结点中） 4、假设所删关键字为非终端结点中ki，则可以用指针pi所指子树中的最小关键字y代替ki，然后在相应结点中删除ynull1、删除倒数第二层结点中的关键字35。直接删除该关键字及其右部指针null2、删除倒数第二层结点中的关键字85。null3、删除倒数第二层结点中的关键字70。null4、删除倒数第二层结点中的关键字65。75 80null5、删除关键字60。null5、删除关键字60。null5、删除关键字60。null6、删除关键字40。null6、删除关键字40。null6、删除关键字40。50 65null9.4 哈希查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~ 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字null哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19null从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫~ 同义词：具有相同函数值的两个关键字，叫该哈希函数的~ 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+bnull例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为: H（key）=key +（-1948） 这样就可以方便地存储和查找1948年后任一年的记录。 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少 null数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址null平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况例 关键字为 ：0442205864，哈希地址位数为4null除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率null处理冲突的方法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,……k(km-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2) 伪随机探测再散列：di=伪随机数序列null例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38(2) H(38)=38 MOD 11=5 冲突 H1=(5+1²) MOD 11=6 冲突 H2=(5-1²) MOD 11=4 不冲突38(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突38null再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针null例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突null哈希查找过程及分析 哈希查找过程null哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于： 哈希函数 处理冲突的方法 哈希表的填满因子=表中填入的记录数/哈希表长度null例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9 ASL=(1*6+2+3*3+4+9)/12=2.514 168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12null(2) 用链地址法处理冲突ASL=(1*6+2*4+3+4)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)null哈希查找算法实现 用线性探测再散列法处理冲突 实现 查找过程：同前 删除：只能作标记，不能真正删除 插入：遇到空位置或有删除标记的位置就可以插入 算法描述： 用外链表处理冲突算法Ch7_4.c Ch7_5.c