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