大连理工大学：《数据结构》课程教学课件（PPT讲稿）第七章 查找

第七章查找 ★查找一也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 ★关键字一是数据元素中某个数据项的值，它可 以标识一个数据元素 ★查找方法评价 对含有n个记录的表，4-立pc 冬查找速度 其中：p,为查找表中第i个元素的概率，2P,=1 i=l 占用存储空间多少 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 1.txt 找64 例 0 1 2 3 4 5 6 7 8 9 1011 64 5 13 19 21 37 56 64 75 80 88 92 0 监视哨 比较次数： 比较次数=5 查找第n个元素：l 查找第n-1个元素：2 查找第1个元素： 查找第个元素： 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个记录的表，AsSL=立p4 i=1 设表中每个元素的查找概率相等，= n i-1 ni= n 2 2

顺序查找方法的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,loW、high和mid分别指向待查元素所在 区间的上界、下界和中点，k为给定值 初始时，令low=1,high=n,mid=L(low+high)/2」 必让k与mid指向的记录比较 ●若k==r[mid].key,查找成功 ●若kr[mid].key,则low=mid+1 必重复上述操作，直至oW>high时，查找失败

§7.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 ❖设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 ❖初始时，令low=1,high=n,mid=(low+high)/2 ❖让k与mid指向的记录比较 ⚫若k==r[mid].key，查找成功 ⚫若kr[mid].key，则low=mid+1 ❖重复上述操作，直至low>high时，查找失败

★算法描述 Ch7 2txt 找21 1 2 3 4 5 6 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 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

算法描述 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

找70 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 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 1921 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 low high mid

例 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 找70 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 low high mid 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 high low 2 3 4 5 6 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 判定树： 6 3 9 4 10 2 8 D

1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low 2 5 8 11 1 4 7 10 3 9 判定树： 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92

★算法评价 必判定树：描述查找过程的二叉树叫~ 有n个结点的判定树的深度为logn+1 折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 折半查找的ASL 设表长n=2-1,h=log2(n+1),即判定树是深度为h的满二叉树 设表中每个记录的查找概率相等，=】 则：4-2pe=2s=之2-”行gaa+-1bg,a+D-1 ni-

算法评价 ❖判定树：描述查找过程的二叉树叫~ ❖有n个结点的判定树的深度为log2n+1 ❖折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 ❖折半查找的ASL log ( 1) 1 log ( 1) 1 1 2 1 1 1 2 1, log ( 1), 2 2 1 1 1 1 2 + −  + − + = = =  = = = − = +   = − = = n n n n j n c n ASL p c n p n h n h h j j n i i n i i i i h 则： 设表中每个记录的查找概率相等 设表长 即判定树是深度为 的满二叉树

§7.3分块查找 ★查找过程：将表分成几块，块内无序，块间有序； 先确定待查记录所在块，再在块内查找 ★适用条件：分块有序表 ★算法实现 用数组存放待查记录，每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 ★算法描述 Ch7 3.txt Ch7_3.c

§7.3 分块查找 查找过程：将表分成几块，块内无序，块间有序； 先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 ❖用数组存放待查记录,每个数据元素至少含有关键字域 ❖建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 算法描述 Ch7_3.c

索表 22 48 86 查38 1 7 13 123456789101112131415161718 2212138920334244382448605874578653

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查38