第七章查找 ★查找—也叫检索,是根据给定的某个值,在表 中确定一个关键字等于给定值的记录或数据元素 ★关键字—是数据元素中某个数据项的值。它可 以标识一个数据元素 ★查找方法评价 对含有n个记录的表,ASL=∑PC 心查找速度 其中:P为查找表中第个元素的概率∑p1= ◆占用存储空间多少 c为找到表中第个元素所需比较次数 ◆算法本身复杂程度 ☆平均查找长度ASL( Average Search Length):为确定 记录在表中的位置,需和给定值进行比较的关键字的 个数的期望值叫查找算法的
第七章 查找 查找——也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可 以标识一个数据元素 查找方法评价 ❖查找速度 ❖占用存储空间多少 ❖算法本身复杂程度 ❖平均查找长度ASL(Average Search Length)：为确定 记录在表中的位置，需和给定值进行比较的关键字的 个数的期望值叫查找算法的~ 为找到表中第 个元素所需比较次数 其中： 为查找表中第 个元素的概率， 对含有 个记录的表， c i p i p n ASL p c i n i i i n i i i 1 1 1 = = = =
§7.1顺序查找 ★查找过程:从表的一端开始逐个进行记录的关键 字和给定值的比较 ★算法描述 Ch7 ltrt 找 64 例01234567 91011 645131921375664 808892 视哨比较次数: 比较次数=5 查找第n个元素:1 查找第n-1个元素:2 查找第1个元素:n 查找第个元素:n+1-i Ch7 1.c 查找失败 n+1
§7.1 顺序查找 查找过程：从表的一端开始逐个进行记录的关键 字和给定值的比较 算法描述 Ch7_1.c i 例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数： 比较次数=5 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1
★顺序查找方法的ASL 对含有n个记录的表,AS=∑Pc 设表中每个元素的查找概率相等p=1 则4SL=∑PG=∑ n(n+1)n+1
顺序查找方法的ASL 2 1 2 1 1 ( 1) 1 1 1 + = + = = = = = = n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等= = n i i i n ASL p c 1 对含有 个记录的表
§7.2折半查找 ★查找过程:每次将待查记录所在区间缩小一半 ★适用条件:采用顺序存储结构的有序表 ★算法实现 心设表长为n,|OW、hgh和md分别指向待查元素所在 区间的上界、下界和中点k为给定值 冷初始时,令loW=1high=n,mid=(ow+high)2」 今让k与md指向的记录比较 ●若K=rmd]key,查找成功 ●若k<rmid]key,则hgh=md-1 ●若k>r[mid]key,则low=mid+1 重复上述操作,直至loW>high时,查找失败
§7.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 ❖设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 ❖初始时，令low=1,high=n,mid=(low+high)/2 ❖让k与mid指向的记录比较 ⚫若k==r[mid].key，查找成功 ⚫若k<r[mid].key，则high=mid-1 ⚫若k>r[mid].key，则low=mid+1 ❖重复上述操作，直至low>high时，查找失败
★算法描述 Ch? txt 找21 1234567891011 513192137566475808892 OW mid 12345 513192137566475808892 OW mid high 2345678 513192137566475808892 lowmid high Ch7 2.c
算法描述 low mid high 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowmid high Ch7_2.c