搜索
第六章查找•6.1基本概念•6.2静态查找表•6.3二叉排序树•6.4散列表6.1基本概念▲查找表——由同一类型的数据元素（或记录）构成的集合。▲关键字（键）——用来标识数据元素的数据项称为关键字，简称键；其值称为键值。▲主关键字——可以惟一标识各个数据元素的关键字▲查找——根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。▲静态查找表—进行的是引用型运算▲动态查找表—进行的是加工型运算6.2静态查找表的实现查找表用顺序表表示：（见P163）#definemaxsize20//静态查找表的表长typedefstruct{TableElemetem[maxsize+1];/*一维数组，0号单元留空*/intn;/*最后一个元素的下标，也即表长*/}SqTable;typedefstruct{keytypekey;/*关键字域*/…/*其它域*/}TableElem;6.2.1顺序表上的查找——顺序查找一、过程从表中最后一个记录开始顺序进行查找，若当前记录的关键字=给定值，则查找成功；否则，继续查上一记录…；若直至第一个记录尚未找到需要的记录，则查找失败。二、算法方法一：使用一种设计技巧：设立岗哨intsearch_sqtable(sqtableT,keytypeK）{/*在顺序表R中顺序查找其关键字等于key的元素。若找到，则函数值为该元素在表中的位置，否则为0*/T.item[0].key=key;i=T.n;while(T.item[i].key!=key)i--;returni;}三、算法分析成功查找：ASL=∑ni=1CiPi（设每个记录的查找概率相等）=1/n∑ni=1（n-i+1）=（n+1)/2不成功查找：ASL=n+1▲顺序查找优点：简单，对表无要求；▲顺序查找缺点：比较次数多。6.2.2有序表上的查找——二分查找★1、二分查找思想：每次找中项.中项是，则找到；.否则，根据此中项的关键字与给定关键字的关系，决定在表的前或后半部继续找。关键点。可使下次查找范围缩小一半。二分查找基本思想：每次将处于查找区间中间位置上的数据元素与给定值K比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为0（查找不成功）为止。(2)给定关键字k与中项记录关键字比较①K＜item[mid].key，则所查记录落在表的前半部；继续在前半部找，此时low不变，high=mid-1②K＝item[mid].key，则查找成功，中项即是，结束；③K＞item[mid].key，则所查记录落在表的后半部；继续在后半部找，此时low=mid+1，high不变(3)若low≤high，则转(1)，否则查找不成功。(1)求中间点(low+high)/2mid={item[1],…,item[mid-1],item[mid],item[mid+1],…,item[n]}3、二分查找算法：2、二分查找过程：表头指针low=1表尾指针high=nintSearchBin(SqTableT,keytypekey){/*在有序表T中二分查找其关键字等于key的数据元素；若找到，则返回该元素在表中的位置，否则返回0*/low=1;high=T.n;while(low=high){mid=(low+high)/2;if(K==T.item[mid].key)returnmid;elseif(key＜R.item[mid].key)high=mid-1;elselow=mid+1;}return(0);}因为1835，所以：15，17，18，22，35，51，60，88，93lowmidhigh4、例：（在下列有序顺序表中查找K=18）123456789midhighlow因为1817，所以：highlowmid因为18=18，所以：查找成功，回送结果为mid=35、算法分析：log2n查找成功时：比较次数最多为+1查找不成功时：比较次数最多也为log2n+1成功查找时平均查找长度：ASL=∑ni=1CiPi（设每个记录的查找概率相等）=1/n∑hj=1（j*2j-1）=（n+1)/n*log2(n+1)-1≈log2(n+1)≈log2n＜(n+1)/2注意：对线性表进行二分查找时，要求线性表必：以顺序方式存储，且结点按关键字有序排序6.2.3索引顺序表的查找——分块查找一、查找过程：1.先建立最大（或小）关键字表——索引表（有序）即将每块中最大（或最小）关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表；2.查找索引表，以确定所查元素所在块号；将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号；3.在相应块中按顺序查找关键字为k的记录。二、例：记录表{22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}，查关键字38的元素表可分三块，块间有序，块中无序2212139833424438244860587447第一块第二块第三块2214467411最大关键字块起始地址1231、先在索引表中（按顺序或折半）查找：∵38＞22而38＜44∴38在第二块中2、在第2块中顺序查找得第9号元素其关键字为38。三、算法分析：分块查找的时间性能高于顺序查找而低于二分查找；分块查找不要求存储结构中数据元素按键值有序。6.3动态查找表——树表表结构是在查找过程中动态生成的；对于给定值k，若表中存在其关键字等于k的记录，则查找成功返回，否则在表中插入关键字等于k的记录。一、二叉排序树●什么是二叉排序树？二叉排序树是一种特殊的、增加了限制条件的二叉树，它的存储结构及其类型定义与二叉树相同，它的特殊性表现在结点键值之间的大小关系上，任一结点的键值大于其左孩子(及其子孙)的键值且小于其右孩子(及其子孙)的键值。●性质：中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。2、二叉排序树查找算法见P169二、二叉排序树上的查找：1、过程：当二叉排序树不空时，首先将给定值和根结点的关键字比较,若相等,则查找成功；否则根据给定值与根结点关键字间的大小关系，分别在左子树或右子树上继续进行查找。注：(1)二叉排序树，对每个结点，均有：左子树上的所有结点键值都比根的小；右子树上的所有结点键值都比根的大。(2)构造二叉排序树的同时也对序列排序了；三、二叉排序树的插入和生成★对序列R={k1，k2，…，kn}，k1～kn均为关键字值，则按下列原则可构造二叉排序树：(1)令k1为根；(2)若k1＜k2，则令k2为k1的右孩，否则为左孩；(3)k3，k4，…，kn递归重复(2)◆散列函数（哈希函数）——设记录表A，长为n，ai（1≤i≤n）为表中某一元素，ki为其关键字，则关键字ki和元素ai在表中的地址之间有一函数关系，即：Addr（ai）=H（ki）ai在表中地址散列函数：关键字与元素地址的函数6.4散列表（哈希表）◆散列地址——由散列函数决定数据元素的存储位置，该位置称为散列地址。◆散列查找：给定关键字在表中的地址散列函数转换查看此位置上有无欲查元素有无输出信息将它填到此位置上◆散列表——通过散列法建立的表称为散列表。散列法主要工作.选择一个好的散列函数.解决冲突.函数计算简便，运算速度快.随机性好，地址尽可能均匀分布.冲突小◆冲突：k1≠k2但H（k1）=H（k2）的现象称为冲突。即：不同的关键字映射到同一存储单元。并称k1和k2是同义词。2、除留余数法▲散列函数：取关键字被某个不大于散列表长n的数p除后所得余数作为散列地址。即：H(key)=keymodp，（p≤n）▲例：一组关键字从000,001～859,999散列地址为：0～5999即n=6000取p=5999——余数r在0～5999范围内H=kmod5999设：k=172,148则：H=kmodp=172148mod5999=41766.4.1散列函数的构造1、数字分析法（见P173）方法关键——如何取p？★结论：①p不取偶数②p不取关键字字符基的n倍③一般选p为质数且最接近表长m的质数3、平方取中法（见P174）4、基数转换法（见P174）——即用“链地址法”处理冲突●思想：将散列地址相同记录存储在同一单链表中（称同义词表），同时按散列地址设立一个表头指针向量。●例：已知一组关键字为（13，41，15，44，06，68，25，12，38，64，19，49），按散列函数H(key)=keymod13和链地址法处理冲突构造散列表。6.4.2散列表的实现Key:（13,41,15,44,06,68,25,12,38,64,19,49）0,2,2,5,6,3,12,12,12,12,6,10散列地址：●过程：设有散列表HT（向量），对给定记录R，其关键字k，对应哈希地址H(k)=jHT[j]空吗？HT[j].key=k?记录R存入其中j+1=j找到，输出j=m?0=jYN＝≠YNHT表01:j:m-1●思想：计算出的散列地址已被占用，则按顺序找“下一个”空位。——用“线性探测法”处理冲突构造散列表★要点：①HT[j]空，则R填入；②HT[j].key=k，则输出；③否则，按顺序一步步找“下一个”空位，将R填入。散列表：131241156844063864649250123456789101112●例：已知一组关键字为（13，41，15，44，06，68，25，12，38，64，19，49），按散列函数H(key)=keymod13和线性探测法处理冲突构造散列表。Key:（13,41,15,44,06,68,25,12,38,64,19,49）0,2,2,5,6,3,12,12,12,12,6,10散列地址：●散列法的优缺点：优点：直接由关键字通过哈希函数计算出哈希地址，查找效率高；缺点：常发生冲突，影响查找效率。第六章查找小结▲熟练掌握顺序表和有序表的查找方法和算法；▲掌握二叉排序树的定义、构建方法和查找方法；▲知道二叉排序树的定义及维护平衡四个旋转规则；▲掌握B_树的定义和建树过程，查找方法；▲什么是散列方法、什么是冲突？▲熟练掌握散列表的构造和查找及冲突的处理；▲按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。1．二分查找算法要求被查找的表是（）A.键值有序的链表B.键值不一定有序的链表C.键值有序的顺序表D.键值不一定有序的顺序表2．静态查找表与动态查找表的根本差别在于（）A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同3．在二叉排序树中，对于任意结点a，其左子树中所有结点的键值均（）A.小于结点a的键值B.小于等于结点a的键值C.大于结点a的键值D.大于等于结点a的键值4.在二叉排序树中，对于任意结点a，其右子树中所有结点的键值均（）A.小于结点a的键值B.小于等于结点a的键值C.大于结点a的键值D.大于等于结点a的键值练习5．二分查找法适用于这样的线性表，即按关键字排好序且存储结构为（）A.顺序存储B.链式存储C.散列存储D.顺序存储或链式存储6．在散列函数H(k)=kMODm中，一般来讲，m应取（）A．奇数B.偶数C.质数D.充分大的数7．二分查找法要求查找表中各元素的键值必须是（）A．递增排列B．递减排列C．无序排列D．递增或递减排列