数据结构与算法

A-6 查找

菠萝猫 · 4月29日 · 2020年 159次已读
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>

int main()
{

}

/*
1.顺序表查找(线性查找)——无序、顺序存储
a为数组,n为该数组的元素的个数,key为要查找的关键字
*/
int Sequential_Search(int *a,int n,int key)
{
    int i;
    a[0]=key;//a[0]是关键字 哨兵
    i=n;//从数组的尾部开始循环
    while(a[i]!=key)
    {
        i--;
    }
    return i;//返回0则查找失败
}

/*
2.有序表查找——对已排序的表进行查找
2.1 折半查找(二分查找):
    顺序存储 数据有序(一般是从小到大)
    给定值与中间值进行比较,判断大小再分左右中间值继续进行比较。
2.2 插值查找
    根据要查找的关键字key与查找表中最大、最小记录的关键字
    比较后的查找方法。核心在于插值的而计算公式
    即将折半查找的 mid = (low+high)/2; 改为插值公式即可,见下
    目的:更加缩小需要查找的范围
*/

//折半查找
int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low=0;//low开始记录最低位
    high=n-1;//high开始记录最高位
    while(low<=high)
    {
        mid = (low+high)/2;//折半 中间值
        if(key<a[mid])
        {
            high = mid - 1;//比中间的小,中间的下一位为最高值
        }
        else if(key>a[mid])
        {
            low = mid+1;//同理
        }
        else
        {
            return mid;//若相等则说明id即为查找的位置
        }
    }
    return 0;
}

//插值查找
int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low=0;//low开始记录最低位
    high=n-1;//high开始记录最高位
    while(low<=high)
    {
        mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);//折半 中间值
        if(key<a[mid])
        {
            high = mid - 1;//比中间的小,中间的下一位为最高值
        }
        else if(key>a[mid])
        {
            low = mid+1;//同理
        }
        else
        {
            return mid;//若相等则说明id即为查找的位置
        }
    }
    return 0;
}

/*
3.斐波那契查找——有序、顺序存储
    利用黄金分割线原理来实现,根据斐波那契数列将数组分为多个小范围,每次
    只在给范围内查询,不成功再根据斐波那契数列改变查询范围。
    同样是为了压缩查询范围,减少查询次数。
    F为斐波那契数列
    F={0,1,1,2,3,5,8,13,21....}
*/
int Fibonacci_Search(int *a,int n,int key)
{
    int low,high,mid,i,k;
    low = 0;
    high = n-1;
    k=0;
    while(n>F[k]-1)//计算n位于斐波那契数列的位置
    {
        k++;
    }
    for(i=n;i<F[k]-1;i++){//将不满的数值用数组的最大值补全
        a[i]=a[n];
    }
    while(low<=high)
    {
        mid = low + F[k-1]-1;
        if(key<a[mid]){
            high = mid-1;
            k=k-1;//斐波那契数列下标减1位
        }else if(key>a[mid]){
            low = mid+1;
            k=k-2;//斐波那契数列下标减2位
        }else{
            if(mid<=n){
                return mid;//若相等则说明mid即为查找到的位置
            }else{
                return n;//若mid>n说明是补全数值,返回n
            }
        }
    }
    return 0;
}

/*
4.线性索引查询——无序、顺序存储的数据
    为了解决引入索引这个数据结构
    索引就是把一个关键字与它对应的记录相关联的过程。
    每个索引有若干索引项组成。
    每个索引项至少包含关键字何其对应的记录在存储器中的位置等信息
    按结构分类:线性、树形、多级索引。
这里只讨论线性索引:
    将索引项集合组织为线性结构,也称索引表。
    三种线性索引:
        4.1 稠密索引——数据集非常大
            将数据集中的每个记录对应一个索引项。
            索引项要求一定是按照关键码有序的排列。——在数据非常大的时候空间代价大
            索引项有序:折半、插值、斐波那契等有序查找算法都可以使用
            一个记事本(按序记录),记录东西放在那里即可。
        4.2 分块索引——数据库表查找等
            为了减少索引项在数据非常大的时候的空间代价大的问题
            把数据集的记录分成若干块,满足的条件:
                块内无序:块内记录可以不要求有序。
                快间有序:快间记录的关键字有序——提高查找块的效率
            每一块对应索引表中的一个索引项,其结构分为三个数据项:
                最大关键码:存储每一块中最大的关键字
                块内记录的个数——便于循环时使用
                用于指向块首数据元素额指针——便于遍历
            图书馆图书分类。不同类的书要求按序排列,同类的书不要求有序。
        4.3 倒排索引——搜索技术
            索引表中每一个索引项包含:
                次关键码
                记录号表:存储具有相同关键字的所有记录的记录号(可以是指向
                该记录的指针或者是主关键字)
            源于现实中根据属性(或字段、次关键码)的值查找记录
            即可以理解为索引表的每一项都包括一个属性值和具有该属性值得各
            记录得地址。
            因为是由属性来确定记录所以叫倒排索引。

*/
```

未完待续


版权声明:本站采用 “知识共享署名 – 非商业性使用 – 相同方式共享 4.0 中国大陆许可协议” 进行许可,您可以转载本站文章,转载时请以超链接形式标明文章原始出处,Thanks.


0 条回应