数据结构——C语言实现String字符串操作

#include 
#include 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
#define Status int
typedef char * string;
 
//返回串s的元素个数，即串的长度
int StrLength(string s){
    if(s != NULL){
        int i = 0;
        while(s[i] != '\0'){
            i++;
        }
        return i;
    }
    return 0;
}
 
//生成一个其值等于字符串常量s的串t
Status StrAssign(string *t,string s){
    int len = StrLength(s);
    if(len > 0){
        *t = (char *)malloc(sizeof(char)*len);
        int i = 0;
        while(i < len){
            (*t)[i] = s[i];
            i++;
        }
        (*t)[i] = '\0';
    }
    return ERROR;
}
 
//串s存在，由串s复制得串t
Status StrCopy(string *t, string s){
    *t = s;
    return OK;
}
 
//串s存在，将串清空
Status ClearString(string *s){
    if(s){
        free(*s);//释放后变成野指针，必须置为空指针
        *s = NULL;
    }
    return OK;
}
 
//若串s为空，返回true,否则返回false
Status StringEmpty(string s){
    if(s){
        return FALSE;
    }
    return TRUE;
}
 
//若s>t,返回值>0,若s=t,返回0，若s
int StrCompare(string s,string t){
    int len_s = StrLength(s);
    int len_t = StrLength(t);
    int i = 0;
    while(i < len_s && i < len_t){
        if(s[i] == t[i]){
            i++;
        }else{
            return s[i] - t[i];
        }
    }
    return len_s - len_t;
}
 
//用t返回由s1和s2连接而成的新串
Status StrConcat(string *t,string s1,string s2){
    int len_s1 = StrLength(s1);
    int len_s2 = StrLength(s2);
    int len_t = len_s1 + len_s2;
    
    *t = (string)malloc(sizeof(char)*len_t);
    int i = 0;
    int j = 0;
    int k = 0;
    while(i < len_s1){
        (*t)[k++] = s1[i++];
    }
    while(j < len_s2){
        (*t)[k++] = s2[j++];
    }
    (*t)[k] = '\0';
    return OK;
}
 
//串s存在，1 <= pos <= strlength(s),且 0 <= len <= Strlength(s) - pos + 1,用sub返回串S的第pos个字符起长度为len的子串
Status SubString(string *sub,string s,int pos,int len){
    *sub = (char *)malloc(sizeof(char) * (len + 1));
    int i = 0;
    while( i < len && s[i + pos - 1] != '\0'){
        (*sub)[i] = s[i + pos - 1];
        i++;
    }
    (*sub)[i] = '\0';
    return OK;
}
 
//串t,s存在，t是非空串，1<=pos<=strlength(s).
//若主串s中存在和串t值相同的子串，则返回它在主串s中第pos个字符之后第一次出现的位置，否则返回0
int Index(string s,string t,int pos){
    //朴素模式匹配算法
    int i = pos;
    int j = 0;
    int k = 0;
    while(s[i] != '\0'){
        k = i;
        j = 0;
        while(s[k] != '\0' && t[j] != '\0'){
            if(s[k] != t[j]){
                break;
            }
            j++;
            k++;
        }
        if(t[j] == '\0'){
            return i;
        }
        i++;
    }
    return -1;
}
void GetNextVal(string t,int *nextval){
    int i,j;
    i = 1;
    j = 0;
    int len = 0;
    nextval[1] = 0;
    while(t[len] != '\0'){
        len++;
    }
    while(i < len){
        if(j == 0 || t[i] == t[j]){
            i++;
            j++;
            if(t[i] != t[j]){
                nextval[i] = j;
            }else{
                nextval[i] = nextval[j];
            }
        }else{
            j = nextval[j];
        }
    }
}
//获取next数组
void GetNext(string t,int *next){
    int len = 0;
    int j = 0;
    int i = 1;
    next[1] = 0;
    while(t[len] != '\0'){
        len++;
    }
    while(j < len){
        if(j == 0 || t[i] == t[j]){
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}
int IndexKMP(string s,string t,int pos){
    int i = pos;
    int j = 1;
    int next[255];
    GetNext(t,next);
    int lens = 0;
    int lent = 0;
    while(s[lens] != '\0' && t[lent] != '\0'){
        lens++;
        lent++;
    }
    while(s[lens] != '\0'){
        lens++;
    }
    while(i <= lens && j <= lent){
        if(j == 0 || s[i] == t[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j > lent){
        return i - lent - 1;
    }else{
        return -1;
    }
}
 
//串s,t和v存在，t是非空串。用v替换主串s中出现的所有与t相等的不重叠的子串
string Replace(string s,string t,string v){
    int i = 0;
    int j = 0;
    int k = 0;
    int index = Index(s,t,0);
    if(index < 0){
        return ERROR;
    }
    int lens = StrLength(s);
    int lent = StrLength(t);
    int lenv = StrLength(v);
    char *newS = (char *)malloc(sizeof(char) * (lens + lenv - lent));
    while(i < index){
        newS[k] = s[i];
        i++;
        k++;
    }
    while(j < lenv){
        newS[k] = v[j];
        j++;
        k++;
    }
    for(i = index + lent; i < lens; i++){
        newS[k] = s[i];
        k++;
    }
 
    return newS;
}
 
//串s,t存在，1<=pos<=strlength(s) + 1,在串s的第pos个字符之前插入串t
string StrInsert(string s,int pos,string t){
    int lens = StrLength(s);
    int lent = StrLength(t);
    int i = 0;
    int j = 0;
    int k = 0;
    int index = pos - 1;
    string res = (char *)malloc(sizeof(char) * (lens + lent));
    while(k < index){
        res[i] = s[k];
        i++;
        k++;
    }
    while(j < lent){
        res[i] = t[j];
        j++;
        i++;
    }
    for(k = index;k < lens;k++){
        res[i] = s[k];
        i++;
    }
    res[i] = '\0';
    return res;
}
 
//串s存在，1<=pos<=strlength(s) - len + 1.从串s中删除第pos个字符起长度为len的子串
string StrDelete(string s,int pos, int len){
    int lent = StrLength(s);
    if(len > lent - pos || len <= 0){
        return NULL;
    }
    string res = (char *)malloc(sizeof(char) * (lent - len));
    int i = 0;
    int k = 0;
    while(i < pos){
        res[k] = s[i];
        i++;
        k++;
    }
    for(i = pos + len ; i < lent; i++){
        res[k] = s[i];
        k++;
    }
    res[k] = '\0';
    return res;
}
 
int main(){
    string t = NULL;
 
    string s = "I like DataStructure very much!!!";//字符串常量
    StrAssign(&t,"I like DataStructure very much!!!");
    printf("t = %s\n",t);
    t[0] = 'a';
    printf("t = %s\n",t);
 
    printf("len = %d\n",StrLength(s));
 
    ClearString(&t);
    printf("t = %s\n",t);
 
    StrCopy(&t,s);
    printf("t = %s\n",t);
 
    printf("result = %d\n",StringEmpty(t));
    t = NULL;
    printf("result = %d\n",StringEmpty(t));
 
    t = "hello";
    s = ",world.";
    printf("s - t = %d\n",StrCompare(s,t));
 
    string s_new;
    StrConcat(&s_new,t,s);
    printf("_msize = %d\n",_msize(s_new));
    printf("%s\n",s_new);
 
 
    string sub;
    string ss = "hello,world.";
    SubString(&sub,ss,3,110);
    printf("sub = %s\n",sub);
 
    string t_new = "rl.";
    int i = Index(ss,t_new,0);
    printf("i = %d\n",i);
 
    string sss= "www.hello.world";
    string ttt = "hello";
    string newsss = Replace(sss,ttt,"aa");
    printf("newsss = %s\n",newsss);
 
    string res = StrInsert(sss,2,ttt);
    printf("res = %s \n",res);
    
    printf("res = %s\n",StrDelete(sss,3,2));
    return 0;
}