数据结构之串

天津储鑫盛钢材现货供应商 · 2025-1-3 12:10:20

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

x

数据结构之串（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[100]; // 单纯的字符数组

复制代码

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[MAX_SEGMENTS]; // 存储多个段
int segmentCount; // 当前段数
} IndexString;

复制代码

3. 串的常见操纵

3.1 根本操纵

3.1.1 创建串

初始化字符串。

typedef struct {
char mem[1024]; // 用于存储字符的数组
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[count] != '\0' && count < 1024) {
pstr->mem[count] = str[count];
count++;
}
pstr->curSize = count; // 更新当前长度
return pstr;
}
// 打印字符串
void printstring(LPSTR pstr) {
for (int i = 0; i < pstr->curSize; i++) {
putchar(pstr->mem[i]);
}
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[dest->curSize + i] = src[i];
}
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[i] = src->mem[i];
}
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[i + j] == pattern[j]) {
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" 的前缀表如下：
  1. 模式串: a b a b a c a
  2. 前缀表PMT: 0 0 1 2 3 0 1
  复制代码
  含义：在模式串的第 i 个字符时，前缀与后缀能匹配的最大长度为 PMT。
通过前缀表优化匹配：

当匹配失败时，不需要回退主串的匹配位置，而是通过前缀表直接跳转到模式串的某个位置继承匹配。

如许可以制止重复匹配，从而进步效率。

构造前缀表

前缀表（也叫 next 数组）是 KMP 算法的核心，描述了模式串中每个字符之前的部分匹配信息。

// 计算模式串的前缀表 (next 数组)
void computePrefixTable(const char *pattern, int *next, int n) {
next[0] = 0; // 第一个字符的前缀长度总是 0
int len = 0; // 当前最长前缀的长度
int i = 1;
while (i < n) {
      if (pattern[i] == pattern[len]) {
         len++;
         next[i] = len;
         i++;
      } else {
         if (len > 0) {
            len = next[len - 1]; // 回溯到上一个最长前缀的位置
         } else {
            next[i] = 0;
            i++;
         }
      }
}
}
复制代码
示例：计算 "ababaca" 的前缀表

const char *pattern = "ababaca";
int next[7];
computePrefixTable(pattern, next, strlen(pattern));
for (int i = 0; i < 7; i++) {
printf("%d ", next[i]);  // 输出: 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[i] == pattern[j]) {
         i++;
         j++;
      }
      if (j == n) {
         free(next);
         return i - j; // 匹配成功，返回匹配起始位置
      } else if (i < m && text[i] != pattern[j]) {
         if (j > 0) {
            j = next[j - 1]; // 利用前缀表回溯
         } 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; // 第一个字符的前缀长度总是 0
int len = 0; // 当前最长前缀的长度
int i = 1;
while (i < n) {
      if (pattern[i] == pattern[len]) {
         len++;
         next[i] = len;
         i++;
      } else {
         if (len > 0) {
            len = next[len - 1]; // 回溯到上一个最长前缀的位置
         } else {
            next[i] = 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[i] == pattern[j]) {
         i++;
         j++;
      }
      if (j == n) {
         free(next);
         return i - j; // 匹配成功，返回匹配起始位置
      } else if (i < m && text[i] != pattern[j]) {
         if (j > 0) {
            j = next[j - 1]; // 利用前缀表回溯
         } 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[i + len] = pstr->mem[i];
}
// 插入新字符串
for (int i = 0; i < len; i++) {
      pstr->mem[pos + i] = str[i];
}
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[i] = pstr->mem[i + count];
}
pstr->curSize -= count;
// 清除多余字符
for (int i = pstr->curSize; i < pstr->curSize + count; i++) {
      pstr->mem[i] = '\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[i + j] == pattern[j]) {
         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[1024]; // 用于存储字符的数组
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[count] != '\0' && count < 1024) {
      pstr->mem[count] = str[count];
      count++;
}
pstr->curSize = count; // 更新当前长度
return pstr;
}
// 打印字符串
void printstring(LPSTR pstr) {
for (int i = 0; i < pstr->curSize; i++) {
      putchar(pstr->mem[i]);
}
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[dest->curSize + i] = src[i];
}
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[i] = src->mem[i];
}
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[i + j] == pattern[j]) {
         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[i + len] = pstr->mem[i];
}
// 插入新字符串
for (int i = 0; i < len; i++) {
      pstr->mem[pos + i] = str[i];
}
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[i] = pstr->mem[i + count];
}
pstr->curSize -= count;
// 清除多余字符
for (int i = pstr->curSize; i < pstr->curSize + count; i++) {
      pstr->mem[i] = '\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企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

数据结构之串

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块