数据结构第七章_查找1

《数据结构第七章_查找1》由会员分享，可在线阅读，更多相关《数据结构第七章_查找1（52页珍藏版）》请在金锄头文库上搜索。

1、第七章 查找 查找的基本概念 顺序表、有序表和索引表的查找 二叉平衡树 B-树、B+树的查找 散列表的查找 1数据结构数据结构课程组课程组 关键键字 标识标识 一个数据元素的某个数据 项项或组组合项项的值值 查查找表 具有同一类类型（属性）的数据 元素（记录记录 ）组组成 集合 ,分为为静态查态查 找表和动态查动态查 找表两类类. 查查找 按给给定的某个值值kx，在查查找表 中查查找关键键字为给为给 定值值kx的数据元素（ 记录记录 ）。 查找有关的概念与术语2数据结构数据结构课程组课程组typedef struct KeyType key； / 关键字字段，可以是整型，字符串型 、构造类型等

2、 / 其它字段 ElemType；数据元素类型说明3数据结构数据结构课程组课程组 查查找速度 占用存储储空间间多少 算法本身复杂杂程度 平均查查找长长度ASL(Average Search Length) 为为确定记录记录 在表中的位置，需和给给 定值进值进 行比较较的关键键字的个数的期望值值叫 查查找算法的查找方法评价4数据结构数据结构课程组课程组 静态查态查 找表结结构 静态查态查 找表是数据元素的线线 性表，可以是基于数组组的顺顺序存储储或 以线线性链链表存储储。 静态查找表结构5数据结构数据结构课程组课程组 顺顺序存储结储结 构 typedef struct ElemType *ele

3、m； /数组基址 int length； /表长度 S_TBL； 静态查找表的顺序存储结构6数据结构数据结构课程组课程组 链链式存储结储结 构 typedef struct NODEElemType elem； / 结点的值域 struct NODE *next； /下一个结点指针域 NodeType； 静态查找表的链式存储结构7数据结构数据结构课程组课程组查查找过过程 从表的一端开始逐个进进行记录记录 的关键键字和给给定值值的比 较较i i找找6464 0 1 2 3 4 5 6 7 8 9 10 110 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64

4、75 80 88 925 13 19 21 37 56 64 75 80 88 926464监视哨监视哨i ii ii ii i比较次数比较次数=5=5比较次数：比较次数： 查找第查找第n n个元素：个元素： 1 1 查找第查找第n-1n-1个元素：个元素：2 2 . 查找第查找第1 1个元素：个元素： n n 查找第查找第i i个元素：个元素： n+1-in+1-i 查找失败查找失败： n+1n+1静态查找顺序查找8数据结构数据结构课程组课程组顺序查找方法的ASL9数据结构数据结构课程组课程组 条件 有序表表中数据元素按关键键字升序或降 序排列 折半查查找的思想 每次将待查记录查记录 所在区

5、间缩间缩 小一半静态查找折半查找10数据结构数据结构课程组课程组例：05，13，19，21，37，56，64，75，80，88，92 查找的关键字K=21。 05，13，19，21，37，56，64，75，80，88，9205，13，19，21，37，56，64，75，80，88，9205，13，19，21，37，56，64，75，80，88，9211数据结构数据结构课程组课程组mid =折半查找的基本思想 条件 (1)确定查找区间的中点位置mid (2)将待查的K值与seqlistmid.key比较 (3)若相等，查找成功并返回此位置 (4) 若不相等，确定新的查找区间,返回(1), 重新开

6、始二分法查找 (5) 当上下界相等时,结束查找过程12数据结构数据结构课程组课程组lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid折半查找的算法例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找2113数据结构数据结构课程组课程组1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 3

7、7 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid折半查找的算法例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid找7014数据结构数据结构课程组课程组1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 8

8、8 92low high mid折半查找的算法15数据结构数据结构课程组课程组 插值查找通过下列公式求取中点， 其中low和high分别为表的两个端点下标，kx为给 定值。 若 kxtbl.elemmid.key，则low=mid+1，继续 右半区查找； 若 kx=tbl.elemmid.key，查找成功。静态查找有序表的插值查找思想16数据结构数据结构课程组课程组静态查找有序表的斐波那契查找 斐波那契查找通过斐波那契数列对有序表进行分 割 查找区间的两个端点和中点都与斐波那契数有关 斐波那契数列定义如下： 17数据结构数据结构课程组课程组静态查找有序表的斐波那契查找 分割的思想 对对于表长为

9、长为 F(i)-1的有序表，以相对对low偏移量 F(i-1)-1取中点，即mid=low+F(i-1)-1，对对表进进 行分割 则则左子表表长为长为 F(i-1)-1，右子表表长为长为 F(i)-1- F(i-1)-1-1=F(i-2)-1 可见见，两个子表表长长也都是某个斐波那契数-1， 因而，可以对对子表继续继续 分割。 18数据结构数据结构课程组课程组静态查找分块查找（索引顺序查找） 查查找过过程 将表分成几块块，块块内无序，块块 间间有序 先确定待查记录查记录 所在块块，再在 块块内查查找 适用条件 分块块有序表是后一个子表中 所有记录记录 的关键键字均大于前一个子表中 的最大关键键

10、字 算法实现实现 用数组组存放待查记录查记录 ,每个数据 元素至少含有关键键字域 建立索引表，每个索引表结结点 含有最大关键键字域和指向本块块第一个结结 点的指针针19数据结构数据结构课程组课程组 先用给定值kx在索引表中检测索引项，以确定 所要进行的查找在查找表中的查找分块 (由于索引项按关键字字段有序，可用顺序查找或折半 查找) 然后，再对该分块进行顺序查找。分块查找算法20数据结构数据结构课程组课程组1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 181 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12

11、13 8 9 20 22 12 13 8 9 20 33 42 44 38 24 4833 42 44 38 24 48 60 58 74 57 86 5360 58 74 57 86 5322 48 8622 48 861 7 131 7 13索引表索引表 查查3838分块查找过程21数据结构数据结构课程组课程组静态查找查找方法的比较顺序查找折半查找分块查找 ASL最大最小两者之间 表结构有序表 无序表有序表分块有序表存储结构顺序存储结 线性链表顺序存储 结构顺序存储结 构 线性链表22数据结构数据结构课程组课程组动态查 找表 二叉排序树 二叉排序树树定义义 二叉排序树树（Binary Sort Tree ）或者是一棵空树树；或者是具有下列性 质质的二叉树树： 若左子树树不空，则则左子树树上所 有结结点的值值均小于根结结点的值值； 若右子树树不空，则则右子树树上所 有结结点的值值均大于根结结点的值值。 左右子树树也都是二叉排序树树。 23数据结构数据结构课程组课程组 以二叉链链表作为为二叉排序树树的存储结储结 构 typedef struct NODE ElemTypeelem; /数据元素字段