三、字符串和矩阵

三、字符串和矩阵

1. 字符串

1.1 字符串的按需（堆）存储结构

实现：

//字符串的类
class HString  //只一种类型，不需要模板
{
  friend class BMMatching;
private:
  char *ch;  //若是非空串，则按串长分配存储空间，空串 ch 为 NULL
  int length;
public:
  HString()
  {//构造函数一，产生空串
    ch = NULL;
    length = 0;
  }
  HString(const char* str)
  {//构造函数二，产生与字符串常量 str 字符相同的串
    length = strlen(str);
    ch = new char[length];
    assert(ch != NULL);
    for(int i = 0; i <length; i++)
      ch[i] = str[i];
  }
  HString(const HString &S)
  {//构造函数三，产生与字符串的类对象 S 相同的对象
    length = S.length;
    ch = new char[length];
    assert(ch != NULL);
    for(int i = 0; i < length; i++)
      ch[i] = S.ch[i];
  }
  ~HString()
  {//析构函数，清空串
    ClearString();
  }
  void ClearString()
  {//清空串
    if (ch != NULL)
    {
      delete[] ch;
      ch = NULL;
    }
    length = 0;
  }
  void StrAssign(const char* str)
  {//产生与字符串常量 str 字符相同的串
    ClearString();  //释放原有存储空间
    length = strlen(str);
    if (length)
    {
      ch = new char[length];
      assert(ch != NULL);
      for(int j = 0; j < length; j++)
        ch[j] = str[j];
    }
  }
  void StrCopy(const HString &S)
  {//复制串 S
    ClearString();
    ch = new char[S.length];
    assert(ch != NULL);
    for(int i = 0; i < S.length; i++)
      ch[i] = S.ch[i];
    length = S.length;
  }
  bool StrEmpty()const
  {//若串为空，则返回 true ；否则返回 false
    return length == 0;
  }
  int StrCompare(const HString &S)const
  {//若串 > 串S，则返回值 >0 ，若串 = 串S，则返回 =0 ，若串 < 串S，则返回 <0
    for(int i = 0; i < length && i < S.length; i++)  //在有效范围内
      if (ch[i] != S.ch[i])
        return ch[i] - S.ch[i];  //不相等，则返回两字符 ASCII 码的差值
    return length - S.length;  //在有效范围内字符相等，则返回长度之差
  }
  int StrLength()const
  {//返回串的元素个数
    return length;
  }
  void Concat(const HString &S1, const HString &S2)
  {//返回由串 S1 和 S2 连接而成的新串
    int i;
    ClearString();
    length = S1.length + S2.length;
    ch = new char[length];
    assert(ch != NULL);
    for(int i = 0; i < S1.length; i++)
      ch[i] = S1.ch[i];
    for(int i = 0; i < S2.length; i++)
      ch[S1.length + i] = S2.ch[i];
  }
  bool SubString(HString &Sub, int pos, int len)const
  {//用 Sub 返回串的第 pos 个字符起长度为 len 的子串，成功返回 true；否则返回false
    if (pos < 1 || pos > length || len < 0 || len > length-pos+1)
      return false;
    Sub.ClearString();
    if (len)
    {
      Sub.ch = new char[len];
      assert(Sub.ch != NULL);
      for(int i = 0; i < len; i++)
        Sub.ch[i] = ch[pos - 1 + i];
      Sub.length = len;
    }
    return true;
  }
  bool StrInsert(int pos, const HString &S)
  {//在串的第 pos 个字符之前插入串 S ，成功返回 true ;否则返回 false
    int i;
    char *p;
    if (pos < 1 || pos > length + 1)
      return false;
    if (S.length)
    {
      p = new char[length + S.length];
      assert(p != NULL);
      for(int i = 0; i < pos - 1; i++)
        p[i] = ch[i];
      for(int i = 0; i < S.length; i++)
        p[pos - 1 + i] = S.ch[i];
      for(int i = pos - 1; i < length; i++)
        p[i + S.length] = ch[i];
      delete[] ch;
      ch = p;
    }
    return true;
  }
  bool StrDelete(int pos, int len)
  {//从串中删除第 pos 个字符起长度为 len 的子串
    int i;
    char *p;
    if (len > length - pos + 1)
      return false;
    p = new char[length - len];
    assert(p != NULL);
    for(i = 0; i < pos - 1; i++)
      p[i] = ch[i];
    for(i = pos - 1; i < length - len; i++)
      p[i] = ch[i + len];
    length -= len;
    delete[] ch;
    ch = p;
    return true;
  }
  void StrPrint()const
  {//输出字符串
    for(int i = 0; i < length; i++)
      cout << ch[i];
    cout << endl;
  }
  int Index(const HString &S, int pos)const
  {//若串中第 pos 个字符之后存在与 S 相等的子串
   //则返回第一个这样的字串在串中的位置，否则返回 0
    HString sub;
    if (pos > 0 && pos <= length)
      for(int i = pos; i < length - S.length + 1; i++)
      {//i 从串的第 pos 到倒数第 S.length 个字符
        SubString(sub, i, S.length);
        if (sub.StrCompare(S) == 0)  //匹配到
          return i;
      }
    return 0;
  }
  bool Replace(const HString &T, const HString &V)
  {//初始条件：串 T 和串 V 存在，串 T 是非空串
   //操作结束：用串 V 替换串中出现的所有与串 T 相等的不重叠子串
    int i = 1;  //从串的第一个字符开始查找串 T
    if (!T.length)  //T 是空串
      return false;
    while(i)  //若 i > length ，在 Index() 中会返回 0
    {
      i = Index(T, i);
      if (i)
      {
        StrDelete(i, T.length);
        StrInsert(i, V);
        i += V.length;
      }
    }
    return true;
  }
};

HString 类中存储字符串的方式和 C++ 语言设置的存储字符串的方式不同，在串尾没有 "\0" 作为串结束标志，而是单独用一个私有数据成员 length 存放串长。这导致 HString 类不能使用 C++ 的 string 中的库函数。

1.2 字符串的模式匹配算法

1.2.1 朴素的模式匹配算法

朴素的模式匹配算法即 HString 类中的 Index() 成员函数：由主串的第 pos 个字符起，检验是否存在子串 S 。首先令 i 等于 pos （i 为主串中当前待比较字符的位序），j 等于 1 （j 为 S 中当前待比较字符的位序），如果主串的第 i 个字符与 S 的第 j 个字符相同，则 i, j 各加 1 继续比较，直至 S 的最后一个字符（找到）。若在比较期间出现了不同（没找到），令 i 等于 pos+1 ，j 等于 1，由 pos 的下一位置起，继续查找是否存在子串 S。

该算法简单，容易理解，但主串的指针 i 总要回溯，特别是在有较多的字符匹配又不完全匹配的情况下，回溯得更多。这时，主串的每个自负要进行多次比较，显然效率较低。

1.2.2 KMP 算法和改进的 KMP 算法

如果能使主串的指针 i 不回溯，也就是使主串的每个字符只进行一次比较，效率会大为提高。这是可以做到的。当检测到主串中的第 i （终值）个字符与模式串 S 中第 j （终值）个字符不匹配时，i（终值）之前的字符都是已知的。他们都与模式串 S 中的相应字符相同，故 i 可仍保持在终值处不动，j 回溯到子串 S 的第 1 个字符处与 i 的当前字符继续进行比较。j 回溯到第几个字符是由子串 S 的模式决定的。KMP 算法根据子串 S 生成的 next 数组指示 j 回溯到第几个字符。 next 数组的意义是这样的：如果 next[j] = k ，则当子串 S 的第 j 个字符和主串的第 i 个字符失配时，主串的第 i 个字符继续与 S 的第 k 个字符继续进行比较即可。

KMP 算法还有可改进之处。下面的 get_next() 是改进的求数组 next() 的算法。其中，next[j] = 0 ，并不是将主串的当前字符与模式串的第 0 个字符进行比较，而是主串当前字符的下一个字符与模式串的第 1 个字符进行比较。

实现：

//改进的 KMP 算法
void get_next(HString S, int next[])
{
  int i = 1, j = 0;
  HString subs1, subs2;
  next[1] = 0;  //S 的第一个字符与主串失配，主串的下一个字符与 S 的第一个字符比较
  while(i < S.StrLength())
  {
    S.SubString(subs1, i, 1);  //S 的第 i 个字符在 subs1 中
    S.SubString(subs2, j, 1);  //S 的第 j 个字符在 subs2 中
    if (j == 0 || subs1.StrCompare(subs2) == 0)  // (S.ch[i] == S.ch[j])
    {
      ++i;
      ++j;
      S.SubString(subs1, i, 1);  //S 的第 i 个字符在 subs1 中
      S.SubString(subs2, j, 1);  //S 的第 j 个字符在 subs2 中
      if (subs1.StrCompare(subs2) != 0)  // (S.ch[i] != S.ch[j])
        next[i] = j;
      else
        next[i] = next[j];
    }
    else
      j = next[j];  //j 减小到前面字符相等之处
  }
}

推荐阅读：
KMP算法（研究总结，字符串）
KMP 算法（1）：如何理解 KMP

1.2.3 Boyer-Moore 算法

Boyer-Moore 算法基于以下事实：模式串一般较短，因此只包含字符集中少数字符，如果主串当前比较的字符在模式串中没有，那就可以将模式串向右移动直到主串该字符的下一个字符与模式串的第一个字符对齐。为了提高效率，比较是从模式串的最后一个字符开始的。

Boyer-Moore 算法在匹配过程中对主串一些字符跳不过去检查，但也有一些字符会被检查多次。

实现：

//用类实现 BM 算法
const int N = 256; //字符集扩展到汉字，ASCII 码 0 ~ 255
class BMMatching  //之前设置为 HString 类的友类，以便使用其私有数据成员
{
private:
  HString Main, Sub;  //主串，模式串
  bitset<N> bit;  //N 个二进制（全 0 ）的 STL 位集合类对象
  void MakeBitset()
  {//根据模式串确定位集合 bit 的值
    int i;
    for(i = 0; i < Sub.length; i++)
      bit[(unsigned char)Sub.ch[i]] = 1;  //令相应的bit[] 的 ASCII 码位的值为 1
  }
  int last(char c)
  {//如果字符 c 不在模式串 Sub 中，返回 -1 ；否则返回其在 Sub 中的最大位序
    if (bit[(unsigned cha)c == 0])  //bit中对应字符c的位值为0，则说明c不在模式串中
      return -1;
    else
      for(int i = Sub.length - 1; i >= 0; i--)  //由后向前
        if (c == Sub.ch[i])  //c 在位置 i
          return i;
  }
public:
  BMMatching(const char* str = "", const char* strS = "")
  {//构造函数，产生 HString 类的主串、模式串并根据模式串确定位集合 bit 的值
    Main.StrAssign(strM);  //用字符串 strM 构造主串 Main
    Sub.StrAssign(strS);  //用字符串 StrS 构造模式串 Sub
    MakeBitset();  //根据模式串确定位集合 bit 的值
  }
  int BMMatching()
  {//Boyer-Moore 算法
    int m, n, i, j;
    cout << "主串为" ;
    Main.StrPrint();
    cout << "模式串为" ;
    Sub.StrPrint();
    m = Sub.length;
    n = Main.length;
    j = m - 1;
    i = n - 1;
    do
    {
      if (Sub.ch[j] == Main.ch[j])
        if (j == 0)  //由后向前已经比较到第一个字符
          return i+1;
        else
          i--, j--;
      else
      {
        i = i + m - min(j, 1+last(Main.ch[i]));
        j = m - 1;
      }
    }while(i < n);  //没到主串尾
    return 0;
  }
};

注意：
汉字编码有有两个特性：
（1）两个字节（字符）表示一个汉字；
（2）表示汉字的字符范围是从 128 到 255 （转换成无符号类型）。

推荐阅读：
Boyer-Moore 算法
Sunday 算法

2. 矩阵

2.1 多维数组的顺序存储结构

实现：

//多维数组的类
template<typename T>class MuArray
{
private:
  T *base;  //数组元素基址，由构造函数分配
  int dim;  //数组维数
  int *bounds;  //数组维界基址，由构造函数分配
  int *constants;  //数组映像函数常量基址，由构造函数分配
  bool Locate(va_list ap, int &off)const
  {//若 ap 指示的各下标值合法，则求出该元素在 base 中的相对地址 off
    int i, ind;
    off = 0;
    for(i = 0; i < dim; i++)
    {
      ind = va_arg(ap, int);  //逐一读取各维的下标值
      if (ind < 0 || ind >= bounds[i])  //各维下标值不合法
        return false;
      off += constants[i] * ind;  //相对地址 = 各维下标 * 本维的偏移量之和
    }
    return true;
  }
public:
  MuArray(int Dim, ...)
  {//构造函数，若维数 dim 和各维数长度合法，则构造相应的数组对象
    int elemtotal = 1, i;  //elemtotal 是数组元素总数，初值为 1
    va_list ap;  //变长参数表类型，在 stdarg.h 中
    assert(Dim > 0);
    dim = Dim;
    bounds = new int[dim];
    assert(bounds != NULL);
    va_start(ap, Dim);  //变长参数 "..." 从形参 Dim 之后开始
    for(i = 0; i < Dim; i++)
    {
      bounds[i] = va_arg(ap, int);  //逐一将变长参数赋给 bounds[i]
      assert(bounds[i] > 0);
      elemtotal *= bounds[i];  //数组元素总数 = 各维长度之乘积
    }
    va_end(ap);  //结束提取变长参数
    base = new T[elemtotal];
    assert(base != NULL);
    constants[dim - 1] = 1;  //最后一维的偏移量为 1
    for(i = Dim - 2; i >= 0; i--)
      constants[i] = bounds[i + 1] * constants[i + 1];  //每一维的偏移量
  }
  ~MuArray()
  {//析构函数，释放所有动态生成的存储空间
    delete[] base;
    delete[] bounds;
    delete[] constants;
  }
  bool Value(T &e, int n, ...)const  
  //在 VC++ 中，"..." 之前的形参不能是引用类型，故加形参 n
  {//...依次为各维的下标值，若各下标合法，则 e 被赋值为矩阵相应的元素值
    va_list ap;
    int off;
    va_start(ap, n);
    if (Locate(ap, off) == false)  //求得变长参数所指单元的相对地址
      return false;
    e = *(base + off);  //将变长参数所指单元的值赋给 e
    return true;
  }
  bool Assign(T e, ...)const
  {//...依次为各维下标值，若各下标合法，则将 e 的值赋给矩阵指定的元素
    va_list ap;
    int off;
    va_start(ap, e);
    if (Locate(ap, off) == false)
      return false;
    *(base + off) = e;
    return true;
  }
};

MuArray 中有些成员函数的形参有 "..." ，它代表变长参数表，即 "..." 可用若干个实参取代。这很适合含有维数不定的数组的函数。

2.2 矩阵的压缩存储

实现：

//三元组行逻辑连接顺序表的类
template<typename T>struct Triple
{//三元组类型的结构体
  int i, j;  //行下标，列下标
  T e;  //非零元素值
}
const int MAX_SIZE = 100;  //非零元个数的最大值
const int MAX_RC = 20;  //最大行数
template<typename T>class RLSMatrix
{
private:
  Triple<T> data[MAX_SIZE + 1];  //data[0] 未用
  int rpos[MAX_RC + 1];  //各行第一个非零元素的位置表
  int row, col, num;  //矩阵的行数，列数，非零元的个数
public:
  RLSMatrix()
  {//构造函数，构造 0 行 0 列的空矩阵
    row = col = num = 0;
  }
  RLSMatrix(char* FileName)
  {//构造函数，由文件创建稀疏矩阵
    CreateSMatrixFromFile(FileName);
  }
  bool CreateSMatrixFromFile(char* FileName = "F3-1.txt")  //缺省值
  {//由文件创建稀疏矩阵，要求格式正确，默认文件名是 F3-1.txt
    int i, j;
    ifstream fin(FileName);  //打开文件
    fin >> row >> col >> num;
    if (num > MAX_SIZE || row > MAX_RC)  //矩阵的行数太多或非零元个数太多
      return false;
    data[0].i = 0;  //为下面比较做准备
    for(i = 1; i <= num; i++)
    {
      fin >> data[i].i >>data[i].j >> data[i].e;
      //由文件读入稀疏矩阵的一个非零元素
      if (data[i].i < 1 || data[i].i > row || data[i].j < 1 || data[i].j >col)
        return false;
      if (data[i]. i < data[i - 1].i ||
          data[i].i == data[i - 1].i && data[i].j <= data[i - 1].j)
        return false;  //行或列的输入顺序有错
    }
    fin.close();
    for(i = 1; i <= row; i++) //给rpos[]赋初值 1（每行的第一个非零元素的初始位置）
      rpos[i] = 1;
    for(i = 1; i <= num; i++)
      for(j = data[i].i + 1; j <= row; j++)  //从非零元素所在行的下一行起
        rpos[j]++;  //每行第一个非零元素的位置 +1
    return true;
  }
  void CopySMatrix(const RLSMatrix &M)
  {//由稀疏矩阵 M 复制得到稀疏矩阵
    int i;
    row = M.row;
    col = M.col;
    num = M.num;
    for(i = 0; i <= M.num; i++)
      data[i] = M.data[i];
    for(i = 0; i <= M.row; i++)
      rpos[i] = M.rpos[i];
  }
  void TransposeSMatrix(const RLSMatrix &M)
  {//求稀疏矩阵 M 的转置矩阵
    int i, j, k, colm[MAX_RC + 1];  //[0] 不用
    row = M.col;  //M 的转置的行数 = M 的列数
    col = M.row;  //M 的转置的列数 = M 的行数
    num = M.num;  //M 的转置的非零元素个数 = M 的非零元素个数
    if (num)  //矩阵 M 非空
    {
      for(i = 1; i <= row; ++i)
        colm[i] = 0;  //M 转置的每行非零元素个数，初值设置为 0
      for(i = 1; i <= num; ++i)
        ++colm[M.data[i].j];  //colm[] = M 的每列非零元素个数
      rpos[1] = 1;  //M 转置的第 1 行的第一个非零元素的序号是 1
      for(i = 2; i <= row; ++i)
        rpos[i] = rpos[i-1] + colm[i-1];//求 M 转置中第 i 行的第一个非零元素的序号
      for(i = 1; i <= row; ++i)
        colm[i] = rpos[i];  //colm[i] = M 的当前非零元素在 M 转置中应该存放的位置
      for(i = 1; i <= num; ++i)
      {
        j = M.data[i].j;  //在 M 转置中的行数
        k = colm[j]++;  //在 M 转置中的序号，colm[j] + 1
        data[k].i = j;  //将 M.data[i] 行列对调赋给 data[k]
        data[k].j = M.data[i].i;
        data[k].e = M.data[i].e;
      }
    }
  }
  bool AddSMatrix(const RLSMatrix &M, const RLSMatrix &N)
  {//求两稀疏矩阵的和 = M + N
    int p, q, up, uq;
    if (M.row != N.row || M.col != N.col)
      return false;
    row = M.row;
    col = M.col;
    num = 0;  //矩阵 M 非零元素个数的初值
    for(int k = 1; num <= MAX_SIZE && k <= M.row; ++k)  //k 指示行号
    {
      rpos[k] = num + 1;
      p = M.rpos[k];
      q = N.rpos[k];
      if (k < M.row)  //不是最后一行
      {
        up = M.rpos[k + 1];
        uq = N.rpos[k + 1];
      }
      else  //是最后一行
      {
        up = M.num + 1;  //给最后一行设上界
        uq = N.num + 1;
      }
      while(p < up && q < uq)
        if (M.data[p].j < N.data[q].j)
          data[++num] = M.data[p++];
        else if (M.data[p].j > N.data[q].j)
          data[++num] = N.data[q++];
        else
        {
          if (M.data[p].e + N.data[q].e != 0)
          {
            data[++num] = M.data[p];
            data[num].e += N.data[q].e;  
          }
          p++;
          q++;
        }
        //以下两个循环最多执行一个
        while(p < M.rpos[k + 1] && p <= M.num)
          data[++num] = M.data[p++];
        while(q < N,rpos[k + 1] && q <= N.num)
          data[++num] = N.data[q++];
    }
    if (num > MAX_SIZE)  //非零元素个数太多
      return false;
    else
      return true;
  }
  bool SubtSMatrix(const RLSMatrix &M, RLSMatrix &N)
  {//求两稀疏矩阵的差 = M - N
    int i;
    bool f;
    RLSMatrix S, N1;
    N1.CopySMatrix(N);
    for(i = 1; i < N1.num; ++i)  // N1 = -N
      N1.data[i].e *= -1;
    f = S.AddSMatrix(M, N1);  //S = M + (-N) = M - N
    if (f)
    {
      row = S.row;
      col = S.col;
      num = S.num;
      for(i = 0; i <= S.num; i++)
        data[i] = S.data[i];
      for(i = 0; i <= S.row; i++)
        rpos[i] = S.rpos[i];
    }
    return f;
  }
  bool MultSMatrix(const RLSMatrix &M, RLSMatrix &N)
  {//一种求稀疏矩阵乘积 M * N 的方法（利用 N 的转置矩阵 T）
    int i, j, q, p, up, uq;
    T Qs;  //矩阵单元 data[i][j].e 的临时存放处
    RLSMatrix T;  //存 N 的转置矩阵
    if (M.col != N.row)
      return false;
    row = M.row;
    col = N.col;
    num = 0;
    T.TransposeSMatrix(N);
    for(i = 1; i <= row; i++)
      for(j = 1; j <= col; j++)
      {
        Qs = 0;
        p = M.rpos[i];  //p 指示矩阵 M 在 i 行的第一个非零元素的位置
        q = T.rpos[j];  //q 指示矩阵 T 在 j 行的第一个非零元素的位置
        if (i < M.row)
          up = M.rpos[i + 1];
        else
          up = M.num + 1;
        if (j < T.row)
          uq = T.rpos[j + 1];
        else
          uq = T.num + 1;
        while(p < up && q < uq)
          if (M.data[p].j < T.data[q].j)
            p++;
          else if (M.data[p].j > T.data[q].j)
            q++;
          else
            Qs += M.data[p++].e * T.data[q++].e;
        if (Qs)
        {
          if (++num > MAX_SIZE)
            return false;
          data[num].i = i;
          data[num].j = j;
          data[num].e = Qs;
        }
      }
    return true;
  }
  void PrintSMatrix()const
  {//按矩阵形式输出
    int k = 1;  //非零元计数器
    const Triple<T> *p = data + 1;  //常量指针 p 指向第一个非零元素
    if (num == 0)  //矩阵不存在
      return;
    for(int i = 1; i <= row; i++)
    {
      for(int j = 1; j <= col; j++)
        if (k <= num && p->i == i && p->j == j)
        {
          cout << setw(3) << (p++)->e;
          k++;
        }
        else
          cout << setw(3) << 0;
      cout << endl;
    }
  }
};