一、串的基本概念
1. 串的定义
- 串是零个或多个字符组成的有限序列。
- 记为：
S = "a₁ a₂ ... aₙ"（n ≥ 0）。 - 串中的数据元素只能是单个字符，这使得串是一种特殊的线性表。
2. 串的长度
- 指串中所包含的字符总个数（含空格、标点等所有字符）。
- 长度为0的串称为空串。
3. 空串与空格串
| 概念 | 定义 | 长度 |
|---|---|---|
| 空串 | 不包含任何字符的串，记为 "" |
0 |
| 空格串 | 由一个或多个空格组成的串 | 空格个数 |
- 两者完全不同：空串无任何字符，空格串由空格字符构成。
4. 子串相关概念
- 子串：串中任意个连续的字符组成的子序列（强调连续性）。
- 主串：包含子串的原始串。
- 空串是任意串的子串。
- 任意串是自身的子串。
- 串中任意个字符组成的子序列若不连续，不是子串。
5. 两个串相等的条件
- 两串长度相等，且对应位置上的字符完全相同。
二、串的存储方式
1. 三种主要存储方式
| 存储方式 | 特点 |
|---|---|
| 顺序存储 | 用一组连续的存储单元存放字符序列；串长较短时最节省空间 |
| 链式存储 | 用链表存放，每个结点可存储一个或多个字符 |
| 堆分配存储 | 动态分配内存，是一种动态存储结构 |
2. 串值在C语言中的表示
- C语言中以字符数组存储串，以
'\0'作为串值的终结标志。 - 字符串常量用双引号括起来（如
"abc"），不能用单引号。
三、串的基本操作与通用方法
1. 核心操作函数汇总
| 操作 | 函数原型（示意） | 说明 |
|---|---|---|
| 求串长 | StrLength(S) |
返回串S的字符个数 |
| 串连接 | ConcatStr(S1, S2) |
将S2紧接在S1末尾，得到新串 |
| 求子串 | SubStr(S, pos, len) |
返回从S的第pos位起长度为len的子串 |
| 串比较 | StrCompare(S1, S2) |
按字典序比较两串大小 |
| 定位/模式匹配 | Index(S, T) 或 StrIndex(S, T) |
返回子串T在主串S中首次出现的位置 |
| 替换 | Replace(S, T, V) |
将S中的子串T替换为V |
2. 各操作注意要点
(1) SubStr 求子串——位置从1开始计
SubStr(S, pos, len) 表示从第 pos 个字符开始取 len 个字符。
- 示例：
S = "morning"，SubStr(S, 2, 2)="or"。 - 示例：
S = "Data Structure"，SubStr(S, 6, 3)="Str"（第6个字符是'S'）。
(2) ConcatStr 串连接——直接拼接，不加空格
ConcatStr(S1, S2) 将S2直接拼在S1后面。
- 示例：
S1 = "Good"，S2 = "Morning"，ConcatStr(S1, S2)="GoodMorning"（中间无空格）。
(3) StrCompare 串比较——字典序
- 从第一个字符开始逐个比较字符的ASCII码。
- 当首次出现不同字符时，ASCII码大者所在串更大。
- 若直到某一串结束都相等，则较长的串更大。
- 若长度相等且每个字符都相等，则两串相等。
(4) 模式匹配（串定位）
- 求子串在主串中首次出现的位置，称为模式匹配。
- 示例：
T = "abccdcdccbaa"，P = "cdcc"，从主串T中寻找P首次出现的位置，在第6位匹配成功。
四、复杂嵌套函数运算的通用解法
对于多个串函数嵌套的题目，从最内层括号开始，逐层向外计算。
例1（第14题）
已知 S1="ABCDEFG"，S2="PQRST"，求：
ConcatStr(SubStr(S1, 2, LenStr(S2)), SubStr(S1, LenStr(S2), 2))
逐步求解：
LenStr(S2) = 5SubStr(S1, 2, 5)：从第2位取5个字符 →"BCDEF"SubStr(S1, 5, 2)：从第5位取2个字符 →"EF"ConcatStr("BCDEF", "EF")="BCDEFEF"
例2（第17题）
已知 S1='ABCDEFG'，S2='9898'，S3='###'，S4='012345'，求：
Concat(Replace(S1, SubStr(S1, Length(S2), Length(S3)), S3), SubStr(S4, Index(S2, '8'), Length(S2)))
逐步求解：
Length(S2) = 4Length(S3) = 3SubStr(S1, 4, 3)：从S1第4位取3个字符 →"DEF"Replace(S1, "DEF", S3)：将S1中的"DEF"替换为"###"→"ABC###G"Index(S2, '8')：字符'8'在S2中首次出现的位置 → 1SubStr(S4, 1, 4)：从S4第1位取4个字符 →"0123"Concat("ABC###G", "0123")="ABC###G0123"
五、子串个数的计算方法
问题：长度为n的串，其最大子串（含空串和自身）个数是多少？
通用公式：
- 长度n的串，非空子串数 =
n(n+1) / 2 - 含空串的总子串数 =
n(n+1) / 2 + 1
推导思路：
- 子串由起始位置和结束位置唯一确定。
- 长度为1的子串有n个，长度为2的有n-1个，...，长度为n的有1个。
- 非空子串总数 =
1+2+...+n = n(n+1)/2。
示例（第16题）：S="abcdefgh"，n=8。
- 非空子串数 =
8×9/2 = 36 - 含空串总子串数 =
36 + 1 = 37
六、串的删除算法要点
从串S的第i个位置开始删除连续l个字符，核心步骤：
- 将第
i+l位开始的字符逐个前移。 - 移动代码：
S->ch[i-1] = S->ch[k]（其中k从 i+l-1 开始递增，i从第i-1位置开始递增）。 - 更新长度：
S->len = S->len - l。 - 末尾添加
'\0'结束符。
七、易混判断题辨析
| 判断内容 | 正误 | 知识点 |
|---|---|---|
| 串的数据元素是一个字符 | 对 | 串是特殊的线性表，每个数据元素是单个字符 |
| 空串是由空格构成的串 | 错 | 空串不含任何字符，长度为0；空格串由空格组成 |
| 空串与由空格组成的串没有区别 | 错 | 同上 |
| 空串是任意串的子串 | 对 | 空串是子串的特殊情况 |
| 子串的定位运算称为模式匹配 | 对 | 模式匹配就是求子串首次出现的位置 |
| 串中任意个字符组成的子序列称为该串的子串 | 错 | 必须是连续的字符序列，不是任意子序列 |
| 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串 | 错 | 子串要求连续且顺序一致，仅字母包含不够 |
| 串的堆分配存储是一种动态存储结构 | 对 | 堆分配即动态内存分配 |
| 在顺序存储结构中，串的插入算法是非常方便的 | 错 | 顺序存储插入需移动大量元素，不方便 |
八、知识速记卡
- 串长：含所有字符（空格也算），
'\0'不计入长度。 - 空串 vs 空格串：空串长度0，空格串长度=空格个数。
- 子串：必须是连续的字符子序列，空串是任何串的子串。
- 连接：直接拼接，中间无额外空格。
- 模式匹配：求子串在主串中首次出现的位置。
- 嵌套函数：从内向外逐层计算。
- 子串个数：非空
n(n+1)/2，含空n(n+1)/2 + 1。