数据结构 - 查找算法

一.查找的概念

二.顺序表查找

特点：

        1.记录的数据可以是无序的

        2.当数据量较大时，查找效率低，需要依次遍历

/**
 * @description:            顺序表查找算法，从后往前查找
 * @param - a       :       要操作的数组的指针
 * @param - key     :       指定查找的内容
 * @return          :       成功则返回（元素的下标） ， 失败返回（-1）
*/
int Seqsearch(int *a,int key)
{
    int i;

    /* 从后到前依次遍历 */
    for(i = N-1; i >= 0; i--)
    {
        if(a[i] == key)             //若找到了则直接返回
        {
            return i;
        }
    }

    return -1;
}

三.二分法查找

特点：

        1.数据必须是有序的。

/**
 * @description:            二分法查找算法
 * @param - a       :       要操作的数组的指针
 * @param - key     :       要查找的内容
 * @return          :       成功则返回该元素的序号，失败则返回 -1
*/
int Binsearch(int *a,int key)
{
    /* low 表示区间下界 ， high 表示区间上界 */
    static int low,high,mid;

    low = 0;
    high = N - 1;
    
    /* 循环执行二分法 */
    while(low <= high)
    {
        mid = (low + high) / 2;         //获取中间元素的下标

        /* 1.若下标为 mid 的元素 == key  */
        if(key == a[mid])
            return mid;

        /* 2.若下标为 mid 的元素 > key , 则表示要查找的元素在 mid 的左边 */
        if(key < a[mid])
        {
            high = mid - 1;
        }

        /* 3.若下标为 mid 的元素 < key , 则表示要查找的元素在 mid 的右边 */
        else if(key > a[mid])
        {
            low = mid + 1;
        }

    }

    return -1;
}

三.哈希表查找

1.哈希表定义

        存储记录时，有意的建立 key 与记录的存储位置之间的关系，以构建哈希表。

2.构建哈希表

（1）.选取恰当的哈希函数

        尽可能将记录均匀分布，以减少冲突现象的发生。

        ①.直接地址法（不常用）

        ②.数字分析法（不常用）

        ③.平方取中法

        ④.叠加法

        ⑤.保留余数法（常用）

        ⑥.随机函数法

（2）.处理冲突

        ①.开放地址法

        

②.链地址法

 

原文地址：https://blog.csdn.net/kaneki_lh/article/details/142382563

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！