C语言分块查找算法,索引顺序查找算法
例如,采用分块查找法在有序表 11、12、18、28、39、56、69、89、96、122、135、146、156、256、298 中查找关键字为 96 的元素。
査找特定关键字元素个数为 15,要求用户输入有序表各元素,程序输出査找成功与否,若成功,还显示元素在有序表中的位罝。
(2)自定义函数 block_search(),实现分块查找。
(3) main() 函数作为程序的入口函数。程序代码如下:
本实例中将给出的 15 个数按关键字大小分成了 3 块,这 15 个数的排列是一个有序序列,也可以给出无序序列,但必须满足分在第一块中的任意数都小于第二块中的所有数,第二块中的所有数都小于第三块中的所有数。当要査找关键字为 key 的元素时,先用顺序杳找在已建好的索引表中查出 key 所在的块中,再在对应的块中顺序查找 key,若 key 存在,则输出其相应位置,否则输出提示信息。
査找特定关键字元素个数为 15,要求用户输入有序表各元素,程序输出査找成功与否,若成功,还显示元素在有序表中的位罝。
实现过程:
(1)定义结构体 index,用于存储块的结构,并定义该结构体数组 index_table。(2)自定义函数 block_search(),实现分块查找。
(3) main() 函数作为程序的入口函数。程序代码如下:
#include <stdio.h> struct index //定义块的结构 { int key; //块的关键字 int start; //块的起始值 int end; //块的结束值 }index_table[4]; //定义结构体数组 int block_search(int key,int a[]) //自定义实现分块查找 { int i,j; i=1; while(i<=3&&key>index_table[i].key) //确定在哪个块中 i++; if(i>3) //大于分得的块数,则返回0 return 0; j=index_table[i].start; //j等于块范围的起始值 while(j<=index_table[i].end&&a[j]!=key) //在确定的块内进行顺序查找 j++; if(j>index_table[i].end) //如果大于块范围的结束值,则说明没有要査找的数,j置0 j = 0; return j; } int main() { int i,j=0,k,key,a[16]; printf("请输入15个数:\n"); for(i=1;i<16;i++) scanf("%d",&a[i]); //输入由小到大的15个数 for(i=1;i<=3;i++) { index_table[i].start=j+1; //确定每个块范围的起始值 j=j+1; index_table[i].end=j+4; //确定每个块范围的结束值 j=j + 4; index_table[i].key=a[j]; //确定每个块范围中元素的最大值 } printf("请输入你想査找的元素:\n"); scanf("%d",&key); //输入要查询的数值 k=block_search(key,a); //调用函数进行杳找 if(k!=0) printf("查找成功,其位置是:%d\n",k); //如果找到该数,则输出其位置 else printf("查找失败!"); //若未找到,则输出提示信息 return 0; }
运行结果:
请输入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 存在,则输出其相应位置,否则输出提示信息。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频