数据结构_4串

参考王道计算机考研《数据结构》课程，自主进行知识点归纳总结，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

串

• 串的定义和基本操作
  • 定义
    • 概念
      • 串长、空串、空格串、子串、主串
        • S=”HelloWorld!” T=‘iPhone 11 Pro Max?’ 子串：串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’ 是串T 的子串 主串：包含子串的串。 Eg：T 是子串’iPhone’的主串 字符在主串中的位置：字符在串中的序号。 Eg：’1’在T中的位置是8(第一次出现) 子串在主串中的位置：子串的第一个字符在主串中的位置
      • 字符在主串中的位置、子串在主串中的位置
        • 位序从1开始而不是从0开始 子串在主串中的位置 返回子串在主串s中第一次出现的位置 第一次出现的子串的首字符在主串的位置
    • 串（字符串）是由零个或多个字符组成的有限序列
  • 串V.S线性表
    • 串的数据对象
      • 限定为字符集
    • 串的基本操作
      • 大多以"子串"为操作对象
  • 基本操作
    • 串的定位操作
      • Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
    • 串的比较操作
      • StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0
      • 从第一个字符开始往后依次对比，先出现更大字符的串就更大
        • 
      • 长串的前缀与短串相同时，长串更大
        • (后面有空格，空格也是字符)
      • 只有两个串完全相同时-->相等(长度以及内容)
    • 其他操作4.1.1 P4 PPT
  • 字符集编码
    • 每个字符在计算机中对应一个二进制数
      • y = f(x) 字符集：函数定义域 编码：函数映射规则f y：对应的二进制数
    • 比较字符的大小<--->比较二进制数的大小
• 串的存储结构
  • 顺序存储
    • 静态数组
      • 
    • 动态数组
      • malloc、free
  • 链式存储
    • 可让每个结点存多个字符，没有字符的位置用'#'或'\0'(特殊)补足
  • 王道教材所采用的静态数组
    • 
    • ch[0]废弃不用(字符的位序和数组下标相同)
    • int型Length变量(可表达更大的串长)
  • 基本操作的实现
    • 求子串
      • 函数原型
        • bool SubString(SString &Sub,SString S,int pos,int len)
    • 串的比较
      • int StrCompare(SString S,SString T)
      • 不同情况
        • 由左自右依次扫描两个字符串，直到扫描到两个字符串第一个不相同的字符 判断这两个字符的ASCII码，返回比较值大小 注：不相同的情况 1. 都为字符但不相同 2. 其中一个字符串该位置上是字符，另一字符串该位置上已经结束(没字符)
        • S=T（返回值等于0）
        • S>T（返回值大于0）
        • S<T（返回值小于0）
        • 特殊情况②③(S与T长度不相等)
          • 长串的前缀与短串相同时，长串更大 (后面有空格，空格也是字符)
    • 求串在主串中的位置
      • int Index(SString S,SString T)
      • 思路
        • 在主串中从第一个字符开始依次取与所求子串相同长度的子串
        • 比较所取子串与所求子串是否相同