定义和实现

串的定义

字符串是计算机科学中的一个基本概念，通常被定义为有限序列中字符的有序集合。

形式定义：

字符串 $S$ 时字符集 $\Sigma$ 上的一个有限序列：$S = a_1 a_2 \cdots a_n$，其中 $a_i \in \Sigma$，且 $n$ 为字符串的长度， 当 $n = 0$ 时，称为空字符串。

串的存储结构

1. 定长顺序存储表示

在定长顺序存储表示中，每个字符串都有固定的长度，通常用一个预定义的最大大小来表示。这种表示方法使用一个一维数组，数组的大小等于预定的最大长度。

在某些语境中（例如C语言），使用特殊字符（如 '\0'）来标识字符串结束。

#define MAX_SIZE 100 // 预定义的最大大小

typedef struct {
    char data[MAX_SIZE];  // 字符数组
    int length;           // 当前字符串的长度
} FixedString;

2. 堆分配存储表示

在堆分配存储表示中，每个字符串具有其自己的长度，因此可以动态地分配存储空间。字符串在堆中分配空间，只需要那么多的空间来存储实际的字符以及结束字符或长度信息。

typedef struct {
    char *data;           // 指向动态分配空间的指针
    int length;           // 字符串的长度
} HeapString;

// 创建一个新的字符串
void initHeapString(HeapString *s, const char *str) {
    s->length = strlen(str);
    s->data = (char *)malloc((s->length + 1) * sizeof(char));
    if (s->data == NULL) {
        exit(1);  // 分配失败
    }
    strcpy(s->data, str);
}

// 释放字符串
void freeHeapString(HeapString *s) {
    free(s->data);
    s->length = 0;
}

3. 块链存储表示

块链存储表示是结合了链表与块存储的思想。串分为较小的块，每个块存储一部分字符。块之间使用指针链接。这样，整个字符串就变成了一个字符块的链表。

#define BLOCK_SIZE 4 // 为了简单起见，设块大小为4

typedef struct StringBlock {
    char data[BLOCK_SIZE];   // 块中的字符数据
    struct StringBlock *next;  // 指向下一个块的指针
} StringBlock;

typedef struct {
    StringBlock *head;      // 指向第一个块的指针
    int length;             // 字符串的总长度
} BlockString;

// 初始化块链字符串
void initBlockString(BlockString *s) {
    s->head = NULL;
    s->length = 0;
}

// 为了简化，这里只展示了数据结构定义和初始化函数。实际应用中还需要考虑其他函数，如插入、删除、销毁等。

串的基本操作

• 赋值（Assign）：
  • 将一个串的内容复制到另一个串。
• 比较（Compare）：
  • 根据字符的字典顺序比较两个串。可以判断两个串是否相等，或者一个串是否小于或大于另一个串。
• 长度（Length）：
  • 返回串的长度，即串中字符的数目。
• 连接（Concat）：
  • 将两个串连接成一个新的串。例如，将串"Hello"和串"World"连接为"HelloWorld"。
• 子串提取（Substr）：
  • 从串中提取某个指定位置开始的指定长度的字符序列作为一个新的串。例如，从串"HelloWorld"中提取从位置1开始的5个字符，得到"Hello"。
• 插入（Insert）：
  • 在串的指定位置插入另一个串。例如，在串"HelloWorld"的第6个位置插入串"Beautiful", 得到"HelloBeautifulWorld"。
• 删除（Delete）：
  • 从串中删除从指定位置开始的指定长度的字符。
• 替换（Subsititude）：
  • 将串中某个子串的所有出现替换为另一个子串。例如，将串"apple, banana, apple"中的"apple"替换为"orange"，得到"orange, banana, orange"。
• 模式匹配（Index）：
  • 在串中查找另一个子串的位置。这通常使用算法如KMP、BM或Sunday来加速查找。
• 清空（Clear）：
  • 释放串的存储空间并将其设置为空串。