数据结构 第八章 查找.

Presentation on theme: "数据结构 第八章 查找."— Presentation transcript:

1 数据结构 第八章 查找

2 第八章 查找 知 识 点 难 点 查找的基本概念 三种基本查找方法：顺序查找、二分查找和分块查找 树型查找的基本概念和查找算法
散列法、散列函数冲突的基本概念和解决冲突方法 难 点 二叉排序树查找 平衡树及平衡树的调整 第八章 查找

3 要 求 熟练掌握以下内容： 三种基本查找方法的基本思想和算法 二叉排序树查找的基本思想和算法
散列法基本思想、散列函数的常用构造方法及解决冲突方法 了解以下内容： 平衡树及平衡树的调整 B-树查找 第八章 查找

4 第八章目录 8.1 查找的基本概念 8.2 基本查找方法 8.3 树型查找 8.4 散列法 8.5 应用举例及分析 小 结 习题与练习
8.1 查找的基本概念 8.2 基本查找方法 8.3 树型查找 8.4 散列法 8.5 应用举例及分析 小 结 习题与练习 第八章 查找

5 8.1 查找的基本概念 查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。
在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。 第八章 查找

6 对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。
查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。 返回 第八章 查找

7 8.2.1 顺序查找 顺序查找(Sequential search)也称为线性查找，是采用线性表作为数据的存储结构，对数据在表中存放的先后次序没有任何要求。 顺序查找是最简单的查找方法，它的基本思想是：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。 第八章 查找

8 #define MAXITEM 100 /*最多项数*/ struct element { keytype key;
顺序查找的线性表定义如下： #define MAXITEM 100 /*最多项数*/ struct element { keytype key; Elemtype data; }; typedef struct sqlist[MAXITEM]; 这里keytype和ElemType可以是任何相应的数据类型，如int、float或char等，在算法中我们规定它们缺省是int类型。 第八章 查找

9 顺序查找算法 int sequsearch (sqlist r, int k, n) { /*n为线性表r中元素个数*/ i=1
while (r[i].key!=k && i<=n) i++; if(i>n) i=0; return(i); } 第八章 查找

10 顺序查找算法分析 此函数的主要运算时间是用于循环语句逐单元进行比较判断r[i].key是否等于k，因此顺序查找的速度较慢，最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。 顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。 第八章 查找

11 8.2.2 二分查找 二分查找(Birary search)也称为折半查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。 设n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。 采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标 。 第八章 查找

12 比较结果有三种可能： ⑴ 如果r[m].key>k，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； ⑵ 如果r[m].key<k，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； ⑶ 如果r[m].key=k，查找成功，m所指的记录就是查找到的数据。 第八章 查找

13 重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。
二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围了缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(logn)，对于较大的n显然较顺序查找速度快得多。 第八章 查找

14 二分查找算法 int binsearch(sqlist r,int k,n) { int i,low=1,high=n,m,find=0;
/*low和high分别表示查找范围的起始单元下标和终止单元下标，find为查找成功的标志变量*/ while (low<=high && !find) m=(low+high)/2; if(k<r[m].key) high=m-1; else if (k>r[m].key) 第八章 查找

15 二分查找算法续 low=m+1; else { i=m; find=1; } if (!find) i=0; return(i);
第八章 查找

16 8.2.3 分块查找 分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。
分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。 还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表按关键字值的递增顺序排列。 第八章 查找

17 分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。 例如线性表中关键字为:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如图8.1所示。 第八章 查找

18 图8.1 线性表与索引表 第八章 查找

19 索引表的定义 struct indexterm { keytype key; int low,high; };
typedef struct indexterm index[MAXITEM]; 这里的keytype可以是任何相应的数据类型，如int、float、或char等，在算法中，我们规定keytype缺省是int类型。 第八章 查找

20 分块查找算法 int blksearch (sqlist r,index idx,int k,bn) /*bn为块的个数*/ {
int i,high=bn,low=1,mid,j,find=0; while (low<=high&& !find) { /*二分查找索引表*/ mid=(low+high)/2; if(k<idx[mid].key) high=mid-1; else if(k>idx[mid].key) low=mid+1; 第八章 查找

21 分块查找算法续 else find=1; } if(find==1) { i=idx[mid].low; j=idx[mid].high;
else if (low<bn) /*k小于索引表内最大值*/ 第八章 查找

22 分块查找算法续 { i=idx[low].low; j=idx[low].high; }
while (i<=j && r[i].key !=k) i++; if (i>j) i=0; return(i); 返回 第八章 查找

23 8.3.1 二叉排序树查找 将原始数据表示成二叉排序树，树的每个结点对应一个记录，则可利用此二叉排序树进行类似于二分查找思想的数据查找，这也是一个逐步缩小查找范围的过程。这种查找方法称为树型查找。 基本思想：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右子树继续查找。 向子树查找又是树型查找，先以子树的根结点数据与k进行比较，如果不相等又转向它的左或右子树继续查找。 第八章 查找

24 在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下：
树型查找是一种递归的查找过程。 在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下： btree *search (btree *b,int k) { if (b==NULL) return (NULL); else if(b->data==k) return (b); 第八章 查找

25 二叉排序树查找递归算法 if(k<b->data) return (search (b->left,k)); else
return (search (b->right,k)); } 第八章 查找

26 非递归算法 btree *treesearch (btree *b,int k) { btree *p; p=b;
while(p!=NULL); { if (p->data==k) return (p); else if (k<p->data) p=p->left; else p=p->right; } return (NULL); 第八章 查找

27 在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到所查找结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到某个终端叶子结点的路径。与二分查找类似，和关键字比较的次数不超过二叉排序树的深度。 但是，含有n个结点的二叉树不是唯一的，由于对其结点插入的先后次序不同，所构成的二叉树的形态和深度也可能不同。例如，图8.2是按不同插入次序得到的两个二叉排序树。 第八章 查找

28 图8.2 两个二叉排序树 在查找失败的情况下，在这二个树上所进行的关键字比较次数分别为3和6次。 第八章 查找

29 二叉排序树查找分析 树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。 为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。 第八章 查找

30 8.3.2 平衡树 平衡树(Balanced tree)也称为AVL树，是由阿德尔森—维尔斯基和兰迪斯(Adelson-velskii and landis)于1962年首先提出的。 这是一种附加了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（Balance factor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或-1，即任一结点的左、右子树高度之差不超过1。 如图8.3所示，图中数字为该结点的平衡因子。 第八章 查找

31 平衡树 平衡二叉树 不平衡二叉树 第八章 查找

32 假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加1，我们可能会遇到以下三种情况：
(1) 如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0,插入新结点后将使平衡因子变成+1，但仍符合平衡树的条件，不必对其加以调整； ⑵ 如果原来hl>hr，即原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡树的限制条件，需对其加以调整； ⑶ 如果原来hl<hr，即原来此结点的平衡因子等于-1，插入新结点后将使平衡因子变成0，平衡更加改善，不必加以调整。 第八章 查找

33 如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加1，则也会遇到与之相对应的三种情况。
以图8.4所示的树为例，设原已有关键字为51，29，72，11和46这五个结点，原树符合平衡树条件，图中各结点旁所标数字为该结点的平衡因子。 第八章 查找

34 图8.4 平衡树插入结点 第八章 查找

35 插入新结点破坏了平衡树条件的情况分为两类，仍以向左子树插入新结点为例，这两类情况分别如图8.5（a）和(c)所示。
图中矩形表示子树，矩形的高度表示子树的高度，带阴影线的方形则表示插入新结点后造成的子树高度加1，各结点旁所标数字为该结点的平衡因子。 第八章 查找

36 图8.5 平衡树的调整 第八章 查找

37 第八章 查找

38 平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。
平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。 在插入新结点时，当确定了新结点应插入的位置后，需向回寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。 第八章 查找

39 8.3.3 B-树 前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了。 B-树是一种多路平衡查找树，这是一种适用于外查找的方法的数据结构。 B-树的定义： 一棵m（m≥3）阶的B-树，或者为空树，或者是满足如下条件的m叉树： 第八章 查找

40 B-树定义 (1)树中每个非终端结点至少包含以下数据项： （n,A0,K1,A1,K2,……Kn,An）
其中，n为关键字总数，Ki（1≤i≤n）是关键字，Ai是指向子树根结点的指针。关键字是递增有序的：K1<K2<……Kn，且Ai(0≤i≤n)所指子树中所有结点的关键字均小于Ki+1，An所指子树中所有结点的关键字均大于Kn。 (2)所有的叶子结点都在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。 第八章 查找

41 (4)如果树非空，则根至少有1个关键字，所以如果根不是叶结点，则至少有两棵子树。最多有m-1个关键字，所以最多有m棵子树。
(3)每个非根结点中所包含的关键字个数n满足 ≤n≤m-1，即每个非根结点至少应有 个关键字，至多有m-1个关键字。因为每个内部结点的度数正好是关键字数加1，故每个非根的内部结点至少有 棵子树，至多有m棵子树。 (4)如果树非空，则根至少有1个关键字，所以如果根不是叶结点，则至少有两棵子树。最多有m-1个关键字，所以最多有m棵子树。 第八章 查找

42 图8.6 一棵4阶B-树 返回 第八章 查找

43 8.4.1 散列法 散列法就是也称为哈希查找(Hashed search)或杂凑法。
散列法的核心思想是将每个记录的地址与该记录的关键字之间建立某种函数关系，可直接由关键字查找到该记录，根据关键字求存储地址的函数称为散列函数，又称为哈希函数（Hashed Function），按散列存储方式构造的动态表又称散列表(hashed table)。 第八章 查找

44 设有关键字为1，3，7，12，15的五个记录，定义一个散列函数为： h(k)=(k mod m)+1
h(1)=2,h(3)=4,h(7)=1,h(12)=6,h(15)=2 第八章 查找

45 图8.7 散列法 可能由不同的关键字计算出相同的散列函数值来，例如此例中h(1)和h(15)都等于2，也就是遇到了不同记录占用同一地址单元的情况，这种情况称为发生了冲突（collision）。 第八章 查找

46 散列是一种重要的存储方法，又是一种查找方法。
应用散列法存储记录的过程是对每个记录的关键字进行散列函数的运算，计算出该记录存储的地址，并将记录存入此地址中。 查找一个记录的过程与存储记录的过程一样，就是对待查找记录的关键字进行计算，得到地址，并到此地址中查找记录是否存在。 第八章 查找

47 8.4.2 散列函数构造方法 1. 直接定址法：直接取关键字本身或者关键字加上一个常数作为散列地址。
2. 数字分析法：又称为数字选择法。适用于所有关键字事先都知道，并且关键字的位数比散列地址的位数多的情况，在这种情况下，可将各个关键字列出，分析它们的每一位数字，舍去各关键字取值比较集中的位，仅保留取值比较分散的位作为散列地址。 第八章 查找

48 数字分析法例子 第八章 查找

49 3. 除留余数法：这是一种最简单也最常用的构造散列函数的方法，前面介绍的散列函数： h(k)=(k mod m)+1
就是采用这种方法。这种方法关键在于m的选择，选定m值后就可以决定存储地址的数目了。 4. 折叠法：折叠法是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。 第八章 查找

50 8.4.3 处理冲突的方法 1. 开放地址法：开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。 开放地址法又称为闭散列表处理冲突的方法。散列表按结构形式可分成开散列表和闭散列表，闭散列表的结构是一个向量,也就是一维数组，表中记录按关键字经散列函数运算所得的地址直接存入数组中。 当在闭散列表上发生冲突时，必须按某种方法在散列表中形成一个探查地址序列，沿着这个探查地址序列在数组中逐个查找，直到碰到无冲突的位置为止，并放入记录。 第八章 查找

51 形成探查地址序列最简单的方法是线性探测法，设散列函数为H，闭散列表一维数组的容量为m，对关键字k，计算出的地址为d=H(k)。
线性探测法的基本思想是沿着散列表顺序向后探查，直至找到开放地址为止，如到达表末端仍未找到开放地址，则将表看成是循环的，返回到表的首端再向后找，只要尚有开放地址最终总可以找到。 线性探测法对应的探查地址序列为d+1，d+2，……m,1,……,d-1。探查地址序列对应的计算公式为：di=(H(K)+i) mod m (1≤i≤m-1) 第八章 查找

52 例如，已知一组关键字k1~k5，已计算出各关键字的散列函数值为：
H(k1)=3, H(k2)=5, H(k3)=1, H(k4)=3, H(k5)=3， 总记录个数为5，开辟的一维数组长度可以比实际用的存储单元多一些，取m=8。 第八章 查找

53 图8.8 开放地址的线性探测 第八章 查找

54 二次探测法 二次探测法的基本思想是：生成的探查地址序列不是连续的，而是跳跃式的。二次探测法对应的探查地址序列的计算公式为：
di = (H(k)+i) mod m 其中i=12，-12，22，-22­,……j2，-j2，(j≤m/2)。 第八章 查找

55 图8.9 开放地址的二次探测 第八章 查找

56 2. 链接表法：又称为开散列表处理冲突的方法。
设散列函数为H(k)，函数值范围为0～m-1，开散列表的结构可以设计成一个由m个指针域构成的指针数组T[m]，初始状态都是空指针。其中每一个分量对应一个单链表的头指针，凡散列地址为i的记录都插入到头指针为T[i]的链表中。每一个这样的单链表称为一个同义词表。链接表法解决冲突的方式，就是将所有关键字为同义词的记录链接在同一个单链表中。 例如前面的例子改用链接表法如图8.10所示。 第八章 查找

57 图8.10 链接表法 第八章 查找

58 8.4.4 散列法的查找运算 散列表的目的主要是用于快速查找。
在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。假设给定的值为k，根据建表时设定的散列函数H，计算出散列地址H(k)，如果表中该地址单元为空，则查找失败；否则将该地址中的关键字值与给定值k比较，如果相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址，如此反复下去，直到某个地址单元为空（查找失败）或与关键字值比较相等（查找成功）为止。 第八章 查找

59 设有一批正整数关键字，采用除留余数的散列函数和线性探测开放地址的办法解决冲突，存放入长度约为该批数据总数1
设有一批正整数关键字，采用除留余数的散列函数和线性探测开放地址的办法解决冲突，存放入长度约为该批数据总数1.5倍的一维数组A中，因为关键字值均大于0，所以规定数组元素置0表示开放地址。 要求当查找成功时，给出与该关键字相应的地址，查找失败时则将该关键字插入开放地址单元并输出此地址。待查找的关键字为k，m值取一个接近数组长度的质数，则这种散列法的查找算法如下： 第八章 查找

60 查找算法 int Hashing (int A,m,k) { int i; /*为散列函数值*/ i=(k mod m)+1
while (A[i]!=k && A[i]>0) if (i==m) i=1; else i++;/*i未到达表末端则后移一个单元进行线性探测，否则返回到表首端继续探测，直至找到待查关键字k或者遇到开放地址为止*/ } 第八章 查找

61 查找算法续 } if(A[i]==0) A[i]=k; return (i); 返回 第八章 查找

62 例8.1 设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数：H（k）=k mod 13。采用开放地址的线性探测法解决冲突，试在0～18的散列地址空间中，对该关键字序列构造散列表。 解：依题意m=19，得到线性探测法对应的探查地址序列计算公式为： di=(H(k)+j) mod 19; j=1,2,……,18 其计算函数如下： H(19)=19 mod 13=6 H(01)=01 mod 13=1 第八章 查找

63 H(23)=23 mod 13=10 H(14)=14 mod 13=1 (冲突) H(14)=(1+1) mod 19=2
第八章 查找

64 H(27)=(1+2) mod 19=3 (冲突) H(27)=(1+3) mod 19=4 H(68)=68 mod 13=3 (冲突)
第八章 查找

65 图 例8.1地址分配 第八章 查找

66 例8.2 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。
本题的解题思想是，先在有序表r中利用二分查找算法查找关键字值等于或小于x的结点，mid指向正好等于x的结点或low指向关键字正好大于x的结点，然后采用移动法插入x结点即可。 第八章 查找

67 例8.2算法 insert(sqlist r, int x, int n) { int low=1,high=n,mid,i,find=0;
while( low<=high && !find) mid=(low+high)/2; if(x<r[mid].key) high=mid-1; else if (x>r[mid].key) low=mid+1; else 第八章 查找

68 例8.2算法续 { i=mid; find=1; } if (!find) mid=low; for (i=n;i>=mid;i--)
r[i+1].key=r[i].key; r[mid].key=x; 返回 第八章 查找

69 小结 查找 顺序查找 二分查找 分块查找 树型查找 平衡树 散列法 处理冲突的方法 开放地址法 链接表法 返回 第八章 查找

70 习题与练习 一、基础知识题 1. 解释下列名词 (1) 查找 (2) 树型查找 (3) 平衡因子 (4) 散列函数 (5) 冲突
(1) 查找 (2) 树型查找 (3) 平衡因子 (4) 散列函数 (5) 冲突 2. 设有序表为{a,b,c,d,e,f,g}，请分别画出对给定值f,g和h进行拆半查找的过程。 3. 试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种查找法对长度为n的表的等概率查找长度是多少？ 第八章 查找

71 4. 设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素{15,27,50,73,49,61,37,60} ，试画出采用二次探测法处理冲突的散列表。
6. 设关键字集合为{27,49,79,5,37,1,56,65,83}，散列函数为：H（k）=k mod 7，散列表长度m=10，起始地址为0，分别用线性探测和链接表法来解决冲突。试画出对应的散列表。 第八章 查找

72 二、算法设计题 1. 从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找。
2. 如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。 第八章 查找

73 3. 试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。
4. 设给定的散列表存储空间为H[1~m]，每个单元可存放一个记录，H[i](1≤i≤m)的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突方法为线性探测法，编写一个函数将某记录R填入到散列表H中。 返回 第八章 查找