资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：,贺宁,分块,查找,常州信息职业技术学院,02,03,线性表查找,分块查找,1,、,分块查找表存储结构,：,分块查找表由“分块有序”的线性表和索引表组成。,（,1,）“分块有序”的线性表,将表,R1.n,均分为,b,块，前,b-1,块中结点个数为,s=n/b,，第,b,块结点个数小于等于,s,；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。,（,2,） 索引表,抽取各块中的最大关键字及该块起始位置构成一个索引表,ID1.b,，即：,IDi(1ib),中存放第,i,块的最大关键字及该块在表,R,中的起始位置。由于表,R,是“分块有序”的，所以索引表是一个递增有序表。,分块查找（,block search,）,又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。,04,3,、实例,分块查找,下图给出的就是满足上述要求的存储结构，其中,R,只有,15,个结点，被分成,3,块，每块中有,5,个结点，第一块中最大关键字,22,小于第二块中最小关键字,24,，第二块中最大关键字,44,小于第三块中最小关键字,47,。,分块查找,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,最大关键字值,块地址,ID,R,22,44,74,1,6,11,22,12,13,9,8,33,42,44,38,24,48,60,58,74,47,2,、基本思路,先在索引表中采用二分查找或顺序查找，以确定待查的结点在哪一块；,然后在已确定的块中进行顺序查找。,05,分块查找,4,、算法分析,优缺点,分块查找效率介于二分查找和顺序查找之间，对经常进行插入和删除操作的表，可采用此方法，因为在表中插入或删除记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算，因块内记录的存放是任意的，所以插入或删除无须移动大量记录；分块查找的主要代价是增加辅助存储空间和将初始表分块排序的运算。, 平均查找长度,将含有,n,个元素的线性表平均分成,b,块，每块有,s,个元素。整个查找过程的平均查找长度是两次查找的平均查找长度之和。,以二分查找来确定块，分块查找成功时的平均查找长度,ASL,blk,=AS,Lbn,+ASL,sq,以顺序查找来确定块，分块查找成功时的平均查找长度,ASL,blk,=AS,Lbn,+ASL,sq,THANKS,
展开阅读全文