第4章串、数组和广义表

第4章串、数组和广义表

4.1串的定义

1. 串的定义（课件核心内容）

• 文字定义：由零个或多个字符组成的有限序列。
• 符号化表示：记作 S=′a₁a₂⋯a_n′（n≥0），其中 S 为串名，a₁a₂⋯a_n为串值，n 为串的长度。

关于“串的定义”的考试要点：

• 严谨性要求： 考试中回答定义时必须严谨。核心点是“由零个或多个字符组成”。老师特别强调，很多同学容易忽略“零个”的情况，只回答“若干个”，这是不完整的，“零个”字符也是一个合法的串。
• 两种表示形式（满分答法）： 考试中如果能同时给出以下两种形式，通常是满分标准：
  1. 文字定义： “由零个或多个字符组成的有限序列”。
  2. 符号化表示： S=′a₁a₂⋯a_n′（n≥0）。其中 n 可以等于 0，表示空串。

2. 串的术语（课件核心内容）

术语	课件定义	【老师补充讲解】
串名	串的标识（如上述 S）	通常用大写字母（如 、）表示，用于区分不同串，无实际字符意义。
串值	用单引号括起来的字符序列	单引号是串值的 “标识符号”，不属于串的组成部分；例如 ′BE**I′ 中，串值为 “BEI”。
长度	串中字符的数目	长度最小为 0（空串），最大为有限值；需注意 “空格” 算一个字符（如 ′BEIJIN**G′ 长度为 8）。
空串	含零个字符的串（记为 ∅）	空串 ≠ 空格串：空格串是由 1 个或多个 “键盘 space 键” 组成的串（如 长度为 3），属于非空串。
空格串	由一个或多个空格组成的串	空格是合法字符，需计入长度；例如课件中 d=′BEIJIN**G′ 因含 1 个空格，长度比 c=′BEIJIN**G′ 多 1。
子串	串中任意个连续的字符组成的子序列	① 关键属性：“连续”—— 非连续字符序列不属于子串（如 ′BEIJIN**G′ 中 “BJ” 不是子串）；② 任意范畴：“零个或多个字符”（零个子串即空串，多个字符需连续）。
字符在串的位置	字符在序列中的序号	序号有两种计数方式：① 从 1 开始（常用，如 ′BE**I′ 中 “B” 位置为 1）；② 从 0 开始（编程中常见，如 ′BE**I′ 中 “B” 位置为 0），需结合场景判断。
子串在串的位置	子串的第一个字符在串中的位置	例如 ′JIN**G′ 在 ′BEIJIN**G′ 中位置为 4（从 1 计数），因第一个字符 “J” 在原串第 4 位；注意不是子串最后一个字符的位置。
相等	当且仅当两个串的值相等	需同时满足 “长度相等”+“对应位置字符完全一致”；例如 ′ABC′\=′ABD′（第 3 位字符不同），′A**B′\=′ABC′（长度不同）。

关于“串的术语”详解：

• 串值 (String Value)： 注意是用单引号括起来的字符序列（例如 'abc'），这是表征串值的标准方式。
• 空串 (Empty String)： 长度为 0，不含任何字符。
• 空格串 (Blank String)： 千万别混淆！ 空格串不是空串。它是由一个或多个“空格字符”（键盘上的 Space 键）组成的串。空格也是字符，占用长度。
• 子串 (SubString) 的核心定义：
  • 定义：串中任意个、连续的字符组成的子序列。
  • 关键点 1 “任意个”： 这里的“任意”范围是零个或零个以上。零个字符（空串）也是任意串的子串。
  • 关键点 2 “连续”： 这是判断是否为子串的最核心标准。必须是原串中连续在一起的一段字符，不能跳着取。
• 位置 (Position)：
  • 字符位置： 指的是序号。注意序号可能从 0 开始（计算机习惯），也可能从 1 开始（人类习惯），具体看题目约定。
  • 子串位置： 指的是该子串在主串中第一个字符出现的位置（首字符索引）。

3. 串的举例（课件核心内容）

课件示例：a=′BEI′、b=′JING′、c=′BEIJING′、d=′BEIJING′

• 长度：分别为 3、4、7、8；

• 子串关系：a 和 b 均是 c 和 d 的子串；

• 位置：a 在 c 和 d 中位置均为 1；b 在 c 中位置为 4，在 d 中位置为 5（因 d 中 “BEI” 后有 1 个空格，“J” 在第 5 位）；

• 相等判断：a、b、c、d 彼此不相等（长度或串值不同）。

• 空格的影响：d 因含 1 个空格，长度比 c 多 1，且 b 在 d 中的位置比在 c 中多 1，需注意空格对 “位置” 和 “长度” 的影响；

• 考试常见题型：给定多个串，判断子串关系、计算长度或位置，需重点关注空格字符。

4. 串的比较（课件核心内容）

串的比较： 通过组成串的字符之间的比较来进行的。

给定两个串：X='x₁x₂...x_n' 和Y='y₁y₂...y_n' ，则：

• 当n=m且 x₁=y₁, ..., x_n=y_n 时，称 X=Y;

• 当下列条件之一成立时，称 X < Y:

  • n<m且 x_i=y_i(1 ≤ i ≤ n);
  • 存在 k ≤ min(m,n)，使得 x_i=y_i(1 ≤ i ≤ k-1)且 x_k<y_k。

串比较的核心规则（通俗理解）：

• 对应字符比较： 两个串（串 1 和串 2）从第一个位置开始，两两比较相同位置上的字符。

• 停止时机： 一旦发现相同位置上的字符不一样，立即停止比较。

• 大小判定： 停止位置上，哪个字符的 ASCII 码大，所在的那个串就大。

  • ASCII_差 = 0 →字符相等。

  • ASCII_差 < 0 → 前者小。

  • ASCII_差 > 0 → 前者大。

• 重要误区： 串的大小绝不是比长度！ 并不是字符串越长就越大。例如 "A..." 很长，但只要第一个字符比对方小，整个串就小。

形式化定义详解（考研/科研基础）： 老师强调要掌握这种“形式化语言”，这是将文字描述转化为公式推理的基础。

• 相等 (\(X=Y\))： 必须满足两个条件：① 长度相等 (n=m)；② 对应位置字符完全一致。
• 小于 ( X < Y) 的两种情况：
  • 情况 1（前缀相同，X 短）：X的所有字符都和 Y 的前 n 个字符一样，但 X 比 Y短 (n<m)。
    • 例子： X='ABC', Y='ABCD'。X 是 Y 的前缀，且更短，所以 X< Y 。
  • 情况 2（出现字符差异）： 在第k个位置首次出现不同 (x_k≠_y__k)，而在 k 之前的所有字符都相同。如果此时 x_k<y_k，则 X< Y 。
    • 例子 1： X='ABC', Y='ZHYK'。第 1 个字符 'A' < 'Z'，直接判定 X< Y。
    • 例子 2： X='ABCDEFG...'(很长), Y='ZHY'。第 1 个字符 'A' < 'Z'，依然是 X< Y，与长度无关。

5.串与线性表的区别（课件核心内容）

对比维度	串	线性表
数据对象	仅限定为字符集（如 ASCII 字符、Unicode 字符）	无限制（可是数字、结构体、字符等任意数据类型）
基本操作对象	以 “串的整体” 为单位（如查找子串、插入子串、删除子串）	以 “单个元素” 为单位（如查找单个元素、插入单个元素、删除单个元素）

为什么把“串、数组、广义表”放在一章？

• 这一章展示了从线性到非线性，再到统一范式的演变。
• 串： 简单的线性结构。
• 数组： 一维数组是线性，二维及以上是非线性，但结构规整。
• 广义表： 是本章的升华。它可以包含异构数据（原子或子表），能将线性结构（串、数组）和非线性结构（树、图）统一到一个框架（范式）下进行表示。

考试要求：

• 串： 掌握 BF 和 KMP 算法。
• 数组： 掌握两类操作——压缩（特殊矩阵、稀疏矩阵）和表征（地址计算）。
• 广义表： 理解其递归定义和基本运算（Head/Tail）。

参考资料：教材《数据结构 C 语言 第 3 版》 数据结构考研指导（基础篇） 、数据结构考研指导（基础篇） 视频课程｜赵海英