数据结构之串
数据结构之串（String）在数据结构中，串（String） 是一种用于表示和操纵字符序列的结构。它是最根本的线性表类型之一，广泛应用于文本处理、模式匹配、字符串操纵等领域。
1. 串的界说
串是由零个或多个字符组成的有限序列，也可以称为字符串。比方：
[*]空串：长度为零的串。
[*]非空串：如 "abc" 或 "数据结构"。
一个勾通常表示为：
S = "a1a2a3...an" (n >= 0)
其中，a1, a2, ..., an 是串中的字符，n 为串的长度。字符可以是字母、数字、符号、空格等任意字符。
串的干系概念：
[*] 空串 (Null String)：
[*]长度为 0 的串。
[*]空串与 NULL 不同，空串是合法的字符串对象，只是内容为空。
[*] 空格串 (Blank String)：
[*]由一个或多个空格字符组成的串，比方 " "。
[*]空格串的长度大于等于 1。
[*] 子串 (Substring)：
[*]串中任意连续字符组成的子序列称为该串的“子串”。
[*]子串可为空串。比方，"abc" 的子串包括 "a", "ab", "bc", 以及空串 ""。
[*] 主串 (Master String)：
[*]包含子串的串称为“主串”。比方，"abcde" 是子串 "bcd" 的主串。
[*] 串的长度 (Length)：
[*]串中所包含字符的个数，不包含结束标记 \0。
[*] 前缀 (Prefix)：
[*]一个字符串的前缀是从第一个字符开始到某个字符位置的子串。比方，"abc" 的前缀有：""，"a"，"ab"。
[*] 后缀 (Suffix)：
[*]一个字符串的后缀是从某个字符位置到末了一个字符的子串。比方，"abc" 的后缀有：""，"c"，"bc"。
2. 串的存储结构
根据串的存储形式，常见的实现方式有以下几种：
2.1 顺序存储
[*]将串的字符按顺序存储在一块连续的存储空间中。
[*]优点：支持随机访问，操纵效率高。
[*]缺点：插入和删除操纵需要移动大量字符，效率较低。
char str; // 单纯的字符数组
2.2 链式存储
[*]使用链表存储串的字符，每个节点存储一个字符。
[*]优点：支持动态扩展，插入和删除操纵较快。
[*]缺点：占用额外的存储空间，随机访问效率较低。
typedef struct StringNode {
char data;
struct StringNode *next;
} StringNode;
2.3 索引存储
[*]将串分段存储，同时使用索引表记载每段的起始地址。
[*]优点：得当处理超大字符串，分段加载，节流内存。
[*]缺点：管理复杂度较高。
#define MAX_SEGMENT_LENGTH 50 // 每个段的最大长度
#define MAX_SEGMENTS 10 // 最大段数
typedef struct {
char *data; // 存储段的数据
} Segment;
typedef struct {
Segment segments; // 存储多个段
int segmentCount; // 当前段数
} IndexString;
3. 串的常见操纵
3.1 根本操纵
3.1.1 创建串
初始化字符串。
typedef struct {
char mem; // 用于存储字符的数组
int curSize; // 当前字符串长度
} String, *LPSTR;
// 创建字符串
LPSTR createstring(const char *str) {
LPSTR pstr = (LPSTR)malloc(sizeof(String));
assert(pstr);
memset(pstr->mem, '\0', 1024); // 初始化数组
int count = 0;
while (str != '\0' && count < 1024) {
pstr->mem = str;
count++;
}
pstr->curSize = count; // 更新当前长度
return pstr;
}
// 打印字符串
void printstring(LPSTR pstr) {
for (int i = 0; i < pstr->curSize; i++) {
putchar(pstr->mem);
}
putchar('\n');
}
3.1.2 求串长度
返回字符串中字符的个数。
// 求串长度
int getlength(LPSTR pstr) {
return pstr->curSize;
}
3.1.3 勾通接
将两个字符串拼接为一个字符串。
// 串连接
void concatstring(LPSTR dest, const char *src) {
int srcLen = strlen(src);
if (dest->curSize + srcLen >= 1024) {
printf("字符串过长，无法连接！\n");
return;
}
for (int i = 0; i < srcLen; i++) {
dest->mem = src;
}
dest->curSize += srcLen;
}
3.1.4 串比较
比较两个字符串的大小（字典顺序）。
// 串比较
int comparestring(LPSTR str1, LPSTR str2) {
return strcmp(str1->mem, str2->mem);
}
3.1.5 串拷贝
将一个字符串复制到另一个字符串中。
// 串拷贝
void copystring(LPSTR dest, LPSTR src) {
memset(dest->mem, '\0', 1024); // 清空目标串
for (int i = 0; i < src->curSize; i++) {
dest->mem = src->mem;
}
dest->curSize = src->curSize;
}
3.2 高级操纵
3.2.1 查找子串
BF算法（Brute Force）
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继承比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出末了的匹配效果。BF算法是一种蛮力算法。
// 查找子串 - BF算法
int findsubstringBF(LPSTR mainStr, const char *pattern) {
int m = mainStr->curSize; // 主串长度
int n = strlen(pattern);// 模式串长度
for (int i = 0; i <= m - n; i++) {
int j = 0;
while (j < n && mainStr->mem == pattern) {
j++;
}
if (j == n) {
return i; // 返回匹配的起始位置
}
}
return -1; // 未找到
}
KMP算法（Knuth-Morris-Pratt）
KMP算法是一种高效的字符串匹配算法，它的核心思想是使用已匹配的部分信息来制止重复匹配，从而提拔匹配效率。相较于朴素的暴力匹配算法（BF算法），KMP在最坏情况下的时间复杂度为 O(m + n)，其中 m 是主串长度，n 是模式串长度。
核心思想
[*] 前缀表 (Partial Match Table, PMT)：
[*]前缀表存储的是模式串中每个位置之前的子串的“前缀”和“后缀”的最大匹配长度。
[*]前缀：子串的前面部分。
[*]后缀：子串的后面部分。
[*]例："ababaca" 的前缀表如下：模式串: ababaca
前缀表PMT: 0012301
含义：在模式串的第 i 个字符时，前缀与后缀能匹配的最大长度为 PMT。
[*] 通过前缀表优化匹配：
[*]当匹配失败时，不需要回退主串的匹配位置，而是通过前缀表直接跳转到模式串的某个位置继承匹配。
[*]如许可以制止重复匹配，从而进步效率。
构造前缀表
前缀表（也叫 next 数组）是 KMP 算法的核心，描述了模式串中每个字符之前的部分匹配信息。
// 计算模式串的前缀表 (next 数组)
void computePrefixTable(const char *pattern, int *next, int n) {
next = 0; // 第一个字符的前缀长度总是 0
int len = 0; // 当前最长前缀的长度
int i = 1;
while (i < n) {
if (pattern == pattern) {
len++;
next = len;
i++;
} else {
if (len > 0) {
len = next; // 回溯到上一个最长前缀的位置
} else {
next = 0;
i++;
}
}
}
}
示例：计算 "ababaca" 的前缀表
const char *pattern = "ababaca";
int next;
computePrefixTable(pattern, next, strlen(pattern));
for (int i = 0; i < 7; i++) {
printf("%d ", next);// 输出: 0 0 1 2 3 0 1
}
KMP 主串匹配
通过前缀表实现高效的字符串匹配。
// KMP 模式匹配
int KMP(const char *text, const char *pattern) {
int m = strlen(text); // 主串长度
int n = strlen(pattern); // 模式串长度
// 构造前缀表
int *next = (int *)malloc(sizeof(int) * n);
computePrefixTable(pattern, next, n);
int i = 0; // 主串索引
int j = 0; // 模式串索引
while (i < m) {
if (text == pattern) {
i++;
j++;
}
if (j == n) {
free(next);
return i - j; // 匹配成功，返回匹配起始位置
} else if (i < m && text != pattern) {
if (j > 0) {
j = next; // 利用前缀表回溯
} else {
i++;
}
}
}
free(next);
return -1; // 未找到匹配
}
测试代码
以下是完整测试代码，展示了如何使用 KMP 算法进行模式匹配：
#include <stdio.h>#include <string.h>#include <stdlib.h>// 计算模式串的前缀表 (next 数组)
void computePrefixTable(const char *pattern, int *next, int n) {
next = 0; // 第一个字符的前缀长度总是 0
int len = 0; // 当前最长前缀的长度
int i = 1;
while (i < n) {
if (pattern == pattern) {
len++;
next = len;
i++;
} else {
if (len > 0) {
len = next; // 回溯到上一个最长前缀的位置
} else {
next = 0;
i++;
}
}
}
}
// KMP 模式匹配
int KMP(const char *text, const char *pattern) {
int m = strlen(text); // 主串长度
int n = strlen(pattern); // 模式串长度
// 构造前缀表
int *next = (int *)malloc(sizeof(int) * n);
computePrefixTable(pattern, next, n);
int i = 0; // 主串索引
int j = 0; // 模式串索引
while (i < m) {
if (text == pattern) {
i++;
j++;
}
if (j == n) {
free(next);
return i - j; // 匹配成功，返回匹配起始位置
} else if (i < m && text != pattern) {
if (j > 0) {
j = next; // 利用前缀表回溯
} else {
i++;
}
}
}
free(next);
return -1; // 未找到匹配
}
int main() { const char *text = "ababcabcacbab"; // 主串 const char *pattern = "abcac"; // 模式串 int pos = KMP(text, pattern); if (pos != -1) { printf("模式串在主串中的起始位置为: %d\n", pos); // 输出: 5 } else { printf("模式串未找到！\n"); } return 0;} 3.2.2 插入子串
在指定位置插入一个字符串。
// 插入子串
void insertstring(LPSTR pstr, const char *str, int pos) {
int len = strlen(str);
if (pos < 0 || pos > pstr->curSize || pstr->curSize + len >= 1024) {
printf("插入失败：无效下标或字符串过长！\n");
return;
}
// 移动原有字符腾出空间
for (int i = pstr->curSize - 1; i >= pos; i--) {
pstr->mem = pstr->mem;
}
// 插入新字符串
for (int i = 0; i < len; i++) {
pstr->mem = str;
}
pstr->curSize += len;
}
3.2.3 删除子串
区间删除：直接删除指定范围的字符。
// 删除子串
void deletestring(LPSTR pstr, int start, int end) {
if (start < 0 || end >= pstr->curSize || start > end) {
printf("删除失败：区间不合法！\n");
return;
}
int count = end - start + 1;
// 后续字符前移
for (int i = start; i < pstr->curSize - count; i++) {
pstr->mem = pstr->mem;
}
pstr->curSize -= count;
// 清除多余字符
for (int i = pstr->curSize; i < pstr->curSize + count; i++) {
pstr->mem = '\0';
}
}
匹配删除：删除与某个模式串匹配的部分。
匹配删除操纵需要先找到模式串在主串中的位置，然后将其删除。
[*]使用子串查找算法（如 BF 算法）确定模式串的位置。
[*]假如找到模式串，调用区间删除函数 deletestring 删除该部分内容。
// 查找子串位置 - BF算法
int findsubstringBF(LPSTR mainStr, const char *pattern) {
int m = mainStr->curSize; // 主串长度
int n = strlen(pattern);// 模式串长度
for (int i = 0; i <= m - n; i++) {
int j = 0;
while (j < n && mainStr->mem == pattern) {
j++;
}
if (j == n) {
return i; // 返回匹配的起始位置
}
}
return -1; // 未找到
}
// 匹配删除
void matchdelete(LPSTR pstr, const char *pattern) {
int start = findsubstringBF(pstr, pattern);// 找到模式串的起始位置
if (start == -1) {
printf("未找到模式串，无法删除！\n");
return;
}
int end = start + strlen(pattern) - 1;// 计算模式串的结束位置
// 调用区间删除函数
deletestring(pstr, start, end);
}
3.3.4 替换子串
将子串替换为新的内容。
// 替换子串
void replacestring(LPSTR pstr, const char *oldStr, const char *newStr) {
int pos = findsubstringBF(pstr, oldStr);
if (pos == -1) {
printf("子串未找到，无法替换！\n");
return;
}
// 删除旧子串
deletestring(pstr, pos, pos + strlen(oldStr) - 1);
// 插入新子串
insertstring(pstr, newStr, pos);
}
4. 串的存储实现与代码示例
以下代码展示了基于顺序存储的一些根本串操纵的实现，包括创建串、插入操纵、区间删除等：
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>// 界说字符串数据结构typedef struct {
char mem; // 用于存储字符的数组
int curSize; // 当前字符串长度
} String, *LPSTR;
// 创建字符串
LPSTR createstring(const char *str) {
LPSTR pstr = (LPSTR)malloc(sizeof(String));
assert(pstr);
memset(pstr->mem, '\0', 1024); // 初始化数组
int count = 0;
while (str != '\0' && count < 1024) {
pstr->mem = str;
count++;
}
pstr->curSize = count; // 更新当前长度
return pstr;
}
// 打印字符串
void printstring(LPSTR pstr) {
for (int i = 0; i < pstr->curSize; i++) {
putchar(pstr->mem);
}
putchar('\n');
}
// 求串长度
int getlength(LPSTR pstr) {
return pstr->curSize;
}
// 串连接
void concatstring(LPSTR dest, const char *src) {
int srcLen = strlen(src);
if (dest->curSize + srcLen >= 1024) {
printf("字符串过长，无法连接！\n");
return;
}
for (int i = 0; i < srcLen; i++) {
dest->mem = src;
}
dest->curSize += srcLen;
}
// 串比较
int comparestring(LPSTR str1, LPSTR str2) {
return strcmp(str1->mem, str2->mem);
}
// 串拷贝
void copystring(LPSTR dest, LPSTR src) {
memset(dest->mem, '\0', 1024); // 清空目标串
for (int i = 0; i < src->curSize; i++) {
dest->mem = src->mem;
}
dest->curSize = src->curSize;
}
// 查找子串 - BF算法
int findsubstringBF(LPSTR mainStr, const char *pattern) {
int m = mainStr->curSize; // 主串长度
int n = strlen(pattern);// 模式串长度
for (int i = 0; i <= m - n; i++) {
int j = 0;
while (j < n && mainStr->mem == pattern) {
j++;
}
if (j == n) {
return i; // 返回匹配的起始位置
}
}
return -1; // 未找到
}
// 插入子串
void insertstring(LPSTR pstr, const char *str, int pos) {
int len = strlen(str);
if (pos < 0 || pos > pstr->curSize || pstr->curSize + len >= 1024) {
printf("插入失败：无效下标或字符串过长！\n");
return;
}
// 移动原有字符腾出空间
for (int i = pstr->curSize - 1; i >= pos; i--) {
pstr->mem = pstr->mem;
}
// 插入新字符串
for (int i = 0; i < len; i++) {
pstr->mem = str;
}
pstr->curSize += len;
}
// 删除子串
void deletestring(LPSTR pstr, int start, int end) {
if (start < 0 || end >= pstr->curSize || start > end) {
printf("删除失败：区间不合法！\n");
return;
}
int count = end - start + 1;
// 后续字符前移
for (int i = start; i < pstr->curSize - count; i++) {
pstr->mem = pstr->mem;
}
pstr->curSize -= count;
// 清除多余字符
for (int i = pstr->curSize; i < pstr->curSize + count; i++) {
pstr->mem = '\0';
}
}
// 替换子串
void replacestring(LPSTR pstr, const char *oldStr, const char *newStr) {
int pos = findsubstringBF(pstr, oldStr);
if (pos == -1) {
printf("子串未找到，无法替换！\n");
return;
}
// 删除旧子串
deletestring(pstr, pos, pos + strlen(oldStr) - 1);
// 插入新子串
insertstring(pstr, newStr, pos);
}
// 主函数测试int main() { // 创建字符串 LPSTR str1 = createstring("Hello World"); printf("原始字符串: "); printstring(str1); // 求字符串长度 printf("字符串长度: %d\n", getlength(str1)); // 勾通接 concatstring(str1, "!!!"); printf("连接后的字符串: "); printstring(str1); // 插入子串 insertstring(str1, " Beautiful", 5); printf("插入后的字符串: "); printstring(str1); // 删除子串 deletestring(str1, 6, 15); printf("删除后的字符串: "); printstring(str1); // 替换子串 replacestring(str1, "World", "Universe"); printf("替换后的字符串: "); printstring(str1); // 查找子串 int pos = findsubstringBF(str1, "Universe"); if (pos != -1) { printf("子串 'Universe' 的起始位置: %d\n", pos); } else { printf("子串 'Universe' 未找到！\n"); } // 串拷贝 LPSTR str2 = createstring(""); copystring(str2, str1); printf("拷贝后的字符串: "); printstring(str2); // 串比较 const char *compareResult = comparestring(str1, str2) == 0 ? "相等" : "不相等"; printf("str1 和 str2 比较效果: %s\n", compareResult); // 开释内存 free(str1); free(str2); return 0;} 5. 串的现实应用
[*]文本编辑器：字符串的插入、删除、查找、替换等操纵。
[*]网络传输：处理传输的数据包和协议，比方 HTTP 报文。
[*]搜索引擎：关键词匹配、统计、自动补全等。
[*]DNA 序列分析：基因比对、模式匹配。
[*]文件路径剖析：操纵体系中对文件路径的处理。
[*]正则表达式：复杂模式查找与替换。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]