串（字符串）和数组是数据结构中的两个重要分支，它们在程序设计中承担着不同但互补的角色。串专门处理字符数据，而数组则提供了多维数据的存储和访问机制。本文将深入探讨这两种数据结构的理论基础、实现方法和核心算法。
文章目录
- 1.串的基本概念
- 串的抽象数据类型定义
- 串的核心特性
- 2.串的存储实现
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 带长度的索引表
- 带末指针的索引表
- 带特征位的索引表
- 3.串的核心算法实现
- 串连接运算
- 求子串运算
- 4.模式匹配算法
- 简单模式匹配算法
- 链式存储的模式匹配
- KMP算法优化
- 5.数组的抽象数据类型
- 多维数组的地址计算
- 6.特殊矩阵的压缩存储
- 稀疏矩阵
- 稀疏矩阵转置
- 快速转置算法
- 7.存储效率对比
- 不同存储方式的空间复杂度
- 算法效率分析
- 8.应用场景与选择策略
- 串的应用领域
- 数组的应用领域
- 选择指导原则
- 9.总结
1.串的基本概念
串是由零个或多个字符组成的有限序列，是一种特殊的线性表，其数据元素仅由字符构成。串在文本处理、编译器设计、生物信息学等领域有着广泛应用。
串的抽象数据类型定义
ADT String {数据对象: D = {cᵢ | cᵢ ∈ CharacterSet, i = 1,2,...,n, n ≥ 0}数据关系: R = {<cᵢ,cᵢ₊₁> | cᵢ,cᵢ₊₁ ∈ D, i = 1,2,...,n-1}操作集合:StrAssign(&T, chars) // 串赋值StrCopy(&T, S) // 串复制 StrEmpty(S) // 判空StrCmp(S, T) // 串比较StrLength(S) // 求串长StrCat(&T, S) // 串连接SubStr(&Sub, S, pos, len) // 求子串StrIndex(S, T, pos) // 子串定位Replace(&S, T, V) // 串替换StrInsert(&S, pos, T) // 串插入StrDelete(&S, pos, len) // 串删除
} ADT String
这个定义包含了串的11种基本运算，涵盖了字符串处理的所有核心操作。
串的核心特性
- 有限性：串的长度是有限的
- 有序性：字符在串中的位置是有意义的
- 同质性：所有元素都是字符类型
- 可为空：空串（长度为0）是有效的串
2.串的存储实现
顺序存储结构
顺序存储是串最常用的存储方式，将字符依次存放在连续的存储单元中。
#define MAXSIZE 100typedef struct {char ch[MAXSIZE]; // 存放串值的字符数组int length; // 串的实际长度
} SeqString;
优点：
- 随机访问效率高，时间复杂度O(1)
- 存储密度高，没有额外指针开销
- 实现简单，便于理解和调试
缺点：
- 需要预先分配固定大小的存储空间
- 插入和删除操作可能需要移动大量字符
- 存在空间浪费或溢出风险
链式存储结构
链式存储将每个字符存储在单独的节点中，通过指针连接。
typedef struct linknode {char data; // 字符数据域struct linknode *next; // 指向下一个字符的指针
} LinkString;
特点分析：
- 存储灵活：动态分配，无固定长度限制
- 插入删除高效：在已知位置插入删除为O(1)
- 空间开销大：每个字符需要额外的指针空间
- 访问效率低：随机访问需要O(n)时间
索引存储结构
索引存储适用于管理多个串的场景，通过索引表记录串的元数据。
带长度的索引表
#define MAXSIZE 1024typedef struct {char name[MAXSIZE]; // 串名称int length; // 串长度char *start_addr; // 串值起始地址
} LengthNode;
带末指针的索引表
typedef struct {char name[MAXSIZE];char *start_addr, *end_addr; // 起始和结束地址
} EndNode;
带特征位的索引表
typedef struct {char name[MAXSIZE];int tag; // 特征位：0-短串直接存储，1-长串存储地址union {char *start_addr; // 长串地址char value[4]; // 短串直接存储} uval;
} TagNode;
这种设计优化了短串的存储效率，避免了指针的额外开销。
3.串的核心算法实现
串连接运算
串连接是将两个串依次拼接成一个新串的操作。
SeqString *StrCat(SeqString *s, SeqString *t) {SeqString *r = (SeqString*)malloc(sizeof(SeqString));// 检查长度溢出if (s->length + t->length >= MAXSIZE) {printf("串长度溢出\n");free(r);return NULL;}int i;// 复制第一个串for (i = 0; i < s->length; i++) {r->ch[i] = s->ch[i];}// 连接第二个串for (i = 0; i < t->length; i++) {r->ch[s->length + i] = t->ch[i];}r->ch[s->length + t->length] = '\0'; // 添加字符串结束符r->length = s->length + t->length;return r;
}
时间复杂度：O(m + n)，其中m、n分别为两个串的长度
空间复杂度：O(m + n)，需要分配新的存储空间
求子串运算
从主串中提取指定位置和长度的子串。
SeqString *SubStr(SeqString *s, int pos, int len) {// 参数合法性检查if (pos < 0 || pos >= s->length || len < 0 || pos + len > s->length) {printf("参数超出有效范围\n");return NULL;}SeqString *t = (SeqString*)malloc(sizeof(SeqString));if (t == NULL) {printf("内存分配失败\n");return NULL;}// 提取子串for (int k = 0; k < len; k++) {t->ch[k] = s->ch[pos + k];}t->ch[len] = '\0';t->length = len;return t;
}
关键点：
- 位置索引从0开始
- 需要严格检查边界条件
- 返回的是新分配的串对象
4.模式匹配算法
模式匹配是在主串中查找模式串位置的核心算法，是串处理的重点内容。
简单模式匹配算法
也称为朴素算法或暴力匹配算法。
int SimpleIndex(SeqString *s, SeqString *t) {int i = 0, j = 0;while (i < s->length && j < t->length) {if (s->ch[i] == t->ch[j]) {i++; // 继续比较下一个字符j++;} else {i = i - j + 1; // 回溯到下一个起始位置j = 0; // 模式串重新开始匹配}}if (j == t->length) {return i - t->length; // 匹配成功，返回起始位置} else {return -1; // 匹配失败}
}
性能分析：
- 最好情况：O(n)，第一次就匹配成功
- 最坏情况：O(mn)，每次都在最后一个字符失配
- 平均情况：接近O(n)
链式存储的模式匹配
LinkString *LinkIndex(LinkString *s, LinkString *t) {LinkString *first = s; // 记录主串起始比较位置LinkString *sptr = first; // 主串当前比较位置LinkString *tptr = t; // 模式串当前比较位置while (sptr && tptr) {if (sptr->data == tptr->data) {sptr = sptr->next; // 字符匹配，继续比较tptr = tptr->next;} else {first = first->next; // 回溯到下一个起始位置sptr = first;tptr = t;}}return (tptr == NULL) ? first : NULL;
}
KMP算法优化
KMP算法通过预处理模式串，避免了不必要的回溯，显著提高了匹配效率。
// 计算next数组
void GetNext(SeqString *t, int next[]) {int i = 0, j = -1;next[0] = -1;while (i < t->length - 1) {if (j == -1 || t->ch[i] == t->ch[j]) {i++;j++;next[i] = j;} else {j = next[j]; // 利用已计算的next值}}
}// KMP模式匹配
int KMPIndex(SeqString *s, SeqString *t) {int next[t->length];GetNext(t, next);int i = 0, j = 0;while (i < s->length && j < t->length) {if (j == -1 || s->ch[i] == t->ch[j]) {i++;j++;} else {j = next[j]; // 模式串智能移动}}return (j == t->length) ? i - t->length : -1;
}
KMP算法优势：
- 时间复杂度：O(m + n)，其中m为主串长度，n为模式串长度
- 空间复杂度：O(n)，用于存储next数组
- 无回溯：主串指针不回退，提高了效率
5.数组的抽象数据类型
数组是相同数据类型元素的集合，支持多维索引访问。
ADT Array {数据对象: D = {aᵢ₁ᵢ₂...ᵢₙ | 0 ≤ iⱼ < boundⱼ, j = 1,2,...,n}数据关系: R = {相邻关系由下标序偶确定}操作集合:InitArray(&A, n, bound1, ..., boundn) // 构造数组DestroyArray(&A) // 销毁数组 Value(A, &e, index1, ..., indexn) // 取元素Assign(&A, e, index1, ..., indexn) // 赋值元素
} ADT Array
多维数组的地址计算
以二维数组为例，假设数组A[m][n]：
行优先存储：
Address(A[i][j]) = BaseAddress + (i × n + j) × sizeof(ElementType)
列优先存储：
Address(A[i][j]) = BaseAddress + (j × m + i) × sizeof(ElementType)
6.特殊矩阵的压缩存储
稀疏矩阵
稀疏矩阵是大部分元素为零的矩阵，使用三元组表示法可以大大节省存储空间。
#define MAXSIZE 100typedef struct {int row, col; // 行号和列号int value; // 元素值
} Triple;typedef struct {int rows, cols, nums; // 行数、列数、非零元个数Triple data[MAXSIZE]; // 三元组数组
} SparseMatrix;
稀疏矩阵转置
SparseMatrix *TransposeMatrix(SparseMatrix *a) {SparseMatrix *b = (SparseMatrix*)malloc(sizeof(SparseMatrix));b->rows = a->cols;b->cols = a->rows; b->nums = a->nums;if (a->nums == 0) {return b;}int currentB = 0;// 按列号顺序转置for (int col = 0; col < a->cols; col++) {for (int p = 0; p < a->nums; p++) {if (a->data[p].col == col) {b->data[currentB].row = a->data[p].col;b->data[currentB].col = a->data[p].row;b->data[currentB].value = a->data[p].value;currentB++;}}}return b;
}
算法分析：
- 时间复杂度：O(n × t)，其中n为原矩阵列数，t为非零元个数
- 空间复杂度：O(t)，与非零元个数成正比
- 适用性：当非零元个数远小于矩阵总元素数时，压缩效果显著
快速转置算法
通过预先计算每列的元素个数和起始位置，实现O(n + t)的转置。
SparseMatrix *FastTranspose(SparseMatrix *a) {SparseMatrix *b = (SparseMatrix*)malloc(sizeof(SparseMatrix));int colSize[a->cols]; // 每列非零元个数int colStart[a->cols]; // 每列在转置矩阵中的起始位置b->rows = a->cols;b->cols = a->rows;b->nums = a->nums;if (a->nums == 0) return b;// 统计每列非零元个数for (int col = 0; col < a->cols; col++) {colSize[col] = 0;}for (int t = 0; t < a->nums; t++) {colSize[a->data[t].col]++;}// 计算每列起始位置colStart[0] = 0;for (int col = 1; col < a->cols; col++) {colStart[col] = colStart[col-1] + colSize[col-1];}// 执行转置for (int p = 0; p < a->nums; p++) {int col = a->data[p].col;int q = colStart[col];b->data[q].row = a->data[p].col;b->data[q].col = a->data[p].row;b->data[q].value = a->data[p].value;colStart[col]++;}return b;
}
7.存储效率对比
不同存储方式的空间复杂度
| 存储方式 | 空间复杂度 | 适用场景 |
|---|---|---|
| 完全存储 | O(m×n) | 密集矩阵 |
| 三元组 | O(t) | 稀疏矩阵(t<<m×n) |
| 十字链表 | O(t) | 动态稀疏矩阵 |
| 压缩存储 | O(n) | 对角、三角矩阵 |
算法效率分析
| 操作 | 完全存储 | 三元组存储 |
|---|---|---|
| 随机访问 | O(1) | O(t) |
| 矩阵转置 | O(m×n) | O(n×t) |
| 矩阵加法 | O(m×n) | O(t1+t2) |
| 矩阵乘法 | O(m×n×k) | O(t1×t2×k) |
8.应用场景与选择策略
串的应用领域
- 文本处理：编辑器、搜索引擎
- 编译器：词法分析、语法分析
- 生物信息学：DNA序列分析
- 网络安全：模式匹配、入侵检测
数组的应用领域
- 科学计算：数值分析、图像处理
- 图形学：矩阵变换、3D渲染
- 机器学习：特征矩阵、权重存储
- 数据库：索引结构、关系存储
选择指导原则
串存储选择：
- 顺序存储：长度相对固定，需要高效随机访问
- 链式存储：长度变化频繁，插入删除操作多
- 索引存储：管理大量不同长度的串
数组存储选择：
- 完全存储：元素密集，需要频繁随机访问
- 压缩存储：具有特殊模式（对称、三角等）
- 稀疏存储：大部分元素为零或默认值
9.总结
串和数组作为基础数据结构，各自具有独特的特点和应用价值：
串的核心价值：
- 专门处理字符数据，支持丰富的文本操作
- KMP等高效模式匹配算法在文本处理中不可或缺
- 为编译器、搜索引擎等系统提供基础支撑
数组的核心价值：
- 提供多维数据的统一存储和访问机制
- 压缩存储技术大幅提高空间效率
- 为科学计算、图形处理等领域提供基础设施
理解这两种数据结构的设计思想和实现技巧，不仅有助于提高程序设计能力，更为学习更复杂的数据结构和算法奠定了坚实基础。在实际应用中，应根据具体的数据特征和操作需求，选择合适的存储方式和算法实现。
