【强烈推荐考研辅导最佳图书--------零基础学数据结构】第11章查找.ppt

《【强烈推荐考研辅导最佳图书--------零基础学数据结构】第11章查找.ppt》由会员分享，可在线阅读，更多相关《【强烈推荐考研辅导最佳图书--------零基础学数据结构】第11章查找.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【强烈推荐考研辅导最佳图书-零基础学数据结构】第11章查找11.1 11.1 查找的基本概念查找的基本概念在介绍有关查找的算法之前，先介绍与查找相关的基在介绍有关查找的算法之前，先介绍与查找相关的基本概念。本节主要介绍查找的基本概念及相关概念。本概念。本节主要介绍查找的基本概念及相关概念。关键字与主关键字：数据元素中某个数据项的值。如关键字与主关键字：数据元素中某个数据项的值。如果该关键字可以将所有的数据元素区别开来，也就是说可果该关键字可以将所有的数据元素区别开来，也就是说可以唯一标识一个数据元素，则该关键字被称为主关键字，以唯一标识一个数据元素，则该关键字被称为主关键字，否则被称为次关键字

2、。特别地，如果数据元素只有一个数否则被称为次关键字。特别地，如果数据元素只有一个数据项，则数据元素的值即是关键字。据项，则数据元素的值即是关键字。11.2.1 11.2.1 顺序表的查找顺序表的查找顺序表的存储结构用顺序表的存储结构用C语言描述如下。语言描述如下。#define MaxSize 100typedef struct KeyType key;DataType;typedef struct DataType listMaxSize;int length;SSTable;11.2.1 11.2.1 顺序表的查找顺序表的查找int SeqSearch(SSTable S,DataType

3、 x)/*在在顺顺序表中序表中查查找关找关键键字字为为x的元素，如果找到返回的元素，如果找到返回该该元素在表中的位置，否元素在表中的位置，否则则返回返回0*/int i=0;while(ix.key)/*从有序从有序顺顺序表的最后序表的最后一个元素开始向前比一个元素开始向前比较较*/i-;return i;11.2.1 11.2.1 顺序表的查找顺序表的查找假设表中有假设表中有n个元素且要查找的数据元素在数据元素个元素且要查找的数据元素在数据元素集合中出现的概率相等即为集合中出现的概率相等即为1/n，则有序顺序表在查找成功，则有序顺序表在查找成功时的平均查找长度为：时的平均查找长度为：即查找成

4、功时平均比较次数约为表长的一半。在查找即查找成功时平均比较次数约为表长的一半。在查找失败时，即要查找的元素没有在表中，则有序顺序表在查失败时，即要查找的元素没有在表中，则有序顺序表在查找失败时的平均查找长度为：找失败时的平均查找长度为：即查找失败时平均比较次数也同样约为表长的一半。即查找失败时平均比较次数也同样约为表长的一半。11.2.2 11.2.2 有序顺序表的查找有序顺序表的查找2折半查找折半查找11.2.2 11.2.2 有序顺序表的查找有序顺序表的查找int BinarySearch(SSTable S,DataType x)/*在有序在有序顺顺序表中折半序表中折半查查找关找关键键字

5、字为为x的元素，如果找到返回的元素，如果找到返回该该元素在表中的位元素在表中的位置，否置，否则则返回返回0*/int low,high,mid;low=0,high=S.length-1;/*设设置待置待查查找元素范找元素范围围的下界和上界的下界和上界*/while(low=high)mid=(low+high)/2;if(S.listmid.key=x.key)/*如果找到元素，如果找到元素，则则返回返回该该元素所在的位置元素所在的位置*/return mid+1;else if(S.listmid.keyx.key)/*如果如果mid所指示的元素大于关所指示的元素大于关键键字，字，则则修修

6、改改high指指针针*/high=mid-1;return 0;11.2.2 11.2.2 有序顺序表的查找有序顺序表的查找11.2.2 11.2.2 有序顺序表的查找有序顺序表的查找对于具有对于具有n个结点的有序表刚好能够构成一个深度为个结点的有序表刚好能够构成一个深度为h的满二叉树，则有的满二叉树，则有h=。二叉树中第。二叉树中第i层的结点个数层的结点个数是是2i-1，假设表中每个元素的查找概率相等，即，假设表中每个元素的查找概率相等，即 。则有。则有序表的折半查找成功时的平均查找长度为：序表的折半查找成功时的平均查找长度为：在查找失败时，即要查找的元素没有在表中，则有序在查找失败时，即要

7、查找的元素没有在表中，则有序顺序表的折半查找失败时的平均查找长度为：顺序表的折半查找失败时的平均查找长度为：11.2.3 11.2.3 索引顺序表的查找索引顺序表的查找索引顺序表的查找就是将顺序表分成几个单元，然后索引顺序表的查找就是将顺序表分成几个单元，然后为这几个单元建立一个索引，利用索引在其中一个单元中为这几个单元建立一个索引，利用索引在其中一个单元中进行查找。索引顺序表查找也称为分块查找，主要应用在进行查找。索引顺序表查找也称为分块查找，主要应用在表中存在大量的数据元素的时候，通过为顺序表建立索引表中存在大量的数据元素的时候，通过为顺序表建立索引和分块来提高查找的效率。和分块来提高查找

8、的效率。11.2.3 11.2.3 索引顺序表的查找索引顺序表的查找11.2.4 11.2.4 静态查找应用举例静态查找应用举例下面通过一个实例来说明静态查找的应用。下面通过一个实例来说明静态查找的应用。例例11_1 给定一组元素，利用顺序表查找、有序顺序表给定一组元素，利用顺序表查找、有序顺序表查找和索引顺序表查找值查找和索引顺序表查找值x的元素。的元素。1。顺序表的各种查找方式的实现。顺序表的各种查找方式的实现2。顺序表的各种查找方式的实现。顺序表的各种查找方式的实现11.3 11.3 动态查找动态查找动态查找是指在查找的过程中动态生成表结构，对于动态查找是指在查找的过程中动态生成表结构，

9、对于给定的关键字，如果表中存在则返回其位置，表示查找成给定的关键字，如果表中存在则返回其位置，表示查找成功，否则，插入该关键字的元素。动态查找包括二叉树和功，否则，插入该关键字的元素。动态查找包括二叉树和树结构两种类型的查找。本节的主要学习内容包括二叉排树结构两种类型的查找。本节的主要学习内容包括二叉排序树的查找、平衡二叉树的查找。序树的查找、平衡二叉树的查找。11.3.1 11.3.1 二叉排序树二叉排序树1二叉排序树的定义与查找二叉排序树的定义与查找typedef struct NodeDataType data;struct Node*lchild,*rchild;BiTreeNode,

10、*BiTree;11.3.1 11.3.1 二叉排序树二叉排序树11.3.1 11.3.1 二叉排序树二叉排序树BiTree BSTSearch(BiTree T,DataType x)/*二叉排序二叉排序树树的的查查找，如果找到元素找，如果找到元素x，则则返回指向返回指向结结点的指点的指针针，否，否则则返回返回NULL*/BiTreeNode*p;if(T!=NULL)/*如果二叉排序如果二叉排序树树不不为为空空*/p=T;while(p!=NULL)if(p-data.key=x.key)/*如果找到，如果找到，则则返回指向返回指向该结该结点的指点的指针针*/return p;else i

11、f(x.keydata.key)/*如果关如果关键键字小于字小于p指向的指向的结结点的点的值值，则则在在左子左子树树中中查查找找*/p=p-lchild;elsep=p-rchild;/*如果关如果关键键字大于字大于p指向的指向的结结点的点的值值，则则在右子在右子树树中中查查找找*/return NULL;11.3.1 11.3.1 二叉排序树二叉排序树2二叉排序树的插入操二叉排序树的插入操作作3二叉排序树的删除操二叉排序树的删除操作作11.3.1 11.3.1 二叉排序树二叉排序树4二叉排序树的应用举例二叉排序树的应用举例11.3.2 11.3.2 平衡二叉树平衡二叉树1平衡二叉树的定义平衡

12、二叉树的定义11.3.2 11.3.2 平衡二叉树平衡二叉树2二叉排序树的平衡处理二叉排序树的平衡处理二叉排序树的平衡处理算法实现包括四种情形：二叉排序树的平衡处理算法实现包括四种情形：LL型、型、LR型、型、RL型和型和RR型。型。1LL型的平衡处理型的平衡处理2LR型的平衡处理型的平衡处理3RL型的平衡处理型的平衡处理4RR型的平衡处理型的平衡处理11.3.2 11.3.2 平衡二叉树平衡二叉树11.3.2 11.3.2 平衡二叉树平衡二叉树LL型型11.3.2 11.3.2 平衡二叉树平衡二叉树当二叉树失去平衡时，对当二叉树失去平衡时，对LL型二叉排序树的调整用以型二叉排序树的调整用以下

13、语句实现：下语句实现：BSTree b;b=p-lchild;/*lc指向指向p的左子树的根结点的左子树的根结点*/p-lchild=b-rchild;/*将将lc的右子树作为的右子树作为p的左子的左子树树*/b-rchild=p;p-bf=b-bf=0;/*修改平衡因子修改平衡因子*/11.3.2 11.3.2 平衡二叉树平衡二叉树LR型型 11.3.2 11.3.2 平衡二叉树平衡二叉树相应地，对于相应地，对于LR型的二叉排序树的调整可以用以下语型的二叉排序树的调整可以用以下语句实现：句实现：BSTree b,c;b=p-lchild,c=b-rchild;b-rchild=c-lchil

14、d;/*将将结结点点C的左子的左子树树作作为结为结点点B的右子的右子树树*/p-lchild=c-rchild;/*将将结结点点C的右子的右子树树作作为结为结点点A的左子的左子树树*/c-lchild=b;/*将将B作作为结为结点点C的左子的左子树树*/c-rchild=p;/*将将A作作为结为结点点C的右子的右子树树*/*修改平衡因子修改平衡因子*/p-bf=-1;b-bf=0;c-bf=0;11.3.2 11.3.2 平衡二叉树平衡二叉树RL型型11.3.2 11.3.2 平衡二叉树平衡二叉树相应地，对于相应地，对于RL型的二叉排序树的调整可以用以下语型的二叉排序树的调整可以用以下语句实现

15、：句实现：BSTree b,c;b=p-rchild,c=b-lchild;b-lchild=c-rchild;/*将将结结点点C的右子的右子树树作作为结为结点点B的左子的左子树树*/p-rchild=c-lchild;/*将将结结点点C的左子的左子树树作作为结为结点点A的右子的右子树树*/c-lchild=p;/*将将A作作为结为结点点C的左子的左子树树*/c-rchild=b;/*将将B作作为结为结点点C的右子的右子树树*/*修改平衡因子修改平衡因子*/p-bf=1;b-bf=0;c-bf=0;11.3.2 11.3.2 平衡二叉树平衡二叉树RR 型型11.3.2 11.3.2 平衡二叉树

16、平衡二叉树相应地，对于相应地，对于RR型的二叉排序树的调整可以用以下语型的二叉排序树的调整可以用以下语句实现：句实现：BSTree b,c;b=p-rchild;p-rchild=b-lchild;/*将将结结点点B的左子的左子树树作作为结为结点点A的右子的右子树树*/b-lchild=p;/*将将A作作为结为结点点B的左子的左子树树*/*修改平衡因子修改平衡因子*/p-bf=0;b-bf=0;11.4 B_11.4 B_树与树与B B+树树B_树与树与B+是两种特殊的动态查找树。本节的主要学习是两种特殊的动态查找树。本节的主要学习内容包括内容包括B_树定义、查找、插入与删除操作，最后对树定义

17、、查找、插入与删除操作，最后对B+树树进行了简单的介绍。进行了简单的介绍。11.4.1 B_11.4.1 B_树树1B_树的定义树的定义11.4.1 B_11.4.1 B_树树例如，一棵深度为例如，一棵深度为4的的4阶的阶的B_树如图树如图11.18所示。所示。11.4.1 B_11.4.1 B_树树2B_树的查找树的查找B_树树的的类类型定型定义义用用C语语言描述如下：言描述如下：#define m 4/*B_树树的的阶阶数数*/typedef struct BTNode/*B_树类树类型定型定义义*/int keynum;/*每个每个结结点中的关点中的关键键字个数字个数*/struct B

18、TNode*parent;/*指向双指向双亲结亲结点点*/KeyType datam+1;/*结结点中关点中关键键字信息字信息*/struct BTNode*ptrm+1;/*指指针针向量向量*/BTNode,*BTree;11.4.1 B_11.4.1 B_树树3B_树的插入操作树的插入操作11.4.1 B_11.4.1 B_树树11.4.1 B_11.4.1 B_树树11.4.1 B_11.4.1 B_树树11.4.2 B11.4.2 B+树树4B_树的删除操作树的删除操作11.4.2 B11.4.2 B+树树B+树是树是B_树的一种变型。它与树的一种变型。它与B_树的主要区别在于：树的主

19、要区别在于：（1）如果一个结点有）如果一个结点有n棵子树，则该结点也必有棵子树，则该结点也必有n个个关键字，即关键字个数与结点的子树个数相等；关键字，即关键字个数与结点的子树个数相等；（2）所有的非叶子结点包含子树的根结点的最大或）所有的非叶子结点包含子树的根结点的最大或者最小的关键字信息，因此所有的非叶子结点可以作为索者最小的关键字信息，因此所有的非叶子结点可以作为索引；引；（3）叶子结点包含所有关键字信息和关键字记录的）叶子结点包含所有关键字信息和关键字记录的指针，所有叶子结点中的关键字按照从小到大的顺序依次指针，所有叶子结点中的关键字按照从小到大的顺序依次通过指针链接。通过指针链接。11

20、.4.2 B11.4.2 B+树树11.5 11.5 哈希表哈希表在前面学习过的有关查找的算法都经过了一系列的比在前面学习过的有关查找的算法都经过了一系列的比较过程，查找算法效率的高低取决于比较的次数。而比较较过程，查找算法效率的高低取决于比较的次数。而比较理想的情况是不经过比较就能确定要查找元素的位置，那理想的情况是不经过比较就能确定要查找元素的位置，那么就需要建立一种数据元素的关键字与数据元素存放地址么就需要建立一种数据元素的关键字与数据元素存放地址之间的对应关系，通过数据元素的关键字直接确定其存放之间的对应关系，通过数据元素的关键字直接确定其存放的位置。的位置。11.5.1 11.5.1

21、 哈希表的定义哈希表的定义如何在查找元素的过程中，不与给定的关键字进行比如何在查找元素的过程中，不与给定的关键字进行比较，就能确定所查找元素的存放位置。这就需要在元素的较，就能确定所查找元素的存放位置。这就需要在元素的关键字与元素的存储位置之间建立起一种对应关系，使得关键字与元素的存储位置之间建立起一种对应关系，使得元素的关键字与唯一的存储位置对应。哈希表也称为散列元素的关键字与唯一的存储位置对应。哈希表也称为散列函数。函数。11.5.2 11.5.2 哈希函数的构造方法哈希函数的构造方法1直接定址法直接定址法2平方取中法平方取中法3折叠法折叠法4除留余数法除留余数法11.5.3 11.5.3

22、 处理冲突的方法处理冲突的方法1开放定址法开放定址法2再哈希法再哈希法3链地址法链地址法11.5.3 11.5.3 处理冲突的方法处理冲突的方法11.5.4 11.5.4 哈希表应用举例哈希表应用举例1哈希表的操作哈希表的操作2测试部分测试部分11.6 11.6 小结小结本章主要介绍了数据结构中经常使用的技术本章主要介绍了数据结构中经常使用的技术查找查找在计算机的非数值处理中，查找是一种非常重要的操在计算机的非数值处理中，查找是一种非常重要的操作。作。静态查找主要包括：顺序表、有序顺序表和索引顺序静态查找主要包括：顺序表、有序顺序表和索引顺序表的查找。表的查找。动态查找主要包括二叉排序树、平衡二叉树、动态查找主要包括二叉排序树、平衡二叉树、B_树和树和B+树。树。哈希表是利用哈希函数的映射关系直接确定要查找元哈希表是利用哈希函数的映射关系直接确定要查找元素的位置，大大减少了与元素的关键字的比较次数。素的位置，大大减少了与元素的关键字的比较次数。本章的内容是数据结构中的一个关键技术。在介绍查本章的内容是数据结构中的一个关键技术。在介绍查找的过程中，本文给出了相应的图示和应用举例，以加深找的过程中，本文给出了相应的图示和应用举例，以加深理解。理解。此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!