北京师范大学《数据结构——C语言描述》教学课件：第八章 查找

第八章查找

第八章 查找

静态查找表 ■基本概念 顺序查找 折半查找

一、静态查找表 ◼ 基本概念 ◼ 顺序查找 ◼ 折半查找

所谓查找,就是在数据集合中寻找满足某 种条件的数据对象 查找的结果通常有两种可能: ◆查找成功,即找到满足条件的数据对象 这时,作为结果,可报告该对象在结构中 的位置,还可给出该对象中的具体信息。 查找不成功,或查找失败。作为结果, 应报告一些信息,如失败标志、位置等

◼ 所谓查找，就是在数据集合中寻找满足某 种条件的数据对象。 ◼ 查找的结果通常有两种可能： ◆ 查找成功，即找到满足条件的数据对象 这时,作为结果, 可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。 ◆ 查找不成功，或查找失败。作为结果, 应报告一些信息, 如失败标志、位置等

通常称用于查找的数据集合为查找结构, 它是由同一数据类型的对象或记录)组成。 在每个对象中有若干属性,其中有一个属 性,其值可唯一地标识这个对象。称为关 键码。使用基于关键码的查找,查找结果 应是唯一的。但在实际应用时,查找条件 是多方面的,可以使用基于属性的查找方 法,但查找结果可能不唯一

◼ 通常称用于查找的数据集合为查找结构， 它是由同一数据类型的对象(或记录)组成。 ◼ 在每个对象中有若干属性，其中有一个属 性，其值可唯一地标识这个对象。称为关 键码。使用基于关键码的查找，查找结果 应是唯一的。但在实际应用时，查找条件 是多方面的，可以使用基于属性的查找方 法，但查找结果可能不唯一

实施查找时有两种不同的环境。 ◆静态环境,查找结构在插入和删除等操 作的前后不发生改变。 静态查找表 ◆动态环境,为保持较高的查找效率,查 找结构在执行插入和删除等操作的前后 将自动进行调整,结构可能发生变化。 动态查找表

◼ 实施查找时有两种不同的环境。 ◆ 静态环境，查找结构在插入和删除等操 作的前后不发生改变。 ⎯ 静态查找表 ◆ 动态环境，为保持较高的查找效率, 查 找结构在执行插入和删除等操作的前后 将自动进行调整，结构可能发生变化。 ⎯ 动态查找表

静态查找表结构的定义 #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，因此