数据结构——D/串

一、串的定义和基本操作



1. 串的定义





1）串的概念





• 组成结构: 串是由零个或多个字符组成的有限序列，记为

  S=′a1a2⋯an′S='a_1a_2\cdots a_n'S=′a1​a2​⋯an′​

  （

  n≥0n \geq 0n≥0

  ），其中

  SSS

  是串名，

  aia_iai​

  可以是字母、数字或其他字符
• 长度特性: 串中字符的个数

  nnn

  称为串的长度，

  n=0n=0n=0

  时的串称为空串（用

  ∅\emptyset∅

  表示）
• 边界符说明: 单引号或双引号只是边界符，不计入串长度（如"Hello World!"长度为11）
• 编程语言差异: Java/C使用双引号，Python使用单引号表示字符串

2）子串





• 定义: 字符串中任意连续字符组成的子序列（包括空串）
• 示例特性: 从主串"iPhone 11 Pro Max"中，"11 Pro"、"Pro"等都是其子串
• 包含关系: 空串是任何字符串的子串

3）字符





• 位置编号: 字符在主串中的位置从1开始计数（与线性表位序一致）
• 空格处理: 空格也是有效字符（如"11 Pro"中空格是第3个字符）
• 存储大小: 每个字符占1字节（8比特），跨考同学需特别注意

4）子串在主串中的位置



• 定位规则: 以子串第一个字符在主串中的位置作为子串位置
• 示例说明: 子串"11 Pro"在主串"iPhone 11 Pro Max"中的位置是8（'1'的位置）

5）空串和空格串的区别





• 空串: 长度为零的串（如

  M=′′M=''M=′′

  ）
• 空格串: 包含空格字符的串（如

  N=' '

  长度为3）
• 存储差异: 空串不占存储空间，空格串占用与空格数对应的存储空间

2. 串与线性表的区别





• 元素限制:
  • 线性表：元素可为任意数据类型
  • 串：元素限定为字符（中英文字符、数字、标点等）
• 操作对象:
  • 线性表：以单个元素为操作单位
  • 串：通常以子串为操作单位（如搜索引擎处理字符串）
• 实际应用: 字符串操作更符合人类语言处理需求（需多个字符组合表达语义）

3. 串的基本操作





1）判空操作





• 实现方式: 判断字符串长度是否为0
• 返回值: 空串返回true，非空返回false

2）销毁串





• 与清空区别:
  • 清空：仅逻辑清空，保留存储空间
  • 销毁：回收存储空间，不可再次使用
• 内存管理: 销毁操作涉及动态内存释放机制

3）串的连接





• 操作示例:

  SSS

  ="iPhone"，

  WWW

  ="Pro"连接后

  TTT

  ="iPhonePro"
• 存储考虑: 频繁连接需设计可扩展的存储结构

4）求子串





• 

• 参数指定: 需要起始位置和子串长度
• 边界处理: 需验证参数有效性（如起始位置+长度不超过主串长度）

5）定位操作





• 功能描述: 查找子串在主串中首次出现的位置
• 返回值: 找到返回位置序号（从1开始），未找到返回0
• 算法核心: 依赖子串匹配算法实现

6）比较操作





• 比较规则:
  • 逐字符比较ASCII码值
  • 先出现较大字符的串更大
  • 全相同则较长串更大
• 返回值约定:

  • S>TS>TS>T

    返回正值

  • S=TS=TS=T

    返回0

  • S<TS<TS<T

    返回负值
• 字典序原理: 基于字符在编码表中的二进制值比较（如'a'<'o'因ASCII码97<111）

4. 字符集编码



1）字符与二进制数的对应关系





• 存储原理: 计算机只能存储二进制数，所有字符必须通过编码规则转换为二进制形式存储
• 映射关系: 每个字符对应唯一的二进制数，如字母'a'存储为高四位0110加低四位0001的组合

2）ASCII编码示例





• 编码结构: ASCII码使用8位二进制数（1字节）表示，分为非打印控制字符（0-31）和可打印字符（32-127）
• 输入方式: 可通过ALT+小键盘数字键输入，如ALT+65输入大写字母'A'

3）字符比较与二进制数的关系





• 比较机制: 计算机直接比较字符对应的二进制数值大小，如'c'（01100011）>'a'（01100001）
• 实际应用: 英文字典排序本质是二进制数的升序排列

4）空格串与空串的区别





• 空格串: 对应二进制00100000，占用1字节存储空间
• 空串: 无实际字符内容，不占用存储空间（NULL）

5）字符集的概念





• 集合定义: 特定语言所有字符的集合，如ASCII包含英文字母、标点符号等128个字符
• 扩展需求: 中文等语言字符量远超256个，需要更大字符集

6）不同字符集的编码需求



• 容量限制: 8位二进制仅能表示256种状态，无法满足中文需求
• 解决方案: Unicode字符集包含全球文字符号，如中文"任"字需要更长的二进制编码

7）编码规则与字符集映射





• 数学模型: 字符集为定义域（x），编码规则为映射函数（f），二进制数为值域（y）
• 编码方案: 同一字符集可有多种编码规则（如UTF-8、UTF-16），对应不同二进制表示

8）编码方案的选择与字符空间占用





• 空间差异: ASCII每个字符占1字节，UTF-8中文字符占3字节
• 考研重点: 只需掌握英文字符的1字节存储情况

5. 拓展乱码问题





1）乱码问题的产生原因





• 核心原因: 文件存储与读取使用不同编码规则，如存储用

  y=f(x)y=f(x)y=f(x)

  而读取用

  y=g(x)y=g(x)y=g(x)

• 实例说明: "码"字在规则A中编码为0101...，在规则B中可能解码为完全不同的字符

2）从函数角度理解乱码问题





• 数学模型: 正确解码需使用原编码规则的反函数

  x=f−1(y)x=f^{-1}(y)x=f−1(y)

• 错误本质: 实际使用了错误的逆映射

  g−1(y)g^{-1}(y)g−1(y)

  导致字符解析失败

3）字符串基本概念回顾





• 术语定义:
  • 串长：字符串包含的字符数量
  • 子串：主串中连续字符组成的片段
  • 位置：字符/子串在主串中的序号（从1开始）

4）字符串比较与字符集编码



• 比较规则: 按字符编码值逐位比较，类似字典序排列
• 操作重点: 子串定位算法（如Index(S,T)）是后续学习的核心内容