分块查找实现.pptVIP

3． 索引顺序表的设计与实现 根据教材介绍的索引顺序表， 定义块的大小 k，输入适当数据构造索引顺序表， 实现分块查找算法， 并进行测试验证。 简介：索引顺序表包括存储数据的顺序表（称为主表）和索引表两部分。顺序表被分为若干子表（又称块），整个顺序表有序或分块有序。将每个子表中的最大关键字取出，再加上指向该关键字记录所在子表第一个元素的指针，就构成一个索引项，将这些索引项按关键字增序排列，就构成了索引表。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 索引顺序表的设计与实现 过程分为两个阶段： 确定待查记录所在的子表（块），由于索引表是按关键字有序排列的，对于索引表可按折半查找，若待查记录关键字的key值，=第i个子表最大关键字，且大于第i-1个子表的最大关键字，即K(i-1) key K(i)，则待查关键字位于第i个子表中。 (2) 在已确定的子表中确定待查记录的位置，由于子表中的记录不一定按关键字有序排列，只能按顺序查找法查找。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 折半查找法： ?int BinSearch(T A[],int low,int high,T key)//递归实现折半查找 { int mid; // 初始化中间值的位置 T midvalue; // 初始化中间值 if (lowhigh) { s=A[high]; d=A[low]; ss=high; dd=low; return -1;} // 如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。 索引顺序表的设计与实现 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ?? else { mid=(low+high)/2; // 中间位置为低位与高位和的一半取整。 midvalue=A[mid]; if (keyA[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); // 否则递归调用哦个函数，有哪些信誉好的足球投注网站上半部分 } } ?????? 索引顺序表的设计与实现 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 顺序查找函数： 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值，说明有哪些信誉好的足球投注网站失败。 } 索引顺序表的设计与实现 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 主函数中，首先对所需要的参数变量进行初始化，由键盘输入关键字，分块的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组： 索引顺序表的设计与实现 int **p2 ; p2 = new int*[row] ; //声明一个