《分块查找实现》PPT课件.ppt

《《分块查找实现》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3．索引顺序表的设计与实现根据教材介绍的索引顺序表，定义块的大小k，输入适当数据构造索引顺序表，实现分块查找算法，并进行测试验证。简介：索引顺序表包括存储数据的顺序表（称为主表）和索引表两部分。顺序表被分为若干子表（又称块），整个顺序表有序或分块有序。将每个子表中的最大关键字取出，再加上指向该关键字记录所在子表第一个元素的指针，就构成一个索引项，将这些索引项按关键字增序排列，就构成了索引表。索引顺序表的设计与实现过程分为两个阶段：确定待查记录所在的子表（块），由于索引表是按关键字有序排列的，对于索引表

2、可按折半查找，若待查记录关键字的key值，<=第i个子表最大关键字，且大于第i-1个子表的最大关键字，即K(i-1)high){s=A[high];d=A[

3、low];ss=high;dd=low;return-1;}//如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。索引顺序表的设计与实现else{mid=(low+high)/2;//中间位置为低位与高位和的一半取整。midvalue=A[mid];if(key>A[mid-1]&&key<=A[mid])returnmid;elseif(midvalue

4、函数，搜索下半部分elsereturnBinSearch(A,low,mid-1,key);//否则递归调用哦个函数，搜索上半部分}}索引顺序表的设计与实现顺序查找函数：templateintshuxuSearch(TA[],inthigh,Tkey)//顺序查找{inti=0;A[high]=key;//初始化i，使A的最高位为key值while(A[i]!=key)i++;returni;//如果A中有key值，则在i不到n+1时就会输出，否则，返回high值，说明搜索失败。}索引

5、顺序表的设计与实现主函数中，首先对所需要的参数变量进行初始化，由键盘输入关键字，分块的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组：索引顺序表的设计与实现int**p2;p2=newint*[row];//声明一个二维数组for(i=0;i

6、/将所有关键字，按块的不同存入二维数组中cout<<"分块情况为"<=M[i])M[i]=p2[i][j];//找到块的最大关键字存储在M[]}cout<

7、初始化一个一维数组，将关键字所在快的元素重新定义为一个数组Spos=shuxuSearch(S,B[kuai],key);//在S中顺序查找关键字intq=0;for(i=0;i

8、，K=97索引表关键码字段指针字段133887990346132833388776999601234567谢谢！