sstring.h

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

//字符串类

#include <iostream.h>
#include <string.h>

class SString                                    //字符串类
{
  private:
    char *element;                               //动态字符数组
    int size;                                    //数组容量
    int len;                                     //串长度

    void init(char *str="", int size=64);        //初始化指定容量的串对象
  public:
    SString(char *str="");                       //以字符串常量构造串对象
    SString(int size);                           //构造指定容量的空串对象
    SString(SString &str);                       //拷贝构造函数，由已知串构造新串，串复制
    ~SString();                                  //析构函数

    int length();                                //返回串长度
    char charAt(int i);                          //返回第i（i≥0）个字符
    bool setCharAt(int i, char ch);              //设置第i个字符为ch
    SString substring(int i, int n);             //返回从第i个字符开始长度为n的子串
    SString substring(int i);                    //返回从第i个字符开始至串尾的子串
    void insert(int i, char *str);               //在第i个字符处插入字符串常量str
    void insert(int i, SString &str);            //在第i个字符处插入串str
    void concat(SString &str);                   //在当前串之后连接串str
    bool remove(int i, int n);                   //删除从第i个字符开始长度为n的子串
    bool remove(int i);                          //删除从第i个字符开始至串尾的子串

    friend ostream& operator<<(ostream& out, SString &s);  //输出串，重载输出流运算符<<
    SString& operator=(SString &str);            //赋值，串复制功能，重载运算符=
    SString& operator+=(SString &str);           //连接串，在当前串之后连接串str，重载运算符＋=
    SString operator+(SString &str);             //连接串，返回连接起来的新串，重载运算符＋
    bool operator==(char *str);                  //比较两个串是否相等，重载运算符==
    bool operator==(SString &str);
    bool operator<(char* str);                   //比较两个串的大小，重载运算符<
    bool operator<(SString &str);

    int index(SString pattern);                  //返回模式串pattern在串中的首次匹配位置
    int index(SString pattern, int start);       //返回pattern从start开始的首次匹配位置
    void replace(SString sub, SString replacement);    //替换串中包含的首个sub子串 
    void replaceAll(SString sub, SString replacement); //替换串中包含的所有sub子串 
    void remove(SString sub);                    //删除串中包含的首个sub子串
    void removeAll(SString sub);                 //删除串中包含的所有sub子串

//第3章习题
    SString(char ch);                            //以字符常量构造串对象
    void uppercase();                            //将串中的小写字母转换成大写字母
    void trim();                                 //删除串所有空格
    int index(char ch);                          //返回字符ch在当前串中的序号

  private:
    void getNext(int next[]);                    //返回模式串pattern改进的next数组

};

void SString::init(char *str, int size)          //构造指定容量的空串对象
{
    int i=0;
    while (str[i]!='\0')
       i++;
    len = i;                                     //获得字符串str长度
    size = size>len ? size : len;                //参数size获得size与len的较大值
    this->size = size<64 ? 64 : size;            //指定成员变量size值，最小为64
    element = new char[this->size];
    for (i=0; str[i]!='\0'; i++)                 //复制字符串str
       element[i]=str[i]; 
    element[i] = '\0'; 
}

SString::SString(int size)                       //构造指定容量的空串对象
{
    init("", size);
}

SString::SString(char *str)                      //以字符串常量构造串对象
{
    init(str);
}

SString::SString(SString &str)                   //拷贝构造函数，由已知串构造新串，串复制
{
    init(str.element);
}

SString::~SString()                              //析构函数
{
    delete[] element;
}

int SString::length()                            //返回字符串长度
{
    return len;
}

char SString::charAt(int i)                      //返回第i（i≥0）个字符
{
    if (i>=0 && i<len)
        return element[i];
    throw "字符序号越界异常";                    //抛出异常，程序运行非正常终止
}

bool SString::setCharAt(int i, char ch)          //设置第i个字符为ch
{                                                //操作成功返回true，若i指定序号无效返回false
    if (i>=0 && i<len)
    {
        element[i] = ch;
        return true;
    }
    return false;
}

ostream& operator<<(ostream& out, SString &str)  //输出串，重载输出流运算符<<
{
    out<<"\""<<str.element<<"\""; 
    return out;
}

//【例3.1】  判断标识符。

SString SString::substring(int i, int n)         //返回从第i个字符开始长度为n的子串
{
    if (len==0 || i<0 || i>=len || n<=0)         //空串、指定字符序号错误或所求子串长度非正数
    {
        SString sub; 
        return sub;                              //返回空串
    }
    if (n>len-i)                                 //子串长度容错
        n=len-i;
    SString sub(n);                              //创建指定容量的空串对象
    for (int j=0; j<n; j++)
        sub.element[j] = this->element[i+j];
    sub.element[n]='\0';
    sub.len=n;
    return sub;                                  //返回局部变量sub的复制对象
}

SString SString::substring(int i)                //返回从第i个字符开始至串尾的子串
{
    return substring(i, len-i+1);
}

void SString::insert(int i, char *str)           //在第i个字符处插入字符串常量str
{
    int n=strlen(str), j;
    if (n==0)  return;
    if (i<0)  i=0;                               //序号容错
    if (i>len) i=len;
    char *p=element;
    if (size-len<=n)                             //若当前串的字符数组空间不足，则扩充容量
    {
//        cout<<"  len="<<len<<"  size="<<size<<"  n="<<n<<endl;
        size = (len+n+1)*2;
        element = new char[size];                //重新申请字符数组空间
        for (j=0; j<i; j++)                      //复制当前串前i-1个字符
            element[j] = p[j];
    }
    for (j=len; j>=i; j--)                //从i开始至串尾的子串（包括'\0'）向后移动n个字符
        element[j+n] = p[j];
    if (p!=element)                              //若扩充容量，则释放原数组空间
        delete[] p;
    for (j=0; j<n; j++)                          //插入str串
        element[i+j] = str[j];
    len+=n;
}

void SString::insert(int i, SString &str)        //在第i个字符处插入串str
{
    insert(i, str.element);
}

void SString::concat(SString &str)               //在当前串最后插入串str
{
    insert(len, str.element);
}

//【例3.2】  串的逆转。

bool SString::remove(int i, int n)               //删除从第i个字符开始长度为n的子串
{
    if (len==0 || i<0 || i>=len || n<=0)
        return false;
    if (n>len-i)                                 //子串长度容错
        n=len-i;
    for (int j=i+n; j<=len; j++)                 //从i+n开始至串尾的子串（包括'\0'）向前移动n个字符
        element[j-n] = element[j];
    len -= n;
    return true;
}

bool SString::remove(int i)                      //删除从第i个字符开始至串尾的子串
{
    return remove(i, len-i);
}

SString& SString::operator=(SString &str)        //赋值，串复制功能，重载运算符=
{
    len=0;                                       //令当前串为空
    concat(str);
    return *this;
}

SString& SString::operator+=(SString &str)       //连接串，在当前串之后连接str，重载运算符＋=
{                                                //*this += str，改变当前串