第9章-查找电子课件.pptx

江西省高等学校精品课程

计算机科学与技术专业核心课程;揭安全;主要内容;揭安全;计算机是如何帮用户

查找数据的？;查找是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。;静态查找表：查找的前后不会改变查找表的内容。;对于具有n个数据元素的集合，查找某元素成功的平均查找长度为：;查找分类;线性表查找;树型查找;散列查找;;;;揭安全;顺序表;链表;#includeseqlist.h

/*顺序查找的非递归实现*/

intseqsearch(seqlistl,datatypekey)

{intk=l.len-1;

while(k=0l.data[k]!=key)

k--;

return(k);

};线性表查找;linklistlinkSearch(linklisthead,datatypekey)

{

linklistp=head-next;

while(pp-data!=key)

p=p-next;

returnp;

};对于具有n个元素的顺序表

查找成功情况下：

最好情况1次；最坏情况n次。

等概率情况的平均查找次数：;揭安全;10;10;intbinsearch1(seqlistl,datatypekey)

{intlow=0,high=l.len-1,mid;//初始化有哪些信誉好的足球投注网站区间

while(low=high)

{mid=(low+high)/2;//二分

if(l.data[mid]==key)returnmid;//查找成功

if(l.data[mid]key)

high=mid-1;//继续在左半部分进行查找; elselow=mid+1;

//继续在右半部分进行二分查找

}

return-1; //查找失败

};intbinsearch2(seqlistl,datatypekey,intlow,inthigh)

{intmid,k;

if(lowhigh)return-1; //查找失败

else

{mid=(low+high)/2;//二分

if(l.data[mid]==key)returnmid;//查找成功 if(l.data[mid]key)

return

else

return

}

};10;;; 第1层节点有1个，有哪些信誉好的足球投注网站第1层节点要比较1次；第2层节点有2个，有哪些信誉好的足球投注网站第2层节点要比较2次；…，因此：;ASLbins=;顺序查找VS二分查找; 1、时间复杂度为O（log2n）;揭安全;揭安全;9.2.3分块查找;分块查找(BlockingSearch)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。;（1）“分块有序”的线性表

线性表R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关??字必须小于后一块中的最小关键字，即表是分块有序的。;（2）索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。

由于表R是分块有序的，所以索引表是一个递增有序表。;图9.2分块有序表的索引存储表示;2、分块查找的过程;分块查找方法通过将查找缩小在某个块中从而提高了查找的效率，其查找的效率由两部分组成：

一是为确定某一块对索引表的平均查找长度El

二是块内查找所需的平均查找长度Eb。;若以顺序查找来确定块，则分块查找成功时的平均查找长度为：;若以二分查找来确定块，则分块查找查找成功时的平均查找长度为：

ASL=El+Eb

?log2（b+1）-1+（s+1）/2

?log2（n/s+1）+s/2;揭安全;;;;二叉排序树(BinarySortTree)又称二叉查找(有哪些信誉好的足球投注网站)树(BinarySearchTree)。

其定义为：二叉排序树或者是空树，或是满足：

①若它的左子树非空，则左子树上所有节点的值均小于根节点的值