C语言动态顺序串实现--KMP算法

秒速五厘米 2022-12-16 13:15 183阅读 0赞

数据结构C语言动态顺序串，相比于静态顺序串只是多了能增加最大容纳量函数的操作。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define StrSize 20 //动态顺序串当前最大长度 
    
    typedef struct
    { 
        char *ch;//数据域 
        int length;//串长 
        int MaxSize;//最大容量 
    }SString;
    
    void InitString(SString &S)//初始化串
    { 
        S.ch = (char *)malloc(sizeof(char )*StrSize+1);//申请一个长度为StrSize+1的连续空间 
        if(S.ch == NULL)//判断是否分配到 
            printf("EROOR!\n");
        else
        { 
            S.length = 0;//串长为0 
            S.MaxSize = StrSize;//最大容纳量为当前最大长度 
        }
    }
    
    int StrAssign(SString &S,char chars[])//串的赋值，使数组chars[]中的数据元素填入串S中 
    { 
        int i=0;
        while(chars[i])//利用循环，使对串中的每一个值进行一对一赋值，当chars[i]等于空时，循环结束
        { 
            if(i>=S.MaxSize)//如果超出最大容纳量，跳出循环 
            { 
                printf("ERROR!\n");
                    break;
            }
            S.ch[i+1] = chars[i];//串的存储是从1开始的，而数组元素的存储是从0开始的
            i++;
        }
        S.length = i;//长度便是i 
        return 0;
    }
    
    int IsEmpty(SString S)//判断串是否为空，如果为空返回1，否则返回0 
    { 
        if(S.length)
            return 0;
        return 1;
    }
    
    void OutputStr(SString S)//打印串 
    { 
    	if(IsEmpty(S))//判断是否为空串 
    	{ 
    		printf("ERROR!\n");
    		exit(1);
    	}
        int i;
        for(i=1;i<=S.length;i++)//利用循环一个一个输出，串时从1开始的 
            printf("%c ",S.ch[i]);
        printf("\n");
    }
    
    int Strcopy(SString &T,SString S)//串S的copy(复制)，使串S中的数据复制到串T中
    { 
        if(IsEmpty(T)==0)//判断串T是否为空 
        { 
            printf("ERROR!\n");//如果非空，结束此函数，并打印ERROR
            return 0;
        }
        int i;
        for(i=1;i<=S.length;i++)//利用循环对空串T赋值
        { 
            T.ch[i] = S.ch[i];
        }
        T.length = S.length;//因为是拷贝，所以串T长度等于串S长 
        return 0;
    }
    
    int StrCompare(SString S,SString T)//比较串S和串T的大小，
    { 
        int i;
        for(i=1;i<=S.length&&i<=T.length;i++)//利用循环找出 从第一个元素开始，出现不相同元素的位置 ，循环终止条件是出现一个串比较到最后，
            if(S.ch[i] != T.ch[i])
                return S.ch[i]-T.ch[i];//出现不同位置，直接返回其相减的值，其值时ASCII码对应数相减 
        return S.length - T.length;//如果没出现，直接输出串长相减
    }
    
    int SubString(SString &T,SString S,int i,int len)//求子串
    { 
    	if(IsEmpty(T)==0)//判断串T是否为空 
        { 
            printf("ERROR!\n");//如果非空，结束此函数，并打印ERROR 
            return 0;
        }
        if(i<1||i>S.length)//判断位置是否错误 
        { 
            printf("位置错误！\n");
            return 0;
        }
        if(i+len > S.length+1)//判断所求子串是否在串S的范围内 
        { 
            printf("ERROR!\n");
            return 0;
        }
        int j=1,a=i;
        for( ;i<a+len;i++)//利用循环赋值 
        { 
            T.ch[j] = S.ch[i];
            j++;
        }
        T.length = len;//子串长为len 
        return 0;
    }
    
    int StrInset(SString &S,SString T,int i)//串的插入，使串T插入到串S的第i个位置 
    { 
        if(S.length+T.length>S.MaxSize)//判断两个串插入到一个串时是否超出最大值
        { 
            printf("ERROR!\n");
            return 0;
        }
        if(i<1||i>S.length+1)//判断插入位置i是否合理 
        { 
            printf("ERROR!\n");
            return 0;
        }
        SString L;
        InitString(L);//重新申请一个串 
        L.length = S.length+T.length;//使串S和串T都插入到重新申请的串L中 
        int j=1;
        for( ;j<i;j++)//在串S的第i位之前的数据导入串L 
            L.ch[j] = S.ch[j];
        for( j=1;j<=T.length;j++)//串L第i位开始，导入串T 
            L.ch[i+j-1] = T.ch[j];
        for( j=i+T.length;j<=L.length;j++)//使未导入串L的串S剩余部分导入
            L.ch[j] = S.ch[j-T.length];
        S = L;//输出S
        return 0;
    }
    
    int StrDelete(SString &S,int i,int len)//串S的删除，删除串S从第i位开始长度为len的子串，并返回S 
    { 
        if(i<1||i>S.length)//判断删除位置i是否合理 
        { 
            printf("ERROR!\n");
            return 0;
        }
        if(i+len>S.length+1)//判断所删除子串是否在串S的范围内
        { 
            printf("ERROR!\n");
            return 0;
        }
        for( ;i<S.length-len+1;i++)
            S.ch[i] = S.ch[i+len];
        S.length = S.length-len;//长度变为删除之后的长度 
        return 0;
    }
    
    void Nextval(SString T,int nextval[])//求nextval值函数 
    { 
        int i=1,j=0;
        nextval[1]=0;
        while(i<T.length)
        { 
            if(j==0||T.ch[i]==T.ch[j])
            { 
                i++;
                j++;
                if(T.ch[i]!=T.ch[j])
                    nextval[i] = j;
                else
                    nextval[i] = nextval[j];
            }
            else
                j = nextval[j];
        }
    }
    
    int KMP(SString S,SString T)//求子串位置，KMP算法 
    { 
        int i=1,
            j=1;//初始化 
        int nextval[T.length+1];//nextval数组是从1开始存数的，所以长度加1 
        Nextval(T,nextval);//调用 next函数修正值函数 
        while(i<=S.length&&j<=T.length)//两个串均为比较到串尾 
        { 
            if(S.ch[i]!=T.ch[j])//指针后退重新开始匹配 
            { 
                if(j == 1)//避开死循环 
                    i++;
                else
                    j = nextval[j];
            }
            else//继续比较后继字符
            { 
                j++;
                i++;
            }
        }
        if(j<=T.length)//匹配失败 
            return 0;
        return i-j+1;//匹配成功，并返回其值 
    }
    
    int IncreaseStr(SString &S,int len)//增加串的最大容纳量，使其增大len（和静态顺序串的唯一区别） 
    { 
        int i,
            a = S.length;//使串S的长度固定为a 
        char* p;//创建一个指针 
        p = S.ch;//使其指向串S的基地址 
        S.ch = (char*)malloc(sizeof(char)*(StrSize+len+1));//重新对串S进行初始化，并使申请的空间变大 
        S.MaxSize = StrSize+len;//最大容纳量增加 
        S.length = a;//使串S的长度回到最开始的长度 
        for(i=1;i<=a;i++)//利用循环使旧的串中的数据赋值给新串中 
            S.ch[i] = p[i];
        free(p); //释放旧串的空间 
        return 0;
    }
    
    int main()
    { 
        char a[] = "jdigohsdiofghhsa";
        char b[] = "gohsdi";	//定义数组a[],b[],并赋值 
        SString S;
        SString T;	//创建串T和串S 
        InitString(S);
        InitString(T);	//初始化串T和串S
        StrAssign(S,a);	//使数组a[]中的数据填入串s中 
        StrAssign(T,b);	//使数组b[]中的数据填入串T中 
        OutputStr(S);	//打印串S
        //Strcopy(T,S); //使串S中的数据填入空串T中 
        //SubString(T,S,10,4); //使串S中从第i个位置开始长度为len的子串，填入到空串T中 
        OutputStr(T);	//打印串T
        printf("%d\n",StrCompare(S,T));	//比较串T和串S的大小
        IncreaseStr(S,19);	//增加串S的最大容量，增加了len 
        StrInset(S,T,8);	//使串T插入到串S的第i个位置 
        OutputStr(S);
        StrDelete(S,14,6);	//删除串S的从第i个位置开始长度为len的子串
        OutputStr(S);
        printf("%d\n",KMP(S,T));	//查找子串位置，输出的是子串T在主串S中的位置
        free(S.ch);//释放空间 
        return 0;
    }

（完）