网站的衡量标准,宁波模板做网站,高端网页设计培训学校,瑞安这边有没有做网站的文章目录一、基本概念二、顺序查找#xff08;线性查找#xff09;一般线性表的顺序查找有序表的顺序查找二、折半查找#xff08;二分查找#xff09;三、分块查找#xff08;索引顺序查找#xff09;四、B树五、B树六、散列表构造散列函数1. 直接定址法2. 除留取余法3.…
文章目录一、基本概念二、顺序查找线性查找一般线性表的顺序查找有序表的顺序查找二、折半查找二分查找三、分块查找索引顺序查找四、B树五、B树六、散列表构造散列函数1. 直接定址法2. 除留取余法3. 数字分析法4. 平方取中法冲突处理1. 开放定址法2. 拉链法链地址法性能分析一、基本概念
查找在数据集合中寻找满足某种条件的数据元素的过程称为查找。 查找表查找结构用于查找的数据集。它由同一类型的数据元素或记录组成可以是一个数组或链表等的数据类型。对查找表的常见操作一般有四种
查询某个特定元素是否在查找表中检索满足条件的某个特定数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个数据元素。
静态查找表若查找表涉及的操作只有上述的1、2则无序动态地修改查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等。 动态查找表若查找表涉及上述所有四个操作则需要动态插入删除查找表。适合动态查找表的查找方式有二叉排序树的查找、二叉平衡树的查找、B树的查找、散列查找等。 关键字数据元素中唯一标识该元素的某个数据项的值。使用基于关键字的查找其查找结果应是唯一的。 平均查找长度ASL在查找过程中一次查找的长度是指需要比较的关键字次数而平均查找长度是所有查找过程中关键字比较次数的平均值。ASL是衡量查找算法效率的最主要指标。
二、顺序查找线性查找
适用于顺序表和链表。对于顺序表通过数组下标递增来顺序扫描每个元素对于链表通过next指针来依次扫描每个元素。
一般线性表的顺序查找
基本思想是从线性表的一端开始逐个检查关键字是否满足给定条件。若查找到某个元素的关键字满足条件按则查找成功返回该元素在线性表中的位置若已找到表的另一端但还没找到符合条件的元素则返回查找失败的信息。 下面给出算法
int searchSeq(SSTable ST, ElemType key){// 引入哨兵元素在创建查找表时0号单元留空预留给带查找元素关键字// 引入哨兵元素的目的是使得循环不必判断数组是否越界可以避免很多不必要的判断语句提高效率ST.elem[0] key; // 从后往前查找满足i0时循环一定会跳出for(i ST.length; ST.elem[i] ! key; --i);return i;
}对于有n个元素的表定位第 i 个元素时需进行n-i1次比较。假设每个元素的查找概率相同即Pi1/nP_i1/nPi1/n时ASL(成功)∑i1nPi(n−i1)n12ASL_{(成功)}\sum_{i1}^nP_i(n-i1)\frac{n1}{2}ASL(成功)i1∑nPi(n−i1)2n1 查找不成功时与表中各关键字的比较次数为n1次ASL(不成功)n1ASL_{(不成功)}n1ASL(不成功)n1
通常查找表中记录的查找概率并不相等若能预先得知每个记录的查找概率则可以先对记录按查找概率进行排序。
缺点当n较大时ASL较大效率低。 优点对数据元素的储存没有要求顺序储存或链式存储只能顺序查找皆可。对表中记录的有序性也没有要求。
有序表的顺序查找
若在查找前就知道表的关键字是有序的则可以不用再比较到表的另一端就能确定查找失败从而降低失败的ASL。 可以用查找判定树来描述查找过程。树中圆形结点标识表中存在的元素举行结点称为失败结点描述的是不在表中的数据值的集合若有n个结点则相应有n1个失败结点。 查找成功的ASL和一般线性表相同。 查找失败是查找指针一定走到了某个失败结点。失败结点时虚构的所以到达失败结点时的查找长度等于其父结点所在的层数。 ASL(不成功)∑j1nqj(lj−1)12⋯nnn1n2nn1ASL_{(不成功)}\sum_{j1}^nq_j(l_j-1)\frac{12\cdotsnn}{n1}\frac{n}{2}\frac{n}{n1}ASL(不成功)j1∑nqj(lj−1)n112⋯nn2nn1n式中qjq_jqj是到达第 j 个失败结点的概率在相等查找概率的情形下它为1/(n1)1/(n1)1/(n1)ljl_jlj是第 j 个失败结点所在层数。
二、折半查找二分查找
基本思想首先将给定值key于表中间位置的元素进行比较若相等则查找成功返回元素位置若不等则目标元素只能在中间元素以外的前半部分或后半部分然后在缩小的范围内继续同样的查找。 算法如下
int binnarySearch(SqList L, ElemType key){int low 0;int high L.length - 1;int mid;while(low high){mid (low high) / 2;if(L.elem[mid] key)return mid;else if(L.elem[mid] key)low mid 1;elsehigh mid - 1;} return -1; // 查找失败
}折半查找也可用判定树来描述。每个结点值均大于其左子结点小于其右子结点。若有序序列有n个元素则判定树中有n个非叶结点和n1个叶节点。 显然二分查找的判定树是一棵平衡二叉树。 ASL(成功)1n∑i1nli1n(1×12×2⋯h×2h−1)n1nlog2(n1)−1≈log2(n1)−1(n较大时可近似为)\begin{aligned} ASL_{(成功)}\frac{1}{n}\sum_{i1}^nl_i\\ \frac{1}{n}(1\times12\times2\cdotsh\times2^{h-1})\\ \frac{n1}{n}\log_2(n1)-1\\ \approx\log_2(n1)-1(n较大时可近似为)\\ \end{aligned} ASL(成功)n1i1∑nlin1(1×12×2⋯h×2h−1)nn1log2(n1)−1≈log2(n1)−1(n较大时可近似为) 式中h是树的高度元素个数为 n 时h⌈log2(n1)⌉h\lceil\log_2(n1)\rceilh⌈log2(n1)⌉与n个结点的完全二叉树相同。 时间复杂度为O(log2n)O(\log_2n)O(log2n)平均情况下比顺序查找效率高。 计算失败的ASL时同样已其父节点的高度作为失败结点的高度。
折半查找需要快速定位查找区域要求线性表必须具有随机存取的特性。该查找法仅适合于顺序存储结构且要求元素按关键字有序排序。
三、分块查找索引顺序查找
基本思想将查找表分为若干子块块内元素可以无序但块之间是有序的即前一块中的最大关键字小于后一块中的最小关键字。再建立一个索引表索引表中的每个元素含有各块中的最大关键字和各块中的第一个元素的地址索引表按关键字有序排序。
分块查找吸取了顺序查找和折半查找各自的优点既有动态结构又适合于快速查找。查找分为两步第一步是在索引表中确定待查记录所在的块可以使用顺序查找或折半查找第二部是在块内顺序查找。
分块查找的ASL为索引查找和块内查找的平均长度之和。设索引查找和块内查找ASL为LIL_ILI、LS、L_S、LS则分块查找ASLLILSASLL_IL_SASLLILS。 将长度为 n 的查找表均匀分为 b 块每块有 s 个记录在等概率情况下 若块内和索引表均采用顺序查找则ASL(成功)LILSb12s12s22sn2sASL_{(成功)}L_IL_S\frac{b1}{2}\frac{s1}{2}\frac{s^22sn}{2s}ASL(成功)LILS2b12s12ss22sn此时若sns\sqrt{n}sn则ASL有最小值sn1s\sqrt{n}1sn1 若对索引表采用折半查找则ASL(成功)LILS⌈log2(b1)⌉s12ASL_{(成功)}L_IL_S\lceil\log_2(b1)\rceil\frac{s1}2ASL(成功)LILS⌈log2(b1)⌉2s1
四、B树
不考暂略。
五、B树
不考暂略。
六、散列表
散列函数把查找表中的关键字映射成该关键字对应地址的函数记为AddrHashkey。这里的地址可以是数组下标、索引或内存地址等。 冲突散列函数可能把两个不同的关键字映射到相同地址这种情况称为冲突。发生碰撞的不同关键字称为同义词。设计好的散列函数应尽可能避免冲突但冲突总是不可避免的。 散列表根据关键字直接进行访问的数据结构。散列表建立了关键字和储存地址的一种直接映射关系。
理想情况下散列表的查找时间复杂度为O(1)O(1)O(1)即与表中元素的个数无关。
构造散列函数
构造散列函数时必须注意一下几点
散列函数的定义域必须包含全部需要储存的关键字而值域的范围依赖于散列表的大小。散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中从而减少冲突的发生。散列函数应尽量简单以减少计算时间。
1. 直接定址法
直接取关键字的某个线性函数值作为散列地址。散列函数为 H(key)keyH(key)keyH(key)key 或 H(key)a×keybH(key)a\times keybH(key)a×keyb
这种方法计算最简单且不会产生冲突。 适合关键字分布基本连续的情况若关键字分布不连续会导致存储空间的浪费。
2. 除留取余法
假定散列表表长为m取一个不大于m但最接近m的质数p。散列函数为 H(key)key%pH(key)key\%pH(key)key%p
这是一种最简单、最常用的方法。 关键是选好p使得每个关键字通过散列函数转换后能等概率地映射到散列空间中从而进坑了减少冲突的可能性。
3. 数字分析法
设关键字是 r 进制数而r个数码在各位上的频率不一定相同可能在某些位上分布均匀一些此时应选取数码分布较为均匀的若干位作为散列地址。
这种方法适合已知的关键字集合。若更换了关键字则需要重新构造新的散列函数。
4. 平方取中法
取关键字平方值的中间几位作为散列地址。
这种方法得到的散列地址与关键字的每位都有关系因此使得散列地址分布比较均匀适合关键字的每位取值都不够均匀或均小于散列地址所需的位数。
冲突处理
任何散列函数都不能绝对避免冲突必须考虑发生冲突时的处理方法即为冲突的关键字寻找下一个空的hash地址。若得到的另一个散列地址仍然发生冲突则需要继续求下一个hash地址。
1. 开放定址法
指看存放新表项的空闲地址既向它的同义词表项开放又向它的非同义词表项开发。递推公式为Hi(H(key)di)%mH_i(H(key)d_i)\%mHi(H(key)di)%m式中HiH_iHi表示处理冲突第 i 次探测得到的散列地址m表示散列表表长did_idi为增量序列。
取定某一增量序列did_idi后对应的处理方法就是确定的。通常有以下4种取法
线性探测法线性探测再散列法di0,1,2⋯,m−1d_i0,1,2\cdots ,m-1di0,1,2⋯,m−1 冲突发生时顺序查看表中下一个单元直到找出一个空单元或查遍全表此时表已满。线性探查法可能使第 i 个散列地址的同义词存入第 i1 个散列地址这样本应存入第 i1 个散列地址的元素就要争夺 i2 个散列地址。造成大量元素在相邻的散列地址上聚集堆积起来大大降低了查找效率。 平方探测法二次探测再散列法di02,12,−12,22,−22,⋯,k2,−k2(k≤m2)d_i0^2,1^2,-1^2,2^2,-2^2,\cdots,k^2,-k^2(k\leq\frac m2)di02,12,−12,22,−22,⋯,k2,−k2(k≤2m) 散列表长度m必须是一个可以表示为4k3的素数。是一种处理冲突的较好方法可以避免出现堆积问题。缺点是不能探测到散列表上的所有单元但至少能探测到一半单元。 再散列法双散列法diHash2(key)d_iHash_2(key)diHash2(key) 当通过第一个散列函数得到的地址发生冲突时利用第二个散列函数计算该关键字的地址增量。具体散列函数为Hi(H(key)i×Hash2(key))%mH_i(H(key)i\times Hash_2(key))\%mHi(H(key)i×Hash2(key))%m最多经过m-1次探测就会遍历表中所有位置。 伪随机序列法did_idi为伪随机数序列。
在开放定址法中不能随便物理删除表中已有的元素因为若删除元素会截断其他具有相同散列地址的元素的查找地址。因此要删除一个元素时可以给它添加一个删除标记进行逻辑删除。这种方法需要定期维护散列表把删除标记的元素物理删除。
2. 拉链法链地址法
把所有同义词储存在一个线性链表中。这个线性链表由其散列地址唯一标识。 适合于经常进行插入和删除的情况。
性能分析
散列表的查找过程于构造散列表的过程基本一致。根据散列函数和关键字可以计算出记录的散列地址。若散列地址上①无记录说明查找失败②若有记录且关键字相同则查找成功③若有记录但关键字不同使用给定的处理冲突方法计算下一个散列地址再次进行比较。 装填因子定义为一个表的装满程度即α表中记录数n散列表长度m\alpha \frac{表中记录数n}{散列表长度m}α散列表长度m表中记录数n 散列表的查找效率取决于散列函数、处理冲突的方法和装填因子。 散列表的ASL依赖于装填因子而不直接依赖于n或m。
