串

1. 考点：串的基本概述

1.1 串的定义

• 基本概念​：串（String）是仅由字符构成的有限序列，本质上是一种特殊的​线性表。

• 表示方法：一般记为：

  $$S = 'a_1a_2a_3 \dots a_n$$

  • 其中，$S$ 是​串名。
  • 单引号括起来的字符序列 $a_1a_2a_3 \dots a_n$ 是​串值。
  • $n$ 为串的长度（即字符个数），当 $n = 0$ 时称为​空串。

1.2 串的存储结构

与线性表类似，串主要也有两种存储方式：

1. 顺序存储：用一组地址连续的存储单元来依次存放串中的字符序列。
2. 链式存储：用链表来存放串值（每个节点可以存放一个或多个字符），灵活性高但存储密度相对较低。

1.3 串的几个基本概念

1.3.1 1. 空串与空格串

• 空串：长度为零，不包含任何字符。
• 空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。

1.3.2 2. 子串与子序列

• 子串 (Substring) ​：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。

  • 子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。
  • 空串是任意串的子串。

• 子序列 (Subsequence) ：一个串的“子序列”是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系（注意：子序列中的字符在原串中不一定需要是连续的）。

1.3.3 3. 串比较与串相等

• 串比较：

  • 两个串比较大小​以字符的 ASCII 码值（或其他字符编码集合）作为依据。
  • 比较规则：从两个串的第一个字符开始逐个进行对比，字符的码值大者所在的串为大。
  • 长度不同时的规则​：若其中一个串先结束（即短串是长串的前缀），则以​串长较大者为大。

• 串相等​：指两个串长度相等且​对应序号的字符也完全相同。

2. 考点：串的基本 操作

2.0.1 赋值操作 ​StrAssign(s, t)

• 功能：将串 $s$ 的值赋给串 $t$。

2.0.2 连接操作 ​Concat(s, t)

• 功能：将串 $t$ 接续在串 $s$ 的尾部，形成一个新的串。

2.0.3 求串长 ​StrLength(s)

• 功能：返回串 $s$ 的长度（即字符个数）。

2.0.4 串比较 ​StrCompare(s, t)

• 功能：比较两个串的大小。
• 返回值：返回值 $-1$、$0$ 和 $1$ 分别表示 $s < t$、$s = t$ 和 $s > t$ 三种情况。

2.0.5 求子串 ​SubString(s, start, len)

• 功能：返回串 $s$ 中从 ​start​ 开始的、长度为 ​len 的字符序列。

3. 经典例题

3.1 题目一

题目： 下列有关字符串的描述中，说法正确的是（ B ）。

• A. 空串就是指含有空白字符构成的串
• B. 子串是指任意个连续的字符组成的子序列
• C. 子序列是特殊的子串
• D. 字符串的比较实质就是两个串的长度对比

详细解析：

1. 选项 A 错误：

   • 空串是指长度为零、不包含任何字符的串（长度 $n = 0$）。
   • 由一个或多个空格组成的串称为​空格串，空格串的长度不为零。两者概念不同。

2. 选项 B 正确：

   • 子串的定义正是指主串中任意长度的连续字符构成的序列，符合数据结构中的标准定义。

3. 选项 C 错误：

   • 应该是“​子串是特殊的子序列”。
   • 子串要求字符必须是连续的；而子序列只要求保持相对位置不变，字符可以是不连续的。因此，任意子串都属于子序列，但子序列不一定是子串。

4. 选项 D 错误：

   • 字符串的比较大小是以字符的 ​ASCII 码值（或其他字符编码）从前往后逐个对比决定的，只有在短串是长串的前缀且完全相同时，才会比较串的长度。因此不能说其实质就是长度对比。

正确答案：B。

‍