数据结构（6）：串（上）

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统（如搜索引擎）、文本编辑程序（如 Word）、问答系统、自然语言翻译系统等，都是以字符串数据作为处理对象的。本文详细介绍字符串的存储结构及相应的操作。

串的定义

串（string）是由零个或多个字符组成的有限序列。一般记为

其中，S 是串名，单引号括起来的字符序列是串的值；串中字符的个数 n 称为串的长度。n=0 时的串称为空串（用∅表示）。

串中任意连续个字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

例如，有串 A='China Beijing'，B='Beijing'，C='China'，则它们的长度分别为 13，7 和 5。B 和 C 是 A 的子串，B 在 A 中的位置是 7，C 在 A 中的位置是 1。

需要注意的是，由一个或多个空格（空格是特殊字符）组成的串称为空格串（注意，空格串不是空串），其长度为串中空格字符的个数。

串的逻辑结构和线性表极为相似，区别仅在于串中的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。 

串的存储结构

大家看完定义就会明白，这不就是 Python 中的 str 数据类型吗？确实如此，所以我就不用Python 的 str 套壳实现一个串了，依旧换成 C/C++ 来实现串。

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

#define MAXLEN 255//预定义串中最大串长为 255
class SString
{
private:
  char ch[MAXLEN];//为每个分量存储一个字符
  int length;//串的实际长度
};

串的实际长度只能小于等于 MAXLEN，超过预定义长度的串值会被舍去，称为截断。串长有两种表示方法：一是如上述定义那样，用一个额外的变量 len 来存放串的长度；二是在串值后面加一个不计入串长的结束标记字符“\0”，此时串长为隐含值。

在一些串的操作（如插入、联接等）中，若串值序列的长度超过上界 MAXLEN，约定用“截断”法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。

class HString
{
private:
  char* ch;//按串长分配存储区，ch 指向串的基地址
  int length;//串的长度
};

在 C 语言中，存在一个称之为“堆”的自由存储区，并用 malloc()和 free()函数来完成动态存储管理。利用 malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由 ch 指针来表示 ；若分配失败，则返回 NULL。已分配的空间可用 free()释放掉。

上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅作简单介绍。

块链存储表示

类似于线性表的链式存储结构，也可以采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点即可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

串的基本操作

串的基本操作一共有 10 个：赋值操作、复制操作、判空操作、比较操作、求串长、求子串、串联接、定位操作、清空操作和销毁串。

我在这里基于堆分配存储表示来实现这 10 个基本操作。

赋值操作

void StrAssign(const char* chars)
  {
    length = 0;
    while (chars[length])
      length++;
    ch = new char[length + 1];
    if (!ch)
      return;
    for (int i = 0; i < length; i++)
      ch[i] = chars[i];
    ch[length] = 0;
  }

复制操作

void StrCopy(HString& T)
  {
    T.StrAssign(ch);
  }

判空操作

bool StrEmpty()
  {
    return length ? false : true;
  }

比较操作

int StrCompare(HString T)
  {
    int len = length < T.length ? length : T.length;
    for (int i = 0; i < len; i++)
    {
      if (ch[i] < T.ch[i])
        return-1;
      else if (ch[i] > T.ch[i])
        return 1;
    }
    if (ch[len])
      return 1;
    if (T.ch[len])
      return-1;
    return 0;
  }

求串长

int StrLength()
  {
    return length;
  }

求子串

void SubString(HString& Sub, int pos, int len)
  {
    if (pos + len - 1 > length)
      return;
    Sub.length = len;
    Sub.ch = new char[len + 1];
    if (!Sub.ch)
      return;
    for (int i = pos - 1, j = 0; j < len; i++, j++)
      Sub.ch[j] = ch[i];
    Sub.ch[len] = 0;
  }

串联接

void ConCat(HString S1, HString S2)
  {
    length = S1.length + S2.length;
    ch = new char[length + 1];
    if (!ch)
      return;
    int i = 0;
    for (; i < S1.length; i++)
      ch[i] = S1.ch[i];
    for (; i < length; i++)
      ch[i] = S2.ch[i - S1.length];
    ch[length] = 0;
  }

定位操作

int Index(HString T)
  {
    int i = 1;
    HString sub;
    while (i <= length - T.length + 1)
    {
      SubString(sub, i, T.length);
      if (sub.StrCompare(T) != 0)
        ++i;
      else
        return i;//返回子串在主串中的位置
    }
    return 0;//S 中不存在与 T 相等的子串
  }

清空操作

void ClearString()
  {
    ch = new char[1];
    ch[0] = 0;
    length = 0;
  }

销毁串

~HString()
  {
    delete[]ch;
    ch = 0;
  }

总结

关于串的定义和基本操作就说到这里，下一回我们来看一个有关于串的应用：模式匹配！

当然，我从今年开始已经入驻 B 站了！下面给出 B 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！

今天的文章有不懂的可以后台回复“加群”，备注：Python 机器学习算法说书人，不备注可是会被拒绝的哦~！