数据结构与C++

数据结构与C++ 知识量:9 - 32 - 91

4.2 串的顺序存储及基本运算><

串的定长顺序存储- 4.2.1 -

串的定长顺序存储是指按照预定义的大小,为每个串变量分配一个固定长度的存储区。这种存储方式类似于顺序表,使用一组地址连续的存储单元来存储串值中的字符序列。

在定长顺序存储中,每个串变量都有一个固定长度的存储空间,通常以字符为单位。例如,如果定义一个串变量时指定长度为100,那么该串变量将占用100个字符的存储空间。

这种存储方式的特点是简单、直观,便于实现串的基本操作。但由于每个串变量的大小是固定的,因此在处理变长串时会造成存储空间的浪费。为了解决这个问题,可以使用动态分配存储空间的方式,根据实际需要为串变量分配不同大小的存储空间。

以下是C++中表示定长顺序存储的示例代码:

#include <iostream>  
#include <cstring>  
  
using namespace std;  
  
const int MAX_LENGTH = 100; // 定义最大长度  
  
int main() {  
    char str[MAX_LENGTH]; // 定义定长字符数组存储串值  
    cout << "请输入一个长度不超过" << MAX_LENGTH << "的字符串:" << endl;  
    cin >> str; // 读入字符串  
  
    // 输出字符串  
    cout << "输入的字符串为:" << str << endl;  
  
    return 0;  
}

在上述代码中,定义了一个最大长度为100的定长字符数组str来存储输入的字符串。通过使用cin语句读入字符串,并将其存储在str数组中。然后,输出存储在str数组中的字符串。

定长顺序串的基本运算- 4.2.2 -

定长顺序串的基本运算主要包括以下几种:

  • 初始化:为定长顺序串分配存储空间,并初始化为空串。

  • 赋值:将一个串的值赋给另一个串。

  • 拼接:将两个串拼接在一起。

  • 插入:在指定位置插入一个子串。

  • 删除:删除指定位置的字符或子串。

  • 查找:查找指定字符或子串在串中的位置。

  • 替换:将串中的指定字符或子串替换为另一字符或子串。

  • 长度计算:计算串的长度。

  • 拷贝:将一个串的值复制到另一个串。

  • 比较:比较两个串的大小,判断是否相等。

这些基本运算可以根据实际需求进行组合,以完成对定长顺序串的各种操作。需要注意的是,由于定长顺序串的长度是固定的,因此在执行插入、删除等操作时,可能需要重新分配存储空间,以保持串的连续存储特性。

以下是一个使用C++进行定长顺序串基本运算的示例代码:

#include <iostream>  
#include <cstring>  
  
using namespace std;  
  
const int MAX_LENGTH = 100; // 定义最大长度  
  
int main() {  
    char str1[MAX_LENGTH]; // 定义定长字符数组存储串值  
    char str2[MAX_LENGTH];  
    char result[MAX_LENGTH];  
  
    cout << "请输入第一个字符串:" << endl;  
    cin >> str1; // 读入第一个字符串  
  
    cout << "请输入第二个字符串:" << endl;  
    cin >> str2; // 读入第二个字符串  
  
    // 拼接字符串  
    strcat(str1, str2);  
    cout << "拼接后的字符串为:" << str1 << endl;  
  
    // 查找子串位置  
    int pos = strstr(str1, str2);  
    if (pos != -1) {  
        cout << "子串在原串中的位置为:" << pos << endl;  
    } else {  
        cout << "未找到子串" << endl;  
    }  
  
    // 替换子串  
    int len = strlen(str1);  
    if (len >= strlen(str2)) {  
        cout << "替换子串前的字符串为:" << str1 << endl;  
        char newStr[] = "newStr"; // 替换成的子串  
        int newStrLen = strlen(newStr);  
        if (newStrLen <= len - strlen(str2)) {  
            char* p = strstr(str1, str2); // 查找子串位置  
            while (p != NULL) { // 替换所有子串  
                strcpy(p + newStrLen, p + strlen(str2)); // 移动后缀字符  
                p = strstr(p + newStrLen, str2); // 查找下一个子串位置  
            }  
            cout << "替换子串后的字符串为:" << str1 << endl;  
        } else {  
            cout << "替换成的子串长度超过剩余长度" << endl;  
        }  
    } else {  
        cout << "原串长度不足以包含子串" << endl;  
    }  
  
    return 0;  
}

在上述代码中,定义了三个定长字符数组str1、str2和result,分别用于存储输入的字符串、需要查找或替换的子串以及结果。通过使用cin语句读入输入字符串,并使用C标准库中的字符串处理函数进行拼接、查找、替换等操作。最后,输出相应的结果。

模式匹配- 4.2.3 -

串的模式匹配(也称为子串定位)是计算机科学和数据结构中的一个重要概念,主要用于在主串(或称为目标串)中找到一个特定的子串(或称为模式串)。这个过程在许多场合中都非常有用,比如文本编辑、数据挖掘、字符串搜索等。

以下是一个简单的C++代码示例,用于实现串的模式匹配(子串定位):

#include <iostream>  
#include <string>  
  
using namespace std;  
  
int patternMatching(string s, string t) {  
    int m = s.length();  
    int n = t.length();  
      
    // 如果子串长度为0,则返回0  
    if (n == 0) {  
        return 0;  
    }  
      
    // 如果主串长度为0,则返回-1  
    if (m == 0) {  
        return -1;  
    }  
      
    // 逐个字符比较主串和子串的字符  
    for (int i = 0; i <= m - n; i++) {  
        int j;  
        for (j = 0; j < n; j++) {  
            if (s[i + j] != t[j]) {  
                break;  
            }  
        }  
        if (j == n) {  
            // 匹配成功,返回子串在主串中的起始位置  
            return i;  
        }  
    }  
      
    // 匹配失败,返回-1  
    return -1;  
}  
  
int main() {  
    string s = "ABABDABACDABABCABAB";  
    string t = "ABABCABAB";  
    int index = patternMatching(s, t);  
    if (index == -1) {  
        cout << "Pattern not found in string." << endl;  
    } else {  
        cout << "Pattern found at index: " << index << endl;  
    }  
    return 0;  
}

这个示例中,patternMatching函数接受两个字符串s和t作为输入,并返回子串t在主串s中的起始位置。如果匹配失败,则返回-1。在主函数中,定义了两个字符串s和t,并调用patternMatching函数来查找子串在主串中的位置。根据返回值,输出相应的结果。