跳转至

5、字符串详解

1、字符数组和字符串简介

C++ 中的字符串和字符数组都可以用来存储一系列字符，但是它们在实现、使用上有一些不同。

字符数组是一个固定长度的数组，其中每个元素都是一个字符。例如，下面的语句定义了一个包含 10 个字符的字符数组：

C++
1
char myCharArray[10];

要访问该字符数组中的特定字符，可以使用该字符在数组中的索引，如下所示：

C++
1
2
3
4
5
myCharArray[0] = 'H';
myCharArray[1] = 'e';
myCharArray[2] = 'l';
myCharArray[3] = 'l';
myCharArray[4] = 'o';

字符串则是由多个字符组成的序列，可以动态地增长或缩小。C++ 中有两种表示字符串的方式：使用字符数组或使用标准库提供的 string 类型。

使用字符数组表示字符串时，需要在末尾添加一个空字符 '\0' 来表示字符串的结束。例如，下面的语句定义并初始化了一个包含 "Hello" 的字符串：

C++
1
char myString[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

也可以使用如下简化的方式来初始化：

C++
1
char myString[] = "Hello";

要访问该字符串中的特定字符，可以像访问字符数组一样使用索引：

C++
1
myString[0] = 'J';

但需要注意的是，不能直接将一个字符数组赋值给另一个字符数组来进行字符串之间的赋值。

相比之下，使用 string 类型表示字符串时，可以更方便地进行字符串操作。例如，以下语句创建了一个包含 "Hello" 的字符串：

C++
1
string myString = "Hello";

要访问该字符串中的特定字符，可以像使用数组一样使用索引：

C++
1
myString[0] = 'J';

也可以使用 string 类型提供的函数来进行字符串操作，如下所示：

C++
1
2
myString.append(" World");
myString.replace(0, 1, "j");

总体来说，字符数组和字符串都有其各自的优点和应用场景。对于需要固定长度且性能要求较高的场景，建议使用字符数组；对于动态长度且需要灵活操作的场景，则可以使用 string 类型。

2、字符数组和字符串的常见操作

C++ 中的字符数组和字符串都有许多常用的方法，可以方便地对它们进行各种操作。

下面是一些常用的字符数组方法：

  • strlen(str)：返回字符数组 str 的长度（不包括末尾的空字符 '\0'）。
  • strcpy(dest, src)：将字符数组 src 复制到字符数组 dest 中。
  • strcat(dest, src)：将字符数组 src 拼接到字符数组 dest 的末尾。
  • strcmp(str1, str2)：比较字符数组 str1 和 str2 的大小。如果 str1 大于 str2，则返回一个正整数；如果 str1 等于 str2，则返回 0；如果 str1 小于 str2，则返回一个负整数。

下面是一些常用的字符串方法（其中 str 可以是字符数组或 string 类型）：

  • size() 或 length()：返回字符串的长度。
  • empty()：判断字符串是否为空字符串。
  • clear()：清空字符串中的内容。
  • append(str) 或 push_back©：将字符串 str 或字符 c 添加到字符串末尾。
  • insert(pos, str) 或 insert(pos, c)：在字符串指定位置 pos 插入字符串 str 或字符 c。
  • replace(pos, len, str) 或 replace(pos, len, c)：将从字符串位置 pos 开始的 len 个字符替换为字符串 str 或字符 c。
  • substr(pos, len)：返回从字符串位置 pos 开始的长度为 len 的子字符串。
  • find(str)：查找字符串 str 在当前字符串中出现的位置，返回该位置的索引值。如果找不到，则返回 string::npos。

除此之外，字符数组和字符串还支持类似数组的索引操作和迭代器操作，可以方便地遍历其中的元素。需要注意的是，在使用字符数组时，应该尽量避免越界访问和缺少空字符 '\0' 的情况。

3、字符数组和字符串的输入和输出

在 C++ 中，可以使用输入输出流和标准库中的一些函数来对字符数组和字符串进行输入和输出操作。

对于字符数组，可以使用以下方式进行输出：

C++
1
2
char myCharArray[] = "Hello";
cout << myCharArray;  // 输出 Hello

需要注意的是，如果字符数组中没有以空字符 '\0' 结尾，则可能会导致输出不完整或错误。

对于字符串，也可以使用类似的方式进行输出：

C++
1
2
string myString = "Hello";
cout << myString;  // 输出 Hello

除了输出外，还可以使用输入流来读取用户输入的字符数组或字符串。例如，下面的代码通过 cin 从控制台读取用户输入的字符串：

C++
1
2
string inputString;
cin >> inputString;  // 从控制台读取字符串

需要注意的是，上述读取操作会在遇到空格、换行符等空白字符时停止读取，因此通常只能读取单个单词或连续的字符序列。如果需要读取包含空格等特殊字符的完整字符串，可以使用 getline 函数：

C++
1
2
string inputString;
getline(cin, inputString);  // 从控制台读取一行字符串
  • 除了标准输入输出流之外，C++ 还提供了一些与字符数组和字符串相关的函数，例如 sscanf 和 sprintf 函数，可以将格式化的字符串转换为字符数组或字符串。例如，下面的代码使用 sprintf 函数将一个整数转换为字符串：
C++
1
2
3
int num = 123;
char str[10];
sprintf(str, "%d", num);  // 将 num 转换为字符串

需要注意的是，sscanf 和 sprintf 等函数对于输入输出格式的控制较为灵活，但也容易引入各种安全隐患和错误，因此使用时应该谨慎。

4、字符串的相关算法介绍

在 C++ 中，标准库提供了一些可以对字符串进行各种操作的函数和算法。以下是一些常用的字符串算法：

1.find

find 函数可以在一个字符串中查找指定字符或子字符串，并返回其出现位置的迭代器。例如，以下代码使用 find 查找字符 'o' 在字符串中出现的位置：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    auto it = find(str.begin(), str.end(), 'o');  // 查找字符 'o'
    if (it != str.end()) {
        cout << "Found at position " << it - str.begin() << endl;
    }
    return 0;
}

输出为 "Found at position 4"，表示字符 'o' 在字符串中第五个位置（从 0 开始计数）。

2.replace

replace 函数可以将字符串中所有指定的字符替换为另一个字符。例如，以下代码使用 replace 将所有小写字母替换为大写字母：

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    replace(str.begin(), str.end(), 'l', 'L');  // 将字符 'l' 替换为 'L'
    cout << str << endl;  // 输出 HELLo, worLd!
    return 0;
}

3.sort

sort 函数可以按照指定的顺序对字符串进行排序。例如，以下代码使用 sort 将字符串按照字典序排序：

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    sort(str.begin(), str.end());  // 按照字典序排序
    cout << str << endl;  // 输出 " !,HWdellloor"
    return 0;
}

需要注意的是，sort 函数默认按照字符的 ASCII 码值进行排序。

4.reverse

reverse 函数可以将字符串中的字符反转顺序。例如，以下代码使用 reverse 反转字符串：

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    reverse(str.begin(), str.end());  // 反转字符串
    cout << str << endl;  // 输出 "!dlrow ,olleH"
    return 0;
}

5.count

count 函数可以统计一个字符串中指定字符或子字符串出现的次数。例如，以下代码使用 count 统计字符 'l' 在字符串中出现的次数：

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    int count = count(str.begin(), str.end(), 'l');  // 统计字符 'l' 的出现次数
    cout << "The character 'l' appears " << count << " times." << endl;
    return 0;
}

6.tolower 和 toupper

tolower 和 toupper 函数分别将一个字符转换为小写或大写形式。例如，以下代码将字符串中所有字符都转换为小写形式：

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <string>

int main() {
    string str = "Hello, world!";
    transform(str.begin(), str.end(), str.begin(), ::tolower);  // 将所有字符转换为小写
    cout << str << endl;  // 输出 hello, world!
    return 0;
}

7.stoi 和 stod

stoi 和 stod 函数可以将一个字符串转换为整数或浮点数类型。例如，以下代码将一个字符串转换为整数：

C++
1
2
3
4
5
6
7
8
#include <string>

int main() {
    string str = "123";
    int num = stoi(str);  // 将字符串转换为整数
    cout << num << endl;  // 输出 123
    return 0;
}

8.to_string

to_string 函数可以将一个数值类型转换为字符串类型。例如，以下代码将一个整数转换为字符串：

C++
1
2
3
4
5
6
7
8
#include <string>

int main() {
    int num = 123;
    string str = to_string(num);  // 将整数转换为字符串
    cout << str << endl;  // 输出 "123"
    return 0;
}

9.getline

getline 函数可以从输入流中读取一行字符串。例如，以下代码从标准输入流中读取一行字符串：

C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <string>

int main() {
    string str;
    getline(cin, str);  // 从输入流中读取一行字符串
    cout << str << endl;  // 输出读取到的字符串
    return 0;
}

需要注意的是，在使用 getline 函数时，可以指定分隔符（默认为换行符），以便在读取字符串时进行分割。

以上只是一些常见的字符串处理函数和算法，C++ 标准库中还有许多其他的字符串处理函数和算法，可以根据需要选择使用。

5、字符串查找的相关算法

在字符串中进行查找操作是一种常见的字符串处理需求，以下是一些常用的字符串查找算法：

1.Brute-Force 算法

Brute-Force 算法（暴力匹配算法）是一种简单直接的字符串查找算法，它的基本思想是从文本串的第一个字符开始和模式串逐个字符比较，如果匹配则继续比较下一个字符，否则从文本串的下一个位置重新开始匹配。

Brute-Force 算法的时间复杂度为 O(mn)，其中 m 和n 分别表示模式串和文本串的长度。虽然 Brute-Force 算法的时间复杂度比较高，但是它的实现简单易懂，对于小规模的字符串匹配问题可以考虑使用。

以下是 Brute-Force 算法的 C++ 实现代码：

C++
 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
29
30
31
32
33
34
35
#include <iostream>
#include <string>
using namespace std;

// Brute-Force 算法实现字符串查找
int brute_force(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    for (int i = 0; i <= n - m; ++i) {  // i 表示文本串中当前比较的位置
        bool match = true;
        for (int j = 0; j < m; ++j) {  // j 表示模式串中当前比较的位置
            if (text[i+j] != pattern[j]) {  // 如果当前字符不匹配，则退出循环
                match = false;
                break;
            }
        }
        if (match) {  // 如果匹配成功，则返回起始位置
            return i;
        }
    }
    return -1;  // 如果没有找到，则返回 -1
}

// 测试代码
int main() {
    string text = "hello, world!";
    string pattern = "world";
    int pos = brute_force(text, pattern);
    if (pos == -1) {
        cout << "Pattern not found." << endl;
    } else {
        cout << "Pattern found at position " << pos << "." << endl;
    }
    return 0;
}

在上述代码中，Brute-Force 算法的主要思想就是从文本串的第一个字符开始和模式串逐个字符比较，如果匹配则继续比较下一个字符，否则从文本串的下一个位置重新开始匹配。具体实现过程中，我们通过两个嵌套的循环分别遍历了文本串和模式串，如果发现有不匹配的情况，则直接退出内层循环，继续从下一个位置开始匹配。

需要注意的是，在循环的判断条件中，我们将 i 的范围控制在了 n-m 的区间内，因为当文本串中剩余长度不足以匹配整个模式串时，就可以直接退出循环。另外，在匹配成功时，我们返回的是起始位置 i，而不是结束位置 i+m-1，这也是 Brute-Force 算法的一种常见实现方式。

2.KMP 算法

KMP 算法（Knuth-Morris-Pratt 算法）是一种更高效的字符串查找算法，它利用了已知信息来避免在模式串和文本串的匹配过程中出现重复的比较，从而达到提高效率的目的。

KMP 算法的时间复杂度为O(m+n)，其中 m 和 n 分别表示模式串和文本串的长度。虽然 KMP 算法的实现比 Brute-Force 算法稍微复杂一些，但是它的时间复杂度更低，在实际应用中更为常用。

以下是 KMP 算法的 C++ 实现代码及注释：

C++
 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 计算模式串的前缀函数（Partial Match Table）
vector<int> compute_prefix(const string& pattern) {
    int m = pattern.length();
    vector<int> pi(m);
    pi[0] = 0;
    int k = 0;
    for (int i = 1; i < m; ++i) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = pi[k-1];
        }
        if (pattern[k] == pattern[i]) {
            ++k;
        }
        pi[i] = k;
    }
    return pi;
}

// KMP 算法实现字符串查找
int kmp(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> pi = compute_prefix(pattern);  // 计算模式串的前缀函数
    int q = 0;  // 表示已经匹配成功的字符数
    for (int i = 0; i < n; ++i) {
        while (q > 0 && pattern[q] != text[i]) {  // 不匹配则回退
            q = pi[q-1];
        }
        if (pattern[q] == text[i]) {
            ++q;
        }
        if (q == m) {  // 匹配成功，返回起始位置
            return i - m + 1;
        }
    }
    return -1;  // 如果没有找到，则返回 -1
}

// 测试代码
int main() {
    string text = "hello, world!";
    string pattern = "world";
    int pos = kmp(text, pattern);
    if (pos == -1) {
        cout << "Pattern not found." << endl;
    } else {
        cout << "Pattern found at position " << pos << "." << endl;
    }
    return 0;
}

在上述代码中，KMP 算法的主要思想是利用已知信息计算出模式串的前缀函数，并根据前缀函数的值来尽可能减少字符比较的次数。具体实现过程中，我们首先通过 compute_prefix 函数计算出模式串的前缀函数，然后遍历文本串并逐一比较字符，如果发现不匹配的情况，则根据前缀函数的值回退到相应的位置进行重新匹配。

需要注意的是，在计算前缀函数 pi 的过程中，我们使用了一个变量 k 来表示当前已经匹配成功的字符数，以及一个 while 循环来不断地回退 k 的值，从而更新前缀函数的值。在实际使用时，我们可以将 pi 存储为一个数组或向量，从而方便后续的查找操作。

3.Boyer-Moore 算法

Boyer-Moore 算法是一种基于字符比较次数最少原则的字符串查找算法，它利用了模式串中的信息来尽可能地减少在匹配过程中出现的字符比较次数。

Boyer-Moore 算法的时间复杂度为O(mn)，但是在实际应用中通常能够取得很好的效果，因为它可以根据模式串中的信息跳过很多不必要的字符比较，从而减少比较次数。

以下是 Boyer-Moore 算法的 C++ 实现代码：

C++
 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 计算字符 c 在模式串中出现的最右位置
int compute_rightmost(const string& pattern, char c) {
    int m = pattern.length();
    for (int i = m - 1; i >= 0; --i) {
        if (pattern[i] == c) {
            return i;
        }
    }
    return -1;
}

// 计算模式串的好后缀和坏字符规则
void compute_rule(const string& pattern, vector<int>& rightmost, vector<int>& suffix, vector<bool>& match) {
    int m = pattern.length();
    rightmost.resize(256, -1);  // 初始化为 -1
    for (int i = 0; i < m; ++i) {
        rightmost[pattern[i]] = i;
        suffix.push_back(-1);
        match.push_back(false);
    }
    for (int i = m - 2; i >= 0; --i) {
        int j = i;
        while (j >= 0 && pattern[j] == pattern[m-1-i+j]) {
            --j;
        }
        suffix[m-1-i] = i - j;
        if (j < 0) {  // 如果整个后缀都匹配，则标记为匹配成功
            match[m-1-i] = true;
        }
    }
}

// Boyer-Moore 算法实现字符串查找
int boyer_moore(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> rightmost;
    vector<int> suffix;
    vector<bool> match;
    compute_rule(pattern, rightmost, suffix, match);  // 计算模式串的好后缀和坏字符规则
    int i = 0;  // 表示文本串中当前比较的位置
    while (i <= n - m) {
        int j = m - 1;  // 表示模式串中当前比较的位置
        while (j >= 0 && pattern[j] == text[i+j]) {  // 从后往前比较模式串和文本串
            --j;
        }
        if (j < 0) {  // 匹配成功，返回起始位置
            return i;
        } else {  // 否则根据好后缀和坏字符规则移动模式串的位置
            int x = j - rightmost[text[i+j]];
            int y = 0;
            if (j < m - 1) {  // 如果存在好后缀，则将模式串向右移动相应距离
                y = suffix[j+1];
            }
            i += max(x, y);
        }
    }
    return -1;  // 如果没有找到，则返回 -1
}

// 测试代码
int main() {
    string text = "hello, world!";
    string pattern = "world";
    int pos = boyer_moore(text, pattern);
    if (pos == -1) {
        cout << "Pattern not found." << endl;
    } else {
        cout << "Pattern found at position " << pos << "." << endl;
    }
    return 0;
}

在上述代码中，Boyer-Moore 算法的主要思想是利用模式串中已知的信息来尽可能减少字符比较的次数，并根据好后缀和坏字符规则来移动模式串的位置。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用