索引顺序表的设计与实现
else { mid=(low+high)/2; // 中间位置为低位与高位和的一半取 整。 midvalue=A[mid]; if (key>A[mid-1]&&key<=A[mid]) return mid; else if (midvalue < key) //如果关键字的值大于中间 值 return BinSearch(A,mid+1,high,key); // 递归调用函 数，搜索下半部分 else return BinSearch(A,low,mid-1,key); // 否则递归调用 哦个函数，搜索上半部分 }
索引顺序表的设计与实现
cout<<"分块情况为"<<endl; for( i = 0 ; i < row ; i ++ ) { for( j = 0 ;j <B[i] ; j ++ ) { cout<<p2[i][j]<<' ' ; if(p2[i][j]>=M[i]) M[i]=p2[i][j]; //找到块的最大关键字存储在M[] } cout<<endl; } //输出二维数组，检验分块是否为预期
索引顺序表的设计与实现
int *S; S = new int[kuai] ; for(i=0;i<B[kuai];i++) {S[i]=p2[kuai][i]; } //初始化一个一维数组，将 关键字所在快的元素重 新定义为一个数组S pos=shuxuSearch(S,B[kuai],key);//在S中顺序查找关键字 int q=0; for(i=0;i<kuai;i++) {q=q+B[i];} if (pos!=B[kuai]) cout<<"该元素的位置为:"<<pos+q<<endl; //如果关键 字存在，输出其位置
声明折半查 找函数
声明顺序查 找函数
程序设计流程
主函数
声明各种变 量
输入关键字 的个数
输入分块个 数
输入每个分块 中的关键字的 个数
得到关键字所
声明一个二维数组 并将关键字按快存 储在二维数组中
输入关键字
调用顺序查找函 数，对关键字所 在快进行查找
指针字段
13 0
28 1
33 2
38 3
87 4
76 5
99 6
96 7
3． 索引顺序表的设计与实现
根据教材介绍的索引顺序表， 定义块的大小 k，输入适当数据构造索引顺 序表， 实现分块查找算法， 并进行测试验证。
简介：索引顺序表包括存储数据的顺序表（称为主表）和
索引表两部分。顺序表被分为若干子表（又称块），整个顺序
表有序或分块有序。将每个子表中的最大关键字取出，再加上 指向该关键字记录所在子表第一个元素的指针，就构成一个索 引项，将这些索引项按关键字增序排列，就构成了索引表。
(2) 在已确定的子表中确定待查记录的位置，由于子表中的记录不一定按
关键字有序排列，只能按顺序查找法查找。
索引顺序表的设计与实现
折半查找法： int BinSearch(T A[],int low,int high,T key)//递归实 现折半查找 { int mid; // 初始化中间值的位置 T midvalue; // 初始化中间值 if (low>high) { s=A[high]; d=A[low]; ss=high; dd=low; return -1;} // 如果low的值大于high的值，输出-1， 并且将此时的low与high的值存储。
索引顺序表的设计与实现
过程分为两个阶段： (1) 确定待查记录所在的子表（块），由于索引表是按关键字有序排列 的，对于索引表可按折半查找，若待查记录关键字的key值，<=第i个 子表最大关键字，且大于第i-1个子表的最大关键字，即K(i-1) < key < K(i)，则待查关键字位于第i个子表中。
索引顺序表的设计与实现
顺序查找函数：
template <class T> int shuxuSearch(T A[],int high,T key) // 顺序查找 { int i=0; A[high]=key; // 初始化i，使 A的最高位为 key值 while(A[i]!=key) i++; return i; // 如果A中有key值，则在i不到n+1时就会 输出，否则，返回high值，说明搜索失败。 }
索引顺序表的设计与实现
主函数中，首先对所需要的参数变量进行初始化，由键盘 输入关键字，分块的多少，每一块有多少个关键字。为了用户 的人性化考虑，这里由用户自己决定分块的多少和数目。为了 实现这一功能，引入了一个动态存储的二维数组： int **p2 ; p2 = new int*[row] ; //声明一个二维数组 for( i = 0 ; i < row ; i ++ ) p2[i] = new int[col] ; for( i = 0 ; i < row ; i ++ ) {for( j = 0 ; j < B[i] ; j ++ ) {p2[i][j]=A[k]; k=k+1;} } //将所有关键字，按块的不同存入二维数组中
判断函数返回至 是否等于输入数组长
No
YES
输出位置
YES
输出无该关 键字
询问用户是否再 次查找
NO
结束
测试实例：设主表关键字序列：{13 28 33 38 87 76 99 96}， L=4 ，依次查找K=13， K=33，K=99，K=11，K=30，K=97
关键码字段 索引表
13 0 38 3 87 4 99 6