第九章 查找

9.1基本概念9.2静态查找表(StaticSearchTable)顺序表的查找有序表的查找静态树表的查找索引顺序表的查找9.3动态查找表(DynamicSearchTable)二叉排序树和平衡二叉树B-树和B＋树键树9.4哈希表(HashTable)哈希表的构造处理冲突的方法本章主要内容知识点1．集合数据结构，元素间不存在任何逻辑关系。2.三种方法（静态查找表，动态查找表，哈希表）实现集合的运算。3．静态查找表：顺序表，有序表，静态树表，索引顺序表。4．动态查找表：二叉排序树，平衡二叉树，B-树，B+树，键树。5．哈希表。重点难点1．静态查找表中各种方法及其运算。2．二叉排序树的建立、查找，插入和删除算法。3．最佳二叉排序树，平衡二叉树的性质和手工绘制。4．B-树是多路平衡外查找树，手工模拟B-树插入和删除。5．键树中每个结点是关键字的一个字符，键树的插入和删除。6．哈希表的建立、查找。7.平均查找长度（ASL)的计算9.1基本概念四大类数据结构：线性结构；树结构；图结构；集合结构9.1基本概念集合：是一种逻辑结构，其特点是元素之间没有逻辑关系（即逻辑关系集合为空集），元素只是共处于一个集合当中。9.1基本概念查找表(SearchTable)是由同一类型的数据元素（或记录）构成的集合9.1基本概念书号书名作者出版社定价015010C程序设计谭浩强清华大学出版社26.00015024数据结构严蔚敏清华大学出版社22.00015025离散数学左孝凌上海科学技术文献出版社14.00015080计算机操作系统汤子瀛西安电子科技大学出版社24.00以图书查找表为例，来讨论计算机中表的概念。对查找表进行的操作1.查询某个“特定的”数据元素是否在查找表中；2.检索某个“特定的”数据元素的各种属性；3.在查找表中插入一个数据元素；4.在查找表中删除一个数据元素；查找表分类根据操作类型的不同把查找表分为：静态查找表（操作后查找表结构不变化）：仅作查询和检索操作的查找表；动态查找表（操作后查找表结构发生变化）：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入查找表；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。什么叫查找？查找(Searching)：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。或者说是在数据元素集合中查找满足某种条件的数据元素。关键字？关键字(Key)：是数据元素（或记录）中某个数据项的值，用以识别（标识）一个数据元素（或记录）。主关键字(PrimaryKey)：如果此关键字可以识别唯一的一个记录。如学生号码，工作证号码次关键字(SecondaryKey)：如果此关键字可以识别若干个记录。查找成功或者不成功查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。查找成功：若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；查找不成功：否则称“查找不成功”，查找结果：给出“空记录”或者“空指针”。查找不成功时静态查找表和动态查找表的处理不一样如何进行查找？取决于查找表的结构。如电话号码表、查字典…….如何进行查找？取决于查找表的结构。但是：查找表本身是一种非常松散的结构，所以，为了提高查找的效率，需要在查找表的元素之间人为地附加某种确定的关系，换言之：用另外一种结构表示查找表。如把书架上的书分门别类存放9.2静态查找表ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素；数据关系R：数据元素同属一个集合。基本操作P：Creat(ST,n)；//生成一个静态查找表STDestroy(ST)；//销毁静态查找表STSearch(ST,key)；//查找静态查找表STTraverse(ST,visit())；//遍历静态查找表ST}ADTStaticSearchTable静态查找表的运算Search(ST,key)；初始条件：静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值；操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。静态查找表的运算Traverse(ST,visit())；初始条件：静态查找表ST存在，visit是对元素操作的应用函数；操作结果：按某种次序对ST的每个元素调用函数visit一次且仅一次，一旦visit失败，则操作失败。静态查找表分类1.顺序查找表；2.有序查找表；折半查找（BinarySearch）菲波那契查找（FibonacciSearch）插值查找（InterpolationSearch）3.静态查找树表；4.索引顺序表；静态查找表的顺序存储结构设静态查找表主要以顺序表作为存储结构，有关的类型说明如下：typedefstruct{ElemTypekey;∥关键字域intlength；//表的长度…∥其它域}rectype;1.顺序查找表以顺序表或线性链表表示静态查找表也称为线性表上的查找回顾顺序表的查找算法：顺序查找（SequentialSearch）的方法：对于给定的关键字k，从线性表的第一个元素开始，依次向后与记录的关键字域相比较，如果某个记录的关键字等于k，则查找成功，否则查找失败。3022564836910688397618….0123456789101112r.lengthr.key从前往后找，查找指针初值i＝1回顾顺序表的查找算法按值查找:intSeqListLocate(SeqListL,ElemTypex){//在顺序表L中查找第一个与x值相等的元素。若查找成功，则返回它在顺序表中的位置；否则，返回0。i=1;while(i=L.length&&L.data[i]!=x)//第i个元素的下标为ii++;if(i=L.length)returni;//返回数据元素的位置elsereturn0;//查找失败}对查找算法加以改进3022564836910688397618….0123456789101112r.lengthr.key883022564836910688397618….0123456789101112r.lengthr.key从后往前找，查找指针初值i＝n待查找元素放在0号单元顺序表的查找顺序查找的方法：对于给定的关键字k，从线性表的第n个元素开始，依次往前与记录的关键字域相比较，如果某个记录的关键字等于k，则查找成功，否则查找失败。顺序查找算法typedefrectypeSeqList[n+1];∥0号单元用作哨兵intSearchSeq(SeqListr,intk){∥在顺序表r[1..n]中顺序查找关键字为k的结点，成//功返回结点位置，失败返回0r[0].key=k;∥设置哨兵for(i=r.length;r[i].key!=k;i--)；∥从表尾向前查找returni;∥找不到为0，找到为在顺序表中的位置}∥SearchSeq教材P.174.算法9.1定义：查找算法的平均查找长度ASL（AverageSearchLength）:和给定值进行比较的关键字个数的“期望值”，称为查找算法的平均查找长度。查找成功时的平均查找长度为：分析顺序查找的时间性能niiicpASL1ASL是衡量查找算法性能的主要依据。顺序表的查找分析其中n为表长，pi为查找表中第i个记录的概率，且有ci为找到该记录时，曾和给定值比较过的关键字的个数。niiicpASL111niip顺序表的查找分析niiisscpASL1nnpppnnp1212)1(=设查找为等概率查找npi1niiisscpASL1nininn121)1(1=对顺序表而言：1inCi顺序表的查找分析在查找概率已知但不等的情况下，ASLss在时取极小值如汉字库中的汉字的查找概率不同。英文字母的查找概率也不同121......PPPPnn顺序表的查找分析若查找概率事先无法测定，则可以采用下列改进的查找算法：在每次查找之后，就将刚刚查找到的记录直接移至表尾的位置上。如医院病历档案的处理等。顺序表的查找分析优点：算法简单且适用面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。缺点:平均查找长度较大，特别是当表长n很大时，查找效率低。2.有序查找表031015192528405583….….….0123456789highr.keylowmid有序表之折半查找思想：首先，将给定的查找关键字k与线性表的中间位置上的元素进行比较，若相等，则查找成功。否则，中间元素将线性表分成两个部分，前一部分中的元素均小于中间元素，而后一部分中的元素则均大于中间元素。因此，k与中间元素比较后，若k小于中间元素，则应在前一部分中查找，否则在后一部分中查找。重复上述过程，直至查找成功或失败。缩小区间的方法折半查找示例（03，10，15，19，25，28，40，55，83）查找关键字为55的数据元素031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh示例031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh查找关键字为18的数据元素highlow折半查找非递归算法intSearchBin1(SeqListr,intk){∥在有序表r中折半查找关键字为k的元素，成功返//回结点位置，失败返回0low=1;high=r.length;//设置区间初值while(low=high){mid=(low+high)/2;if(k==r[mid].key)returnmid;∥找到待查元素elseif(kr[mid].key)low=mid+1;∥继续在后半区间查找elsehigh=mid-1;∥继续在前半区间查找}return0;}∥SearchBin1教材P.176.算法9.12a折半查找递归算法intSearchBin2(SeqListr,intk,intlow,inthigh){∥在有序表r中递归折半查找关键字为k的结点，成功返回结//点位置，失败返回0if(lowhigh)return0;mid=(low+high)/2;if(k==r[mid].key)returnmid;∥找到待查元素elseif(kr[mid].key)returnSearchBin2(r,k,mid+1,high);∥继续在后半区间查找elsereturnSearchBin2(r,k,low,mid-1);∥继续在前半区间查找}∥SearchBin2教材P.177.算法9.2b折半查找的性能先看一个具体情况，假设表长n＝9i123456789Ci122333344判定树527136849折半查找的性能折半查找过程可用一个称为判定树的二叉树描述判定树中每一结点对应表中一个元素，但结点的值不是关键字的值，而是元素在表中的位置。根结点对应当前区间的中间记录，左子树对应前半子表，右子树对应后半子表。9个结点的判定树527136849带外部结点的判定树527136849-11-22-35-66-77-83-44-58-99-内部结点外部结点折半查找的性能一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同，均为log2n+1。因此，折半查找成功时，与关键字的比较