c语言的七大查找算法,非常值得学习

时间:2024-03-17 20:53:05

今天带着大家学习下,C语言七大查找算法!!!!!!!!!!

这里我们首先看下算法的概念:

         算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。

         如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

如下所示:C语言的七大查找算法。

1、顺序查找

2、二分查找

3、插值查找

4、斐波那契查找

5、树表查找

6、分块查找

7、哈希查找

这里我们看下查找的概念:

       查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。

       我这里简单介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。

        插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找


查找算法分类:

1)静态查找和动态查找;

注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2)无序查找和有序查找。

无序查找:被查找数列有序无序均可;

有序查找:被查找数列必须为有序数列。


        平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。

Pi:查找表中第i个数据元素的概率。

Ci:找到第i个数据元素时已经比较过的次数。

1、顺序查找

说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。


基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。


复杂度分析:

查找成功时的平均查找长度为:(假设每个数据元素的概率相等) 

ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时,需要n+1次比较,时间复杂度为O(n);

所以,顺序查找的时间复杂度为O(n)。


理论结合实践,我们这里直接看顺序查找C语言实现吧:


//顺序查找C语言实现

//基本思路:用顺序结构存储数据(数组、链表),从前到后依次查询目标值,

//            如果发现则返回查找到的值,否则返回0.

#include<stdio.h>


int FindBySeq(int *ListSeq, int ListLength, int KeyData);


int main()

{

    int TestData[5] = { 34, 35, 26, 89, 56 };

    int retData = FindBySeq(TestData, 5, 89);

    printf("retData: %d\n", retData);

    return 0;

}


int FindBySeq(int *ListSeq, int ListLength, int KeyData)

{

    int tmp = 0;

    int length = ListLength;

    for (int i = 0; i < ListLength; i++)

    {

        if (ListSeq[i] == KeyData)

            return i;

    }

    return 0;

}

.

2、二分查找

说明:元素必须是有序的,如果是无序的则要先进行排序操作。


基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。


复杂度分析:最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n);

注:折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。


理论结合实践,我们这里直接看二分查找C语言实现吧:

#include<stdio.h>

//二分查找-C语言实现

//基本思路:将排序好的数据存放到数组里(不能是链表)

//        这只前中后标签,与中间元素比,若小于就将后变为原来的中

//        继续计算中,比较,循环,直至等于中,或循环结束。

int binsearch(int *sortedSeq, int seqLength, int keyData);


int main()

{

    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    int location;

    int target = 4;

    location = binsearch(array, 9, target);

    printf("%d\n", location);

    return 0;

}


int binsearch(int *sortedSeq, int seqLength, int keyData)

{

    int low = 0, mid, high = seqLength - 1;


    while (low <= high)

    {

        mid = (low + high) / 2;//奇数,无论奇偶,有个值就行

        if (keyData < sortedSeq[mid])

        {

            high = mid - 1;//是mid-1,因为mid已经比较过了

        }

        else if (keyData > sortedSeq[mid])

        {

            low = mid + 1;

        }

        else

        {

            return mid;

        }

    }

    return -1;

}



3、插值查找


     在介绍插值查找之前,首先考虑一个新问题,为什么上述算法一定要是折半,而不是折四分之一或者折更多呢?

      打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。

      同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。

       经过以上分析,折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下:

mid=(low+high)/2, 即mid=low+1/2*(high-low);

通过类比,我们可以将查找的点改进为如下:

mid=low+(key-a[low])/(a[high]-a[low])*(high-low),

        也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。


基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找

注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。


复杂度分析:查找成功或者失败的时间复杂度均为O(log2(log2n))。


理论结合实践,我们这里直接看插值查找C语言实现吧:

#include<stdio.h>

//插值查找-C语言实现

//基本思路:二分查找改进版,只需改一行代码。

//        mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

int insertSearch(int *sortedSeq, int seqLength, int keyData);


int main()

{

    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    int location;

    int target = 4;

    location = insertSearch(array, 9, target);

    printf("%d\n", location);

    return 0;

}


int insertSearch(int *sortedSeq, int seqLength, int keyData)

{

    int low = 0, mid, high = seqLength - 1;


    while (low <= high)

    {

        mid = low + (keyData - sortedSeq[low]) / (sortedSeq[high] - sortedSeq[low]);

        if (keyData < sortedSeq[mid])

        {

            high = mid - 1;//是mid-1,因为mid已经比较过了

        }

        else if (keyData > sortedSeq[mid])

        {

            low = mid + 1;

        }

        else

        {

            return mid;

        }

    }

    return -1;

}


关注微信公众号获取更多嵌入式软件开发学习方法!!!!!!!!!!

c语言的七大查找算法,非常值得学习