强烈考研辅导最佳图书零基础学数据结构查找.ppt

,Click to edit Master title style,Click to edit Master text styles,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,11.1 查找的基本概念,在介绍有关查找的算法之前，先介绍与查找相关的基本概念。本节主要介绍查找的基本概念及相关概念。,关键字与主关键字：数据元素中某个数据项的值。如果该关键字可以将所有的数据元素区别开来，也就是说可以唯一标识一个数据元素，则该关键字被称为主关键字，否则被称为次关键字。特别地，如果数据元素只有一个数据项，则数据元素的值即是关键字。,11.1 查找的基本概念,查找表：,查找：,静态查找：,动态查找：,平均查找长度：,11.2,静态查找,静态查找主要包括：顺序表、有序顺序表和索引顺序表的查找。本节的主要学习内容是几种静态表的查找。,11.2.1 顺序表的查找,顺序表的查找是指从表的一端开始，逐个与关键字进行比较，如果某个数据元素的关键字与给定的关键字相等，则查找成功，函数返回该数据元素所在的顺序表的位置。,11.2.1 顺序表的查找,顺序表的存储结构用C语言描述如下。,#define MaxSize 100,typedef struct,KeyType key;,DataType;,typedef struct,DataType listMaxSize;,int length;,SSTable;,11.2.1 顺序表的查找,int SeqSearch(SSTable S,DataType x),/*在顺序表中查找关键字为x的元素，如果找到返回该元素在表中的位置，否则返回0*/,int i=0;,while(ix.key)/*从有序顺序表的最后一个元素开始向前比较*/,i-;,return i;,11.2.1 顺序表的查找,假设表中有n个元素且要查找的数据元素在数据元素集合中出现的概率相等即为1/n，则有序顺序表在查找成功时的平均查找长度为：,即查找成功时平均比较次数约为表长的一半。在查找失败时，即要查找的元素没有在表中，则有序顺序表在查找失败时的平均查找长度为：,即查找失败时平均比较次数也同样约为表长的一半。,11.2.2 有序顺序表的查找,2折半查找,11.2.2 有序顺序表的查找,int BinarySearch(SSTable S,DataType x),/*在有序顺序表中折半查找关键字为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所指示的元素大于关键字，则修改high指针*/,high=mid-1;,return 0;,11.2.2 有序顺序表的查找,11.2.2 有序顺序表的查找,对于具有n个结点的有序表刚好能够构成一个深度为h的满二叉树，则有h=。二叉树中第i层的结点个数是2,i-1,，假设表中每个元素的查找概率相等，即 。则有序表的折半查找成功时的平均查找长度为：,在查找失败时，即要查找的元素没有在表中，则有序顺序表的折半查找失败时的平均查找长度为：,11.2.3 索引顺序表的查找,索引顺序表的查找就是将顺序表分成几个单元，然后为这几个单元建立一个索引，利用索引在其中一个单元中进行查找。索引顺序表查找也称为分块查找，主要应用在表中存在大量的数据元素的时候，通过为顺序表建立索引和分块来提高查找的效率。,11.2.3 索引顺序表的查找,11.2.4 静态查找应用举例,下面通过一个实例来说明静态查找的应用。,例11_1 给定一组元素，利用顺序表查找、有序顺序表查找和索引顺序表查找值x的元素。,1。顺序表的各种查找方式的实现,2。顺序表的各种查找方式的实现,11.3 动态查找,动态查找是指在查找的过程中动态生成表结构，对于给定的关键字，如果表中存在则返回其位置，表示查找成功，否则，插入该关键字的元素。动态查找包括二叉树和树结构两种类型的查找。本节的主要学习内容包括二叉排序树的查找、平衡二叉树的查找。,11.3.1 二叉排序树,1二叉排序树的定义与查找,typedef struct Node,DataType data;,struct Node*lchild,*rchild;,BiTreeNode,*BiTree;,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 if(x.keydata.key)/*如果关键字小于p指向的结点的值，则在左子树中查找*/,p=p-lchild;,else,p=p-rchild;/*如果关键字大于p指向的结点的值，则在右子树中查找*/,return NULL;,11.3.1 二叉排序树,2二叉排序树的插入操作,3二叉排序树的删除操作,11.3.1 二叉排序树,4二叉排序树的应用举例,11.3.2 平衡二叉树,1平衡二叉树的定义,11.3.2 平衡二叉树,2二叉排序树的平衡处理,二叉排序树的平衡处理算法实现包括四种情形：LL型、LR型、RL型和RR型。,1LL型的平衡处理,2LR型的平衡处理,3RL型的平衡处理,4RR型的平衡处理,11.3.2 平衡二叉树,11.3.2 平衡二叉树,LL型,11.3.2 平衡二叉树,当二叉树失去平衡时，对LL型二叉排序树的调整用以下语句实现：,BSTree b;,b=p-lchild;/*lc指向p的左子树的根结点*/,p-lchild=b-rchild;/*将lc的右子树作为p的左子树*/,b-rchild=p;,p-bf=b-bf=0;/*修改平衡因子*/,11.3.2 平衡二叉树,LR型,11.3.2 平衡二叉树,相应地，对于LR型的二叉排序树的调整可以用以下语句实现：,BSTree b,c;,b=p-lchild,c=b-rchild;,b-rchild=c-lchild;/*将结点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 平衡二叉树,RL型,11.3.2 平衡二叉树,相应地，对于RL型的二叉排序树的调整可以用以下语句实现：,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 平衡二叉树,RR 型,11.3.2 平衡二叉树,相应地，对于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_树与B,+,树,B_树与B,+,是两种特殊的动态查找树。本节的主要学习内容包括B_树定义、查找、插入与删除操作，最后对B,+,树进行了简单的介绍。,11.4.1 B_树,1B_树的定义,11.4.1 B_树,例如，一棵深度为4的4阶的B_树如图11.18所示。,11.4.1 B_树,2B_树的查找,B_树的类型定义用C语言描述如下：,#define m 4/*B_树的阶数*/,typedef struct BTNode/*B_树类型定义*/,int keynum;/*每个结点中的关键字个数*/,struct BTNode*parent;/*指向双亲结点*/,KeyType datam+1;/*结点中关键字信息*/,struct BTNode*ptrm+1;/*指针向量*/,BTNode,*BTree;,11.4.1 B_树,3B_树的插入操作,11.4.1 B_树,11.4.1 B_树,11.4.1 B_树,11.4.2 B,+,树,4B_树的删除操作,11.4.2 B,+,树,B,+,树是B_树的一种变型。它与B_树的主要区别在于：,（1）如果一个结点有n棵子树，则该结点也必有n个关键字，即关键字个数与结点的子树个数相等；,（2）所有的非叶子结点包含子树的根结点的最大或者最小的关键字信息，因此所有的非叶子结点可以作为索引；,（3）叶子结点包含所有关键字信息和关键字记录的指针，所有叶子结点中的关键字按照从小到大的顺序依次通过指针链接。,11.4.2 B,+,树,11.5 哈希表,在前面学习过的有关查找的算法都经过了一系列的比较过程，查找算法效率的高低取决于比较的次数。而比较理想的情况是不经过比较就能确定要查找元素的位置，那么就需要建立一种数据元素的关键字与数据元素存放地址之间的对应关系，通过数据元素的关键字直接确定其存放的位置。,11.5.1 哈希表的定义,如何在查找元素的过程中，不与给定的关键字进行比较，就能确定所查找元素的存放位置。这就需要在元素的关键字与元素的存储位置之间建立起一种对应关系，使得元素的关键字与唯一的存储位置对应。哈希表也称为散列函数。,11.5.2 哈希函数的构造方法,1直接定址法,2平方取中法,3折叠法,4除留余数法,11.5.3 处理冲突的方法,1开放定址法,2再哈希法,3链地址法,11.5.3 处理冲突的方法,11.5.4 哈希表应用举例,1哈希表的操作,2测试部分,11.6,小结,本章主要介绍了数据结构中经常使用的技术查找,在计算机的非数值处理中，查找是一种非常重要的操作。,静态查找主要包括：顺序表、有序顺序表和索引顺序表的查找。,动态查找主要包括二叉排序树、平衡二叉树、B_树和B,+,树。,哈希表是利用哈希函数的映射关系直接确定要查找元素的位置，大大减少了与元素的关键字的比较次数。,本章的内容是数据结构中的一个关键技术。在介绍查找的过程中，本文给出了相应的图示和应用举例，以加深理解。,