字符串

发表于 分类于 阅读次数： 本文字数： 395 阅读时长 ≈ 1 分钟

Data Structures Experiment #6 - 封装字符串类。

  • MyString.h中的private需要添加必要的成员变量。并实现MyString.cpp中的接口方法。

  • MyString::MyString(const char* str);
    构造函数，使用str构造MyString实例。

  • MyString::~MyString();
    析构函数。

  • int MyString::length() const;
    返回储存字符串的长度。

  • void MyString::replace(const char* replace, int loc);
    将字符串中，从loc开始替换为replace。

    例如，假设MyString实例msa储存的字符串为“hello”,执行msa.replace("str", 1)后，msa中储存的字符串变为 “hstr”。

  • int MyString::find(const char* str) const;
    在MyString实例中查找str第一次出现的位置。如果实例中不包含str，则返回-1。注意，需要使用KMP方法实现。
    例如MyString实例msa储存的字符串为“aaabab”， 执行msa.find("ab")返回2。msa.find("abc") 返回-1。

  • const char* MyString::c_string() const;
    返回储存在实例中字符串。

0x00 数据域封装

字符数组及其长度。

1
2
3
private:
    char* myStr;
    int len;

0x01 构造函数

长度即为输入串的长度，对字符指针分配内存并拷贝，末尾加'\0'。

1
2
3
4
5
6
MyString::MyString(const char* str){
    len = strlen(str);
    myStr = new char[len + 1];
    strcpy(myStr, str);
    myStr[len] = '\0';
}

0x02 length

直接返回长度。

1
2
3
int MyString::length() const{
    return len;
}

0x03 replace

如果替换后长度增加，则需要重新分配内存。

再从loc处开始拷贝。

长度改变。

1
2
3
4
5
6
7
8
9
10
11
void MyString::replace(const char* rep, int loc){
    int rLen = strlen(rep);
    if ((loc + rLen) > len) {
        myStr = (char*)realloc(myStr, loc + rLen + 1);
    }
    for (int i = loc; i < loc + rLen; i++)
        myStr[i] = rep[i - loc];
    myStr[loc + rLen] = '\0';

    len = loc + rLen;
}

0x04 find

利用KMP方法。

  • 首先获取next数组：

    子串str自身匹配，求最大匹配数（第12行）。

  • 获取next数组后开始对比：

    myStr串不回溯，每当不匹配时str串索引j回溯到next[j]处。当j == strlen(str)时说明已找到，否则未找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int MyString::find(const char* str) const{
    int next[strlen(str)];
    next[0] = -1;
    int i = 0, j = -1;

    while (i < strlen(str)) {
        if (j == -1 || str[i] == str[j]) {
            i++;
            j++;
            next[i] = j;
        } else
            j = next[j];
    }

    i = 0;
    j = 0;
    while (i < len && (j == -1 || j < strlen(str))) {
        if (j == -1 || myStr[i] == str[j]) {
            i++;
            j++;
        } else
            j = next[j];
    }
    if (j == strlen(str))
        return i - j;
    else
        return -1;
}

0x05 c_string

返回字符数组。

1
2
3
const char* MyString::c_string() const{
    return myStr;
}

0x06 析构函数

释放内存。

1
2
3
4
5
6
7
MyString::~MyString(){
    if (myStr) {
        delete[] myStr;
        myStr = NULL;
    }
    len = 0;
}