C 分块查找算法,索引顺序查找算法

  1. #include <stdio.h>
  2. struct index //定义块的结构
  3. {
  4. int key; //块的关键字
  5. int start; //块的起始值
  6. int end; //块的结束值
  7. }index_table[4]; //定义结构体数组
  8. int block_search(int key,int a[]) //自定义实现分块查找
  9. {
  10. int i,j;
  11. i=1;
  12. while(i<=3&&key>index_table[i].key) //确定在哪个块中
  13. i++;
  14. if(i>3) //大于分得的块数,则返回0
  15. return 0;
  16. j=index_table[i].start; //j等于块范围的起始值
  17. while(j<=index_table[i].end&&a[j]!=key) //在确定的块内进行顺序查找
  18. j++;
  19. if(j>index_table[i].end) //如果大于块范围的结束值,则说明没有要査找的数,j置0
  20. j = 0;
  21. return j;
  22. }
  23. int main()
  24. {
  25. int i,j=0,k,key,a[16];
  26. printf(“请输入15个数:\n);
  27. for(i=1;i<16;i++)
  28. scanf(“%d”,&a[i]); //输入由小到大的15个数
  29. for(i=1;i<=3;i++)
  30. {
  31. index_table[i].start=j+1; //确定每个块范围的起始值
  32. j=j+1;
  33. index_table[i].end=j+4; //确定每个块范围的结束值
  34. j=j + 4;
  35. index_table[i].key=a[j]; //确定每个块范围中元素的最大值
  36. }
  37. printf(“请输入你想査找的元素:\n);
  38. scanf(“%d”,&key); //输入要查询的数值
  39. k=block_search(key,a); //调用函数进行杳找
  40. if(k!=0)
  41. printf(“查找成功,其位置是:%d\n,k); //如果找到该数,则输出其位置
  42. else
  43. printf(“查找失败!”); //若未找到,则输出提示信息
  44. return 0
  45. }

运行结果:

请输入15个数:
11 12 18 28 39 56 69 89 96 122 135 146 156 256 298
请输入你想査找的元素:
96
查找成功,其位置是:9

技术要点:

分块査找也称为索引顺序査找,要求将待查的元素均匀地分成块,块间按大小排序,块内不排序,所以要建立一个块的最大(或最小)关键字表,称为索引表。

本实例中将给出的 15 个数按关键字大小分成了 3 块,这 15 个数的排列是一个有序序列,也可以给出无序序列,但必须满足分在第一块中的任意数都小于第二块中的所有数,第二块中的所有数都小于第三块中的所有数。当要査找关键字为 key 的元素时,先用顺序杳找在已建好的索引表中查出 key 所在的块中,再在对应的块中顺序查找 key,若 key 存在,则输出其相应位置,否则输出提示信息。