vi设计是品牌设计吗,拼多多关键词优化步骤,公司网站seo怎么做,网站建设商务的术语1、查找的基本概念
查找也即检索。 文件#xff1a;由记录组成的集合#xff0c;即含有大量数据的元素线性组合而成。 记录#xff1a;由若干数据项组成的数据元素#xff0c;这些数据项也常称作记录中的数据域#xff0c;用以表示某个状态的物理意义。 关键字#xff1…1、查找的基本概念
查找也即检索。 文件由记录组成的集合即含有大量数据的元素线性组合而成。 记录由若干数据项组成的数据元素这些数据项也常称作记录中的数据域用以表示某个状态的物理意义。 关键字用以区分文件中记录的数据项的值。若此关键字可以惟一地标识一个记录则称此关键字为主关键字。也就是说对于不同的记录其对应的主关键字的值均不相同。若数据元素只有一个数据项其关键字即为该数据元素的值。 查找是指根据给定的某个值确定关键字值查询确定关键字值与给定值相等的记录在文件中的位置。它是程序设计中一项重要的基本技术。查找的结果有两种情况若在文件中找到了待查找的记录则称查找成功这时可以得到该记录在文件中的位置或者得到该记录中其他的信息若在文件中没有找到所需要的记录则称查找不成功或查找失败这时相应的查找算法给出查找失败的信息同时也得到记录插入文件的位置。
查找可分为静态查找和动态查找两种在查找过程中不修改查找表的长度和表中内容的方法称作静态查找反之称作动态查找。
2、查找算法的评价指标
平均查找长度ASL 在查找的过程中一次查找的长度是指需要比较的关键字次数而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。 n记录的个数pi查找第i个记录的概率 ( 通常认为pi 1/n )ci找到第i个记录所需的比较次数
3、静态查找表
3.1 顺序查找
1应用范围
顺序表或线性链表表示的静态查找表
2顺序表的表示
typedef struct { //查找表的数据结构ElemType *R; //元素存储空间基址int length; //表的长度
}SSTable;3性能分析
查找成功时的平均查找长度(设表中各记录查找概率相等)ASL(12 … n)/n (n1)/2查找不成功时的平均查找长度ASL n1
4特点
算法简单对表结构无任何要求顺序和链式。n很大时平均查找长度较大查找效率较低。改进措施非等概率查找时可按照查找概率进行排序。
3.2 折半查找
1算法思想
设表长为nlow、high和mid分别指向待查元素所在区间的上界、下界和中点k为给定值 初始时令low1, highn, mid(lowhigh)/2 让k与mid指向的记录比较若k R[mid].key查找成功若k R[mid].key则highmid-1若k R[mid].key则lowmid1 重复上述操作直至lowhigh时查找失败。 2折半查找的性能分析
查找过程每次将待查记录所在区间缩小一半比顺序查找效率高时间复杂度O(log2 n)适用条件采用顺序存储结构的有序表不宜用于链式结构
3.3 分块查找块间有序块内无序
分块有序即分成若干子表要求每个子表中的数值都比后一块中数值小但子表内部未必有序。 然后将各子表中的最大关键字构成一个索引表表中还要包含每个子表的起始地址即头指针。 1分块查找过程
对索引表使用折半查找法因为索引表是有序表确定了待查关键字所在的子表后在子表内采用顺序查找法因为各子表内部是无序表
2分块查找优缺点
优点插入和删除比较容易无需进行大量移动。缺点要增加一个索引表的存储空间并对初始索引表进行排序运算。适用情况若线性表既要快速查找又经常动态变化则可采用分块查找
3分块查找的性能分析
分块查找的平均长度为索引查找和块内查找的平均长度值和。设索引查找和块内查找的平均长度分别为 L1L2则分块查找的平均查找长度为 4、B树和B树
B树是一种多路平衡查找树它的每一个结点最多包含 m 个孩子m 被称为 B 树的阶。
B树主要应用于文件系统以及部分数据库索引比如 MongoDB。
而大部分关系型数据库比如 Mysql则使用 B 树作为索引。 一个m阶的B树具有如下几个特征
树中每个结点至多有 m 棵子树即至多含有 m-1 个关键字。若根节点不是终端结点则至少有两颗子树。除根节点外的所有非叶结点至少有⌈m/2⌉棵子树即至少有⌈m/2⌉ - 1 个关键字。所有的叶子结点都位于同一层且不带信息。每个节点中的元素从小到大排列。
B树的高度
若 n ≥ 1则对任意一棵包含 n 个关键字、高度为 h 、阶数为 m 的 B 树。
h ≥ logm(n1)h ≤ log⌈m/2⌉((n1)/2)1。
一个m阶的B树具有如下特征
每个分支最多有 m 棵子树。非叶根节点至少有两颗子树其他每个分支结点至少有 ⌈m/2⌉ 棵子树。结点子树个数与关键字个数相等。所有分支结点中仅包含它的各个子结点即下一级的索引块中关键字的最大值及指向其子结点的指针。所有的叶子结点中包含了全部元素的信息及指向含这些元素记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。在 B 树中叶结点包含了全部关键字即在非叶结点中出现的关键字也会出现在叶结点中而在 B 树中叶结点包含的关键字和其他结点包含的关键字是不重复的。 B树的优势
单一节点存储更多的元素使得查询的IO次数更少。所有查询都要查找到叶子节点查询性能稳定。所有叶子节点形成有序链表便于范围查询。
5、哈希表的查找
1基本思想记录的存储位置与关键字之间存在对应关系
优点查找速度极快为O(1)查找效率与元素个数n无关。
装填因子
