串String

  • 子串在主串中的位置以子串的第一个字符在主串位置表示

o 串的匹配

  • Brute-Force算法（暴力匹配） 略

  • KMP算法

堆串

  • 堆串存储方法

    • 以一组地址连续的存储单元顺序存放串中的字符,但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间,每当建立一个新串时,系统就从这个空间中分配一个大小和字符串长度相同的空间用于存储新串的串值。

  • 串名符号表:

    • 所有串名的存储映像构成一个符号表。借助此结构可以在串名和串值之间建立一个对应关系,称为串名的存储映像。

块链串

  • 结点大于1：当BLOCK_SIZE大于1时,每个结点存放多个字符,当最后一个结点未存满时，不足处可用特定字符(如#)补齐。虽然存储密度相对结点大小等于Ⅰ的存储方法来说,存储密度较高,但此时插人﹑删除的处理方法比较复杂,需要考虑结点的分拆和合并。