算法-查找

2017-06-28

线性表的查找

顺序查找

线性表的顺序查找

//不考虑链式，其实本质相同，默认元素不重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配，0号单元留空
    int TableLen;   //表的长度
}SSTable;
//ST.elem[0]为哨兵元素，存储待找元素
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0] = key;
    int index;
    for(index=ST.TableLen;ST.elem[index]!=key;--index){}
    return index;   //返回数组下标
}

有序表的顺序查找

//不考虑链式，其实本质相同，默认元素不重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
}SSTable;
int Search_SeqOrderly(SSTable ST,ElemType key){
    ST.elem[0] = key;
    int index;
    for(index=ST.TableLen-1;ST.elem[index]!=key;--index){
        if(ST.elem[index]<key){
            return -1;//从后往前，找到比key小还没找到，说明没有
        }
    }
    return index;   //返回数组下标，-1则没有
}

折半查找

有序表的折半查找

//只有有序表才能够进行折半查找，不考虑元素重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
}SSTable;
int Binary_Search(SSTable ST,ElemType key){
    int low = 0;
    int high = ST.TableLen-1;
    int mid;
    while(low<=high){
        mid = (low+high)/2;
        if(ST.elem[mid] == key){
            return mid;
        }else if(ST.elem[mid] > key){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;  //上面没有return，则找不到
}

分块查找

局部有序表的折半查找

//局部有序，说明索引块之间的最大值是有序的，索引块内部可以无序
typedef struct{ //查找表的索引
    ElemType max; //该索引块中的最大值
    int index;  //索引块的第一个下标
    int IndexLen;   //索引块的长度
}SSTableIndex;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
    SSTableIndex *Tableindex; //索引表,存储空间基址，建表时实际长度分配
    int TableIndexLen;   //索引表的长度
}SSTable;
int Block_Search(SSTable ST,ElemType key){
    int indexblock = 0;
    //第一步寻找key可能所在的分块
    while(indexblock<ST.TableIndexLen-1 && ST.Tableindex[indexblock].max<key){  //如果已经是最后一块了，则不用往下找
        indexblock++;
    }
    for(int i=0;i<ST.Tableindex[indexblock].IndexLen;i++){
        if(ST.elem[i+ST.Tableindex[indexblock].index==key]){
            return i+ST.Tableindex[indexblock].index;
        }
    }
    return -1;  //上面没有返回，则没有找到，返回-1
}

查找的应用

字符串匹配

简单的模式匹配

//C语言，自行封装String
typedef struct{
    char *elem;
    int length; //String长度
}String;
int findStringIndex(String main,String key){
    int i=0,j=0;
    while(i<main.length&&j<key.length){
        if(main.elem[i]==key.elem[j]){
            i++;
            j++;
        }else{
            j=0;
            i=i-j+1;
        }
    }
    if(j==key.length){
        return i-j;  //说明已经找到
    }else{
        return -1;  //说明没有找到
    }
}

改进的模式匹配——KMP算法

//求next数组
void get_next(String key,int next[]){
    int i =0;
    int j=-1;   //说明正在匹配第一个
    next[0] = -1;
    while(i<key.length){
        if(j==-1||key.elem[i]==key.elem[j]){
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int KMP(String main,String key,int next[],int pos){
    //求Key在main中第pos个字符后的位置
    int i = pos-1;
    int j = -1; //说明正在匹配第一个
    while(i<main.length&&j<key.length){
        if(j==-1||main.elem[i]==key.elem[j]){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    return 0;
}