《典型查找算法》PPT课件

1,第9章典型查找算法,顺序查找、折半查找和分块查找的方法和算法，相应的平均查找长度二叉排序树查找方法和算法，二叉平衡树概念散列表的概念，散列函数的构造方法，处理冲突的方法及散列表各种运算的实现算法,2,第9章典型查找算法,9.1实例：学生分配座位9.2静态查找9.3动态查找9.4散列查找本章总结,3,9.1实例：学生分配座位,9.1.1问题描述9.1.2问题的分析9.1.3实现算法9.1.4基本概念,4,9.1.1问题描述,教室中的学生座位分配是一个最简单的例子。假定某教室有35个座位，如果不加限定任意就坐或按某种规律就座，则要查找某学生时就要将待查找的学生与当前座位上的学生进行比较。,5,9.1.2问题的分析,用计算机来解决查找学生问题，通常需要做以下工作：第一，学生信息以什么形式表示和存储；第二，查找的具体实现方法(算法)。,6,structstudentintnum1;/表示座号intnum2;/表示学号charname12;/表示姓名；structlistStudentstusize;/保存学生记录Intlen;/学生人数;,学生信息的存储方式：,7,从第一个学生开始，依次与查找的学生进行比较。在查找过程中，若某个学生的记录与所查找学生记录相等，则查找成功，返回该学生在表中位置；若全部比较完毕，没有符合条件的学生记录，则查找不成功，返回-1。,查找学生的方法：,8,9.1.3实现算法,intsearch(List,9,9.1.4基本概念,查找表：由同一类型的数据元素构成的集合。静态查找表：只做查找操作的查找表。动态查找表：在查找过程中做插入和删除操作的查找表。关键字、主关键字、次关键字查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。,10,查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。,平均查找长度定义为：,其中，n是结点的个数；pi是查找第i个结点的概率，ci是找到第i个结点所需要的比较次数,11,9.2静态查找,9.2.1顺序查找9.2.2折半查找9.2.3分块查找,12,9.2静态查找,查找过程中，进行如下操作：查询某个特定的数据元素是否在查找表中或检索某个数据元素的各种属性。此查找表称为静态查找表(StaticSearchTable)。查找表定义为顺序存储的线性表，数据类型定义如下：structElemtype/数据元素类型定义keytypekey;/关键字项；#definemaxlenmaxsize/分配的存储单元个数structListSqElemtypeemaxsize;intlen;,13,9.2.1顺序查找,顺序查找（线性查找）基本思想：从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。,14,9.2.1顺序查找,typedefstructkeytypekey;datatypeother;DataNode;TypedefstructDataNodeRmaxsize;intlength;SSTable;,typedefstructintnumber;charname10;floatscore;DataNode;TypedefstructDataNodeRmaxsize;intlength;SSTable;,15,intSEQSEARCH(SSTableST,keytypeK)inti;ST.R0.keyK;/设置监视哨for(i=ST.length;ST.Ri.key!=K;i);/从表尾开始向后扫描returni;/返回下标,顺序查找算法：,16,算法中监视哨R0的作用是为了在for循环中省去判定防止下标越界的条件i0，从而节省比较的时间。顺序查找的平均查找长度为：,有时，表中各结点的查找概率并不相等。因此若事先知道表中各结点查找概率的分布情况，则可将表中结点按查找概率从大到小排列，以便提高顺序查找的效率。顺序查找的特点：算法简单，但查找效率低。,17,折半查找又称为二分查找。折半要求查找表是有序的。折半查找的基本思想是：首先将待查的K值与有序表R0到Rn-1的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若Rmid.keyK，则说明待查找的结点只可能在左表R0到Rmid-1中，只需在左子表中继续查找；否则在右子表中继续查找。这样，经过一次键字的比较就缩小了一半的查找区间。重复执行，直到找到关键字为K的元素或当前查找区间为空(即表明查找失败)为止。,9.2.2折半查找,18,0513192137566475808892,0513192137566475808892,0513192137566475808892,查找K=21的过程（查找成功）,19,0513192137566475808892,0513192137566475808892,0513192137566475808892,查找K=85的过程（查找失败）,0513192137566475808892,20,折半查找算法（low和high分别表示当前查找区间的下界和上界）intBINSEARCH(SSTableST,keytypeK)intlow,mid,high;low0;highn-1;while(low=high)mid(low+high)/2;/整除if(K=ST.Rmid.key)returnmid;if(KST.Rmid.key)highmid-1;elselowmid+1;return-1;/查找失败,21,算法分析,虽然折半查找的效率较高，但它要求被查找序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，折半查找只适用于顺序存储结构，因此，折半查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。,22,二叉判定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找区间的中间点元素，它的左子树和右子树分别对应该区间的左子表和右子表。二叉判定树是一棵二叉排序树。二分查找的平均查找长度为：,23,9.2.3分块查找,分块查找(索引顺序查找)基本思想：首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表，为每个子表分别建立一个索引项，由所有子表的索引项构成一个索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定值K刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录。实现算法：（略）索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。,24,平均查找长度为：设将长度为n的表均匀分成b块，每块有s个记录，则b=n/s，查找表中每条记录的概率相等，则每块查找的概率为1/b，块中每条记录的查找概率为1/s。则顺序查找索引表时：,25,分块有序表的索引存储表示,26,索引表结点的数据类型定义如下：,#defineMaxIndextypedefstructKeyTypekey;intaddr(link);IdxType;在这种结构下，查找过程要分为两步：首先查找索引表。因为索引表是有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的块中进行顺序查找。,27,分块查找算法如下：,intIdxSerch(SeqListA,IdxTypeindex,intb,KeyTypek,intn)/分块查找关键字为k的记录，索引表为index0.b-1intlow=0,high=b-1,mid,i;ints=n/b;/每块记录个数while(low=high)/在索引表中进行二分查找，找到的位置放在low中mid=(low+high)/2;if(indexmid.keyk)low=mid+1elsehigh=mid-1;if(lowelem.key)/*kx大于当前结点*q的元素关键码*/*p=*q;*q=(*q)-rc;/*将当前结点*q的右子女置为新根*/elseif(kxelem.key)/*kx小于当前结点*q的元素关键码*/*p=*q;*q=(*q)-lc;/*将当前结点*q的左子女置为新根*/elseflag=1;break;/*查找成功，返回*/*while*/returnflag;,36,时间复杂度：分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。普通情况下，对二叉排序树进行查找的时间复杂度为O()；最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。,为使得由任何初始序列构成的二叉排序树的平均查找长度是对数级的，所以我们可使得构造的二叉排序树是一个平衡二叉树。,37,三.二叉排序树插入操作和构造一棵二叉排序树,向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。,38,图9.5从空树开始建立二叉排序树的过程,39,【算法9.5】intInsertNode(NodeType*t,KeyTypekx)/*在二叉排序树*t上插入关键码为kx的结点*/NodeType*q,*s,*p=*t;intflag=0;if(!SearchElem(*t,40,9.3.2二叉平衡树,二叉平衡树(AVL树)：或者是一棵空树，或者是一棵具有如下性质的非空二叉树：它的左子树和右子树都是二叉平衡树，且左子树和右子树的深度之差的绝对值不大于1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子BF，则BF的值只可能为1、0和1。,41,对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：LL型：单向右旋平衡处理RR型：单向左旋平衡处理LR型：双向旋转(先左后右)平衡处理RL型：双向旋转(先右后左)平衡处理时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时间复杂度为O(log2n)。,42,平衡二叉树和非平衡二叉树,图9.9,43,图9.9给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平衡因子只能取-1，0，1三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树。如图9.9（a）所示的二叉排序树。在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：,44,对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：LL型：单向右旋平衡处理RR型：单向左旋平衡处理LR型：双向旋转(先左后右)平衡处理RL型：双向旋转(先右后左)平衡处理时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时间复杂度为O(log2n)。,45,左单旋转（RR型）,在图(a)所示的树上插入结点x，如图(b)所示。结点x插入在结点c的右子树E上，导致结点a的平衡因子绝对值大于1，以结点a为根的子树失去平衡。,46,【调整策略】调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点c的左子树，结点c为新的根结点，如图(c)。【平衡化调整操作判定】沿插入路径检查三个点a、c、E，若它们处于“”直线上的同一个方向，则要作左单旋转，即以结点c为轴逆时针旋转。,47,说明：1.旋转操作的正确性可以由二叉排序树的特性：中序遍历所得关键字序列自小至大有序证明之。2.当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所由祖先结点的平衡度。,48,二.右单旋转（LL型）,右单旋转与左单旋转类似，沿插入路径检查三个点a、c、E，若它们处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图9.11所示。,49,如图9.12为插入前的子树，根结点a的左子树比右子树高度高1，待插入结点x将插入到结点b的右子树上，并使结点b的右子树高度增1，从而使结点a的平衡因子的绝对值大于1，导致结点a为根的子树平衡被破坏，如图9.12插入前图9.13(a)、9.14(d)所示。,图9.12插入前,50,三.先左后右双向旋转（LR型）,图9.13,51,52,沿插入路径检查三个点a、b、c，若它们呈“”字形，需要进行先左后右双向旋转：1.首先，对结点b为根的子树，以结点c为轴，向左逆时针旋转，结点c成为该子树的新根，如图(b、e)；2.由于旋转后，待插入结点x相当于插入到结点b为根的子树上，这样a、c、b三点处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图(c、f)。,53,四.先右后左双向旋转（RL型）先右后左双向旋转和先左后右双向旋转对称，自行补充整理。,54,9.4散列查找,9.4.1散列存储和散列函数的构造方法9.4.2解决冲突的方法9.4.3散列查找实现算法和性能分析,55,9.4.1散列存储和散列函数构造,基本术语：散列存储：以数据中每个元素的关键字K为自变量，通过一个函数f(k)计算出函数值，把这个值同存储空间中一个唯一的存储位置相对应，将该元素存储到这个存储位置中。函数f(k)称为散列函数或哈希函数。f(k)的值称为散列地址或哈希地址；进行散列存储的地址空间称为散列表或哈希表。冲突：实际应用中，由于散列函数的构造方法不同，常会出现多个元素同时占用一个存储单元的情况，即散列地址相同，这种现象叫冲突。具有相同函数值的不同关键字的元素，称为同义词。,56,常用的构造散列函数的方法：,直接定址法:取关键字或关键字的某个现行函数值为哈希地址。即：H(key)=key或H(key)=akey+b。数字分析法假设关键字是以r为基的数(如：以10为基的十进制数)，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。平方取中法：取关键字平方后的中间几位为哈希地址。折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=keyMODp,p=m该方法是一种最简单，也最常用的构造哈希函数的方法。随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址。即:H(key)=random(key),57,9.4.2解决冲突的方法,常用的解决冲突的方法有以下几种：,开放定地址链地址法再哈希法建立一个公共溢出区,58,从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲存储单元，把发生冲突的待插入元素存入到该单元中的一类解决冲突的方法。设H(key)为散列函数，m为散列表长度。则开放定址法中找下一个空闲空间的散列函数为：Hi=(H(key)+di)%m其中，i=1,2k；di称为增量，以di的取值分为以下三种：(1)di=1,2,3m-1,称线性探测再散列。(2)di=12,-12，22，-22，k2,(km/2)称二次探测再散列。(3)di=随机数序列，称为随机探测再散列。,开放定址法：,59,把具有相同散列地址的关键字放在同一链表中，称为同义词链表。通常把具有相同散列地址的关键字都存放在一个同义词链表中，有m个散列地址就有m个链表，同时用数组tm存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以ti为头指针的单链表中。,链地址法：,60,9.4.3散列查找实现算法和性能分析,算法思想：在哈希表上进行查找的过程和哈希造表的过程一致。给定K值，根据造表时设定的哈西函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若何给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值时为止。结论：l由于产生“冲突”，查找过程仍是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表的查找效率的量度。l查找过程中比较个数取决于因素：散列函数、解决冲突的方法和散列表的装填因子。装填因子定义：=越小，发生冲突的可能性就越小；越大，发生冲突的可能性就越大。,61,本章总结,本章主要介绍了数据处理中的几种典型的查找方法、及实现算法和各种查找方法的性能分析。查找：指在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。查找过程：是数据处理的一个环节，它的下一环节是对查找到的结果进行处理，根据所做的操作的不同，将查找方法分为静态查找和动态查找。静态查找方法介绍了顺序查找、二分查找和分块查找三种方法。动态查找方法介绍了二叉排序树查找和二叉平衡树查找。,62,顺序查找既适用于顺序表，也适用与单链表，时间复杂度是O（n），平均查找长度为（n+1）/2。折半查找只适用于顺序存储的有序表。折半查找的时间复杂度为O（log2n）。折半查找的查找过程可以画成一棵二叉判定树，它是一棵二叉排序树。分块查找过程分为两部分：先在索引表中查找；然后在主表的对应块中顺序查找。二叉排序树查找：根据二叉排序树的定义，首先访问根结点，若其值等于给定值则查找成功；若给定值比根结点大，继续向右子树中查找；否则给定值比根结点小，继续在左子树中查找，直到找到该结点或找不到为止，此时查找失败。,63,二