wordpress多城市子站,翻译wordpress,图片转换链接生成器,电商平台app定制开发查找#xff08;Searching#xff09;是根据给定的某个值#xff0c;在查找表中确定一个其关键字等于给定值的数据元素#xff08;或记录#xff09;。
一、顺序表查找
顺序查找又叫线性查找#xff0c;是最基本的查找技术#xff0c;它的查找过程是#xff1a;从表中…查找Searching是根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素或记录。
一、顺序表查找
顺序查找又叫线性查找是最基本的查找技术它的查找过程是从表中第一个或最后一个记录开始逐个记性记录的关键字和给定值比较若某个记录的关键字和给定值相等则查找陈宫找到所查的记录如果直到最后一个或第一个记录其关键字和给定值比较都不等时则表中没有所查的记录查找不成功。 时间复杂度为O(n)。
二、有序表查找
一折半查找 折半查找又称二分查找。它的前提是线性表中的记录必须是关键码有序通常是从小到大有序线性表必须采用顺序存储。 折半查找的基本思想是在有序表中取中间记录作为比较对象若给定值与中间记录的关键字相等则查找成功若给定值小于中间记录的关键字则在中间记录的左半区继续查找若给定值大于中间记录的关键字则在中间记录的右半区继续查找。不断重复上述过程直到查找成功或所有查找区域无记录查找失败为止。 时间复杂度为O(logn
二插值查找 插值查找的关键是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法其核心就在于插值的计算公式key-a[low]/(a[high]-a[low])。 从时间复杂度上看它也是O(logn但对于表长比较大而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比这般查找要好很多。
三斐波那契查找
三、线性索引查找
索引是把一个关键字与它对应的记录相关联的过程。一个索引由若干个索引构成每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。 线性索引是将索引项集合组织委员线性结构称为索引表。 以下重点介绍三种线性索引稠密索引、分块索引、倒排索引。
一稠密索引 稠密索引是指在线性索引中将数据集中的每个记录对应一个索引项。 稠密索引要应对的可能是成千上万的数据因此对于稠密索引这个索引表来说索引项一定是按照关键码有序的排列。
二分块索引 例子图书馆藏书。 分块有序是把数据集的记录分成了若干块将每块对应一个索引项并且这些块需要满足 1块内无序即每一块内的记录不要求有序。当然你如果能够让块内有序对查找来说更理想不过这就要付出大量时间和空间代价因此通常我们不要求快内有序。 2块间有序例如要求第二块所有记录的关键字均要大于第一块中所有记录的关键字第三块所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序才有可能在查找时带来效率。 分块索引的索引项结构分为三个数据项 1最大关键码存储每一块中的最大关键字 2存储了块中的记录个数以便循环时用 3用于指向块首数据元素的指针便于开始对这一块中记录进行遍历。
三倒排索引 网页搜索一般用的就是倒排索引。 倒排索引的通用结构是
次关键码如“英文单词”记录号表如“文章编号”
记录号表存储具有相同次关键字的所有记录的记录号可以是指向记录的指针或者是该记录的主关键字
四、二叉排序树
二叉排序树又称为二叉查找树。它或者是一棵空树或者是具有下列性质的二叉树。
若它的左子树不空则左子树上所有结点的值均小于它的根结构的值若它的右子树不空则右子树上所有结点的值均大于它的根结构的值它的左、右子树也分别为二叉排序树。 按中序遍历它是棵有序树。
五、平衡二叉树AVL树
平衡二叉树是一种二叉排序树其中每一个结点的左子树和右子树的高度差至多等于1。
六、多路查找树B树
多路查找树其每一个结点的孩子书可以多于两个且每一个结点处可以存储多个元素。
一2-3树 2-3树是一棵多路查找树其中的每一个结点都具有两个孩子称为2结点或三个孩子称为3结点。 一个2结点包含一个元素和两个孩子或没有孩子。 一个3结点包含一小一大两个元素和三个孩子或没有孩子。
二2-3-4树 2-3-4树是2-3树的扩展包括了4个结点的使用。一个结点包含小中大三个元素和四个孩子或没有孩子。
三B树 B树是一种平衡的多路查找树2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶因此2-3树是3阶的B树2-3-4树是4阶的B树。
四B树
七、散列表查找哈希表概述
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置fkey。查找时根据这个确定的对应关系找到给定值key的映射fkey若查找集合中存在这个记录则必定在fkey的位置上。 我们把上述的对应关系f称为散列函数又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中这块连续存储空间称为散列表后哈希表。
