查找-数据结构课件-6

1第9章查找Search主讲：顾为兵第9章查找/检索(Search)目录§9.0查找概述查找§9.1静态查找表§9.2动态查找表§9.3散列表（哈希表）查找概述查找表(SearchTable)：同类型数据元素(又称记录）的集合关键字其他项查找•查找概述数据元素/记录：查找操作：给定一个值K，在查找表中找出键值等于K的记录关键字其他项ElemTypekeyother教材中几个带参宏定义作为比较函数：对数值型关键字：#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))查找•查找概述对字符串型关键字：#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))0)#defineLQ(a,b)(strcmp((a),(b))=0)查找表的存储结构：线性结构：顺序表，链表树形结构：二叉排序树，B－树等散列结构哈希表（散列表）查找•查找概述散列结构：哈希表（散列表）查找性能的评价指标：平均查找长度ASL:在查找过程中，给定值K与关键字比较次数的期望值∑nPiCiASL查找•查找概述∑=×=iPiCiASL1n---查找表中记录个数Ci----查找到第i条记录时，K与关键字的比较次数Pi----查找第i条记录的概率2F查找表的基本运算：创建表：Create(&ST,n)销毁表：Destroy(&ST)查找：Search(ST,K)读表元：Get(ST,pos)静态查找表态查找表查找•查找概述插入：Insert(&ST,e)删除：Delete(&ST,K)F静态查找表：查找表被创建后，一般不做插入和删除的修改，即没有为其定义插入和删除操作；F动态查找表：既查找，又修改动态查找表§9.1静态查找表9.1.1顺序查找9.1.2折半查找查找9.1.2折半查找9.1.3索引顺序查找9.1.1顺序查找假定,查找表采用顺序存储结构：typedefstruct{ElemType*elem;//数组的基地址itlth//表中记录的个数静态查找表•顺序查找intlength；//表中记录的个数}SSTable；0123nSTR1R2R3......RnST.lengthreturn顺序查找思想：从表的一端开始，逐个将给定值K与关键字进行比较，直到找到记录或查找失败；静态查找表•顺序查找注意：这里“顺序”的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。intSearch(SSTableST,KeyTypeK){//从表尾开始，顺序查找,查找成功返回元素的位置下标//查找失败返回0123nSTR1R2R3......Rn静态查找表•顺序查找//查找失败，返回0inti=ST.length;while(i0&&ST.elem[i].key!=K)i--;returni;}//search检测下标i是否越界intSearch(SSTableST,KeyTypeK){//带哨兵的检索从表尾开始顺序查找0123nSTKR1R2R3......Rn监视哨静态查找表•顺序查找//带哨兵的检索，从表尾开始，顺序查找//查找成功返回元素的位置下标；查找失败，返回0inti=ST.length;ST.elem[0].key=K;while(ST.elem[i].key!=K)i--;returni;}3查找效率：F查找成功时的ASL：∑∑+=×+−=×=nnninPiCiASL211)1(静态查找表•顺序查找∑∑==iin112)(F查找失败时的ASL：ASL=n+1F平均：ASL＝3(n+1)/4顺序查找小结：F最朴素的查找方法F对表的限制最少F不仅适用于顺序存储结构，而且适用于链式存储静态查找表•顺序查找F不仅适用于顺序存储结构，而且适用于链式存储结构F时间性能最差，O(n)F等概情况下查找成功时ASL＝(n+1)/2§9.1静态查找表9.1.1顺序查找912折半查找查找9.1.2折半查找9.1.3静态树表查找9.1.4索引顺序查找9.1.2折半查找(二分查找)这种查找方法对表有严格的限制：1.顺序存储；静态查找表•折半查找2.按关键字值有序排列折半查找方法：设查找区间为R[low..high],取mid=⎣(low+high)/2⎦，则F当KR[mid].key，下一个查找区间为R[low..mid-1](左半区间）静态查找表•折半查找F当KR[mid].key，下一个查找区间为R[mid+1..high](左半区间）F当K==R[mid].key，查找成功，结束F当lowhigh，查找失败，结束intSearch_Bin(SSTableST,KeyTypeK){intlow=1,high=ST.length;intmid;while(low=high){mid=(low+high)/2;if(KST[mid].key)静态查找表•折半查找high=mid-1;//在左区间继续查找elseif(KST[mid].key)low=mid+1;//在右区间继续查找elsereturnmid;//查找成功的出口}//whilereturn0;//查找失败的出口}//Search_Bin4折半查找判定树：mid静态查找表•折半查找左半区间右半区间Low..mid-1mid+1..high731002161122252733425677817901324568791011131239查找K＝39：静态查找表•折半查找查找成功的过程是自树根沿树枝到达目标结点，K与关键字的最大比较次数不超过树高⎣log2n⎦+1158122469111373101581202161122252733425677817901324568791011131239查找K＝13：静态查找表•折半查找查找失败的过程是从树根开始，沿树枝到达一个外部结点，K与关键字的最大比较次数也不超过树高1581224691113R2KR373101581224691113n=13静态查找表•折半查找24691113查找成功:ASL=(1×1+2×2+3×4+4×6)/13=41/13查找失败:ASL=(3×2+4×12)/14=54/14折半查找的ASL设:n=2h-1----折半查找判定树是高为h的满二叉树h=log2(n+1)静态查找表•折半查找∑∑=−=×=×=hjjnijnPiCiASL1112111011222212−=−×++×+×=×=∑hhjjhjS:设hhhhSSShhhhhh+×=++++×=×++×+××++×+×==)12(2)222(2)22221(-)22221(211011021－－－－静态查找表•折半查找nnn+++=)1(log)1()(21)1(log1)1(log1122−+≈−++==nnnnSnASL5折半查找小结一种效率很高的查找方法，时间复杂度O(log2n)；对表有严格的限制：有序的顺序表；折半查找判定树是分析查找性能的有效工具，查找每个结点所需的比较次数等于该结点在树上的层次数；折半查找判定树是一棵理想平衡二叉树，树的高度为⎣log2n⎦+1；无论查找成功或失败，与关键字的最大比较次数都不会超过树的高度。§9.1静态查找表9.1.1顺序查找9.1.2折半查找查找9.1.2折半查找9.1.3静态树表查找**9.1.4索引顺序查找9.1.4索引顺序查找（分块查找）查找性能介于顺序查找和折半查找之间；对表的限制也是介于顺序查找和折半查找之间；静态查找表•索引顺序查找查找表的特点：分块有序，块内无序，块间有序。第i块的最大关键字小于第i＋1块的最小关键字；除了查找表外，还需要建一个索引表，查找分两级进行。67147015941608864515945372948351508122313121110987654321151013stadr块起始地址查找表：索引表：静态查找表•索引顺序查找23486494key块内最大键值01234F索引表是有序表F在索引表中查块号，采用顺序查找或折半查找均可F在查找表中找目标记录，只能采用顺序查找FASL＝索引表的ASL＋查找表的ASL索引表的类型定义：typedefstruct{KeyTypekey;//块内最大键值intstadr;//块起始地址}IndexItem;静态查找表•索引顺序查找}IndexItem;typedefstruct{IndexItem*elem;//索引表基地址intlength;//索引表长度}IndexTable;设：将n个元素均匀地分为b块，前b-1块每块有s个元素，s=⎡n/b⎤第b块有n-s×(b-1)个元素对索引表采用用顺序查找：nsssbASL2112++=+++=静态查找表•索引顺序查找sASL222=+=1+=nns取得极小值时，当ASL对索引表采用用折半查找查找：2)1(log21]1)1(log1[22ssnsbbbASL++≈++−++=6第九章查找/检索(Search)目录§9.0查找概述查找§9.1静态查找表§9.2动态查找表§9.3散列表（哈希表）§9.2动态查找表----二叉排序树9.2.1二叉排序树的定义9.2.2二叉排序树的查找动态查找表9.2.3二叉排序树的插入与生成9.2.4二叉排序树的删除9.2.1二叉排序树的定义BinerySortTree定义(P141)二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：动态查找表•二叉排序树•定义(1)若它的左子树不空，则左子树上所有结点的键值均小于根结点的键值；(2)若它的右子树不空，则右子树上所有结点的键值均大于根结点的键值；(3)它的左、右子树也分别是二叉排序树。32482639295634124419动态查找表•二叉排序树•定义34441946中序序列：12，19，26，29，32，34，39，44，46,48，56二叉排序树的一个重要性质：中序序列是一个有序序列§9.2动态查找表----二叉排序树9.2.1二叉排序树的定义9.2.2二叉排序树的查找动态查找表9.2.3二叉排序树的插入与生成9.2.4二叉排序树的删除9.2.2二叉排序树的查找32482639295634124419bt动态查找表•二叉排序树•查找给定值K，当Kbt-key:在bt的左子树上继续查找当Kbt-key:在bt的右子树上继续查找当K==bt-key:查找成功46732482639295634124419举例:K＝34K＝18动态查找表•二叉排序树•查找46查找成功：自树根沿树枝到达目标结点查找失败：自树根沿树枝到达一个外部结点成功或失败的最大比较次数都不超过树高查找的递归算法:查找成功，返回目标记录的指针；查找失败，返回空指针BiTreeBSTSearch(BiTreebt,KeyTypeK){//在根为bt的二叉排序树上查找键值等于K的记录if(!bt||K==bt-key)returnbt;//查找成功或失败而结束动态查找表•二叉排序树•查找elseif(Kbt-key)returnBSTSearch(bt-lchild,K);//在左子树上继续找elsereturnBSTSearch(bt-rchild,K)//在右子树上继续找}查找的非递归算法StatusBSTSearch(BiTreebt,KeyTypeK,BiTree&p,BiTree&f){//在根为bt的二叉排序树上查找键值等于K的记录//查找成功,用指针p指向目标;f指向目标的双亲,f初值为NULLp=bt;hil(){动态查找表•二叉排序树•查找while(p){if(Kp-key){f=p;p=p-lchild;}//左子树上继续找elseif(Kp-key){f=p;p=p-rchild;}//右子树上继续找elsereturnTRUE;//查找成功}//endwhilereturnFALSE;//查找失败}动态查找表•二叉排序树•