数据结构(查找)

Jasmineyaoyao 2020-05-11

静态查找

数据集合稳定,不需要添加,删除元素的查找

对于静态查找:可以用线性表结构组织数据,这样便可使用顺序查找算法,如果再对关键字进行排序,则可使用折半查找法或斐波那契查找法等来提高效率

动态查找

数据集合在查找的过程中需要同时添加或删除元素的查找

对于动态查找:可考虑使用二叉排序树的查找技术,另外还可使用散列表结构来解决一些查找问题


顺序查找:

从第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值进行比较

//顺序查找,a为要查找的数组;n为数组长度,key为查找的关键字
int Sq_Search(int *a,int n,int key){
    int i;
    for(i=0;i<=n;i++){
        if(a[i]==key){
            return i;
        }
    }
    return 0;
}

由于每次循环都要判断两次,所以可以考虑添加一个“哨兵”来承担监视越界的问题省去一次判断,这样效率就可提高一倍;

//顺序查找,a为要查找的数组;n为数组长度,key为查找的关键字
int Sq_Search(int *a,int n,int key){
    int i=n-1;
    a[0]=key;
    while(a[i]!=key)
        i--;
    return i;
}

折半查找法

二分法搜索:确定待查找范围,缩小范围【O(Log?n)】

差值查找法

原理:按照数据分布的数据差值比例,按这个比例来决定下一次查找位(关键是差值要按比例分布)

按比例查找:与折半查找法相似(只不过将二分改为了按比例查而已)

例如:再字典中查找apple不会用折半查找法,而是差值查找法

int bin_search(int a[],int n,int key){
    int low=0,high=n-1,mid;
    while(low<=high){
        printf("循环\n");
        //中心思路是:key下标/查找范围≈key/范围边缘两值的差;根据这种思想,不断缩短范围直到查找到key
        mid=low+(key-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==key)
            return mid;
        else if(a[mid]<key)//说明key在mid的右边
            low=mid+1;
        else//说明key在mid左边
            high=mid-1;
    }
    return -1;
}

斐波那契查找

斐波那契数列(F[k]):1,1,2,3,5,8,13,21,34,...(前后两个数比重逐渐接近:0.618)

所以利用斐波那契把差值查找中的比例改为不断接近0.618的比例就叫斐波那契查找法;

数据结构(查找)

#define MAXSIZE 20

int bin_search(int a[],int n,int key){
    int low=0,high,mid;
    int i=1,j=1,k=2;
    int f[MAXSIZE]={1,1};
    while(f[k]<n&&j<MAXSIZE){
        k++;
        f[k]=f[i]+f[j];
        i=f[j];
        j=f[k];
    }
    high=f[k];
    while(low<=high){
        printf("循环\n");
        mid=f[k-1];
        if(a[mid]==key)
            return mid;
        else if(a[mid]<key){//说明key在mid的右边
            low=mid+1;
            k-=2;
            mid=f[k-1];
        }else{//说明key在mid左边
            high=mid-1;
            k-=1;
            mid=f[k-1];
        }
    }
    return -1;
}

线性索引查找

  • 稠密索引:文件每个搜索码值都对应索引值,即为数据记录文件的每一条记录设一个(键——指针)对。
  • 如图:索引项包括索引值以及指向该搜索码的第一条数据记录的指针
  • 缺点:所占空间较大,若数据量较大时不太适合

数据结构(查找).

分块索引

  • 为减小索引项的个数,对数据表进行分块,使其分块有序
  • 对每一块建立一个索引项
  • 需要注意的是各块间有序,块内数据无序

数据结构(查找)

倒排索引

根据属性值来查看记录;

相关推荐