【数据结构】串的深度学习

数据结构再度学习（详细注释版）：串<常规操作，模式匹配>

串的常规操作与模式匹配

//
//  main.c
//  StringList
//
//  Created by Eason on 2020/8/3.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10
typedef int Status;
typedef char String[MAXSIZE+1];  //串的存储结构，第一个位置存储长度信息所以实际数组要比定义的MAXSIZE+1

//用c值初始化一个串(S为空，c为一个串）
Status initString(String S, char *c){
    if(strlen(c)>MAXSIZE){   //判断用来初始化的串是否超出了串本身的存储范围
        printf("初始值过大，无法初始化\n");
        return ERROR;
    }else{   //未超出范围，继续进行
        S[0]=strlen(c);   //S串的长度置为c串的长度
        for(int i=1;i<=S[0];i++){   //循环将c串的字符一个个存入S串中
            S[i] = *c;   //存入
            c+=1;   //切换到下一个字符，循环继续
        }
    }
    return OK;
}

//判断是否为空串
Status isEmpty(String S){
    if(S[0]==0){   //S[0]为串的长度，若为0则表示串为空
        return TRUE;
    }else{
        return FALSE;
    }
}

//判断串是否已满
Status isFull(String S){
    if(S[0]==MAXSIZE){   //S[0]为串的长度，若为MAXSIZE则表示串已满
        return TRUE;
    }else{
        return FALSE;
    }
}

//清空串
Status clearString(String S){
    S[0]=0;   //将串的长度置0即将串清空了
    return OK;
}

//获取串的长度（方法返回的即是长度值）
int getLength(String S){
    return S[0];   //将串的长度S[0]的数据返回
}

//复制串（将串C的内容复制到串S中）
Status copyString(String S, String C){
    if(isEmpty(C)){   //判断要进行拷贝的串是否为空
        printf("需要复制的串为空，无法复制\n");
        return ERROR;
    }
    if(C[0]>MAXSIZE){   //判断拷贝的串是不是超出了粘贴串的长度MAXSIZE
        printf("需要复制的串过长，无法完全复制\n");  //若超出了长度，则只能复制MAXSIZE前的内容
        for(int i=1;i<=C[0];i++){   //循环存入
            S[i] = C[i];   //存入
        }
        S[0]=C[0];   //S串的长度置为拷贝来的串的长度C[0]
        return OK;
    }
    for(int i=1;i<=C[0];i++){   //如果没有超出长度则可以完全进行循环存储
        S[i]=C[i];  //存储
    }
    S[0]=C[0];   //S串的长度置为拷贝来的串的长度C[0]
    return OK;
}

//串的比较（若串S与C相等则返回0，不想等则返回S-C）
Status compareString(String S, String C){
    int len = S[0]<=C[0]?S[0]:C[0];   //比较两个串的长度，按照短的进行比较
    for(int i=1;i<=len;i++){   //整个长度的串逐个进行比较
        if(S[i]!=C[i]){   //若现在位置的串的两个字符不想等，则表示串不想等
            return S[i]-C[i];   //不想等则返回当前字符的S-C差值
        }
    }
    //计较完成，即短的串与长串中前短串长度的内容都想等
    if(S[0]==C[0]){   //若两个串的长度也想等，则说明两个串完全相等，则返回0
        return 0;
    }else{   //如果只是短串想等，则返回两个串的长度S-C差值
        return S[0]-C[0];
    }
}

//串的连接（S1串在前，S2串在后，连接后的串为New）
Status connectString(String S1, String S2, String New){
    if(S1[0]+S2[0]>MAXSIZE){   //若连个串连接的总长度超过了最大存储长度，则只能存储MAXSIZE长度的串，多余的内容摒弃
        printf("字符串连接过长，尽力连接\n");
        New[0] = MAXSIZE;   //因为已经超过总长度了，所以长度只能是MAXSIZE了
        for(int i=1;i<=S1[0];i++){   //先用循环存储的方式将S串的内容添加至新串中
            New[i] = S1[i];   //存入
        }
        int p=1;   //S2串当前需要存储位置的计数器
        for(int i=S1[0]+1;i<=New[0];i++){   //在S1存储完成后的位置再开始存储S2串
            New[i] = S2[p];   //存入到对应位置
            p++;   //S2需存储位置向后移一位，继续循环进行存储
        }
        return OK;
    }
    //若总长度未超过MAXSIZE则按照如下连接
    New[0] = S1[0]+S2[0];  //新串的长度等于两个字串长度之和
    for(int i=1;i<=S1[0];i++){   //现将子串S1的内容存储到新串中
        New[i] = S1[i];   //存入
    }
    int p=1;   //S2串当前需要存储位置的计数器
    for(int i=S1[0]+1;i<=New[0];i++){   //在S1存储完成后之后的位置再开始存储S2串的内容
        New[i] = S2[p];   //存入
        p++;   //S2的位置向后走一位，循环继续存入
    }
    return OK;
}

//串的插入（在S串的第l位置前插入串N）
Status insertString(String S, int l, String N){
    if(l<1 || l>S[0]+1){   //判断插入位置是否合法
        printf("插入位置不合法，无法插入");
        
    }
    if(S[0]+N[0]>MAXSIZE){   //判断是否可以完全插入，如果超出最大存储容量则丢失一部分
        printf("插入过长，丢失一部分插入\n");
        int temp = MAXSIZE;   //串S向后移动的计位器
        for(int i=S[0];i>=l;i-- ){   //从串的最后一个位置开始向后移动到插入后的位置，为插入的元素腾出位置
            S[temp] = S[i];   //移动到对应位置存入
            temp--;   //计位器-1，一直到插入位置的元素也移动完毕为止
        }
        int length = MAXSIZE-S[0];   //腾出来位置的长度
        int t=1;   //串N计位器
        for(int i=l;i<MAXSIZE-(S[0]-l);i++){   //从插入位置开始插入，到腾出来的位置的末尾
            S[i] = N[t];   //找到对应位置并存入
            t++;   //串向下走继续执行插入操作
        }
        S[0] = MAXSIZE;   //由于是不完全插入，所以最终S串达到了最大的长度
        return OK;
    }
    //若插入后的长度不超过最大存储容量则完全插入执行以下步骤
    int newlength = S[0]+N[0];   //插入后的总长度
    int t = newlength;   //移动目标位置计位器即移动到的最后位置
    for(int i=S[0];i>=l;i--){   //从最后位置开始移动到指定的位置
        S[t] = S[i];   //找到对应的位置并存入
        t--;   //移动目标位置-1，因为是从后往前移动
    }
    int d=1;   //N串的临时计位器
    for(int i=l;i<l+N[0];i++){   //从要插入的位置开始插入
        S[i] = N[d];   //从N的第一个元素插到指定位置开始向后存入
        d++;   //N串的计位器+1，即向后挪动一位继续执行插入操作
    }
    S[0] = newlength;   //新串的长度为总长度
    return OK;
}

//串的删除（删除串S的第i个位置开始长度为length的串）
Status deleteString(String S, int i, int length){
    if(i<1 || i>MAXSIZE || length<0){   //判断要删除位置与长度信息是否合法
        printf("删除信息不合法，无法删除\n");
        return ERROR;
    }
    for(int n=i+length;n<=S[0];n++){   //将删除完成后删除串的末尾后的一个元素开始向前移动一直到删除后半截的元素都向前移动完毕
        S[n-length] = S[n];   //找到移动到的对应位置存入
    }
    S[0] =S[0]-length;   //新串的长度为老串长度减去删掉的对应长度
    return OK;
}


//串的截取（将S串l位置开始向后长度为length的串截取下来存入N（即截取的串））
Status subString(String S, int l, int length, String N){
    if(l<1 || length<0 || l>S[0]){   //判断要截取子串的长度与位置是否合法
        printf("输入截取信息不合法，无法截取");
        return ERROR;
    }
    int n=1;   //S串当前位置计位器
    N[0] = length;   //截取的串的长度即为指定的长度
    for(int i=l;i<l+length;i++){   //从指定的位置开始直到length个元素后结束
        N[n] = S[i];   //找到指定的截取元素并赋给N
        n++;   //继续向下判断是否也应该截取
    }
    return OK;
}

//子串的定位（查找S串的第l位置后第一次出现L串的位置信息）
int localString(String S, String L, int l){
    if(L[0]>S[0]){   //判断要查找的字串的长度是否合法
        printf("字串过大，定位不合法\n");
        return ERROR;
    }
    String sub;   //定义一个临时的截取片段的串容器
    for(int i=l;i<=S[0]-L[0]+1;i++){   //从指定的位置开始截取直到最后只剩子串L的长度为止
        subString(S,i,L[0],sub);   //从当前位置截取子串长度的子串
        if(compareString(sub, L)==0){   //如果当前截取的字串与指定的字串想等，则返回当前位置
            return i;   //返回当前位置i
        }
    }
    return ERROR;
}

//子串的替换（将串S中出现C字串的地方将C字串替换成R串）
Status replaceString(String S, String C, String R){
    if(isEmpty(C)){   //判断要替换的字串是否为空
        printf("替换的串为空，不合法");
        return ERROR;
    }
    int n=1;   //开始位置标志一下
    int i;   //当前匹配到的C字串在S串的位置信息
    do{
        i = localString(S, C, n);   //从第1个位置开始查找第一次出现C字串的位置信息赋给i
        if(i){   //如果i存在，即查找到了对应的字串位置信息
            deleteString(S, i, C[0]);   //将出现位置开始删除C串长度的串，即将C字串从S串中删除掉
            insertString(S, i, R);   //再将要替换上的字串插入到删除字串的位置
            n+=R[0];   //从查找到的字串后继续开始查找是否还有C字串的存在
        }
    }while(i);   //如果i为0了说明找不到C字串的位置了，即所有C字串已经被替换完成
    return OK;
}

//串的打印
Status printString(String S){
    printf("字符串为：");
    if(S[0]==0){   //判断要打印的字串是否为空，若为空则输出：空
        printf("空\n");
        return OK;
    }
    for(int i=1;i<=S[0];i++){   //从第一个元素的位置开始直到串的最后一个位置结束
        printf("%c", S[i]);   //输出对应位置的元素信息
    }
    printf("\n");
    return OK;
}

//--------------------模式匹配部分-----------------------
//朴素模式匹配(查询S串第l个位置之后串N首次出现的位置）
int normalFind(String S, String N, int l){
    int i = l;   //S的位置计数器 初始从第l个位置开始比较
    int n = 1;   //N串的位置计数器 初始从第一个开始比较
    while(i<=S[0] && n<=N[0]){   //若两个串都还没匹配完毕则继续循环进行，若匹配完毕则推出循环
        if(S[i]==N[n]){   //如果当前串位置的元素等的话就进入
            i++;   //S串位置向下走一格
            n++;   //N串的位置也向下走一格然后继续比较
        }else{
            i = i-n+2;   //若当前位置不一样则重新从S串本次匹配开始的地方的下一个位置为首再进行匹配操作
            n = 1;   //N串还是从第一个位置开始比较
        }
    }
    if(n>N[0]){   //若n的值大于N串的总长度了，说明N串已经全部匹配成功了，则说明找到了对应的N字串
        return i-N[0];   //返回S串当前所在位置减去N串的长度，即回到了开始的位置
    }
    return ERROR;   //如果不是n大于N字串的总长度说明S串全部匹配完也没找到对应的完整N字串的位置，则返回ERROR
}

//普通版KMP算法：
//获取字串的next数组值
Status getNext(String N, int *next){
    int i = 1;   //表示串味指针
    int j = 0;   //表示串头部指针
    next[1] = 0;   //第一个元素前肯定无元素与之匹配，故next数组的第一个值永远为0
    while(i<=N[0]){   //即将N串的元素全部进行操作
        if(j==0 || N[i]==N[j]){
            //如果已经达到表头或者当前所指的元素想等则继续向下走且为next复制
            i++;   //串尾向后走一格
            j++;   //串头向后走一格
            next[i] = j;   //当前next[i]值即为j的长度值
        }else{
            j = next[j];   //如果j！=0并且当前元素也不想等，则回溯到j匹配成功的表头
        }   //next[j]存放的就是j对应位置头部有几个元素是相等的，则直接回溯到相等的元素之后进行匹配就可以了
    }
    return OK;
}

//普通KMP
Status normalKMP(String S, String N, int l){
    int i=l;
    int j=1;
    int next[11];   //定义一个int数组next用来存放字串的next值
    getNext(N, next);   //获取串N的next值
    while(i<=S[0] && j<=N[0]){
        if(S[i] == N[j]){
            i++;
            j++;
        }else{
            j = next[j];  //本质上就这里不相同，若此时元素不想等，则j回溯到next指定的位置（因为这个位置前的都是相等的，不需要再进行比较了
        }
    }
    if(j>N[0]){
        return i-N[0];
    }
    return ERROR;
}

//打印next值
Status printNext(int next[], int length){
    for(int i=1;i<=length;i++){
        printf("%d", next[i]);
    }
    printf("\n");
    return OK;
}

//改良后的KMP算法
//获取nextval值
Status getNextval(String N, int *nextval){
    int i=1;
    int j=0;
    nextval[1] = 0;
    while(i<N[0]){
        if(j==0 || N[i]==N[j]){
            i++;
            j++;
            if(N[i]!=N[j]){   //与求next值只差这一点，为了避免有大量重复的元素同样占用时间，则进行一个新的比较
                nextval[i] = j;   //若当前两值是不想等的话则nextval值就与next值相同
            }else{
                nextval[i] = nextval[j];   //但如果此时位置的元素是相等的话，nextval值就等于next对应的元素位置的值的nextval值想等
            }
        }
        else{
            j = nextval[j];
        }
    }
    return OK;
}

//改进后的KMP算法
Status newKMP(String S, String N, int l){
    int i=l;
    int j=1;
    int nextval[21];
    getNextval(N, nextval);
    while(i<=S[0] && j<=N[0]){
        if(S[i]==N[j]){
            i++;
            j++;
        }else{
            j = nextval[j];  //同普通KMP算法，这里只是更换成了nextval值
        }
    }
    if(j>N[0]){
        return i-N[0];
    }
    return ERROR;
}

//打印nextval值
Status printNextval(int *nextval, int length){
    for(int i=1;i<=length;i++){
        printf("%d", nextval[i]);
    }
    printf("\n");
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    String S1, S2, S3;
    initString(S1, "abcbcf");
    initString(S2, "bc");
    initString(S3, "gg");
    
    printf("S1");
    printString(S1);
    printf("S1的长度为：%d\n", getLength(S1));
    
    printf("S2");
    printString(S2);
    printf("S2的长度为：%d\n", getLength(S2));
    
    printf("S3");
    printString(S3);
    printf("S3的长度为：%d\n", getLength(S3));
    
    printf("将S1中与S2相同的串替换为S3可得S1：\n");
    replaceString(S1, S2, S3);
    printString(S1);
    
    printf("删除S1第一个位置后长度为3的串后得S1：\n");
    deleteString(S1, 1, 3);
    printString(S1);
    
    printf("寻找S1中与S3首个相同的串开始的位置，无则返回0：%d\n", localString(S1, S3, 1));
    
    printf("比较S1与S3，若相同返回0，不同则返回S1-S3的值：%d\n", compareString(S1, S3));
    
    printf("向S2串的第二个位置插入S3串后可得S2串：\n");
    insertString(S2, 2, S3);
    printString(S2);
    
    printf("清除S3串后得S3串为：\n");
    clearString(S3);
    printString(S3);
    
    printf("将S2串复制给S3后可得S3串为：\n");
    copyString(S3, S2);
    printString(S3);
    
    printf("\n-------------以下测试模式匹配算法------------\n");
    printf("初始化两个串S4与S5，他们对应为：\n");
    printf("S4串为：\n");
    String S4,S5;
    initString(S4, "aaaabcdbc");
    initString(S5, "aabcd");
    int *next, *nextval;
    int l = S5[0];
    next = (int*)malloc((l+1)*sizeof(int));
    nextval = (int*)malloc((l+1)*sizeof(int));
    printString(S4);
    printf("S5串为：\n");
    printString(S5);
    printf("根据KMP算法我们可以得到S5对应的next值与nextval值：\n");
    printf("next值：\n");
    getNext(S5, next);
    printNext(next, getLength(S5));
    printf("nextval值：\n");
    getNextval(S5, nextval);
    printNextval(nextval, getLength(S5));
    printf("使用普通匹配算法可得位置为：%d\n", normalFind(S4, S5, 1));
    printf("使用KMS算法可得位置为：%d\n", normalKMP(S4, S5, 1));
    printf("使用改进版KMS算法可得位置为：%d\n", newKMP(S4, S5, 1));
    return 0;
}