第八章查找
第八章 查找
静态查找表 ■基本概念 顺序查找 折半查找
一、静态查找表 ◼ 基本概念 ◼ 顺序查找 ◼ 折半查找
所谓查找,就是在数据集合中寻找满足某 种条件的数据对象 查找的结果通常有两种可能: ◆查找成功,即找到满足条件的数据对象 这时,作为结果,可报告该对象在结构中 的位置,还可给出该对象中的具体信息。 查找不成功,或查找失败。作为结果, 应报告一些信息,如失败标志、位置等
◼ 所谓查找,就是在数据集合中寻找满足某 种条件的数据对象。 ◼ 查找的结果通常有两种可能: ◆ 查找成功,即找到满足条件的数据对象 这时,作为结果, 可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。 ◆ 查找不成功,或查找失败。作为结果, 应报告一些信息, 如失败标志、位置等
通常称用于查找的数据集合为查找结构, 它是由同一数据类型的对象或记录)组成。 在每个对象中有若干属性,其中有一个属 性,其值可唯一地标识这个对象。称为关 键码。使用基于关键码的查找,查找结果 应是唯一的。但在实际应用时,查找条件 是多方面的,可以使用基于属性的查找方 法,但查找结果可能不唯一
◼ 通常称用于查找的数据集合为查找结构, 它是由同一数据类型的对象(或记录)组成。 ◼ 在每个对象中有若干属性,其中有一个属 性,其值可唯一地标识这个对象。称为关 键码。使用基于关键码的查找,查找结果 应是唯一的。但在实际应用时,查找条件 是多方面的,可以使用基于属性的查找方 法,但查找结果可能不唯一
实施查找时有两种不同的环境。 ◆静态环境,查找结构在插入和删除等操 作的前后不发生改变。 静态查找表 ◆动态环境,为保持较高的查找效率,查 找结构在执行插入和删除等操作的前后 将自动进行调整,结构可能发生变化。 动态查找表
◼ 实施查找时有两种不同的环境。 ◆ 静态环境,查找结构在插入和删除等操 作的前后不发生改变。 ⎯ 静态查找表 ◆ 动态环境,为保持较高的查找效率, 查 找结构在执行插入和删除等操作的前后 将自动进行调整,结构可能发生变化。 ⎯ 动态查找表
静态查找表结构的定义 #define max size 100 查找表最大尺寸 typedef int Data Type;/查找数据的类型 typedef struct i ∥查找表结点定义 Data Type key: ∥/关键码域 other, ∥其他数据域 3 ListNode typedef struct dataList{∥查找表结点定义 ListNode data MaxSize;∥数据存储数组 int ng ∥数组当前长度
#define MaxSize 100 //查找表最大尺寸 typedef int DataType; //查找数据的类型 typedef struct { //查找表结点定义 DataType key; //关键码域 other; //其他数据域 } ListNode; typedef struct dataList { //查找表结点定义 ListNode data[MaxSize]; //数据存储数组 int n; //数组当前长度 } 静态查找表结构的定义
衡量一个查找算法的时间效率的标准是 在查找过程中关键码的平均比较次数,也 称为平均查找长度AsL( verage Search Length),通常它是查找结构 中对象总数m的函数。 在静态查找表中,利用数组元素的下标作 为数据对象的存放地址。查找算法根据给 定值x在数组中进行查找。直到找到x 在数组中的位置或可确定在数组中找不到 x为止。 另外衡量一个查找算法还要考虑算法所需 要的存储量和算法的复杂性等问题
◼ 衡量一个查找算法的时间效率的标准是: 在查找过程中关键码的平均比较次数,也 称 为 平 均 查 找 长 度 ASL(Average Search Length),通常它是查找结构 中对象总数 n的函数。 ◼ 在静态查找表中, 利用数组元素的下标作 为数据对象的存放地址。查找算法根据给 定值x, 在数组中进行查找。直到找到x 在数组中的位置或可确定在数组中找不到 x为止。 ◼ 另外衡量一个查找算法还要考虑算法所需 要的存储量和算法的复杂性等问题
顺序查找( Sequential Search) 所谓顺序查找,又称线性查找,主要用于 在线性结构中进行查找。 设若表中有n个对象,则顺序查找从表 的先端(或后端)开始,顺序用各对象 的关键码与给定值x进行比较,直到找 到与其值相等的对象,则查找成功;给出 该对象在表中的位置。 若整个表都已检测完仍未找到关键码与x 相等的对象,则查找失败。给出失败信息
顺序查找 (Sequential Search) ◼ 所谓顺序查找, 又称线性查找, 主要用于 在线性结构中进行查找。 ◼ 设若表中有 n 个对象,则顺序查找从表 的先端 (或后端) 开始, 顺序用各对象 的关键码与给定值 x 进行比较, 直到找 到与其值相等的对象, 则查找成功; 给出 该对象在表中的位置。 ◼ 若整个表都已检测完仍未找到关键码与x 相等的对象, 则查找失败。给出失败信息
设置“监视哨”的顺序查找算法 It LinearSearch( dataList A, Data Type x)i 在数据表 A datal.n中顺序查找关键码为x /的数据对象, A data0lkey作为控制查找自动 结束的“监视哨”使用 A data o key=x; int 1-An; /将送0号位置设置监视哨 while(A datai]. key =x)1--i /)后向前顺序查找 return 1
int LinearSearch ( dataList A, DataType x ) { //在数据表A.data[1..n]中顺序查找关键码为x //的数据对象,A.data[0].key 作为控制查找自动 //结束的“监视哨”使用 A.data[0].key = x; int i = A.n; //将x送0号位置设置监视哨 while ( A.data[i].key != x ) i-- ; //从后向前顺序查找 return i; } 设置“监视哨”的顺序查找算法
顺序查找的平均查找长度 设查找第个元素的概率为p,查找到第i个 元素所需比较次数为c,则查找成功的平均 查找长度 在顺序查找并设置“监视哨”情形: C1=n-i+1,i=n,n-1,,1,因此
顺序查找的平均查找长度 − = − = = = 1 0 1 0 n i i n i ASLsucc pi ci . ( p 1) ( 1) 1 = − + = ASL p n i n i succ i 设查找第 i 个元素的概率为 pi , 查找到第 i 个 元素所需比较次数为 ci , 则查找成功的平均 查找长度: 在顺序查找并设置“监视哨”情形: ci = n- i +1, i = n, n-1, , 1,因此