中国网络推广网站排名,wordpress教程nginx,朝阳发布,中国建筑装饰集团有限公司哎呀呀#xff0c;sorry艾瑞波地#xff0c;这次真的断更一个月了#xff0c;又发生了很多很多事情#xff0c;秋风开始瑟瑟了#xff0c;老父亲身体查出肿瘤了#xff0c;有病请及时就医#xff0c;愿每一个人都有一个健康的身体#xff0c;God bless U and FAMILY. 直…哎呀呀sorry艾瑞波地这次真的断更一个月了又发生了很多很多事情秋风开始瑟瑟了老父亲身体查出肿瘤了有病请及时就医愿每一个人都有一个健康的身体God bless U and FAMILY. 直接上货了 文章目录 查找概念线性表的查找顺序查找(线性)应用范围表示方法算法算法7.2时间效率分析讨论优缺点 折半查找(对半/二分)算法思路二分查找效率分析 - 判定树平均查找长度ASL(成功时)优缺点 分块查找(索引顺序查找)条件性能分析优缺点 树表的查找二叉排序树 (Binary Sort Tree二叉排序树定义二叉排序树的性质二叉排序树查找二叉排序树的插入二叉排序树的生成二叉排序树的删除平衡二叉树 散列表的查找散列表术语散列函数构造方法直接定址法除留余数法 处理冲突的方法开放地址法链地址法 散列表查找 查找
内容回顾
概念 查找表是由同一类型的数据元素或记录构成的集合。由于集合中的数据元素之间存在着松散的关系因此查找表是一种应用灵便的结构。 查找 – 根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素或记录查找成功返回该记录信息或者位置查找不成功则给出空记录或者空指针。 关键字用来标识一个数据元素或记录的某个数据项的值。分为 主关键字(可唯一地标识一个记录的关键字) 和 次关键字(用以识别若干记录的关腱字)。 对查找表的操作查询记录 检索属性 插入数据元素 删除数据元素。 查找表分类 静态(仅查询)动态(可插入删除) 查找算法的评价指标 – 平均查找长度(关键字的平均比较次数) – ASL(Average Search Length) 查找的方法取决于查找表的结构即表中数据元素是依何种关系组织在一起的。为提高查找效率一个办法就是在构造查找表时在集合中的数据元素之间人为地加上某种确定的约束关系。
线性表的查找
顺序查找(线性)
应用范围
顺序表或线性链表表示的静态查找表表内元素之间无序
表示方法
// 数据元素的类型定义
typedef struct {KeyType key; //关键字域...... //其他域
} ElemType;// 顺序表结构类型定义
typedef struct {ElemType *R; // 表基址int length; //表长
} SSTable; //Sequential Search Table//定义一个顺序表ST
SSTable ST;算法 // 算法7.1
int Search_Seq(SSTable ST, KeyType key) {// 如成功则返回位置信息不成功返回0for(iST.length; i1; --i) {if (ST.R[i].key key) return i;return 0;}
}// 算法改1
int Search_Seq(SStable ST, KeyType key) {for(iST.length; ST.R[i].key ! key; --i)if (i0) break;if (i0) return i;else return 0;
}// 算法改2
inti Search_Seq(SStabl ST, KeyType key) {for(iST.length; ST.R[i].key ! keyi0; --i);if (i0) return i;else return 0;
}上面的算法的每一次循序都需要进行两次比较能否改进
查找的值是否相等i的值是否越界
改进
把待查关键字 key 存入表头哨兵、“监视哨”) 从后往前个比较可免去查找过程中每一步都要检测是否查找完毕加快速度。(如果找不到在表头[0]位置也一定会找到)。
当ST.length较大时此改进能使进行一次查找所需的平均时间几乎减少一半。 // 改进算法7.2
int Search_Seq(SSTable ST, KeyType key) {ST.R[0].key key;for (iST.length; ST.R[i].key ! key; --i);return i;}
}算法7.2时间效率分析 时间复杂度O(n)
查找成功时的平均查找长度设表中各记录查找概率相等(注意这里是指的是查找成功时所以不算哨兵位置)
ASLs(n)(1 2 … n)/n (n1)/2
空间复杂度O(1) — 辅助空间用于哨兵位置
讨论
1 、记录的查找概率不相等时如何提高查找效率
查找表存储记录原则按照查找概率高低存储1 查找概率越高比较次数越少2 查找概率越低比较次数较多。
2 、记录的查找概率无法测定日日何提高查找效率
方法 – 按查找概率动态调整记录顺序1 在每个记录中设一个访问频度域2 始终保持记录按非递增有序的次序排列3 每次查找后均将刚查到的记录直接移至表头。
优缺点
优点算法简单逻辑次序无要求且不同存储结构均适用。
缺点ASL 太长时间效率太低。
折半查找(对半/二分)
折半查找每次将待查记录所在区间缩小一半。 算法思路
非递归算法 设表长为nlow、high 和 mid 分别指向待查元素所在区间的上界、下界和中点 key 为给定的要查找的值 初始时令low 1highn, mid$\lfloor(lowhigh)/2\rfloor $ 让 k 与 mid 指向的记录比较 若key R[mid].key 查找成功若key R[mid].key, 则 highmid-1若 key R[mid].key, 则 lowmid1 重复上述操作直至 lowhigh 时查找失败
// 二分查找(非递归)
int Search_Bin(SSTabl ST, KeyType key) {low 1;high ST.length; // 初始化置区间值while (low high) { mid (low high) / 2;if (ST.R[mid].key key) return mid; // 找到元素else if (ST.R[mid].key key) { // 缩小区间low mid 1; // 继续在后半区查找} else high mid -1; // 继续在前半区查找}return 0; // 表中不存在待查元素
} // Search_Bin// 二分查找(递归)
int Search_Bin(SSTable ST, KeyType key, int low, int high) {if (low high) return 0; // 查找不到时返回0mid (low high)/2if (ST.R[mid].key key) return mid;else if (ST.R[mid].key key) {Search_Bin(ST, key, low, mid-1);} else {Search_Bin(ST, key, mid1, high);}
}二分查找效率分析 - 判定树 平均查找长度ASL(成功时) 优缺点
折半查找优点效率比顺序查找高
折半查找缺点只适用于有序表且限于顺序存储结构对线性链表无效。
分块查找(索引顺序查找)
条件 将表分成几块且表或者有序或者分块有序若i j则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。 建立索引表每个结点含有最大关键字域和指向本块第一个结点的指针且按关键字有序。 查找过程找38 -- 目标在索引48的块中 -- 顺序/折半在块内查找– 找到38
性能分析 优缺点
优点插入和删除比较容易无需进行大量移动。
缺点要增加一个索引表的存储空间并对初始索引表进行排序运算。
适用情况如果线性表既要快速查找又经常动态变化则可采用分块查找。 树表的查找
动态查找表 – 几种特殊的树, 用来解决插入删除频繁操作但需要维护表的有序性情况。
表结构在查找过程中动态生成对于给定值 key若表中存在则成功返回否则插入关字等于 key 的记录
分类
二叉排序树平衡二叉树红黑树B- 树B 树键树
二叉排序树 (Binary Sort Tree
又称为二叉搜索树、二叉查找树
二叉排序树定义
二叉排序树或是空树或是满足如下性质的二叉树 若其左子树非空则左子树上所有结点的值均小于根结点的值 若其右子树非空则右子树上所有结点的值均大于等于根结点的值 其左右子树本身又各是一棵二叉排序树
二叉排序树的性质
中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
如上图就是 3 12 24 37 45 53 61 78 90 100
二叉排序树查找
算法 typedef struct {KeyType key; //关键字项infoType otherinfo; //其他数据域
}ElemType;typedef stuct BSTNode {ElemType data; //数据域struct BSTNode *lchild, *rchild; //左右孩子指针
}BSTNode, *BSTree;BSTree T; //定义二叉排序树TBSTree SearchBST(BSTree T, KeyType key) {if (!T) || (key T-data.key) return T; //表为空或者表不为空且找到了都返回一个指针T(BSTree类型)else if (key T-data.key) // 判断key在左右子树的位置return SearchBST(T-lchild, key); //继续在左子树上找else return SearchBST(T-rchild, key); //继续在右子树上找
}//SearchBST平均查找长度 二叉排序树上查找某关键字等于给定值的结点过程其实就是走了一条从根到该结点的路径。 总结含有 n 个结点的二叉排序树的平均查找长度和树的形态有关 二叉排序树的插入 若二叉排序树为空则插入结点作为根结点插入到空树中 否则继续在其左、右子树上查找 树中已有不再插入 树中没有 查找直至某个叶子结点的左子树或右子树为空为止则插入结点应为该叶子结点的左孩子或右孩子 插入的元素一定在叶结点 二叉排序树的生成 从空树出发经过一系列的查找、插入操作之后可生成一棵二叉排序树。 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。(插入的结点均为叶子结点故无需移动其他结点) 关键字的输入顺序不同建立的不同二叉排序树。
二叉排序树的删除
从二叉排序树中删除一个结点不能把以该结点为根的子树都删掉只能删掉该结点并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。(中序遍历二叉树得到递增有序的序列) 被删除的结点是叶子结点直接删去该结点。 被删除的结点只有左子树或者只有右子树用其左子树或者右子树替换它结点替换。 其双亲结点的相应指针域的值改为“指向被删除结点的左子树或者右子树” 被删除的结点既有左子树也有右子树 以其中序前趋值替换之值替换然后再删除该前趋结点。前趋是左子树中最大的结点。 也可以用其后继替换之然后再除该后继结点。后继是右子树中最小的结点。 总结图
平衡二叉树
平衡二叉树 (balanced binary tree)又称 AVL (Adelson VeIskii and Landis)
一棵平衡二叉树或者是空树或者是具有下列性质的二叉排序树
左子树与右子树的高度之差的绝对值小于等于 1左子树和右子树也是平衡二叉排序树。
结点的平衡因子 (BF) 给每个结点附加一个数字给出该结点左子树右子树的高度差。值范围(-1, 0 ,1) 平衡因子结点左子树的高度-结点右子树的高度 对于一棵有 n 个结点的 AVL 树其高度保持在 O(log2n 数量级ASL也保持在 O(log2n 量级 失衡二叉排序树的调整
四种类型 调整原则
降低高度保持二叉排序树的性质 LL型调整 RR型 LR型 RL型
构造案例
输入关键字序列163711926181415), 给出构造AVL 树的步骤。 散列表的查找
基本思想记录的存储位置与关键字之间存在对应关系
对应关系-- hash 函数 Loc(i) H(keyi)
散列表术语
散列方法杂凑法
选取某个函数依该函数按关键字计算元素的存储位置并按此存放查找时由同一个函数对给定值 k 计算地址将 k 与地址单元中元素关键码进行比确定查找是否成功。
散列函数杂凑函数散列方法中使用的转换函数
散列表杂凑表按上述思想构造的表
散列存储选取某个函数依该函数按关键字计算元素的存储位置 Loc(i)H(keyi)
冲突不同的关键码映射到同一个散列地址当key1 ! key2 我们的 H(key1)H(key2) 散列函数构造方法
在散列查找方法中冲突是不可能避免的只能尽可能减少。
构造散列函数考虑的因素
执行速度即计算散列函数所需时间关键字的长度散列表的大小关键字的分布情况查找频率。
根据元素集合的特性构造 要求一n 个数据原仅占用 n 个地址。虽然散列查找是以空间换时间但仍希望散列的地址空间尽量小。 要求二无论用什么方法存储目的都是尽量均匀地存放元素以避免冲突。
有以下方法
直接定址法数字分析法平方取中法折叠法除留余数法(最常用)随机数法
直接定址法
Hash(key) a*key b (a 、b为常数
优点以关键码 key 的某个线性函数值为散列地址不会产生冲突。
缺点要占用连续地址空间空间效率低。 除留余数法
Hash(key) key mod p p 是一个整数
如何取p: 设表长为 m 取 p m 且为质数 处理冲突的方法
方法
开放定址法开地址法链地址法拉链法再散列法双散列函数法建立一个公共溢出区
开放地址法
基本思想有冲突时就去寻找下空的散列地址只要散列表足够大空的散列地址总能找到并将数据元素存入。
例如除留余数法Hi(Hash(key)di) mod m (di 为增量序列)
常用方法线性探测法二次探测法伪随机法 线性探测法 例关键码集为{477291116922283}, 散列表长为 m 11 散列函数为 Hash(key)key mod 11 拟用线性探测冲突。建散列表如下: 二次探测法 伪随机探测法 链地址法
基本思想相同散列地址的记录链成一单链表
m个散列地址就设 m个单链表然后用一个数组将m个单链表的表头指针存储起来形成一个动态的结构。 链地址法建立散列表步骤
Step1: 取数据元素的关键字 key 计算其散列函数值地址。若该地址对应的链表为空则将该元素插入此链表否则执行 Step2 解决冲突。
Step2: 根据选择的冲突处理方法计算关键字 key 的下一个存储地址。若该地址对应的链表为不为空则利用链表的前插法或后插法将该元素插入此链表。
优点 非同义词不会冲突无聚集现象 链表上结点空间动态申请更适合表长不确定的情况
散列表查找 例题
已知一组关键字19142316820842755111079散列函数为 H(key) key MOD 13散列表长为 m 16 设每个记录的查找概率相等 使用平均查找长度 ASL 来衡量查找算法 ASL 取决于: 散列函数 处理冲突的方法 散列表的装填因子αα表中填入记录数/哈希表的长度 α越大表中记录数越多说明表装得越满发生冲突的可能性就越大查找时比较次数就越多。
结论
散列表技术具有很好的平均性能优于一些传统的技术链地址法优于开地址法除留余数法作散列函数优于其它类型函数 TO BE CONTINUED…
