数据结构课件第7章找查1

第8章查找Search

主讲：顾为兵(1)第8章查找/检索(Search)目录§8.0查找概述§8.1静态查找表§8.2动态查找表§8.3散列表（哈希表）查找查找概述查找表(SearchTable)：

同类型数据元素/记录的集合数据元素/记录：查找操作：

给定一个值K，在查找表中找出键值等于K的记录关键字其他项ElemType

keyother查找•

查找概述查找表的存储结构：

线性结构：顺序表，链表

树形结构：二叉排序树，B－树

散列结构：哈希表（散列表）查找•

查找概述查找性能的评价指标：平均查找长度ASL:

在查找过程中，给定值K与关键字比较次数的期望值

n---查找表中记录个数Ci----查找到第i条记录时，K与关键字的比较次数Pi----查找第i条记录的概率查找•

查找概述查找表的基本运算：

创建表： Create(&ST,n)

销毁表： Destroy(&ST)

查找： Search(ST,K)

读表元： Get(ST,pos)

插入： Insert(&ST,e)

删除：

Delete(&ST,K)静态查找表：查找表被创建后，一般不做修改和更新，即不具有插入和删除操作；动态查找表：既查找，又修改静态查找表动态查找表查找•

查找概述§8.1静态查找表

8.1.1顺序查找

8.1.2折半查找

8.1.3索引顺序查找查找8.1.1顺序查找

假定,查找表采用顺序存储结构：

typedefstruct{ ElemType*elem;//数组的基地址

intlength；//表中记录的个数

}SSTable；0123nSTR1R2R3......RnST.length静态查找表•

顺序查找

顺序查找思想：

从表的一端开始，逐个将给定值K与关键字进行比较，直到找到记录或查找失败；注意：这里“顺序”的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。静态查找表•

顺序查找intSearch(SSTableST,KeyTypeK){

//从表尾开始，顺序查找,查找成功返回元素的位置下标

//查找失败，返回0

inti=ST.length;while(i>0&&ST.elem[i].key!=K)i--;returni;}//search0123nSTR1R2R3......Rn检测下标i是否越界静态查找表•

顺序查找intSearch(SSTableST,KeyTypeK){

//带哨兵的检索，从表尾开始，顺序查找

//查找成功返回元素的位置下标；查找失败，返回0

inti=ST.length;ST.elem[0].key=K; while(ST.elem[i].key!=K)i--; returni;}0123nSTKR1R2R3......Rn监视哨静态查找表•

顺序查找查找效率：查找成功时的ASL：查找失败时的ASL：

ASL=n+1平均：ASL＝3(n+1)/4静态查找表•

顺序查找顺序查找小结：最朴素的查找方法对表的限制最少不仅适用于顺序存储结构，而且适用于链式存储结构时间性能最差，O(n)等概情况下查找成功时ASL＝(n+1)/2静态查找表•

顺序查找K

R1R2Rn-1Rn…head静态查找表•

顺序查找§8.1静态查找表

8.1.1顺序查找

8.1.2折半查找

8.1.3索引顺序查找查找8.1.2折半查找(二分查找)对表的限制：

1.

顺序存储；2.

按关键字值有序排列查找方法：设查找区间为R[low..high]

取mid＝(low+high)/2，则当K<R[mid].key：下一个查找区间为R[low..mid-1]

当K>R[mid].key：下一个查找区间为R[mid+1..High]

当K==R[mid].key：查找成功，结束当low>high：查找失败，结束静态查找表•

折半查找021611222527334256778179013245687910111312lowmidhigh举例：K＝39K>33low=mid+1midK<56high=mid-1mid39经过与关键字33,56,39的比较，查找成功K==39查找成功静态查找表•

折半查找K<16high=mid-102161122252739334256778179013245687910111312lowmidhigh举例，K＝13midmidmidK<33high=mid-1K>02low=mid+1K>11low=mid+1经过与关键字33,16,02,11的比较，查找失败静态查找表•

折半查找intSearch_Bin(SSTableST,KeyTypeK){ intlow=1,high=ST.length; intmid; while(low<=high){ mid=(low+high)/2; if(K<ST[mid].key) high=mid-1; //在左区间继续查找

elseif(K>ST[mid].key) low=mid+1; //在右区间继续查找

elsereturnmid; //查找成功的出口

}//whilereturn0;//查找失败的出口}//Search_Bin静态查找表•

折半查找折半查找判定树：mid左半区间右半区间Low..mid-1mid+1..high静态查找表•

折半查找n=13的折半查找判定树71..68..133101..24..68..911..131581224691113折半查找判定树是一棵理想平衡树树的高度为H=log2(n+1)或H=log2n+1树的形态取决于n值静态查找表•

折半查找

查找成功的过程是自树根沿树枝到达目标结点，K与关键字的最大比较次数不超过树高log2n+17310158122469111302161122252733425677817901324568791011131239查找K＝39：静态查找表•

折半查找

查找失败的过程是从树根开始，沿树枝到达一个外部结点，K与关键字的最大比较次数也不超过树高7310158122469111302161122252733425677817901324568791011131239查找K＝13：R2<K<R3静态查找表•

折半查找73101581224691113查找成功:

ASL=(1×1+2×2+3×4+4×6)/13=41/13查找失败:

ASL=(3×2+4×12)/14=54/14n=13静态查找表•

折半查找折半查找的ASL

设:n=2h-1----折半查找判定树是高为h的满二叉树

h=log2(n+1)静态查找表•

折半查找静态查找表•

折半查找折半查找小结一种效率很高的查找方法，时间复杂度O(log2n)；对表有严格的限制：有序的顺序表；折半查找判定树是分析查找性能的有效工具，查找每个结点所需的比较次数等于该结点在树上的层次数；折半查找判定树是一棵理想平衡二叉树，树的高度为log2n+1；无论查找成功或失败，与关键字的最大比较次数都不会超过树的高度。§8.1静态查找表

8.1.1顺序查找

8.1.2折半查找

8.1.3索引顺序查找查找9.1.4索引顺序查找（分块查找）查找性能介于顺序查找和折半查找之间；对表的限制也是介于顺序查找和折半查找之间；查找表的特点：分块有序，块内无序，块间有序。第i块的最大关键字小于第i＋1块的最小关键字；除了查找表外，还需要建一个索引表，查找分两级进行。静态查找表•

索引顺序查找67147015941608864515945372948351508122313121110987654321151013

stadr块起始地址23486494

key块内最大键值01234查找表：索引表：

索引表是有序表在索引表中查块号，采用顺序查找或折半查找均可在查找表中找目标记录，只能采用顺序查找

ASL＝索引表的ASL＋查找表的ASL静态查找表•

索引顺序查找索引表的类型定义：typedefstruct{ KeyType key; //块内最大键值

int stadr;//块起始地址}IndexItem;typedefstruct{ IndexItem *elem; //索引表基地址

int length; //索引表长度}IndexTable;静态查找表•

索引顺序查找intsearch_Idx(SSTableST,IndexTableID,KeyTypeK){ low=0;high=ID.length-1;found=FALSE; if(K>ID.elem[high].key)return0; while(low<=high&&!found){//折半查找索引表

mid=(low+high)/2; if(K<ID.elem[mid].key)high=mid-1; elseif(K>ID.elem[mid].key)low=mid+1; else{found=TRUE;low=mid;} }//while***下一步顺序查找ST表的第low块***

s=ID.elem[low].stadr;//确定ST表的查找区间s..t if(low<ID.length-1)t=ID.elem[low+1].stadr-1;elset=ST.length; for(i=s;i<=t&&ST.elem[i].key!=K;i++);//查找ST表

if(k<=t)returni;//查找成功,返回目标在ST表的下标i elsereturn0;//查找失败，返回0}//search_Idx

设：将n个元素均匀地分为b块，前b-1块每块有s个元素，s=n/b

第b块有n-s×(b-1)个元素对索引表采用用顺序查找：对索引表采用用折半查找查找：

静态查找表•

索引顺序查找第8章查找/检索(Search)目录§8.0查找概述§8.1静态查找表§8.2动态查找表§8.3散列表（哈希表）查找§8.2动态查找表----二叉排序树8.2.1二叉排序树的定义8.2.2二叉排序树的查找8.2.3二叉排序树的插入与生成8.2.4二叉排序树的删除动态查找表9.2.1二叉排序树的定义BinerySortTree定义二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的键值均小于根结点的键值；(2)若它的右子树不空，则右子树上所有结点的键值均大于根结点的键值；(3)它的左、右子树也分别是二叉排序树。动态查找表•

二叉排序树•

定义3248263929563412441946中序序列：12，19，26，29，32，34，39，44，46,48，56二叉排序树的一个重要性质：中序序列是一个有序序列动态查找表•

二叉排序树•

定义§8.2动态查找表----二叉排序树8.2.1二叉排序树的定义8.2.2二叉排序树的查找8.2.3二叉排序树的插入与生成8.2.4二叉排序树的删除动态查找表8.2.2二叉排序树的查找给定值K，当K<bt->key:在bt的左子树上继续查找当K>bt->key:在bt的右子树上继续查找当K==bt->key:查找成功3248263929563412441946bt动态查找表•

二叉排序树•

查找3248263929563412441946举例:K＝34K＝18查找成功：自树根沿树枝到达目标结点查找失败：自树根沿树枝到达一个外部结点成功或失败的最大比较次数都不超过树高动态查找表•

二叉排序树•

查找查找的非递归算法StatusBSTSearch(BiTreebt,KeyTypeK, BiTree&p,BiTree&f){

//在根为bt的二叉排序树上查找键值等于K的记录

//查找成功,用指针p指向目标;f指向目标的双亲,f初值为NULL p=bt; while(p){ if(K<p->key){f=p;p=p->lchild;}//左子树上继续找

elseif(K>p->key) {f=p;p=p->rchild;}//右子树上继续找

elsereturnTRUE;//查找成功

}//endwhile

returnFALSE;//查找失败}动态查找表•

二叉排序树•

查找动态查找表•

二叉排序树•

查找查找分析：查找成功时：

ASL＝(1×1＋2×2＋3×4＋4×3＋5×1)/11=34/11查找失败时：

ASL＝(3×5＋4×5＋5×2)/12=45/12

ASL值与树的形态有关3248263929563412441946§8.2动态查找表----二叉排序树9.2.1二叉排序树的定义9.2.2二叉排序树的查找9.2.3二叉排序树的插入与生成9.2.4二叉排序树的删除动态查找表8.2.3二叉排序树的插入与生成新结点作为一个叶子插到二叉排序树上53248527关键字序列：

53，24，45，85，27，121245ASL=(1×1＋2×2＋3×2＋4×1)/6=15/6动态查找表•

二叉排序树•

插入关键字序列

45，24，27，53，12，85452453122785ASL=(1×1＋2×2＋3×3)/6=14/6关键字序列

12，24，27，45,53，85124585272453ASL=(1＋2＋3＋4＋5＋6)/6=21/6动态查找表•

二叉排序树•

插入操作关键字序列

85，12，53，45,24，27854527531224ASL=(1＋2＋3＋4＋5＋6)/6=21/6动态查找表•

二叉排序树•

插入操作从键盘输入记录序列,生成二叉排序树voidCreateBST(BiTree&bt){ bt=NULL; for(scanf(R);R.key!=endmark;scnaf(R)){f=NULL; if(!BSTSearch(bt,R.key,p,f)){//未找到R.key S=newBiNode; S->key=R.key;S->other=R.other; S->lchild=S->rchild=NULL; if(!f)bt=S;//二叉排序树中的第一个结点

elseif(S->key<f->key)f->lchild=S; elsef->rchild=S; }//endif elseprintf("该结点已经存在!\n"); }//for}//endCreateBST§8.2动态查找表----二叉排序树8.2.1二叉排序树的定义8.2.2二叉排序树的查找8.2.3二叉排序树的插入与生成8.2.4二叉排序树的删除操作动态查找表8.2.4二叉排序树的删除操作在下面的讨论中，设：

P是待删结点

F是P的双亲

S是P的中序前驱

Q是S的双亲动态查找表•

二叉排序树•

删除操作P的度＝0：直接删FPFRFPFLFFRFFLF->lchild=NULLF->rchild=NULL

动态查找表•

二叉排序树•

删除操作2.P的度＝1：将P的唯一的孩子交给双亲FPFRPLFPFRPR...PL,P,F,FR......P,PR,F,FR...FFRPLFFRPR...PL,F,FR......PR,F,FR...F－>lchild=P->lchildF->lchild=P->rchild动态查找表•

二叉排序树•

删除操作3.P的度＝2：两种删除方法...CL,C,...,SL,S,P,PR,F,FR...FPFRPRCCL...SSLPFFRPRCCL...SSL...CL,C,...,SL,S,PR,F,FR...方法一：s=p->lchild;while(s->rchild)s=s->rchild;//找P的中序前驱Ss->rchild=p->rchild;//P的右孩子交给SF->lchild=p->lchild;//P的左孩子交给Ffree(p);动态查找表•

二叉排序树•

删除操作...CL,C,...,QL,Q,SL,S,P,PR,F,FR...方法二：FPFRPRCCL...QQLSSLPSSLFFRPRCCL...QQLS...CL,C,...,QL,Q,SL,S,PR,F,FR...q=p;s=p->lchild;whild(s->rchild){q=s;s=s->rchild;}

//找P的中序前驱Sp->key=s->key;p->other=s->other;