第九章查找
第九章查找
9,1基本概念 ,2顺序表 92顺序查找 9.2.2二分法查找 923分块查找
9.1.基本概念 9.2顺序表 9.2.1顺序查找 9.2.2二分法查找 9.2.3分块查找
9.3散列表 931概述 932散列函数的构造方法 9.3处理冲突的方法 9.3,4散列表的性能分祈
9.3散列表 9.3.1概述 9.3.2散列函数的构造方法 9.3.3处理冲突的方法 9.3.4散列表的性能分析
94树表 941二叉排序树 942平衡的二叉排序树 94.3B树 小结
9.4 .树表 9.4.1 二叉排序树 9.4.2 平衡的二叉排序树 9.4.3 B－树 小结
91基本概念 查找表:由同一类型的数据元素(记录)组成的集合, 可以由任意的数据结构实现。 查找表的操作:(1)查询某个“特定的”数据元素 是否在查找表中;(2)查找某个“特定的”数据元素的 属性;(3)在查找表中插入一个数据元素;(4)从查找 表中删除某个数据元素。 ◆静态查找表:若对查找表只作前两种操作,此类查找表称 静态查找表。 ◆动态查找表若在查找过程中同时插入查找表中不存在的 数据元素,或者从查找表中删除已经存在的某个数据元素, 此类查找表为动态查找表
◆查找表：由同一类型的数据元素（记录）组成的集合， 可以由任意的数据结构实现。 9.1 基本概念 ◆查找表的操作：（1）查询某个“特定的”数据元素 是否在查找表中；（2）查找某个“特定的”数据元素的 属性；（3）在查找表中插入一个数据元素；（4）从查找 表中删除某个数据元素。 ◆静态查找表:若对查找表只作前两种操作，此类查找表称 静态查找表。 ◆动态查找表:若在查找过程中同时插入查找表中不存在的 数据元素，或者从查找表中删除已经存在的某个数据元素， 此类查找表为动态查找表
◆关键字:数据元素中某个数据项的值,用它可以标示 查找表中的一个数据元素。主关键字可以唯一地标识 个记录,次关键字用以识别若干记录。 ◆査找:就是根据给定的关键字值,在特定的查找表中 确定一个其关键字与给定值相同的数据元素,并返回 该数据元素在查找表中的位置。如果找到数据元素 则称查找成功,否则查找失败。 ◆平均查找长度:为了确定数据元素在查找表中的位置 需要和给定值进行比较的关键字个数期望值,称为査 找算法在查找成功时的平均查找长度
◆关键字：数据元素中某个数据项的值，用它可以标示 查找表中的一个数据元素。主关键字可以唯一地标识 一个记录，次关键字用以识别若干记录。 ◆查找：就是根据给定的关键字值，在特定的查找表中 确定一个其关键字与给定值相同的数据元素，并返回 该数据元素在查找表中的位置。如果找到数据元素， 则称查找成功，否则查找失败。 ◆平均查找长度：为了确定数据元素在查找表中的位置 需要和给定值进行比较的关键字个数期望值，称为查 找算法在查找成功时的平均查找长度
对于长度为n的查找表,查找成功的平均查找长度为: ASL=PC1+P2C2+……+PnCn=PC 其中P为查找表中第i个数据元素的概率,C1为找到 查找表中第i个元素时,已经进行的比较次数。由于 査找算法的基本元素是关键字之间的比较操作,所以 可以平均査找长度来衡量查找算法的性能
•对于长度为n的查找表，查找成功的平均查找长度为： •其中Pi为查找表中第i个数据元素的概率，Ci为找到 查找表中第i个元素时，已经进行的比较次数。由于 查找算法的基本元素是关键字之间的比较操作，所以 可以平均查找长度来衡量查找算法的性能
92顺序表 顺序表中相邻的两个记录R和Ri+1在存储器中 的物理位置也是相邻的,因此存储结构采用的 是顺序结构。 顺序结构有关C+语言描述的数据类型定义: (为了简单起见,我们假设记录的排序码为整 型,在本章以后讨论的顺序表中均采用这样的 向量存储结构)
9.2顺序表 顺序表中相邻的两个记录Ri和Ri+1在存储器中 的物理位置也是相邻的，因此存储结构采用的 是顺序结构。 顺序结构有关C++语言描述的数据类型定义 ： （为了简单起见，我们假设记录的排序码为整 型，在本章以后讨论的顺序表中均采用这样的 向量存储结构）
# define maxn30∥文件中最大记录数 tyi pedef struct int key;∥假设记录排序码为整数 char *other;∥记录中其它信息城,暂不用 record; typedef record recordfilelmaxn 顺序表的查找方法分为顺序查找法、二分法 (折半)查找法以及分块(索引)查找法
•顺序表的查找方法分为顺序查找法、二分法 （折半）查找法以及分块（索引）查找法。 #define maxn 30 // 文件中最大记录数 typedef struct { int key; // 假设记录排序码为整数 char *other; // 记录中其它信息域，暂不用 } record; typedef record recordfile[maxn];
921顺序查找 顺序查找( sequential search)用待查的关键字值与线 性表里各结点的关键字值逐个比较, 查找 0 2345678 765687697623113244查找次数=5 监视哨 查找第n个元素:比较次数1查找第n-1个元素:比较次数2 查找第1个元素:比较次数n 查找第个元素:比较次数n+1-i查找失败:比较次数n+1
9.2.1顺序查找 顺序查找（sequential search)用待查的关键字值与线 性表里各结点的关键字值逐个比较， •查找第n个元素：比较次数1 查找第n-1个元素：比较次数2 ………. 查找第1个元素：比较次数 n 查找第i个元素：比较次数n+1-i 查找失败：比较次数n+1 76 56 87 69 76 23 11 32 44 0 1 2 3 4 5 6 7 8 监视哨 查 找 76 ↑i ↑i ↑i ↑i ↑i 查找次数＝5