串的存储结构和基本操作
串的存储结构
以 C 语言为例
定长顺序存储
结构定义：
#define MAXSTRLEN 255
typedef struct {
char ch[MAXSTRLEN + 1]; // 存储串的字符数组，ch[0]存放串的长度
int length; // 串的当前长度
} SString;特点：
- 用一维数组存储串中字符
- 数组的 0 号位置存储串的长度，从 1 号位置开始存储字符
- 串长度固定，最大为 MAXSTRLEN
- 存储密度高，操作简单
- 缺点：串长度受限，可能造成存储空间浪费
基本操作时间复杂度：
- 求串长：O(1)
- 串赋值：O(n)
- 串比较：O(min(m,n))
堆分配存储
结构定义：
typedef struct {
char *ch; // 指向动态分配存储区的指针
int length; // 串的当前长度
} HString;特点：
- 动态分配存储空间，按需分配
- 存储空间利用率高，无长度限制
- 需要手动管理内存，防止内存泄漏
- 操作相对复杂，需要考虑内存分配和释放
内存管理：
- 初始化：
malloc()分配初始空间 - 扩容：
realloc()重新分配更大空间 - 释放：
free()释放内存空间
块链存储
结构定义：
#define CHUNKSIZE 80 // 块的大小
typedef struct Chunk {
char ch[CHUNKSIZE];
struct Chunk *next;
} Chunk;
typedef struct {
Chunk *head, *tail; // 串的头指针和尾指针
int curlen; // 串的当前长度
} LString;特点：
- 用链表结构存储，每个节点存储固定数量的字符
- 适合频繁插入和删除操作
- 存储密度相对较低（存在指针开销）
- 操作复杂度较高，但灵活性好
- 适用于长度变化频繁的串
优缺点对比：
| 存储方式 | 存储密度 | 时间效率 | 空间效率 | 适用场景 |
|---|---|---|---|---|
| 定长顺序 | 高 | 高 | 中 | 串长度相对固定 |
| 堆分配 | 高 | 中 | 高 | 串长度变化较大 |
| 块链 | 低 | 低 | 中 | 频繁插入删除 |
串的基本操作
基本操作定义
1. StrAssign(&T, chars)
- 功能：将字符串常量 chars 赋值给串 T
- 时间复杂度：O(n)
2. StrCopy(&T, S)
- 功能：将串 S 复制到串 T
- 时间复杂度：O(n)
3. StrEmpty(S)
- 功能：判断串 S 是否为空串
- 时间复杂度：O(1)
4. StrCompare(S, T)
- 功能：比较串 S 和 T 的大小关系
- 返回值：S>T 返回正数，S=T 返回 0，S<T 返回负数
- 时间复杂度：O(min(m,n))
5. StrLength(S)
- 功能：返回串 S 的长度
- 时间复杂度：O(1) 或 O(n)（取决于存储方式）
6. SubString(&Sub, S, pos, len)
- 功能：从串 S 的第 pos 个字符起取长度为 len 的子串赋给 Sub
- 时间复杂度：O(len)
7. Concat(&T, S1, S2)
- 功能：连接串 S1 和 S2，结果赋给 T
- 时间复杂度：O(m+n)
8. Index(S, T, pos)
- 功能：从串 S 的第 pos 个字符开始查找串 T 首次出现的位置
- 时间复杂度：O(mn)（朴素算法）
9. Replace(&S, T, V)
- 功能：用串 V 替换串 S 中所有与串 T 相等的不重叠子串
- 时间复杂度：O(mn)
10. StrInsert(&S, pos, T)
- 功能：在串 S 的第 pos 个字符前插入串 T
- 时间复杂度：O(n+m)
11. StrDelete(&S, pos, len)
- 功能：从串 S 中删除第 pos 个字符起长度为 len 的子串
- 时间复杂度：O(n)
核心算法实现要点
串匹配算法：
- 朴素模式匹配：时间复杂度 O(mn)，空间复杂度 O(1) 简单的模式匹配
- KMP 算法：时间复杂度 O(m+n)，需要构造 next 数组 KMP 算法
- KMP 改进算法：构造 nextval 数组，避免不必要的比较 KMP 改进算法
字符串操作注意事项：
- 边界条件检查（位置参数的有效性）
- 内存管理（堆分配方式需要注意内存泄漏）
- 字符串结束符的处理（C 语言中的 ‘\0’）
- 串长度的维护和更新