文档介绍：第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析第第9 9章章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析 1数据结构第九章查找 2017 年3月24日星期五 1 第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析第第9 9章章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析 2 第九章查找基本概念查找表:是由同一类型的数据元素(或记录)构成的集合。对查找表经常进行的操作:1)查询某个“特定的”数据元素是否在查找表中; 2)检索某个“特定的”数据元素的各种属性; 3)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素。静态查找表仅作上述 1)和 2)操作的查找表动态查找表有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入查找表;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。 2 第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析第第9 9章章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析 3 第九章查找基本概念关键字: 是数据元素(或记录)中某个数据项的值, 用以标识(识别)一个数据元素(或记录) 若此关键字可以识别唯一的一个记录,则称之谓“主关键字”若此关键字能识别若干记录,则称之谓“次关键字”。查找: 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录) 若查找表中存在这样一个记录,则称“查找成功”,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功”,查找结果:给出“空记录”或“空指针”。 3 第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析第第9 9章章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析 4 第九章查找如何进行查找? 取决于查找表的结构,即:记录在查找表中所处的位置。然而,查找表本身是一种很松散的结构,因此, 为了提高查找的效率,需要在查找表中的元素之间人为地附加某种确定的关系,换句话说,用另外一种结构来表示查找表。本章讨论的重点: 查找表的各种表示方法及其相应的查找算法 4 第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析第第9 9章章 静态查找表顺序查找有序查找表(折半查找索引顺序法 . 动态查找表二叉排序树最佳二叉排序树平衡二叉树 B-树和 B+ 哈希表哈希函数的构造方法碰撞处理方法 Hash 表的检索及分析 5 静态查找表抽象数据类型静态查找表的定义 ADT StaticSearchTable { 数据对象 D:D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一标识数据元素。数据关系 R:数据元素同属一个集合。基本操作 P: Create(&ST, n); 操作结果:构造一个含 n个数据元素的静态查找表 ST 。 Destroy(&ST); 初始条件:静态查找表 ST 存在; 操作结果:销毁表 ST 。 5 第9章 静态查找表顺序查找有序查找表(折半查找索引顺序法 9.