做外贸比较好得网站,最近高清免费资源,网站建设情况简介,福州推广企业网站分块查找#xff0c;也叫索引顺序查找#xff0c;算法实现除了需要查找表本身之外#xff0c;还需要根据查找表建立一个索引表。例如图 1#xff0c;给定一个查找表#xff0c;其对应的索引表如图所示#xff1a; 图 1 查找表及其对应的索引表
图 1 中#xff0c;查找表…分块查找也叫索引顺序查找算法实现除了需要查找表本身之外还需要根据查找表建立一个索引表。例如图 1给定一个查找表其对应的索引表如图所示 图 1 查找表及其对应的索引表
图 1 中查找表中共 18 个查找关键字将其平均分为 3 个子表对每个子表建立一个索引索引中包含中两部分内容该子表部分中最大的关键字以及第一个关键字在总表中的位置即该子表的起始位置。 建立的索引表要求按照关键字进行升序排序查找表要么整体有序要么分块有序。 分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字第三个子表的所有关键字都要大于第二个子表中的最大关键字依次类推。
块子表中各关键字的具体顺序根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的那么可以随机存放否则可按照被查找概率进行降序排序以提高算法运行效率。
分块查找的具体实现
所有前期准备工作完成后开始在此基础上进行分块查找。分块查找的过程分为两步进行
确定要查找的关键字可能存在的具体块子表在具体的块中进行顺序查找。
以图 1 中的查找表为例假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较因为 22 38 48所以可以确定 38 如果存在肯定在第二个子表中。
由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上所以从该位置开始进行顺序查找一直查找到该子表最后一个关键字一般将查找表进行等分具体子表个数根据实际情况而定。结果在第 10 的位置上确定该关键字即为所找。 提示在第一步确定块子表时由于索引表中按照关键字有序所有可以采用折半查找算法。而在第二步中由于各子表中关键字没有严格要求有序所以只能采用顺序查找的方式。 具体实现代码:
#include stdio.h
#include stdlib.hstruct index {//定义块的结构int key;int start;
} newIndex[3];//定义结构体数组int search(int key, int a[]);int cmp(const void *a,const void* b){return (*(struct index*)a).key(*(struct index*)b).key?1:-1;
}
int main(){int i, j-1, k, key;int a[] {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};
//确认模块的起始值和最大值for (i0; i3; i) {newIndex[i].start j1;//确定每个块范围的起始值j 6;for (int knewIndex[i].start; kj; k) {if (newIndex[i].keya[k]) {newIndex[i].keya[k];}}}
//对结构体按照 key 值进行排序qsort(newIndex,3, sizeof(newIndex[0]), cmp);//输入要查询的数并调用函数进行查找printf(请输入您想要查找的数\n);scanf(%d, key);k search(key, a);
//输出查找的结果if (k0) {printf(查找成功您要找的数在数组中的位置是%d\n,k1);}else{printf(查找失败您要找的数不在数组中。\n);}return 0;
}
int search(int key, int a[]){int i, startValue;i 0;while (i3 keynewIndex[i].key) {//确定在哪个块中遍历每个块确定key在哪个块中i;}if (i3) {//大于分得的块数则返回0return -1;}startValue newIndex[i].start;//startValue等于块范围的起始值while (startValue startValue5 a[startValue]!key){startValue;}if (startValuestartValue5) {//如果大于块范围的结束值则说明没有要查找的数return -1;}return startValue;
}
运行结果
请输入您想要查找的数
22
查找成功您要找的数在数组中的位置是7分块查找的性能分析
分块查找算法的运行效率受两部分影响查找块的操作和块内查找的操作。查找块的操作可以采用顺序查找也可以采用折半查找更优块内查找的操作采用顺序查找的方式。相比于折半查找分块查找时间效率上更低一些相比于顺序查找由于在子表中进行比较的子表个数会不同程度的减少所有分块查找算法会更优。总体来说分块查找算法的效率介于顺序查找和折半查找之间。
