数据结构-查找教材课件

数据结构8.1查找的基本概念第8章查找8.2基于线性表的查找法8.3基于树的查找法8.4计算式查找法—哈希表1数据结构8.1查找的基本概念第8章查找查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。2数据结构8.1查找的基本概念第8章查找对查找表常进行的操作:1）查询某个“特定的”数据元素是否在查找表中静态查找动态查找3）在查找表中插入一个数据元素2）检索某个“特定的”数据元素的各种属性4）从查找表中删去某个数据元素3数据结构8.1查找的基本概念第8章查找查找表的分类仅作查询和检索操作静态查找表“不在查找表中”的数据元素插入到查找表中；删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找还可分为：内查找和外查找。4数据结构8.1查找的基本概念第8章查找关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。主关键字：可以识别唯一的一个记录的关键字。次关键字：可以识别若干记录的关键字。5根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（记录）。查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。数据结构8.1查找的基本概念第8章查找6由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说,用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的结构。数据结构8.1查找的基本概念第8章查找7数据结构8.2基于线性表的查找第8章查找①顺序查找②折半查找③分块查找8数据结构8.2基于线性表的查找第8章查找①顺序查找key=64key=6021378819920564568072130123456789101112iiiiiiiiiii结果：查找成功，返回位置7结果：查找不成功int

SeqSearch(RecordListl,KeyTypek){

inti;i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return(i);elsereturn(0);}9数据结构8.2基于线性表的查找第8章查找①顺序查找key=64key=60结果：查找成功，返回位置7结果：查找不成功6460int

SeqSearch(RecordListl,KeyTypek){inti;

l.r[0].key=k;/*标识边界*/i=l.length;while(l.r[i].key!=k)i--;

return(i);}技巧：

r[0]起到监视哨兵的作用,可免去检查表是否查完,且提高算法的执行效率,但并不是真正的待查找记录。21378819920564568072130123456789101112iiiiiiiiiiii10数据结构8.2基于线性表的查找第8章查找①顺序查找分析查找的时间性能:查找算法的平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值(查找成功时）ASL=∑PiCii=1n其中:n为表长；Pi为查找表中第i个记录的概率，且;Ci为找到该记录时，曾和给定值比较过的关键字的次数。∑Pi=1i=1n11在等概率查找的情况下，顺序表查找成功的平均查找长度为：Pi=1/n对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn8.2基于线性表的查找第8章查找数据结构21111+=+-=å=n)i(nnASLniSUCC若查找概率无法事先测定，则查找过程采取的改进办法是，附设一个访问频度域或者在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。①顺序查找128.2基于线性表的查找第8章查找数据结构②折半查找顺序查找的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。若以有序表表示查找表，则查找过程可以基于“折半”进行。138.2基于线性表的查找第8章查找数据结构②折半查找1.首先确定查找表的中间位置；2.然后将待查的值与中间位置的值进行比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。基本思想:148.2基于线性表的查找第8章查找数据结构②折半查找例1:key=64

的查找过程如下：lowmidhighlowmidmidhigh①low=11211109876543219288807564563721191305low指示查找区间的下界high=11mid=(1+11)/2=6②key>mid指向的记录值low=mid+1=7mid=(7+11)/2=9③key<mid指向的记录值high=mid-1=8mid=(8+7)/2=7key=mid所指向的记录值查找成功举例:high

指示查找区间的上界mid=(low+high)/270lowmidhighhigh<low查找不成功158.2基于线性表的查找第8章查找数据结构②折半查找算法int

BinSrch(RecordListl,KeyTypek){

intlow=1,high=l.length,mid;while(low<=high){mid=(low+high)/2;if(k==l.r[mid].key)returnmid;elseif(k<l.r[mid].key)high=mid-1;elselow=mid+1;}return0;}168.2基于线性表的查找第8章查找数据结构②折半查找先看一个具体的情况，假设：n=11判定树i1234567891011Ci342341342343149671028115找到有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，给定值进行比较的关键字个数恰是该结点在判定树上的层次数。ASLsuccss=(1

1+2

2+4

3+4

4)/11=33/11ASLunsucc=(4

4+8

5)/12=56/12折半查找的判定树是唯一的。平均查找长度178.2基于线性表的查找第8章查找数据结构②折半查找平均查找长度一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。假设n=2h-1并且查找概率相等，则ASL=∑PiCii=1n=1/n∑Cini=1=1/n∑j*2j-1hj=1=(n+1)/n*log2(n+1)-1在n>50时，可得近似结果

≈log2(n+1)-1折半查找只适用于有序表，且限于顺序存储结构188.2基于线性表的查找第8章查找数据结构③分块查找（索引顺序查找）基本思想：1、把线性表分成若干块，每块包含若干个记录，在每一块中记录的存放是任意的，但块与块之间必须有序。（分块有序）2、建立一个索引表，把每块中的最大关键字值及每块的第一个记录在表中的位置和最后一个记录在表中的位置存放在索引项中。19索引表141186106485122keystartfinish0123221213

8

9

33423824485874498614131211109876543218.2基于线性表的查找第8章查找数据结构③分块查找（索引顺序查找）208.2基于线性表的查找第8章查找数据结构③分块查找（索引顺序查找）索引顺序表的查找过程：1）由索引确定记录所在区间（块）；2）在某个区间（块）内进行顺序查找。注意：索引可以根据查找表的特点来构造。可见，分块查找的过程也是一个“缩小区间”的查找过程。分块查找的平均比较次数

=

查找“索引”的平均比较次数

+查找“块内”的平均比较次数21第8章查找数据结构8.2基于线性表的查找线性表的三种查找方法比较因此，对于不同的表长n、不同的表结构和表存储结构，应采用不同的查找方法。顺序查找折半查找分块查找表的结构有序、无序有序表间有序表的存储顺序、链式顺序顺序、链式ASL最大最小次之22第8章查找数据结构8.3基于树的查找①二叉排序树②二叉平衡树③B-树④B+树⑤键树23第8章查找数据结构8.3基于树的查找①二叉排序树定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：1.若它的左子树不空，则左子树上所有结点的值均小于根结点的值；3.它的左、右子树也都分别是二叉排序树。2.若它的右子树不空，则右子树上所有结点的值均大于根结点的值；24第8章查找数据结构8.3基于树的查找503080209010854035252388例如:是二叉排序树。66不①二叉排序树25第8章查找数据结构8.3基于树的查找①二叉排序树查找算法若给定值等于根结点的关键字，则查找成功；若给定值小于根结点的关键字，则继续在左子树上进行查找；若给定值大于根结点的关键字，则继续在右子树上进行查找。否则，若二叉排序树为空，则查找不成功；在二叉排序树上进行查找，类似折半查找2650308020908540358832第8章查找数据结构8.3基于树的查找例如:二叉排序树查找关键字==50,35,90,953080209085403588325050304035508090①二叉排序树查找算法失败27第8章查找数据结构8.3基于树的查找从上述查找过程可见，在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功①二叉排序树查找算法28BSTree

SearchBST(BSTree

bst,KeyTypekey){if(!bst)returnNULL;elseif(bst->key==key)returnbst；

elseif(key<bst->key)returnSearchBST(bst->lchild,key);elsereturnSearchBST(bst->rchild,key);}第8章查找数据结构8.3基于树的查找①二叉排序树查找算法--递归29①二叉排序树查找算法--非递归第8章查找数据结构8.3基于树的查找BSTree

SearchBST(BSTree

bst,KeyTypekey){

BSTreeq;q=bst;

while(q){if(q->key==k)returnq;if(key<q->data.key)q=q->lchild;elseq=q->rchild;}returnNULL;}30①二叉排序树插入算法第8章查找数据结构8.3基于树的查找根据动态查找表的定义，“插入”操作在查找不成功时才进行；若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。314830103523402025①二叉排序树插入算法第8章查找数据结构8.3基于树的查找设key=30304832①二叉排序树插入算法第8章查找数据结构8.3基于树的查找voidInsertBST(BSTree*bst,KeyTypekey){

BiTrees;if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)

InsertBST(&((*bst)->lchild),key);elseif(key>(*bst)->key)

InsertBST(&((*bst)->rchild),key);

}33①二叉排序树生成算法第8章查找数据结构8.3基于树的查找例如：设关键字输入顺序为：

45，24，53，12，28，9028125324459024，45，53，90，12，28289045122453所以，二叉排序树的形态完全由一个输入序列决定，一个无序序列可以通过构造一棵二叉排序树而得到一个有序序列。34voidCreateBST(BSTree*bst){

KeyTypekey;*bst=NULL;

scanf("%d",&key);while(key!=ENDKEY){

InsertBST(bst,key);

scanf("%d",&key);}}①二叉排序树生成算法第8章查找数据结构8.3基于树的查找354830103523402025二叉排序树特点:1.中序遍历二叉排序树可得到关键字有序序列。2.在构造二叉排序树时，每次插入的新结点都是新的叶子结点，则进行插入时，不必移动其它结点。3.二叉排序树不但拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。中序遍历：10，20，23，25，30，35，40，48第8章查找数据结构8.3基于树的查找36①二叉排序树删除算法第8章查找数据结构8.3基于树的查找和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。37①二叉排序树删除算法第8章查找数据结构8.3基于树的查找50802090403588328530（1）被删除的结点是叶子结点例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”38①二叉排序树删除算法第8章查找数据结构8.3基于树的查找50802090403588328530（2）被删除的结点只有左子树或只有右子树例如:被删关键字=4080其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。39①二叉排序树删除算法第8章查找数据结构8.3基于树的查找50802090403588328530（3）被删除的结点既有左子树也有右子树例如:被删关键字=50以其前驱或后继替代之，然后再删除该前驱或后继结点4040①二叉排序树删除算法第8章查找数据结构8.3基于树的查找BSTNode*DelBST(BSTreet,KeyTypek){

BSTNode*p,*f,*s,*q;p=t;f=NULL;

while(p){

if(p->key==k)break;f=p;if（p->key>k）p=p->lchild;elsep=p->rchild;}41if(p==NULL)returnt；if(p->lchild==NULL){

if(f==NULL)t=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild

；

elsef->rchild=p->rchild;

free(p);}数据结构①二叉排序树删除算法第8章查找8.3基于树的查找42

else{q=p;s=p->lchild;

while(s->rchild){q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;elseq->rchild=s->lchild;p->key=s->key;

free(s);}returnt;}数据结构①二叉排序树删除算法第8章查找8.3基于树的查找43数据结构①二叉排序树性能分析第8章查找8.3基于树的查找由关键字序列1，2，3，4，5构造而得的二叉排序树例如：ASLsucc=（1+2+3+4+5）/5=3ASLsucc=（1+22+2

3）/5=2.24321514352最好情况是与折半查找判定树相同最差情况蜕化为单支树与顺序查找相同3，1，4，2，544含有值相同的n个关键字，构造的二叉排序树中，ASL和树的形态有关；2.最差的情况：当关键字有序时,树的深度为n，其平均查找次数为（n+1）/2。3.最好的情况：二叉排序树的形态和折半查找的判定树相同，平均查找次数和log2n成正比。数据结构①二叉排序树性能分析第8章查找8.3基于树的查找45数据结构第8章查找8.4计算式查找法—哈希表以上两节讨论的表示查找表的各种结构的共同特点：

哈希表是什么？2.查找的过程为给定值依次和关键字集合中各个关键字进行比较;3.查找的效率取决于和给定值进行比较的关键字个数。1.记录在表中的位置和它的关键字之间不存在一个确定的关系；46用这类方法表示的查找表，其

平均查找长度都不为零。不同的表示方法，其差别仅在于：

关键字和给定值进行比较的顺序不同。数据结构第8章查找8.4计算式查找法—哈希表只有一个办法：

预先知道所查关键字在表中的位置。对于频繁使用的查找表，希望ASL=0。

即要求：记录在表中位置和其关键字之间存在一种确定的关系。47数据结构第8章查找8.4计算式查找法—哈希表若以下标为000~999的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。48数据结构第8章查找8.4计算式查找法—哈希表但是，对于动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。1）表长不确定；2）在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。49数据结构第8章查找8.4计算式查找法—哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例如：对于如下9个关键字设哈希函数f(key)=

(Ord(第一个字母)-Ord('A')+1)/2

问题:若添加关键字Zhou,怎么办？能否找到另一个哈希函数？012345678910111213ChenZhaoQianSunLiWuHanYeDei50数据结构第8章查找8.4计算式查找法—哈希表1）哈希函数是一个映象，即将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；从这个例子可见：2）由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1

key2，而f(key1)=(key2)。51数据结构第8章查找8.4计算式查找法—哈希表3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，

使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。52数据结构第8章查找8.4计算式查找法—哈希表哈希表的定义：根据设定的哈希函数H(key)

和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。53数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法54数据结构第8章查找8.4计算式查找法—哈希表哈希函数为关键字的线性函数

H(key)=key或者

H(key)=a

key+bⅠ.直接定址法此法仅适合于：地址集合的大小==关键字集合的大小①构造哈希函数的方法55数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。Ⅱ.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。8134653281372242813874228130136781322817813389671234567856数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。Ⅲ.平方取中法

此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。57数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。Ⅳ.折叠法此方法适合于:关键字的数字位数特别多。有两种叠加处理的方法：移位叠加和间界叠加。58Ⅴ.除留余数法设定哈希函数为:

H(key)=keyMODp

其中，

p≤m(表长)并且

p应为不大于m的素数或是不含20以下的质因子数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法59

给定一组关键字为：12,39,18,24,33,21，

若取p=9,

则他们对应的哈希函数值将为：

3,3,0,6,6,3例如：为什么要对p加限制？可见，若p中含质因子3，则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。数据结构第8章查找①构造哈希函数的方法8.4计算式查找法—哈希表60数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法Ⅵ.随机数法设定哈希函数为:

H(key)=Random(key)其中，Random为伪随机函数此方法适合于：关键字的长度不等61数据结构第8章查找8.4计算式查找法—哈希表①构造哈希函数的方法实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。62数据结构第8章查找8.4计算式查找法—哈希表②处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链地址法3.再哈希法63数据结构第8章查找8.4计算式查找法—哈希表②处理冲突的方法Ⅰ.开放定址法为产生冲突的地址H(key)求得一个地址序列：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODm

i=1,2,…,s64数据结构第8章查找8.4