第11章 查找 主要知识点 查找的基本概念 静态查找表 动态查找表 哈希表.

Presentation on theme: "第11章 查找 主要知识点 查找的基本概念 静态查找表 动态查找表 哈希表."— Presentation transcript:

1 第11章 查找 主要知识点 查找的基本概念 静态查找表 动态查找表 哈希表

2 11.1 查找的基本概念 查找:查询某个关键字是否在(数据元素集合）表中的过程。也 称作检索。
查找:查询某个关键字是否在(数据元素集合）表中的过程。也 称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字:通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素

3 å 静态查找:只查找，不改变数据元素集合内的数据元素 动态查找:既查找，又改变（增减）集合内的数据元素 静态查找表:静态查找时构造的存储结构
动态查找表:动态查找时构造的存储结构 平均查找长度:查找过程所需进行的关键字比较次数的平 均值,是衡量查找算法效率的最主要标准,其数学定 义为： å = × n i C P ASL 1

4 其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。
定义要查找数据元素的结构体为： typedef struct { KeyType key; } DataType;

5 11.2 静态查找表 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表

6 1.顺序表 在顺序表上查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回-1。

7 查找函数设计如下： 查找成功时的平均查找长度ASL为：
int SeqSearch(DataType a[], int n, KeyType key) { int i = 0; while(i < n && a[i].key != key) i++; if(a[i].key == key) return i; else return -1; } 查找成功时的平均查找长度ASL为：

8 2.有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 一、顺序查找
有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找（又称折半查找） 算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素值相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。

9 二分查找算法如下： int BiSearch(DataType a[], int n, KeyType key) { int low = 0, high = n - 1; //确定初始查找区间上下界 int mid;   while(low <= high) { mid = (low + high)/2;//确定查找区间中心下标 if(a[mid].key == key) return mid; //查找成功 else if(a[mid].key < key) low = mid + 1; else high = mid - 1; } return -1; //查找失败

10 算法分析 平均查找长度ASL为：

11 3.索引顺序表 当顺序表中的数据元素个数非常大时，采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。

12 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 5 1 2 15 3 key link 下标 索引表 4 7 11 12 13 16 17 其它域 位置 主表 索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。 索引表结构图

13 相关术语 完全索引表:和主表项完全相同，但只包含索引关键字和该数 据元素在主表中位置信息的索引表
完全索引表:和主表项完全相同，但只包含索引关键字和该数 据元素在主表中位置信息的索引表 二级索引表:当主表中的数据元素个数非常庞大时，按照建立 索引表的同样方法对索引表再建立的索引表。二级以上 的索引结构称作多级索引结构 等长索引表:索引表中的每个索引项对应主表中的数据元素个 数相等;反之称为不等长索引表。不等长索引表中的索 引长度可随着动态插入和动态删除过程改变,因此不仅 适用于静态查找问题，而且也适用于动态查找问题。

14 算法分析 假设索引表的长度为m，主表中每个子表的长度为s，并假设在索引表上和在主表上均采用顺序查找算法，则索引顺序表上查找算法的平均查找长度为：

15 11.3 动态查找表 动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。 二叉排序树和平衡二叉树 一、基本概念 二叉排序树或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。

16 二叉排序树中结点的结构体定义如下： typedef struct node { DataType data; struct node *leftChild; struct node *rightChild; } BiTreeNode;

17 下图所示就是一棵二叉排序树 381 12 410 9 40 394 540 35 190 146 476 760 445 600 800

18 二、二叉排序树的查找算法 int Search(BiTreeNode *root, DataType item) { BiTreeNode *p; if(root != NULL) p = root; while(p != NULL) if(p->data.key == item.key) return 1; if(item.key > p->data.key) p = p->rightChild; else p = p->leftChild; } return 0;

19 三、插入算法 插入操作要求首先查找数据元素是否在二叉排序树中存在，若存在则返回；若不存在，插入查找失败时结点的左指针或右指针上。所插新结点一定在叶结点上。 插入算法设计如下:

20 int Insert(BiTreeNode **root, DataType item)
{ BiTreeNode *current, *parent = NULL, *p;   current = *root; while(current != NULL) { if(current->data.key == item.key) return 0; parent = current; if(current->data.key < item.key) current = current->rightChild; else current = current->leftChild; } /*生成新结点*/ p = (BiTreeNode *)malloc(sizeof(BiTreeNode)); p->data = item; p->leftChild = NULL; p->rightChild = NULL;   if(parent == NULL) *root = p; else if(item.key < parent->data.key) parent->leftChild = p; else parent->rightChild = p; return 1;

21 下图是调用上述插入函数依次插入数据元素 4,5,7,2,1,9,8,11,3的过程。 4 11 5 2 7 9 1 3 8 (d) (c)
(b) (a) (g) (f) (e) (i) (h)

22 五、删除算法 删除操作要求首先查找数据元素是否在二叉排序树中存在，若不存在则结束；存在的情况及相应的删除方法有如下四种： (1)要删除结点无孩子结点，直接删除该结点。 (2)要删除结点只有左孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点。 (3)要删除结点只有右孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点。 (4)要删除结点有左右孩子结点，分如下三步完成：首先寻找数据元素的关键字值大于要删除结点数据元素关键字的最小值，即寻找要删除结点右子树的最左结点；然后把右子树的最左结点的数据元素值拷贝到要删除的结点上；最后删除右子树的最左结点。

23 删除过程分别如图所示 18 14 24 5 16 20 38 7 10 30 35 ptr (a)无孩子结点 (b)有左孩子结点

24 18 14 24 5 16 20 38 7 10 30 35 ptr (c)有右孩子结点 (d)有左右孩子结点

25 例11-2 设计一个测试二叉排序树的主函数。 #include <stdio.h>
#include <stdlib.h> #include <malloc.h> typedef int KeyType; typedef struct { KeyType key; }DataType; typedef struct node { DataType data; struct node *leftChild; struct node *rightChild; } BiTreeNode; #include “BiSortTree.h”  

26 void InTraverse(BiTreeNode *root)
/*中序遍历显示二叉排序树结点信息函数*/ { if(root == NULL) return; if(root->leftChild != NULL) InTraverse(root->leftChild); printf("%d ", root->data.key); if(root->rightChild != NULL) InTraverse(root->rightChild); }

27 void main(void) { DataType test[] = {4,5,7,2,1,9,8,11,3}, x = {9}; int n = 9, i, s; BiTreeNode *root = NULL;   for(i = 0; i < n; i++) Insert(&root, test[i]); InTraverse(root);   s = Search(root, x); if(s == 1) printf(""\n数据元素%d存在！", x.key"); else printf("\n数据元素不存在！");  }

28 程序运行建立的二叉排序树如图11-5（i）所示。程序运行结果如下：
数据元素9存在！

29 六、二叉排序树的性能分析 一棵二叉排序树的平均查找长度为： 其中： C(i)为查找第i个数据元素时的关键字比较次数

30 当二叉排序树是一棵完全二叉树时，二叉排序树的平均查找长度为 ：
当二叉排序树是一棵单分支退化树时，则平均查找长度就和有序顺序表的平均查找长度相同，即为 ：

31 （b）左分支退化二叉排序树时，k = n=7，所以查找成功的平均查找长度为：
3 4 5 6 7 8 10 (a) (b) （b）左分支退化二叉排序树时，k = n=7，所以查找成功的平均查找长度为： （a）满二叉排序树时，k = log2(7+1)=3，所以查找成功的平均查找长度为：

32 在最坏情况下，二叉排序树的平均查找长度为O(n)。在一般情况下，二叉排序树的平均查找长度为O(log2n)。

33 七、平衡二叉树 为了防止二叉排序树的最坏情况出现，可以把二叉排序树改造成平衡二叉树。 平衡二叉树或者是一棵空树，或者是具有这样性质的二叉排序树：它的左子树和右子树都是二叉排序树，并且左子树和右子树的深度之差的绝对值不超过1。 基本方法：就是在构造二叉排序树的基础上，每当如果插入了一个新结点后，使二叉树中某个结点的左子树和右子树的深度之差的绝对值超过1，则调整相应的二叉树，使二叉树中该结点的左子树和右子树的深度之差的绝对值不超过1。 特点：平衡二叉树一定不会出现单分支退化二叉排序树那样的情况，因此，平衡二叉树的平均查找长度为O(lbn)。但相对二叉排序树来说，构造平衡二叉树需要花费较多的时间，而且删除平衡二叉树中某个结点时，也要考虑删除某个结点后，平衡二叉树中某个结点的左子树和右子树的深度之差的绝对值不能超过1。

34 B_树和B+树 1 B_树 B_树是一种平衡多叉排序树。平衡是指所有叶结点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象。因此B_树的动态查找效率更高。 B_树中所有结点的孩子结点的最大值称为B_树的阶，一棵m阶的B_树或者是一棵空树，或者是满足下列要求的m叉树：

35 (2)除根结点外，其他结点至少有m/2个孩子结点 （符号“ ”表示上取整）。 (3)若根结点不是叶结点，则根结点至少有两个孩子结点；
(4)每个结点的结构为： n P0 K1 P1 K2 P2 … Kn Pn (5)所有叶结点都在同一层上。

36 1 50 20 41 72 2 44 3 23 30 35 15 60 77 80 88 ∧ root 一棵4阶B_树

37 B_树的查找算法 在B_树上查找数据元素x的方法为：将 x.key与根结点的Ki逐个进行比较： （1）若x.key=Ki则查找成功。
（2）若key<K1则沿着指针P0所指的子树继续查找。 （3）若Ki<key<Ki+1则沿着指针Pi所指的子树继续查找。 （4）若key>Kn则沿着指针Pn所指的子树继续查找。

38 B_树的插入算法 插入过程分两步完成： （1）利用查找算法找出该关键字的插入结点（B_树的插入结点一定是叶结点）。 （2）判断该结点是否还有空位置，即判断该结点是否满足n<m-1，若该结点满足n<m-1，说明该结点还有空位置，直接把关键字x.key插入到该结点的合适位置上；若该结点有n=m-1，说明该结点已没有空位置，要插入就要分裂该结点。 在3阶B_树上进行插入操作如下图示：

39 100 80 132 a b c 80 90 (a)初始状态 (b)插入90后的状态

40 100 80 90 132 a b c (c) 插入195后结点分裂前的状态

41 80 90 a 120 195 ' b 132 189 200 (d)插入结点195后结点分裂的过程 c 100

42 B_树的删除算法 删除分两步完成： （1）利用查找算法找出该关键字所在的结点。 （2）在结点上删除关键字x.key分两种情况： 一种是在叶结点上删除关键字，共有以下三种情况： （a）假如要删除关键字结点的关键字个数n大于等于m/2 ，说明删去该关键字后该结点仍满足B_树的定义，则可直接删去该关键字。其过程如下图(b)所示

43 100 80 132 116 (a)初始状态 (b)删去110后的状态

44 （b）假如要删除关键字结点的关键字个数n等于m/2 -1，说明删去该关键字后该结点将不满足B_树的定义，此时若该结点的左（或右）兄弟结点中关键字个数n大于m/2 -1，则把该结点的左（或右）兄弟结点中最大（或最小）的关键字上移到双亲结点中，同时把双亲结点中大于（或小于）上移关键字的关键字下移到要删除关键字的结点中，这样删去关键字后该结点以及它的左（或右）兄弟结点都仍旧满足B_树的定义。其过程如图(c)所示

45 100 25 60 116 132 (c)删去80后的状态

46 （c）假如要删除关键字结点的关键字个数n等于m/2-1，并且该结点的左和右兄弟结点（如果存在的话）中关键字个数n均等于m/2 -1，这时需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。其过程如图(d)所示 100 180 25 60 (d)删去116后的状态

47 另一种是在非叶结点上删除关键字。在非叶结点上删除关键字时，假设要删除关键字Ki（1≤i≤n），在删去该关键字后，以该结点Pi所指子树中的最小关键字Kmin来代替被删关键字Ki所在的位置（Pi所指子树中的最小关键字Kmin一定是在叶结点上），然后再以指针Pi所指结点为根结点查找并删除Kmin(在非叶结点上删除问题就转化成了叶结点上的删除问题)。其过程如图(e)所示

48 100 189 25 60 200 (e)删去180后的状态

49 2 B+树的定义 B+树是B_树的一种变型。和B_树主要用于动态查找问题的应用范围不同，B+树主要用于文件系统。一棵m阶B+和一棵m阶B_树的主要差异在于： （1）在B_树中，有n棵子树的结点中有n-1个关键字；而在B+树中，有n棵子树的结点中有n个关键字； （2）B+树比B_树多一层叶子结点，B+树在这层增加的叶子结点中包含了每个数据元素的所有信息，并且所有叶子结点从左到右依次链接，这样刚好构成一个每个叶子结点包含若干个有序关键字的有序单链表； （3）在B_树中，每个非叶子结点中的关键字满足大于相临左指针所指子树中所有结点的关键字值，小于相临右指针所指子树中所有结点的关键字值；而在B+树中，每个非叶子结点中的一个关键字和一个指针对应，这些关键字和对应的指针满足该关键字是对应指针所指子树中所有关键字的最大值。

50 （a）3阶B_树； （b）3阶B+树

51 11.4 哈希表 1.哈希表的基本概念 哈希函数：数据元素的关键字和该数据元素的存放位置之间的映射函数
哈希表：通过哈希函数来确定数据元素存放位置的一种特殊表结构。 1.哈希表的基本概念 构造方法：设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续内存单元，分别以每个数据元素的关键字Ki（0≤i≤n-1）为自变量，通过哈希函数h(Ki)，把Ki映射为内存单元的某个地址h(Ki)，并把该数据元素存储在这个内存单元中。哈希函数h(Ki)实际上是关键字Ki到内存单元的映射，因此，h(Ki)也称为哈希地址，哈希表也称作散列表。

52 构造哈希表时出现Ki≠Kj（i≠j）,但h(Ki)=h(Kj)的现象称作哈希冲突。这种具有不同关键字而具有相同哈希地址的数据元素称作“同义词”，由同义词引起的冲突称作同义词冲突。
解决哈希冲突的基本思想是：通过哈希冲突函数（设为hl(K)（l=1,2,…,m-1））产生一个新的哈希地址使hl(Ki)≠hl(Kj)。把要存储的n个数据元素通过哈希函数映射到了m个连续内存单元中，从而完成了哈希表的构造。 可见，构造哈希表一定要使用主关键字，不能使用次关键字 为什么？

53 例11-1 建立数据元素集合a的哈希表,a = {180, 750, 600, 430, 541, 900, 460},并比较m取值不同时的哈希冲突情况。
分析：数据元素集合a中共有7个数据元素，数据元素的关键字为三位整数，如果我们取内存单元个数m为1000，即内存单元区间为000～999，则第一，在m个内存单元中可以存放下n个数据元素，第二，若取h(K)=K，则当Ki≠Kj（i≠j）时一定有h(Ki) ≠h(Kj)。但是，在1000个内存单元中只存储7个数据元素其空间存储效率太低。

54 我们可适当减少内存单元个数。若取内存单元个数m为13，取哈希函数h(K)为：h(K) = K mod m，即哈希地址h(K)为关键字K除m所得的余数，则有：
h(180) = h(750) = 9 h(600) = 2 h(430) = 1 h(541) = 8 h(900) = 3 h(460) = 5

55 若取内存单元个数m为11，仍取哈希函数h(K)为：h(K) = K mod m，则有：
h(180) = 4 h(750) = 2 h(600) = 6 h(430) = 1 h(541) = 3 h(900) = 9 h(460) = 9 此时h(460) =h(900) = 9，因此存在哈希冲突。 若取第一次哈希冲突函数h1(K)为哈希地址加1后模m，即： h1(K) = (h(K)+1) mod m = (K+1) mod m， 则有： h1(460) = 10

56 构造哈希表时 ，冲突是不可避免的，有关因素主要有如下三个：
(1)与装填因子有关。装填因子是指哈希表中已存入的数据元素个数ｎ与哈希地址空间大小ｍ的比值，即α＝ｎ/ｍ，α越小，冲突的可能性就越小，但哈希表中空闲单元的比例就越大； α越大（最大可取1）时，冲突的可能性就越大，但哈希表中空闲单元的比例就越小，存储空间的利用率就越高。 (2)与所采用的哈希函数有关。 (3)与解决哈希冲突的哈希冲突函数有关。

57 2.哈希函数的构造方法 1.除留余数法 2.直接定址法 3.数字分析法
函数设计目标:使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单，以达到尽可能高的时间效率。 1.除留余数法 2.直接定址法 3.数字分析法 常用的哈希函数构造方法有：

58 h(K) = K mod m 一、除留余数法 优点：计算简单，适用范围广 关键：选好哈希表长度m 技巧：哈希表长m取素数时效果较好
二、直接定址法 h(K) = K + C 优点：计算简单，不会发生冲突 缺点：有可能造成内存单元的大量浪费

59 3.哈希冲突解决方法 一、开放定址法 二、链表法 三、数字分析法
特点：取数据元素关键字中某些取值较均匀的数字位作为哈希地址，只适合于所有关键字值已知的情况 3.哈希冲突解决方法 常见的冲突处理方法有： 一、开放定址法 二、链表法

60 (1)线性探查法 一、开放定址法 设计思路：以发生哈希冲突的哈希地址为自变量、通过某种哈希冲突函数得到一个新的空闲的内存单元地址。
具体实现方法： (1)线性探查法 优点：只要哈希表未被填满，保证能找到一个空地址单元存 放有冲突的元素； 缺点：容易产生“堆积” ，大大降低了查找效率。

61 (2)平方探查法 平方探查法的探查跨步很大，所以可避免出现堆积问题 (3)伪随机数法

62 二、链表法 基本思想：如果没有发生哈希冲突，则直接存放该数据元素；如果发生了哈希冲突，则把发生哈希冲突的数据元素另外存放在单链表中。 方法有两种：第一种方法是为发生哈希冲突的不同的同义词建立不同的单链表;第二种方法是为发生哈希冲突的所有同义词建立一个单链表。

63 例11-2建立数据元素集合a的哈希表。a = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55}。要求哈希函数采用除留余数法，解决冲突方法采用链表法。 设计分析：数据元素集合a中共有13个数据元素，取哈希表的内存单元个数m=13。除留余数法的哈希函数为：h(K) = K mod m有： h(16) = 3 h(74) = 9 h(60) = 8 h(43) = 4 h(54) = 2 h(90) = 12 h(46) = 7 h(31) = 5 h(29) = 3 h(88) = 10 h(77) = 12 h(66) = 1 h(55) = 3

64 采用链表法的第一种方法建立的哈希表存储结构 如下图所示
link data 下标 66 1 54 2 16 3 43 4 31 5 6 46 7 60 8 74 9 88 10 11 90 12 29 55 77 ∧ next

65 4 哈希表设计 例11-3编写一组包括哈希表初始化、哈希表元素插入、哈希表元素删除、哈希表查找和哈希表空间撤消操作的函数。要求哈希函数采用除留余数法，解决哈希冲突方法采用开放定址法的线性探查法。并设计一个测试程序进行测试。 设计： 数据结构设计：结构体HashTable由哈希表数组、数组个数和当前表项个数三部分组成，其中哈希表数组中每个表项的数据类型是结构体HashItem。结构体HashItem由数据元素和表项状态两部分组成，其中数据元素仅包括一个关键字域，表项状态的数据类型为枚举类型，表项状态域有Empty, Active和Deleted三种状态，分别表示表项的空、已占用和被删除三种状态。

66 typedef enum {Empty, Active, Deleted} KindOfItem ; typedef struct { KeyType key; }DataType; DataType data; KindOfItem info; }HashItem; HashItem *ht; int tableSize; int currentSize; }HashTable; 

67 int Initiate(HashTable *hash, int mSize)
{ hash->tableSize = mSize; hash->ht = (HashItem *)malloc(sizeof(HashItem)*mSize); if(hash->ht == NULL) return 0; else { hash->currentSize = 0; return 1; }

68 int Find(HashTable *hash, DataType x)
{ int i = x.key % hash->tableSize; int j = i;  while(hash->ht[j].info == Active && hash->ht[j].data.key != x.key) { j = (j + 1) % hash->tableSize; if(j == i) return -hash->tableSize; } if(hash->ht[j].info == Active) return j; else return -j; into Insert(HashTable *hash, DataType x) { int i = Find(hash, x);   if(i > 0) return 0; else if(i != -hash->tableSize) { hash->ht[-i].data = x; hash->ht[-i].info = Active; hash->currentSize++; return 1; else return 0;

69 int Delete(HashTable *hash, DataType x)
{ int i = Find(hash, x); if(i >= 0) { hash->ht[i].info = Deleted; hash->currentSize--; return 1; } else return 0; void Destroy(HashTable *hash) { free(hash->ht); 三、测试程序 例11-3 测试程序设计。建立数据元素集合a = {180,750,600,430,541,900,460}的哈希表，并分别测试哈希表长度m=13和m=11两种情况得到的哈希表。

70 作业 1) 习题11-1，11-2 ，11-3 2) 习题11-7， 11-8 3) 习题11-6， 11-9