当前位置: article > 正文

数据结构中的串（String）：概念、操作和实际应用

作者：小丑西瓜9 | 2024-04-30 22:38:04

踩

KMP算法（Knuth-Morris-Pratt算法）

2.Brute-Force（暴力匹配）算法

一.引言

在计算机科学中，数据结构是一种用于组织和存储数据的方式。其中，串（String）是一种非常常见的数据结构，用于表示一组字符序列。串通常用于处理文本数据，如文本编辑器、搜索引擎、数据库系统等。在本文中，我们将深入探讨串的概念、操作以及实际应用。

二.串的定义

在计算机科学中，串是由零个或多个字符组成的有限序列，是数据结构中常见的一种基本类型。它可以为空串，也可以是由字符组成的非空串。串通常用于表示文本数据，如文件内容、用户输入等，因此在算法和程序设计中占据着重要的地位。

一个串可以是由字母、数字、符号等任意字符组成，字符的种类和个数没有固定限制。例如，"Hello, World!"、"123456"、"!@#$%" 都是串的例子。

串的重要性在于它是对文本数据进行处理和操作的基础，涉及字符串匹配、文本编辑、编译器设计等多个领域。因此，深入理解串的特性和操作对于程序设计人员至关重要。

三. 串的抽象数据类型（ADT）

在计算机科学中，为了方便对串进行操作和管理，可以定义串的抽象数据类型（ADT），以提供一组操作和属性来描述串的特性。下面是串的抽象数据类型的定义


// 串的抽象数据类型定义
typedef struct {
    char *str;  // 存储串的字符数组
    int length; // 串的长度
} String;

在这个抽象数据类型中，str是一个指向字符数组的指针，用于存储串的内容，length表示串的长度。通过这个抽象数据类型，我们可以方便地对串进行创建、销毁、获取长度等操作，从而实现对串的高效管理和处理。

四. 串的存储结构

串的存储结构是指如何在计算机内存中存储串的数据以及相关信息。常见的存储结构有两种：顺序存储结构和链式存储结构。下面分别介绍这两种存储方式，并给出相应的代码实现。

顺序存储结构

顺序存储结构是将串中的字符顺序地存放在一段连续的存储空间中，通常是字符数组。下面是顺序存储结构的定义：


#define MAX_SIZE 100 // 假设串的最大长度为100
 
typedef struct {
    char str[MAX_SIZE]; // 用字符数组存储串
    int length;         // 串的长度
} SeqString;

在顺序存储结构中，str是一个字符数组，用于存储串的内容，length表示串的长度。通过这种方式，可以直接访问串中的任意字符，并且可以快速获取串的长度。

链式存储结构

链式存储结构是通过链表来存储串的字符，每个节点存储一个字符，并且通过指针将各个节点连接起来。下面是链式存储结构的定义：


typedef struct LNode {
    char data;
    struct LNode *next;
} LNode;
 
typedef struct {
    LNode *head; // 头指针
    int length;  // 串的长度
} LinkString;

在链式存储结构中，每个节点中的data存储一个字符，next指针指向下一个节点。头指针head指向链表的第一个节点，通过遍历链表可以获取串的全部字符。链式存储结构适合于不确定串长度的情况，但需要额外的指针开销。

五. 串模式的存储算法

串模式的存储算法主要用于实现串的模式匹配，下面是串模式常用的几种存储算法：

1.KMP算法（Knuth-Morris-Pratt算法）

KMP算法是一种高效的字符串匹配算法，通过预处理模式串，利用模式串中的信息在匹配失败时尽可能地减少比较次数，从而提高匹配效率。
KMP算法的核心思想是利用模式串内部的信息，在匹配失败时根据已匹配的部分，选择合适的位置进行模式串的移动。
算法的关键在于部分匹配表（Next数组），它记录了模式串每个位置之前的子串中有多大长度的相同前缀和后缀。
匹配过程中，当文本串的某个字符与模式串的对应字符不匹配时，利用Next数组确定模式串的移动位置，从而减少不必要的比较。

特点与应用：

KMP算法的时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。在实际应用中，KMP算法通常比暴力匹配算法具有更高的效率。
由于其高效的匹配速度，KMP算法被广泛应用于字符串匹配、文本搜索、编译器设计等领域。
在处理大规模文本数据时，KMP算法能够提供更快速和可靠的匹配方案，因此被视为处理字符串匹配问题的重要工具之一。

下面是KMP算法的核心部分：


void getNext(char *pattern, int next[]) {
    int len = strlen(pattern);
    next[0] = -1;
    int k = -1, j = 0;
    while (j < len - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            ++k;
            ++j;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}
 
int KMP(char *text, char *pattern) {
    int len1 = strlen(text);
    int len2 = strlen(pattern);
    int i = 0, j = 0;
    int *next = (int *)malloc(sizeof(int) * len2);
    getNext(pattern, next);
    while (i < len1 && j < len2) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    free(next);
    if (j == len2) {
        return i - j; // 匹配成功，返回模式串在文本串中的起始位置
    } else {
        return -1; // 匹配失败
    }
}

2.Brute-Force（暴力匹配）算法

暴力匹配算法是一种简单直接的字符串匹配算法，也称为朴素字符串匹配算法。它的基本思想是从文本串的第一个字符开始，与模式串进行逐个字符比较，若匹配失败，则将模式串右移一位，继续比较，直到找到匹配或者文本串被遍历完为止。
该算法的时间复杂度为O(n*m)，其中n为文本串的长度，m为模式串的长度。

以下是暴力匹配算法的核心部分的伪代码表示：


BruteForceSearch(text, pattern):
    n = 文本串的长度
    m = 模式串的长度
    
    for i from 0 to n - m do:
        j = 0
        while j < m 且 text[i + j] == pattern[j] do:
            j = j + 1
        
        if j == m:  # 找到了匹配
            返回 i  # 返回匹配位置的起始下标
    
返回 -1  # 没有找到匹配

3.Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，其核心思想是利用模式串中的字符出现位置的信息，在匹配失败时尽可能地跳过多的字符，从而减少比较次数。
该算法包含两个启发式规则：坏字符规则和好后缀规则，通过这两个规则可以确定每次匹配失败时模式串的移动位置。
Boyer-Moore算法的时间复杂度在最坏情况下为O(n*m)，但通常情况下具有线性时间复杂度。

以下是Boyer-Moore算法的核心部分的伪代码表示：


BoyerMooreSearch(text, pattern):
    n = 文本串的长度
    m = 模式串的长度
    lastOccurrence = 记录模式串中每个字符最后出现位置的数组
    suffix = 计算模式串的后缀数组
    prefix = 计算模式串的前缀数组
    
    初始化lastOccurrence数组，记录模式串中每个字符最后出现的位置
    初始化suffix数组，计算模式串的后缀数组
    初始化prefix数组，计算模式串的前缀数组
    
    i = m - 1  # 文本串中与模式串最后一个字符对齐的位置
    j = m - 1  # 模式串中最后一个字符的下标
    
    while i < n do:
        if text[i] == pattern[j]:  # 逐个字符比较
            if j == 0:  # 如果模式串已经比较完毕，说明找到了匹配
                返回 i  # 返回匹配位置的起始下标
            else:
                i = i - 1  # 继续向前比较
                j = j - 1
        else:
            badCharacterShift = j - lastOccurrence[text[i]]  # 坏字符规则计算位移
            goodSuffixShift = calculateGoodSuffixShift(j, suffix, prefix)  # 好后缀规则计算位移
            i = i + max(badCharacterShift, goodSuffixShift)  # 取较大的位移
            j = m - 1  # 重新比较模式串的最后一个字符
    
    返回 -1  # 没有找到匹配
 
 
calculateGoodSuffixShift(j, suffix, prefix):
    k = m - 1 - j  # 好后缀的长度
    if suffix[k] != -1:  # 如果找到匹配的好后缀
        return j - suffix[k] + 1
    else:  # 如果找不到匹配的好后缀
        for r from j + 2 to m - 1:
            if prefix[m - r]:
                return r
    return m  # # 如果没有好后缀匹配，则移动整个模式串长度

4.Rabin-Karp算法

Rabin-Karp算法是一种基于哈希的字符串匹配算法，它通过对文本串和模式串进行哈希计算，然后比较它们的哈希值来判断是否匹配。
该算法的优势在于可以在O(n+m)的时间复杂度内完成匹配，且在某些情况下比其他算法更加高效。
然而，Rabin-Karp算法的实现涉及到哈希函数的设计和哈希冲突的处理，因此需要谨慎选择哈希函数以及解决哈希冲突的方法。

以下是Rabin-Karp算法的核心部分的伪代码表示：


RabinKarpSearch(text, pattern):
    n = 文本串的长度
    m = 模式串的长度
    p = 一个较大的素数，用于哈希计算
    
    textHash = 计算文本串text[0:m]的哈希值
    patternHash = 计算模式串pattern的哈希值
    
    for i from 0 to n - m do:
        if textHash == patternHash 且 text[i:i+m] == pattern:  # 判断哈希值相等且子串相等
            返回 i  # 返回匹配位置的起始下标
        
        if i < n - m:  # 更新下一次文本串的哈希值
            textHash = 重新计算text[i+1:i+m+1]的哈希值
    
    返回 -1  # 没有找到匹配

六. 实际案例以及应用

串在计算机科学中有着广泛的应用，比如字符串匹配、文本编辑器、编译器等领域。

下面我们以文本编辑器为例进行说明。

首先，我们需要定义一些常量和全局变量：


#define MAX_LENGTH 1000
 
char text[MAX_LENGTH];
int length = 0;

MAX_LENGTH 是文本的最大长度，text 是用于存储文本的字符数组，length 是当前文本的长度。

然后，我们定义一些函数来实现文本编辑器的功能：


void insert(int pos, char *str) {
    int len = strlen(str);
    if (length + len > MAX_LENGTH) {
        printf("Error: Text is too long\n");
        return;
    }
    for (int i = length; i >= pos; i--) {
        text[i + len] = text[i];
    }
    for (int i = 0; i < len; i++) {
        text[pos + i] = str[i];
    }
    length += len;
}
 
void delete(int pos, int len) {
    if (pos + len > length) {
        printf("Error: Invalid position or length\n");
        return;
    }
    for (int i = pos; i < length - len; i++) {
        text[i] = text[i + len];
    }
    length -= len;
}
 
void replace(int pos, int len, char *str) {
    delete(pos, len);
    insert(pos, str);
}
 
int find(char *str) {
    int i, j, k;
    for (i = 0; i <= length - strlen(str); i++) {
        for (j = i, k = 0; text[j] == str[k]; j++, k++) {
            if (str[k + 1] == '\0') {
                return i;
            }
        }
    }
    return -1;
}

insert 函数用于在指定位置插入一个字符串，delete 函数用于删除指定位置的字符串，replace 函数用于替换指定位置的字符串，find 函数用于查找指定的字符串。

最后，我们编写主函数来测试这些函数：


int main() {
    insert(0, "Hello, ");
    insert(7, "World!");
    printf("Text: %s\n", text);
 
    replace(7, 5, "Dear");
    printf("Text: %s\n", text);
 
    int pos = find("Dear");
    if (pos != -1) {
        printf("Substring 'Dear' found at position %d\n", pos);
    } else {
        printf("Substring 'Dear' not found\n");
    }
 
    return 0;
}
运行这段代码，你将看到以下输出：
 
Text: Hello, World!
Text: Hello, Dear!
Substring 'Dear' found at position 7

七.总结

串是一种非常常见的数据结构，用于表示一组字符序列。它支持多种操作，如插入、删除、替换、查找、比较和连接。串在现实生活中有许多应用，如文本编辑器、搜索引擎、数据库系统和编译器等。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/515652