数据结构（查找）

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;
}

线性索引查找