数据结构——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"、"ro"等都是其子串
  
• 包含关系: 空串是任何字符串的子串
  

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
  ="ro"毗连后 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)）是后续学习的核心内容