C语言实现基础查找算法
1. 顺序查找 ( Sequential search )
顺序查找是按照序列原有顺序对 数组/链表 进行遍历比较查询的基本查找算法。
1.1 算法实现
- 从表中的最后一个数据元素开始，逐个同记录的关键字做比较
- 如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。
- 时间复杂度：O(n)
静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上大同小异。我们这里使用数组进行操作。
// 顺序查找--如果发现则返回查找到的值，否则返回0.
int SequentialSearch(int arr[], int len, int KeyData)
{
// 第一种方法：每次循环都得考虑是否越界
// int tmp = 0;
// for (int i = 0; i < len; i++) {
// if (arr[i] == KeyData)
// return i;
// }
//第二种方法 优化
int i;
arr[0] = KeyData; //设置arr[0]为关键字值，也叫做"哨兵"
i = len - 1; // 循环数组尾部开始
while (arr[i] != KeyData) {
i--;
}
return i;
}
1.2 测试
void printf_arr(int arr[],int size) //打印数组
{
int i = 0;
for (; i < size; i++) {
printf("%d ", arr[i]);
}
printf ("\n");
}
int main()
{
int arr[] = {90, 70, 34, 35, 26, 89, 56};
int len = sizeof (arr) / sizeof (arr[0]);
printf ("原数据:\n");
printf_arr (arr, len);
int retData = SequentialSearch(arr, len, arr[6]);
printf("找到数组[%d] 数据为: %d\n", retData, arr[6]);
return 0;
}
2. 二分查找 ( Binary Search )
二分查找也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
- 时间复杂度：O (
l
o
g
n
log_{n}
logn)
2.1 算法实现
int binary_search(int key,int a[],int n)
{
int left, right, mid;
int count = 0,count1=0;
left = 0;
right = n-1;
while(left < right) { //査找范围不为0时执行循环体语句
count++; //count记录査找次数
mid=(left + right) / 2; //求中间位置
printf ("第 %d 次查找, left : %d right : %d mid : %d\n", count, left, right, mid);
if(key < a[mid]) //key小于中间值时
right = mid - 1; //确定左子表范围
else if(key > a[mid]) //key 大于中间值时
left = mid + 1; //确定右子表范围
else if(key == a[mid]) { //当key等于中间值时，证明查找成功
printf("\n查找成功!\n\n查找 %d 次!", count); //输出査找次数及所査找元素在数组中的位置
count1++; //count1记录查找成功次数
break;
}
}
if(count1 == 0) //判断是否查找失敗
printf("查找失敗!"); //査找失敗输出no found
return mid;
}
2.2 测试
void printf_arr(int arr[],int size) //打印数组
{
int i = 0;
for (; i < size; i++) {
printf("%d ", arr[i]);
}
printf ("\n");
}
int main (void)
{
int i, key, a[100], n;
printf("请输入数组的长度：\n");
scanf("%d",&n); //输入数组元素个数
printf("请输入数组元素：\n");
for(i = 0; i < n; i++)
scanf("%d",&a[i]); //输入有序数列到数组a中
printf ("\n原数据:\n");
printf_arr (a, n);
printf("\n请输入你想查找的元素：\n");
scanf("%d",&key); //输入要查找的关键字
int pos = binary_search(key, a, n);
if(pos != -1)
printf("\n在数组 [%d] 找到元素:%d\n", pos, key);
else
printf("\n未在数组中找到元素: %d\n", key);
return 0;
}
3. 插值查找 ( Interpolation Search )
- 插值查找，有序表的一种查找方式。
- 插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。
- 插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
- 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
- 复杂度分析：查找成功或者失败的时间复杂度均为O (
l
o
g
2
log_{2}
log2(l
o
g
n
log_{n}
logn))。
3.1 算法实现
折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下： mid = (low + high) / 2,即mid = low + 1/2 * (high - low); 通过类比，我们可以将查找的点改进为如下：
mid = ((key - a[low]) * (high - low )) / (a[high] - a[low]) + low
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
int Interpolation_search(int *a, int key, int n) //插值查找
{
int mid, low, high;
int count = 0,count1=0;
low = 0,high = n - 1;
while(low <= high){
count++;
mid = ((key - a[low]) * (high - low )) / (a[high] - a[low]) + low;
printf ("第 %d 次查找, low : %d high : %d mid : %d\n", count, low, high, mid);
if(a[mid] < key) {
low = mid + 1;
} else if (a[mid] == key) {
printf("\n查找成功!\n\n查找 %d 次!",count); //输出査找次数及所査找元素在数组中的位置
count1++;
break;
} else {
high = mid - 1;
}
}
if(count1 == 0) //判断是否查找失敗
printf("查找失敗!"); //査找失敗输出no found
return mid;
}
3.2 测试
void printf_arr(int arr[],int size) //打印数组
{
int i = 0;
for (; i < size; i++) {
printf("%d ", arr[i]);
}
printf ("\n");
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof (arr) / sizeof (arr[0]);
int key;
printf ("\n原数据:\n");
printf_arr (arr, n);
printf("请输入要查找的数字:\n");
scanf("%d",&key);
int pos = Interpolation_search(arr, key, n);
if(pos != -1)
printf("\n在数组 [%d] 找到元素:%d\n", pos, key);
else
printf("\n未在数组中找到元素: %d\n", key);
return 0;
}
4. 斐波那契查找 ( Fibonacci Search )
- 黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
- 也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
- 时间复杂度:
l
o
g
2
n
log_2{n}
log2n
4.1 算法实现
相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：
-
相等，mid位置的元素即为所求
-
大于, low = mid + 1;
-
小于，high = mid - 1。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;
开始将k值与第F(k-1)位置的记录进行比较(及mid = low + F(k-1)-1),比较结果也分为三种
- 相等，mid位置的元素即为所求
- 大于，low=mid+1,k-=2;
说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。 - 小于，high=mid-1,k-=1。
说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。
核心点:
- 斐波那契是一种特殊的分割方法，和二分、插值本质上是一样的，都是分割方法；
- 利用了斐波那契数列特殊的性质，一个长度只要可以被黄金分割，那么分割后的片段仍然可以继续进行黄金分割，循环。
首先，我们构造一个完整的斐波那契数列，然后开始分，小于就取左边的分割，F变为F-1；大于就取右边的分割，F变为F-2。
#define MAXN 11
/*
*产生斐波那契数列
* */
void Fibonacci(int *f)
{
int i;
f[0] = 1;
f[1] = 1;
for (i = 2; i < MAXN; ++i)
f[i] = f[i - 2] + f[i - 1];
}
int Fibonacci_Search(int *a, int key, int n) //斐波那契查找
{
int i, low = 0, high = n - 1;
int mid = 0;
int k = 0;
int F[MAXN];
int count = 0, count1 = 0;
Fibonacci(F);
while (n > F[k] - 1) //计算出n在斐波那契中的数列
++k;
for (i = n; i < F[k] - 1; ++i) //把数组补全
a[i] = a[high];
while (low <= high) {
count++;
mid = low + F[k - 1] - 1; //根据斐波那契数列进行黄金分割
printf ("第 %d 次查找, low : %d high : %d mid : %d\n", count, low, high, mid);
if (a[mid] > key) {
high = mid - 1;
k = k - 1;
} else if (a[mid] < key) {
low = mid + 1;
k = k - 2;
} else {
if (mid <= high) { //如果为真则找到相应的位置
printf("\n查找成功!\n\n查找 %d 次!",count);
count1++;
break;
} else {
mid = -1;
break;
}
}
}
if(count1 == 0) { //判断是否查找失敗
printf("查找失敗!"); //査找失敗输出no found
mid = -1;
}
return mid;
}
4.2 测试
void printf_arr(int arr[],int size) //打印数组
{
int i = 0;
for (; i < size; i++) {
printf("%d ", arr[i]);
}
printf ("\n");
}
int main()
{
int a[MAXN] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int k, res = 0;
int n = sizeof (a) / sizeof (a[0]);
printf ("\n原数据:\n");
printf_arr (a, n);
printf("请输入要查找的数字:\n");
scanf("%d", &k);
res = Fibonacci_Search(a, k, n);
if (res != -1)
printf("\n在数组的第%d个位置找到元素:%d\n", res + 1, k);
else
printf("\n未在数组中找到元素:%d\n", k);
return 0;
}
5. 分块查找 ( Block search )
- 分块查找也叫索引顺序查找,是折半查找和顺序查找的一种改进方法
- 分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。
5.1 算法实现
将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。
主要包含两部分:
- 子表部分中最大的关键字
- 第一个关键字在总表中的位置
建立的索引表要求按照关键字进行升序排序，查找表要么整体有序，要么分块有序。
分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字，第三个子表的所有关键字都要大于第二个子表中的最大关键字，依次类推。
struct 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 BlockSearch(int key, int a[])
{
int i, startValue;
i = 0;
while (i < 3 && key > newIndex[i].key) { //确定在哪个块中，遍历每个块，确定key在哪个块中
i++;
}
if (i >= 3) { //大于分得的块数，则返回0
return -1;
}
startValue = newIndex[i].start; //startValue等于块范围的起始值
while (startValue <= startValue + 5 && a[startValue] != key) {
startValue++;
}
if (startValue > startValue + 5) { //如果大于块范围的结束值，则说明没有要查找的数
return -1;
}
return startValue;
}
5.2 测试
int main()
{
int i, j=-1, k, key;
int a[] = {16, 11, 3, 19, 14, 34, 27, 56, 33, 54, 63, 61, 74, 77, 81};
//确认模块的起始值和最大值
for (i=0; i<3; i++) {
newIndex[i].start = j+1; //确定每个块范围的起始值
j += 6;
for (int k=newIndex[i].start; k<=j; k++) {
if (newIndex[i].key<a[k]) {
newIndex[i].key=a[k];
}
}
}
//对结构体按照 key 值进行排序
qsort(newIndex,3, sizeof(newIndex[0]), cmp);
//输入要查询的数，并调用函数进行查找
printf("请输入您想要查找的数：\n");
scanf("%d", &key);
k = BlockSearch(key, a);
//输出查找的结果
if (k>0) {
printf("查找成功！您要找的数在数组中的位置是：%d\n",k+1);
} else {
printf("查找失败！您要找的数不在数组中。\n");
}
return 0;
}
6. 树表查找 ( Tree table search )
最简单的树表查找算法——二叉树查找算法
参考链接：非线性结构——简单树相关
7. 哈希查找 ( Hash Search )
哈希查找是通过计算数据元素的存储地址进行查找的一种方法。
实现哈希查找的步骤如下：
- 用给定的哈希函数构造哈希表；
- 根据选择的冲突处理方法解决地址冲突；
- 在哈希表的基础上执行哈希查找。
7.1 哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
简而言之，哈希表的建立同数学函数类似，把函数中的 key 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。
哈希地址 = f (key)
哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。f（）是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。
7.1.1 哈希表的构建
7.1.1.1 直接定址法
哈希地址：f(key) = a * key + b (a,b为常数)
- 优点：简单、均匀、无冲突。
- 应用场景：需要事先知道关键字的分布情况，适合查找表较小且连续的情况
7.1.1.2 数字分析法
就是分析我们的关键字，取其中一段，或对其位移，叠加，用作地址。比如我们的学号，前 6 位都是一样的，但是后面 3 位都不相同，我们则可以用学号作为键，后面的 3 位做为我们的散列地址。如果我们这样还是容易产生冲突，则可以对抽取数字再进行处理。我们的目的只有一个，提供一个散列函数将关键字合理的分配到散列表的各位置。
在取法上尽量选择变化较多的位，避免冲突发生。
- 优点：简单、均匀、适用于关键字位数较大的情况
- 应用场景：关键字位数较大，知道关键字分布情况且关键字的若干位较均匀
7.1.1.3 折叠法
处理我们的关键字然后用作我们的散列地址，主要思路是将关键字从左到右分割成位数相等的几部分，然后叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是123456789，则我们分为三部分 123 ，456 ，789 然后将其相加得 1368 然后我们再取其后三位 368 作为我们的散列地址。
-
优点：事先不需要知道关键字情况
-
应用场景：适合关键字位数较多的情况
7.1.1.4 除留余数法
哈希地址：f(key) = key % p (p<=m) m为哈希表表长。
- 优点：计算效率高，灵活
- 应用场景：不知道关键字分布情况
7.1.1.5 乘法散列法
- 用关键字 k 乘上常数 A(0 < A < 1)，并提取 k A 的小数部分
- 用 m 乘以这个值，再向下取整
哈希地址：f(k) = floor ( m * ( kA % 1 ) )
kA % 1 的含义是取 keyA 的小数部分
- 优点：对 m 的选择不是特别关键一般选择它为 2 的某个幂次（m = 2 ^ p ,p为某个整数）
- 应用场景：不知道关键字情况
7.1.1.6 平方取中法
这个方法就比较简单了，假设关键字是 321，那么他的平方就是 103041，再抽取中间的 3 位就是 030 或 304 用作散列地址。再比如关键字是 1234 那么它的平方就是 1522756 ，抽取中间 3 位就是 227 用作散列地址.
- 优点：灵活，适用范围广泛
- 适用场景：不知道关键字分布，而位数又不是很大的情况。
7.1.1.7 随机数法
哈希地址：f(key) = random(key)
这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。
- 适用场景：关键字的长度不等时
7.1.2 处理哈希冲突的方法
对应不同的关键字可能获得相同的hash地址，即 key1≠key2，但是f(key1)=f(key2)。这种现象就是冲突，而且这种冲突只能尽可能的减少，不能完全避免。因为哈希函数是从关键字集合和地址集合的映像，通常关键字集合比较大，而地址集合的元素仅为哈希表中的地址值。
7.1.2.1 开放地址法
开放地址法就是一旦发生冲突，就去寻找下一个空的散列地址，只要列表足够大，空的散列地址总能找到，并将记录存入，为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查。
开放定址法 H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量） 当得出的哈希地址产生冲突时，选取以下 3 种方法中的一种获取 d 的值，然后继续计算，直到计算出的哈希地址不在冲突为止，这 3 种方法为：
线性探测法：d=1，2，3，…，m-1
二次探测法：d=12，-12，22，-22，32，…
伪随机数探测法：d=伪随机数
7.1.2.2 再哈希法
利用不同的哈希函数再求得一个哈希地址，直到不出现冲突为止。
f,(key) = RH,( key ) (i = 1,2,3,4……k)
7.1.2.3 链地址法
key 不同 f(key) 相同的情况，我们将这些同义词存储在一个单链表中，这种表叫做同义词子表，散列表中只存储同义词子表的头指针。我们还是用刚才的例子，关键字集合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为12，我们再用散列函数 f(key) = key mod 12。我们用了链地址法之后就再也不存在冲突了，无论有多少冲突，我们只需在同义词子表中添加结点即可。
7.1.2.4 公共溢出区法
在创建哈希表时，同时创建另一个表，将所有发生哈希冲突的记录都存储到溢出表。
7.2 算法实现
define HASHSIZE 7 //定义散列表长为数组的长度
#define NULLKEY -1
typedef struct{
int *elem;//数据元素存储地址，动态分配数组
int count; //当前数据元素个数
}HashTable;
//对哈希表进行初始化
void Init(HashTable *hashTable)
{
int i;
hashTable->elem = (int *)malloc(HASHSIZE*sizeof(int));
hashTable->count = HASHSIZE;
for (i = 0; i < HASHSIZE; i++) {
hashTable->elem[i] = NULLKEY;
}
}
//哈希函数(除留余数法)
int Hash(int data)
{
return data % HASHSIZE;
}
//哈希表的插入函数，可用于构造哈希表
void Insert(HashTable *hashTable, int data)
{
int hashAddress = Hash (data); //求哈希地址
//发生冲突
while(hashTable->elem[hashAddress] != NULLKEY){
//利用开放定址法解决冲突
hashAddress = (++hashAddress) % HASHSIZE;
}
hashTable->elem[hashAddress] = data;
}
//哈希表的查找算法
int Search(HashTable *hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
while(hashTable->elem[hashAddress] != data) {//发生冲突
//利用开放定址法解决冲突
hashAddress = (++hashAddress) % HASHSIZE;
//如果查找到的地址中数据为NULL，或者经过一圈的遍历回到原位置，则查找失败
if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data)){
return -1;
}
}
return hashAddress;
}
测试
int main(void)
{
int i,result;
HashTable hashTable;
int arr[HASHSIZE]={13,29,27,28,26,30,38};
//初始化哈希表
Init(&hashTable);
//利用插入函数构造哈希表
for (i = 0; i < HASHSIZE; i++) {
Insert(&hashTable, arr[i]);
}
//调用查找算法
result = Search(&hashTable, 29);
if (result==-1)
printf("查找失败");
else
printf("29在哈希表中的位置是: %d\n",result+1);
return 0;
}
