第四章 串

专业基础►数据结构 评论

第四章 串

串的定义

  • 串：

    • 串也是一种线性表

  • 串相等：

    • 长度相等且对应位置相等。
    • 所有的空串相等。

  • 子串：

    • 类似子集的定义。

  • 基本运算：

串的存储结构

  1. 顺序串：用顺序存储结构（数组）存储，且为存储结构为定长。
  2. 堆串：用顺序存储结构存储，但存储结构的长度是根据串的长度来动态分配的。
  3. 块链串：用链式存储结构来存储。

串的顺序存储结构（顺序串）

串的顺序存储结构的定义

  • 两种类型：
    • 紧缩格式
    • 非紧缩格式
  • 结点定义（下面讨论的都是非紧缩）

串的顺序存储结构的基本运算

顺序串的插入

  • 先判断插入位置是否合理
  • 之后判断能否完全插入一个串
    1. 若两个串合起来的长度s->len +t.len也小于s的最大长度，则可以完全插入
    • 第一步先将原串pos位置及以后的字符向后平移(即复制到后面的位置上去）；
    • 然后将要插入的串依次赋值到pos位置及它之后空出来的位置上；
    • 最后修改整个串的长度，即两串的长度相加。
    1. 若插入后只能保存t串的字符(二串相加的总长度大于最大长度，但pos位置后留的位置比t串的长度长)
    • 第一步还是先将s串自pos位开始的字符向后平移，但要给t串留出足够空间，即s串能移多少算多少；
    • 第二步将t串复制进来；
    • 最后串的长度就是s的最大长度。
    1. 若插入之后只能保存t串的部分字符（即pos后的位置在不移s串元素过去的情况下，仍然比t串短）
      • 直接将t串复制到pos位置及以后，到最大长度为止，能复制多少算多少。
      • 最后串的长度就是最大长度。
顺序串的删除

  • 先判断删除位置和个数是否合理：pos位置既不能超出边界，在加上要删除的位数之后也不能超出边界pos > (s->len - k)
  • 先找到待删除区域外的第一个元素，然后依次向前复制，直达到达串的边界。
  • 最后修改串的长度。
顺序串的比较
  • 比较规则：
    • 先不管长短，先比较共同区域内元素的大小；
    • 若共同区域内的元素全都相同，再比较串的长短。（即可能会出现较短的串是较大串的情况）
  • 具体算法：
    • 先找出共同长度（即较短串的长度）;
    • 之后在共同长度内比较；
    • 若共同长度内字符全部一致，则再比较长度。

堆串

堆串的定义

  • 为每个串动态分配空间（这个存储空间的实质是一个数组）储存该字符串的信息，然后设置一个指向该串的指针作为串名。每次对字符串进行增删操作就直接分配新的存储空间，释放原来的空间，修改空间的长度。看堆串的插入能够更好理解堆串的本质。
  • 与普通的顺序串相比，堆串每次存储字符串的空间是定量(根据字符串实际的长度）再分配的,而不是直接提前规定好存储字符串的空间的长度（即数组的MaxSize）。
  • 堆的定义
    typedef struct
{
  char* ch; //指示串的起始地址，即为串分配一个空间，指向这个空间的指针为ch
  int len; //指示串的长度
}HString;
    • 一个堆即一个堆串的一个基本单元

堆串的基本操作

堆串赋值

  • 先要判断串是否不为空，如果是的话，就释放原来的空间，等待重新分配。
  • 之后将要赋值进来的字符数组的长度计数出来，以便可以分配对应长度的空间。
  • 分配一个长度相同的空间，然后用ch指针指向它;
  • 如果要赋值进来的的字符数组是空的，则将ch指针置为NULL。
堆串的插入

  • 先分配一个长度为二串相加的存储空间；
  • 插入操作：
    1. 将原串pos位置之前的字符复制到新的存储空间里;
    2. 在新存储空间的pos位置开始（包含pos位置）,将带插入的串复制进去；
    3. 在之后将原串的剩余部分复制进去。
    • 注意：临界点的判断条件，例如复制待插入的串是从pos位置开始的，即原来的pos位置被新的字符占领了，原来处于pos位置的字符相对的向后移。
  • 最后修改表示长度的len变量；释放原串的存储空间，将指示串位置的ch指针指向新分配的空间。
  • 该基本思想还可以用来实现两串的连接。
堆串的复制

  • 分配新空间，顺序复制字符，修改长度变量即可。
堆串的判空

  • 判断长度是否为0来判读堆串是否为空；
堆串的比较

  • 先逐字符比较，若仍未出结果再比较长度。
堆串的清空

  • 先释放堆串的空间，再将指针置为NULL，长度设为0；
求堆串的子串

  • 先要判断求的子串的长度和位置是否合理；
  • 之后再将子串复制进一个新的堆串中。
堆串的子串定位

  • 先从两个字符串的第一个字符开始比较，若字符相等，则依次比较二者的下一个字符；
  • 若字符不相等，则将原串的下标回溯到第一个字符的下一位，子串的下标归为0继续在比较。即相当于对应原串的每一个字符都可以生成一个子串，每个字符对应的子串都要与目标子串比较，直到找到目标子串。
  • 比较结束的条件是目标子串已遍历完,最后返回子串第一个字符的位置（即当前下标位置i减去子串的长度j或者t.len）。

块链串

  • 块链串即使用链表储存字符串，每一个结点存储一部分字符(类似一句话是整个字符串，而一个结点相当于一个单词)。然后使用next指针连接结点，串成一个大的字符串。
  • 块链串结点定义：
    • 一个结点中包含一个数据域（char类型的数组）和一个指针域（指向下一结点）。
    • 设置一个储存块链串信息的结构，其中包含该串头结点，尾结点，和长度的信息。
    • 块链串没有设置空的头结点。

串的模式匹配

  • 在一个串中找到它的子串的位置称为串的模式匹配

Brute-Force(蛮牛)匹配算法

  • 简称为BF算法，又名简单匹配算法。

  • 基本思想：穷举

  • 算法实现：

    • 先从两个字符串的第一个字符(若pos不为0,则原串从pos位置开始比较）开始比较，若字符相等，则依次比较二者的下一个字符；
    • 若字符不相等，则将原串的下标回溯i = i - j + 1到第一个字符的下一位，子串的下标归为0继续在比较。即相当于对应原串的每一个字符都可以生成一个子串，每个字符对应的子串都要与目标子串比较，直到找到目标子串。
    • 比较结束的条件是目标子串已遍历完,最后返回子串第一个字符的位置（即当前下标位置i减去子串的长度j或者t.len）。

  • 算法分析：

    • 最好情况下的时间复杂度（即原串的第一个字符就可以找到子串）😮(m),其中m为子串的问题规模。
    • 最坏情况下的时间复杂度：O(n x m) ,其中n为原串的问题规模。
    • 平均的时间复杂度：O(n x m)。

KMP匹配算法

  • KMP是三个提出该算法的人的名字的首字母缩写。KMP算法相对于BF算法，主要消除了原串指针的回溯。

  • 算法的思想：（i,j均采用数组的下标表示法）

    1. 若子串没有重复的字符，则当扫描到j位因为字符不相等而退出一轮扫描的时候，说明原串第i位(扫描结束时，j == i)之前的字符与子串第j位之前的字符相等，又因为子串中没有相同的字符，所以子串的的首位字符与原串的前i位字符不相等，所以直接省去子串首字符与原串前i位字符相比较的步骤，跳到与原串第i位开始的字符相比较。这个过程中，j又回溯到了子串首字符，而i没有回溯直接继续向前推进。
    2. 若子串中有重复的字符，则若继续按照没有重复字符的方法，在原串第i位前可能与子串首字符相等的字符就会直接失去比较机会，而实际上它们是有可能与子串匹配的。故此我们先记录下子串中不同字符位置前的字符相等情况（通过创建next数组）,将每一次比较终止第j位前的字符分为三种类型：
      1. 若j位前的字符无重复情况，则j回溯为到首字符,跳到与原串第i位后的字符继续比较（同整个子串无重复字符的情况类似）;
      2. 若第j位前的字符前缀与后缀相同（即像：abcab,或者aa,或者aba等）,则j回溯到前缀后的第一位字符，该字符与原串的第i位字符继续比较。因为前缀等于后缀，而原串与子串的这一部分字符相等，所以前缀与原串第i位前的相同长度的部分字符相等，所以可以直接跳过前缀与其的比较，直接进行前缀后的第一个字符与原串的第i个字符的比较。
      3. 若第j位前的字符中有相等的情况，但是没有出现前后缀相等的情况（即像：abcdae）,此时j回溯到子串的首字符，然后继续与原串第i位字符开始比较。因为既然子串第j位前字符没有前缀与后缀相等的情况，又有原串的第i位字符前的的字符与子串相同长的字符相等，故与字符开头的部分字符不相等，所以可以直接跳过。例如：子串为abcdaef,原串为abcdaegabcdaef,第一次比较在子串的f位置，原串的g位置停下，若担心漏掉第二次a出现的情况，子串的首字符a与原串的第二个字符a开始比较，肯定是不能匹配成功的。

  • next值的求法：

    • 思想：

      • next取值的三种情况，其中其它情况对应着字符无重复，和字符没有形成相等的前后缀的情况。
      • next[j] = -1说明，子串的第j位之前没有任何用于加速匹配的信息（因为此时才开始扫描子串的首字符）,下一趟应从子串的开头j++ => j=0开始匹配。
      • next[j]的值取决于前缀的长度，因为在有前缀的情况下，next[j]代表前缀后第一个字符的下标。
      • 示例：

    • 求next的算法：

      • j的值一直在增加（中间会有停顿，但不会回缩），而k的值则再-1，0,和其它数之间循环；
      • 每遇到一个没有与前面的字符重复的字符，k都会回退到-1。
      • 要想理解这个算法只有用一个字符串来走来试试（如aabaacd）,词穷了，实在难以用语言描述。。。

  • KMP算法实现：

    • 先挨个字符比较，直到遇到不同的字符终止。之后j根据next修改，i不变，再继续比较。
    • 最后返回匹配到的子串的首字符的下标i - t.len,因为最后一次比较后i还再加了一次，所以直接减去子串的长度即为首字符的下标。

  • KMP算法分析：

    • 平均时间复杂度：求next数组的时间复杂度为O(m),后面的匹配中时间复杂度为O(n)，所以总的平均时间复杂度O(n+m)。

  • KMP算法的改进

    • 在计算出next值得同时，如果该位字符与它的next值指向的另一位字符相等，则该位的字符的nextval就指向另一位字符的nextval，如果不等，则该位字符的nextval值就是原来的next值。
    • 解决的问题：
    • 求nextval的算法
      • 在原来的基础上增加了将nextval的值修改为与其next指向的相等的字符的nextval值。
    • KMP算法的改进实现：
      • 除了将next改为了nextval没有任何区别。

Zestaken计算机小白一枚

吾好梦中读书~