sstring.h

数据结构编程---串的知识

    concat(str);
    return *this;
}

SString SString::operator+(SString &str)         //连接串，返回连接起来的新串，重载运算符＋
{                                                //result = *this +str，不改变当前串
    SString result(*this);                       //复制当前串*this
    result += str;
    return result;                               //返回新串，没改变当前串*this
}

bool SString::operator==(char *str)              //比较两个串是否相等，重载运算符==
{
    int i=0;
    while (element[i]!='\0' && str[i]!='0')
        if (element[i]!=str[i])
            return false;
        else
            i++;
    return (element[i]=='\0' && str[i]=='0') ? true : false;
}

bool SString::operator==(SString &str)            //比较两个串是否相等，重载运算符==
{
    return (*this==str.element);                  // 
}


//第8章查找中用
bool SString::operator<(char* str)               //比较两个串的大小，重载运算符<
{
    int i=0;
    while (element[i]!='\0' && str[i]!='0')
        if (element[i]==str[i])
            i++;
        else if (element[i]<str[i])
                 return true;
             else
                 return false;
    return (element[i]=='\0' && str[i]=='0') ? false : true;//算法不完善,不待等长时?"abc"  "abcd"??
    
//    return strcmp(element, str)==-1;
}

bool SString::operator<(SString &str)            //比较两个串的大小，重载运算符<
{
    return (*this < str.element);                  // 
}

//第3章习题
SString::SString(char ch)                        //以字符常量构造串对象
{
    len = 1;
    size = 16;
    element = new char[size];
    element[0] = ch;
    element[1] = '\0';
}

void SString::uppercase()                        //将串中的小写字母转换成大写字母
{
    for (int i=0; i<len; i++)
        if (element[i]>='a' && element[i]<='z')  //小写字母
            element[i] -= 'a'-'A';               //转换成大写字母
}

void SString::trim()                             //删除串对象中的所有空格字符
{
    int i=0, j;
    while (element[i]!=' ' && element[i]!='\0')  //寻找第1个空格
        i++;                                     //i记住第1个空格下标
    for (j=i; element[j]!='\0'; j++)
        if (element[j]!=' ')
            element[i++] = element[j];           //非空格字符向前移动到空格字符位置
    len = i;
    element[len] = '\0';
}

int SString::index(char ch)                      //返回字符ch在当前串中的序号
{
    for (int i=0; i<len; i++)
        if (element[i]==ch)
            return i;
    return -1;
}

//3.3 串的模式匹配

int SString::index(SString pattern)              //返回模式串pattern在串中的首次匹配位置
{                                                //匹配失败时返回－1
    return index(pattern, 0);
}

/*
int SString::index(SString pattern, int start)   //返回模式串pattern在串中从start开始的首次匹配位置
{                                                //匹配失败时返回－1，Brute-Force模式匹配算法
    if (pattern.len>0 && len>=pattern.len)       //当前串较长时进行比较
    {
        int i=start, j=0, count=0;
        while (i<=len-pattern.len && j<pattern.len)   //i表示当前串中某个子串序号
        {
            count++;
            cout<<"\ni="<<i<<"  j="<<j<<"  count="<<count;
            if (element[i+j]==pattern.element[j])     //j为模式串中当前字符序号
                j++;                             //继续比较后续字符
            else
            {
                i++;                             //目标串继续比较下一个子串
                j=0;                             //模式串重新开始
            }
        }
        cout<<"\ncount="<<count<<endl;
        if (j==pattern.len)                      //一次匹配结束，匹配成功
            return i;                            //返回子串序号
    }
    return -1;                                   //匹配失败时返回－1
}
*/

void SString::replace(SString sub, SString replacement)    //替换串中包含的首个sub子串 
{
    int i=index(sub);  
    if (i!=-1)
    {
        remove(i, sub.len);
        insert(i, replacement);
    }
}

void SString::replaceAll(SString sub, SString replacement) //替换串中包含的所有sub子串 
{
    int i=index(sub);
    while (i!=-1)
    {
        remove(i, sub.len);
        insert(i, replacement);
        i=index(sub, i+1);                       //从下一个字符开始再次查找匹配子串
    }
}

void SString::remove(SString sub)                //删除串中包含的首个sub子串
{
    remove(index(sub), sub.len);
}

void SString::removeAll(SString sub)             //删除串中包含的所有sub子串
{
    int i=0;
    do {
        i=index(sub, i);
        remove(i, sub.len);
    } while (i!=-1);
}


int SString::index(SString pattern, int start) //返回模式串pattern从start开始的首次匹配位置
{                                                //匹配失败时返回－1，KMP模式匹配算法
    if (pattern.len>0 && len>=pattern.len)       //当前串较长时进行比较
    {
        int *next = new int[pattern.len];
        pattern.getNext(next);                   //求得模式串的next数组
        cout<<"next[]: ";
        for (int h=0; h<pattern.len; h++)
            cout<<next[h]<<"  ";

        int i=start, j=0;                        //i、j分别为目标串、模式串当前字符序号
        int count=0;                             //记载比较次数
        while (i<len && j<pattern.len) 
        {
            if (j!=-1) count++;
            cout<<"\ni="<<i<<"  j="<<j<<"  count="<<count;
            if (j==-1 || element[i]==pattern.element[j])
            {
                i++;                             //继续比较后续字符
                j++;
            }
            else
                j=next[j];                       //当 时， 继续与 比较
        }
        cout<<"\ncount="<<count<<endl;
        if (j==pattern.len)                      //一趟比较结束，匹配成功
            return i-j;                          //返回匹配的子串序号
    }
    return -1;
}


void SString::getNext(int next[])                //获得模式串pattern改进的next数组
{                                                //当前串*this为pattern
    next[0]=-1;
    int j=0, k=-1;
    while (j<len-1)                              //next数组长度为pattern.len
        if (k==-1 || element[j]==element[k])
        {
            j++;
            k++;
            if (element[j]!=element[k])
                next[j]=k;
            else
                next[j]=next[k];
        }
        else
            k=next[k];
}