6.2 顺序查找和折半查找（p235）

6.2.1 顺序查找(（p235）

1. 一般线性表的顺序查找

typedef struct{        //查找表的数据结构
    ElemType *elem;    //元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen;    //表的长度
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
//在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元素在表中的位置
    ST.elem[0]=key;    //“哨兵”
    for (i=ST.TableLen;ST.elem[i]!=key; --i){    //从后往前找

    }
    return i;        //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

6.2.2 折半查找（p237）

int Binary_Search(SeqList L, ElemType key) {
//在有序表L中查找关键字为key的元素，若存在则分会其位置，不存在返回-1
    int low = 0, high = L.length - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;    //取中间位置
        if (L.elem[mid] == key)
            return mid;        //查找成功则返回所在位置
        else if(L.elem[mid] > key)
            high = mid - 1;        //从前半部分继续查找
        else
            low = mid + 1;        //从后半部分继续查找
    }
    return -1;
}

6.5 字符串模式匹配（p268）

6.5.1 简单的模式匹配算法（p268）

int Index(SString S,SString T){
    int i=1;j=1;
    while(i<=S[0]&&j<=T[0]){
        if(S[i]==T[j])
        {
            ++i;++j;        //继续比较后继字符
        }
        else
        {
            i=i-j+2;j=1;    //指针后退重新开始匹配
        }
    }
    if(j>T[0])
        return i-T[0];
    else
        return 0;
}

6.5.2 改进的模式匹配算法——KMP算法（p269）

void get_next(char T[],int next[]){
    i=1;
    next[1]=0;
    j=0;
    while(i<=T[0]){        //T[0]用于保存字符串的长度
    if(j==0||T[i]==T[j]){
        ++i;++j;next[i]=j;
    }
    else
        j=next[j];
    }
}
int KMP(char S[],char T[],int next[],int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
//其中，T非空，1<=pos<=strlen(S)
    i=pos;
    j=1;
    while(i<=S[0]&&j<=T[0]){
    if(j==0||S[i]==T[j]){
        ++i;
        ++j;
    }
    else
        j=next[j];
    }
    if(j>T[0])
    return i-T[0];
    else
    return 0;
}