《数据结构查找》PPT课件.ppt

第八章 查找,81 查找的基本概念 82 顺序表查找 83 索引查找 84 树表查找 85 散列表查找,8查找的基本概念,1查找表 查找表（Search Table）是由记录序列组成的文件或线性表。 2查找表上常见的操作 （1）查询某个“特定的”记录是否在查找表中；（2）检索某个“特定的”记录的信息；（3）在查找表中插入记录；（4）在查找表中删除记录。根据在查找表上实施的操作不同，可将查找表分为。 3静态查找表和动态查找表 静态查找表只做前两项统称为“查找”的操作，在查找的过程中不再动态地改变查找表，即不做插入和删除记录的操作；动态查找表的表结构本身是在查找过程中动态生成的，即在查找过程中同时插入查找表中不存在的记录，或者从表中删除已经存在的某个记录。,4查找依据：一般是把记录的关键字作为查找的依据 5查找（Search）的定义：给定某个特定值k，在查找表中找出关键字等于给定值k的记录，若找到，则查找成功，返回该记录在表中的序号；否则查找不成功，给出查找失败的信息。 6评价查找算法的效率 平均查找长度ASL（Average Search Length），其计算公式为： 其中，n是记录的个数；Ci是找到第i个记录需要进行的比较次数；Pi是查找第i个记录的概率，这里P1=P2=Pi=Pn=1/n。 7查找表常用的存储方式：顺序、链接、索引和散列四种来存储。本章共介绍了四类查找方法，即顺序表查找、索引查找、树表查找、散列表查找。,82顺序表查找,顺序存储结构存储的查找表，就是顺序表。 顺序表的存储结构用C语言描述如下： #define N 100 typedef struct KeyType key; DataType other; RecType ; RecType RN+1; N是记录的个数；R0闲置的主要原因为： （1）使下标和记录序号对应； （2）留作他用，比如用作监视哨。 基于顺序表的查找两种方法：顺序查找和二分查找,821顺序查找,顺序查找（Sequential Search）又称线性查找，是最简单、最基本的查找方法。 顺序查找的基本思想是：从表的一端开始，依次将每个记录的关键字与给定值k进行比较，若某个记录的关键字与k相等，表明查找成功，并给出记录在表中的位置（序号）；若整个表检测完，仍未找到与k相等的关键字，表明查找失败，给出查找失败的信息。,顺序查找算法的C函数如下 ：,int seqSearch(RecType R , KeyType k) /*在数组R中顺序查找关键字等于k的记录，若找到返回记录序号，否则返回0*/ int i； R0.key = k; /*R0用作监视哨*/ i=N; /*从表的尾端向前查找 */ while（Ri.key!=k） i-； return i； ,顺序查找算法的性能分析,平均查找长度 查找成功时，平均查找长度为： 查找不成功时，与关键字的比较次数总是n+1次。 查找算法的平均时间复杂度O(n)。 优缺点 优点是算法简单，可以方便地插入记录。 缺点是当n很大时，平均查找长度较大，查找效率较低。 顺序查找方法不仅适用于顺序表，也同样适合于单链表。,822 二分查找,二分查找（Binary Search）又称折半查找，是一种效率较高的查找方法。二分查找要求顺序表是有序表 二分查找的基本思想是：初始时，查找区间为整个有序表，取查找区间的中间记录作为比较对象，若中间记录的关键字与给定值相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的前半区继续查找；若给定值大于中间记录的关键字，则在中间记录的后半区继续查找。不断重复上述查找过程，直至新区间中间记录的关键字等于给定值，则查找成功，或者查找区间不断缩小直到为空，表明查找失败。,二分查找的具体查找步骤为： （1）设变量low和high表示查找区间的起始和终端下标，初始时查找区间是R1RN，low取值为1，high取值为N。设变量mid表示查找区间中间位置的下标，计算公式：mid= (low+hign)/2 （2）当lowhigh（查找区间非空）时，求mid= (low+hign)/2，进行如下比较： 若k=Rmid.key，查找成功，返回记录在表中位置 若kRmid.key，则low=mid+1，在后半区继续查找 （3）当lowhigh时，查找区间为空，说明查找失败,例8.一个有序表中有13个记录，记录的关键字序列为（7，14，18，21，23，29，31，35，38，42，46，49，52），给定值k分别为14和22，在表中查找关键字与k相等的记录。, low=1 high=13 mid=7 low=1 high=6 kRmid，调整到后半区：low=mid+1 mid=2 k=Rmid，查找成功，返回找到的记录序号2 查找k=14的过程示意图,0 1 2 3 4 5 6 7 8 9 10 11 12 13, low=1 high=13 mid=7 low=1 high=6 kRmid，low=mid+1 mid=5 low=high=4 kRmid，low=mid+1 lowhigh 查找区间为空，查找失败。 查找k=22的过程示意图,0 1 2 3 4 5 6 7 8 9 10 11 12 13,二分查找非递归算法的C函数： int binarySearch(RecType R , KeyType k) /*用二分查找法在数组R中查找关键字为k的记录，若找到返回该记录的位置，否则返回0。*/ int low, hign, mid; low=1; high=N; /*设置初始查找区间*/ while(low=high) /*查找区间非空*/ mid=(low+high)/2; /*计算查找区间中间位置的下标*/ if(k=Rmid.key) return mid; /*查找成功，返回记录的位置*/ else if(kRmid.key) high=mid-1; /*调整到前半区*/ else low=mid+1; /*调整到后半区*/ return 0; ,二分查找过程判定树,例8.1的二分查找过程对应的判定树,查找成功情况下的平均查找长度为： ASL=（1+22+34+46）/13=36/13。,查找不成功情况下的判定树,查找不成功时的平均查找长度ASL为： ASL不成功=（32+412）/14=54/14。,二分查找性能分析,二分查找的平均查找长度 以树高为k的满二叉树为例，树中共有n=2k-1个结点，第i层有2i-1个结点，则二分查找的平均查找长度为： 二分查找算法的平均时间复杂度为O(log2n),二分查找的特点 优点：比较次数相对较少，查找效率较高。 缺点：在查找之前需要建立有序表，二分查找要求顺序存储有序表，因而在表中插入或删除记录都需要移动大量的记录， 二分查找方法适合于数据相对稳定的静态查找表。 二分查找只适合顺序存储结构，而不适合链接存储结构。,83 索引查找,索引查找是建立在索引存储结构上的查找方法。 例如在英文字典里查找某个单词的过程就是一个索引查找。把字典看作是索引查找的对象，其中，字典的正文是主要部分，称作是主表，字母索引表是为了方便查找而建立的索引，称作是索引表。,831 索引表的组织,索引存储的基本思想是：除了存储主表的记录外，还要为主表建立一个或若干个附加的索引表。索引表用来标识主表记录的存储位置，它由若干个被称为索引项的数据元素组成。 索引项的一般形式为（索引关键字，地址），索引关键字是记录的某个数据项，一般会是记录的关键字，地址是用来标识一个或一组记录的存储位置。 若一个记录对应一个索引项，则该索引表为稠密索引（Dense Index）。若一组记录对应一个索引项，则该索引表为稀疏索引（Sparse Index）。,例8.2 为表8.1所示的通讯录建立索引表。,（1）稠密索引： 稠密索引为每个记录建立索引项（索引关键字，地址） 主表：0 1 2 3 4 5 6 7 8 9 索引表：,1）稀疏索引：把主表的记录按照某种规则划分为几个子表，然后再为每个子表建立索引项（索引关键字，地址） 按照所在院系划分，可以有4个子表，分别为：法学院LA1=（1001，1002，1003），理学院LA2=（1004，1005），外语学院LA3=（1006，1007，1008），艺术学院LA4=（1009，1010）。 索引表： 这种按照主表的非关键字建立的索引表称为辅助索引表。,832 分块查找,分块查找（Block Search）又称索引顺序查找，是对顺序查找方法的一种改进。 分块查找要求对顺序存储的主表建立索引： （1）主表“分块”有序：将主表划分为几个子表，即分块，块内可以无序，但块与块之间必须有序，即前一个块中的最大关键字必须小于后一个块中的最小关键字； （2）建立有序的索引表：为每一块建立索引项，索引项包括：每一块中的最大关键字和每一块在主表中的起止位置。 由于主表分块有序，所以索引表一定是个递增的有序表。 分块查找的基本思想是： 首先在索引表中查找与给定值k对应的索引项，以确定下一步的查找在主表中的哪个分块中进行；然后在分块中继续查找与给定值k对应的记录。,设：记录的关键字序列为（14，31，8，22，18，43，62，49，35，52，88，78，71，83）实现分块查找 。,下标 0 1 2,关键字 起始下标 结束下标,索引表,数组R 下标,主表,1 2 3 4 5 6 7 8 9 10 11 12 13 14,索引表存储结构的C语言描述如下： # define MAXSIZE 10 typedef KeyType IndexType; typedef struct IndexType index; /*IndexType是索引关键字的类型*/ int start,end; /*子表在主表中的起始下标和结束下标*/ IndexTable; /*IndexTable是索引项的类型*/ IndexTable IndexMAXSIZE; /*MAXSIZE的值应该大于索引项数*/,实现分块查找算法的C函数： int blockSearch(RecType R, IndexTable Index, int m, KeyType k) /*在主表R和长度为m的索引表Index中查找关键字为k的记录，查找成功返回记录序号，否则返回0*/ int i,j; for(i=0;im;i+) /*在索引表中顺序查找与k对应的索引项*/ if (k=Indexi.index) break; if (im) /*在第i个子表中顺序查找关键字为k的记录*/ for (j= Indexi.start;j= Indexi.end;j+) if (k=Rj.key) return j; return 0; ,分块查找性能分析：,分块查找的平均查找长度 设n个记录的查找表分为m个子表，且每个子表均有t个元素，则t= n/m。 当m取 时，ASL= +1达到了最小值， 平均时间复杂度为O（ ） 分块查找的性能介于顺序查找和二分查找之间，分块查找可以方便地进行插入和删除记录的操作，不仅查找效率较高，还适合动态查找表使用。,84 树表查找,树表，是查找表的一种树形组织形式，并且使用链接方式进行存储。 树表查找既具有二分查找的效率，同时还能高效率地实现插删。 本节主要介绍二叉排序树和B-树。,841 二叉排序树,二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上 所有结点的值均小于根结点的值； （2）若右子树不空，则右子树上 所有结点的值均大于根结点的值； （3）左、右子树也都是二叉排序树。 对二叉排序树做中序遍历得到的 结点序列是一个有序序列。,图8.6 一棵二叉排序树,二叉排序树存储结构的C语言描述如下： typedef struct node KeyType key; /*关键字域*/ DataType other; /*其他数据项域*/ struct node *lchild,*rchild; /*左、右指针域*/ BstNode;,1二叉排序树的查找,二叉排序树的查找过程为： （1）若二叉排序树为空，查找失败。 （2）若二叉排序树非空，将给定值k与根结点的关键字比较，如果相等，查找成功；否则，当k小于根结点的关键字时，查找将在左子树上继续进行；当k大于根结点的关键字时，查找将在右子树上继续进行。 （3）在子树上的查找与前面的查找过程相同。,二叉排序树查找算法的C函数： BstNode * searchBst(BstNode *t, KeyType k) /*已知二叉排序树的根结点*t，在其中查找关键字为k的记录，若找到返回结点的地址，否则返回空地址*/ while (t!=NULL) if (t-key=k) return t; if (t-key k) t=t-lchild; else t=t-rchild; return NULL; ,2二叉排序树的插入及建立,二叉排序树中插入一个结点的过程如下：设待插入结点为*s，若二叉排序树为空，则将新结点*s作为根结点插入；若二叉排序树非空，比较结点*s与根结点的关键字，可分为三种情况： （1）若s-key与根结点的关键字相等，说明树中已经存在该结点，不用插入； （2）若s-key小于根结点的关键字，则将*s插入到根结点的左子树中； （3）若s-key大于根结点的关键字，则将*s插入到根结点的右子树中。 在左、右子树中的插入过程和二叉排序树的插入过程是相同的。如此进行下去，直到左子树或右子树为空时，新结点*s作为叶子结点插入到二叉排序树中。,一棵二叉排序树插入结点60,63,55,90,42,58,70,98,45,10,67,83,二叉排序树上插入运算的C函数： BstNode *insertNode (BstNode *t, BstNode *s) /*在根结点为*t的二叉排序树上插入新结点*s ，并返回根结点*t */ BstNode *p,*q; if (t=NULL) return s; /*二叉排序树为空，新结点为根结点*/ p=t; /*二叉排序树非空，开始查找插入位置*/ while(p) q=p; if(s-key= p-key) return t; /*二叉排序树中已经存在该结点*/ if(s-key key) p=p-lchild; /*在子树中寻找插入位置*/ else p=p-rchild; if (s-key key) q-lchild=s; /*插入新结点*/ else q-rchild=s; return t; ,建立一棵二叉排序树的过程就是逐个插入新结点的过程，反复调用插入运算即可。 例8.3设记录的关键字序列为（63，90，70，55，67，42，98，83，10，45，58），依次插入各个关键字，建立一棵二叉排序树。,建立二叉排序树的算法的C函数如下： BstNode *creatBst() /*建立一棵二叉排序树，返回这棵树的根结点*/ BstNode *root,*s; KeyType key; DataType data; root=NULL; scanf(“%d”, /*返回根结点*/ ,3二叉排序树的删除,设待删除结点为*p，其双亲结点为*f，以下分三种情况进行讨论。 （1）*p结点为叶子结点。 只需将被删结点的双亲结点相应指针域置为空即可，这种情况最简单。 （2）*p结点为单分支结点。 *p结点只有一棵子树。若只有左子树，根结点为*pl；或者只有右子树，根结点为*pr，此时，只需用*pl或*pr替换*p结点即可，这种情况也比较简单。 （3）*p结点为双分支结点。 *p结点既有左子树，又有右子树，其根结点分别为*pl和*pr。这种情况下删除*p结点比较复杂，可按中序遍历保持有序的原则进行调整，有两种调整方法：第一种方法，把*p的右子树链接到*p的中序遍历前趋结点的右指针域上，*p的中序前趋结点是它的左子树最右下结点，其右指针域一定为空，从而使得*p结点的右子树为空，变成单分支点，然后用*pl 替换*p结点；第二种方法，用*p结点的中序前趋结点（中序后继结点）的值替换*p结点的值，然后删除*p的中序前趋结点（中序后继结点）。*p的中序前趋（中序后继）不是叶子结点就是单分支结点，可以按照（1）或（2）的方法将它删除。,（a） 一棵二叉排序树 （b） 第一种方法删除结点20,（c） 第二种方法删除结点20 （d） 第二种方法删除结点36,4二叉排序树查找性能分析,二叉排序树的形态与结点的插入顺序有关 如结点的插入顺序为：63,90,70,55,67,42,98,10,45,58,构成的二叉排序树如图 (a) ASL=(1+22+34+43)/10=2.9 如果插入顺序为：10,42,45,55,58,63,67,70,90,98,构成的二叉排序树如图 (b) ASL=(1+2+3+4+5+6+7+8+9+10) /10=5.5,(a),(b),二叉排序树的查找效率与树的形态有关。 最好情况下，平均查找长度大约为log2n，时间复杂度为O(log2n)。 最坏的情况下，平均查找长度为(n+1) /2，时间复杂度为O(n)。 查找运算的平均时间复杂度仍为O(log2n)。 二叉排序树的平均查找性能与二分查找近似，查找效率较高，同时使用链式存储结构，它的插入和删除操作也较为方便，所以二叉排序树非常适合作动态查找表。,85 散列表查找,顺序表、索引表和树表中，记录的存储位置与记录的关键字之间不存在确定的关系，在表中查找记录需要进行一系列的比较，所以查找效率主要取决于查找过程中执行的比较次数。 如果记录的存储位置与关键字之间有某种确定的关系，在理想的情况下，记录的存储位置与关键字存在一一对应关系，则可以不通过比较就能找到对应的记录。本节探讨的散列表查找就是这样的查找方法。,851 散列表的概念,散列存储是专为查找而设计的存储结构，它的基本思想是：以表中每一个记录的关键字k为自变量，通过某个函数Hash(k)计算出函数值，把这个值解释为记录的存储位置，将记录存储在Hash(k)所指的位置上。散列存储实现了关键字到存储地址的转换，所以也称关键字地址转换法。 散列表：使用散列存储方式存储的线性表，也称作哈希表（Hash Table）。 散列存储中使用的函数Hash(k)，称为散列函数（哈希函数），Hash(k)的值称为散列地址（哈希地址）。,若有一个长度为9的线性表，其中记录的关键字序列为（23，15，36，99，6，14，65，93，75），使用散列存储方式存储该线性表 .,0 6 14 15 23 36 65 75 93 98 99,(1)直接定址法 设散列函数Hash1(key)=key,将线性表存储在长度为100的数组空间上，散列表的存储情况如图所示。 直接定址法一般形式为：Hash(key)=akey+b，其中，a、b为常数，这里a为1，b为0。 设线性表的长度为n，散列表（一维数组）的长度为m，则称=n/m为散列表的装填因子。 装填因子的取值区间为0.60.9比较合适。本例中n=9，m=100，则为0.09，显然这样的散列函数是不可取的，在实际应用中较少使用。,（2）除留余数法 散列函数为 Hash2（key）=key % 11，将线性表存储在长度为11的数组中，则每个记录的散列地址为： Hash2(23)=23%11=1 Hash2(15)=15%11=4 Hash2(36)=36%11=3 Hash2(99)=99%11=0 Hash2(6)=6%11=6 Hash2(14)=14%11=3 Hash2(65)=65%11=10 Hash2(93)=93%11=5 Hash2(75)=75%11=9 一般地，若某个散列函数Hash(k)对于不相等的关键字key1和key2，得到相同的散列地址，则称该现象为冲突。发生冲突的两个不同的关键字key1和key2被称为同义词，这里36和14就是同义词。,如何设计一个好的散列函数和确定一种解决冲突的办法，是散列存储方式中需要解决的两个最重要问题。,852 散列函数的设计,散列函数的设计原则是：计算简单，节省时间；函数值取值范围合理，避免空间的浪费，保证在合理的取值区间；散列地址尽可能均匀地分布在散列空间上，避免太多的冲突。,1数字分析法 例8.5有一组由7位数字组成的关键字，使用数字分析法设计散列函数。,2除留余数法 Hash(key)=key % p （p是一个整数） 若线性表的长度为n，散列表的长度为m，则一般选取p为质数，且 npm。根据装填因子的取值区间为0.60.9，p应为1.1n1.7n之间的一个质数。,3平方取中法 平方取中法是对关键字取平方后，按散列空间的大小，取中间的若干位作为散列地址。 例8.6 有一组关键字为0100，0111，0101，1001，0011，取平方的结果是：0010000，0012321，0010201，1002001，0000121，如果散列空间的长度为1000，则可取中间的三位作为散列地址100，123，102，020，001。,4折叠法 折叠法是将关键字自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并根据散列表的表长，选取后几位作为散列地址。 例8.7 已知关键字 key=5326248725，散列表长度为1000，使用折叠法计算散列地址。 按照每三位为一部分来分割关键字，关键字分割为如下四组： 532 624 872 5 532 624 872 + 5 2033 Hash(key)=033 折叠法适合于关键字的位数较多，而散列地址的位数较少，同时关键字中的每一位的取值又较集中的情况。,853 解决冲突的方法,1开放地址法 所谓开放地址法，就是散列地址单元一旦发生了冲突，就按照某种方法寻找下一个开放地址。开放地址是指该地址单元为空，可以存储记录。 寻找开放地址的方法有很多，它们的区别是形成的探测序列不同。,（1）线性探测法 线性探测法的基本思想是：将散列表看成一个首尾相接的环形表，设散列表的长度为m，当向散列表中插入关键字为key的记录时，若地址d=Hash (key)的单元为空，即将记录存入该地址单元。若发生冲突，则依次探测下列地址单元：d+1，d+2，m-1，0，1，d-1，直到找到一个空的地址单元，然后将记录存入其中。或者在探测过程中，遇到关键字为key的记录，说明表中已有该记录，无需插入。如果按照这种探测序列搜索整个散列表后又回到了地址空间d，则说明散列表已满。 线性探测法计算下一个开放地址的公式为： Hi=（Hash（key）+i）% m 其中：i取整数，取值范围 1im-1；m为散列表的长度。,例8.8 依次向长度为11的散列表（数组R）中插入关键字为 47，7，29，11，16，92，22，8，3的记录，散列函数为：Hash（key）=key % 11，用线性探测法处理冲突。散列表的存储结构如图所示。,8,29,7,3,16,92,47,22,11,下标 0 1 2 3 4 5 6 7 8 9 10,47，7，11，16，92没有发生冲突；29，22，8 发生冲突，由H1=(Hash(k)+1) % 存入其中；Hash(3)发生冲突，H1=(Hash(3)+1) % 11=