C语言顺序串--BF算法

谁践踏了优雅 2022-12-16 13:14 142阅读 0赞

## 数据结构C语言静态顺序串 ##

代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 50 //静态顺序串的最大容纳量 
    
    typedef struct
    { 
        char ch[MAXSIZE];//数据域 
        int length;//串长 
    }SString;
    
    void InitString(SString &S)//初始化串，静态顺序串中，只让串长等于0，便是对串的初始化 
    { 
        S.length = 0;
    }
    
    int StrAssign(SString &S,char chars[])//串的赋值，使数组chars[]中的数据元素填入串S中 
    { 
        int i=0;
        while(chars[i])//利用循环，使对串中的每一个值进行一对一赋值，当chars[i]等于空时，循环结束 
        { 
        	if(i>=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)//打印串 
    { 
        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>MAXSIZE)//判断两个串插入到一个串时是否超出最大值 
        { 
            printf("ERROR!\n");
            return 0;
        }
        if(i<1||i>S.length+1)//判断插入位置i是否合理 
        { 
            printf("ERROR!\n");
            return 0;
        }
        SString 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;
    }
    
    int BF(SString S,SString T)//求子串在主串的位置 ，BF算法 
    { 
        int i=1,
            j=1;//初始化 
        while(i<=S.length&&j<=T.length)//两个串均为比较到串尾 
        { 
            if(S.ch[i]!=T.ch[j])//指针后退重新开始匹配 
            { 
                i = i-j+2;
                j = 1;
            }
            else//继续比较后继字符 
            { 
                j++;
                i++;
            }
        }
        if(j<=T.length)//匹配失败 
            return 0;
        return i-j+1;//匹配成功，并返回其值 
    }
    
    int main()
    { 
        char a[] = "jdigohsdiogha";
        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的大小 
        StrInset(S,T,8);	//使串T插入到串S的第i个位置 
        OutputStr(S);	
        StrDelete(S,14,6);	//删除串S的从第i个位置开始长度为len的子串 
        OutputStr(S);
        printf("%d\n",BF(S,T));	//查找子串位置，输出的是子串T在主串S中的位置 
        return 0;
    }

（完）