云大数据结构课程教学课件查找表.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2004-12-16 * 算法描述 关键字序列为 0 1 3 4 5 6 7 8 9 2 哈希函数为 Hash(key)=key % 11 10 处理冲突：线性探测再散列 19 56 24 14 冲突继续探测 再次冲突继续探测 68 87 87 14 24 56 19 68 哈希表的构造 2004-12-16 * 0 1 3 4 5 6 7 8 9 2 10 19 56 24 14 68 87 哈希表查找和插入 查找关键字为 68 不等于关键字 继续查找！ 查找成功！ 53 查找失败！此关键字不存在，插入！ 52 算法描述 哈希函数为 Hash(key)=key % 11 处理冲突：线性探测再散列 2004-12-16 * 各种查找比较 静态查找表 顺序查找：简单，常用于未排序元素的查找，但查找 效率不高； 二分查找：仅用于排序元素，查找效率较高当插入、删除运算时会引起大量数据的移动。 动态查找表 二叉查找树：元素插入次序不同，会构成不同的二叉排序树。最佳二叉排序树 的平均查找长度为O(log2n) 。 平衡二叉查找树：维持较高的查找效率 Ｂ树：对于较大的必须存放在外存贮器上的，应采用B树或B+树表示。B+树是B树的变种。B树和B+树都能动态地调整，保持均衡，而使动态字典保持较高的查找效率 哈希表 查找操作达到近乎随机存取的速度。但哈希表表示经常出现碰撞与堆积现象，增加了查找长度。 2004-12-16 * 关键字的定义 关键字（Key） 数据元素中某个数据项的值，可以标识（识别）一个数据元素。 主关键字（primary Key） 可以唯一地标识一个元素的关键字。（对不同的元素，其主关键字均不同） 次关键字（secondary Key） 用以识别若干元素的关键字。 typedef struct{ 　　KeyType key; 　　　// 关键字项 　　……　　　　　　　// 其它数据项 　} ElemType; 　　　　// 数据元素类型 其中的关键字类型可以为整型、实型、字符型、串类型等。 2004-12-16 * 查找的定义 查找（searching） 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 查找成功 若表中存在关键字等于给定值的一个元素，则称查找是成功的， 查找不成功 若表中不存在关键字等于给定值的元素，则称查找不成功， * * * * * * * * * * * * * * * * * * * * * * * * * * * 2004-12-16 * 在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键字最小的叶子结点。可对B+树进行两种查找运算：一种是循叶子结点链的顺序查找，另一种是从根结点开始的随机查找。 在B+树上进行随机查找、插入和删除的过程基本上与B_树类似。只是在查找过程中，如果非叶子结点上的关键字等于给定值，查找并不停止，而是继续沿右指针向下，一直查到叶子结点上的这个关键字。B+树的查找分析类似于B_树。 9.2 动态查找表 2004-12-16 * Ｂ-树性能分析 在B树是进行查找包含两种基本操作： （1）在B树中找结点； （2）在结点中找关键字。 　　由于B树通常存储在磁盘上，因此前一操作是在磁盘上进行的，而后一操作是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中信息读入内存，然后查询。而在磁盘上进行操作比在内存中操作慢得多， 　　　因此在磁盘上进行查找的次数，即待查关键字所在结点在B树是的层次数，是决定B树查找效率的关键因素。 现在考虑最坏的情况： 含n个关键字的m阶B树的最大深度为: 2004-12-16 * B+树 B+树的结构特点 ： B+树是B树的一种变型树，其结构和B树的差异在于 (1) B+树的每个叶子结点中含有 n 个索引项(即 n 个关键码和 n 个指针)；并且，所有叶子结点彼此相链接构成一个有序链表，该有序链表的头指针指向含最小关键码的结点； (2) B+树上每个非叶结点中的关键码 Ki 是其相应指针 Ai 所指子树的索引项，即该关键码为该子树中关键码的最大值； (3) 一棵m阶的B+树中每个结点至多含 m 个关键码(即至多有 m 棵子树)，除根结点至少含2个关键码外，其余结点至少含 m/2 个关键码，所有叶子结点都处在同一层次上。 2004-12-16 * B+树的定义 B+树：