数据结构-串

串的实现

在C语言中所使用的字符串就是串的数据类型的一种。

串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组连续的存储单元存储串值的字符序列。

#define MAXLEN 255 //预定义最大串长为255

typedef struct SString
{
  char ch[MAXLEN]; //每个分量存储一个字符
  int length;   //串的实际长度
}SString;

串的实际长度只能小于或等于MAXLEN，超过预定义长度的串值会被社区，称为截断。串长的表示由两种方法：一种是通过length存放串的长度；二是在串值后面加一个不计入串长的结束标记字符'\0'（C语言种字符串就是采用这种方法），此时串就根据'\0'来算长度。

堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串，但存储空间是动态分配获得。

typedef struct{
    char *ch;   //按串长分配存储区，ch指向串的首地址
    int length; //串的长度
}HString;

在C语言中，用malloc()为每个新产生的串分配一块串长所需的存储空间。

块链存储表示

类似于链式存储结构，也可采用链式方式存储串值。

//串的结点
typedef struct StringNode{
    char ch[4];  //每个结点存多个字符 提高存储密度
    struct StringNode* next; //指向下一个结点
};

串的基本操作

赋值操作

bool StrAssign(SString *T, char chars[])
{
  //获取要赋值字符串长度
  int charsLen = strlen(chars);

  // 长度为零表示空字符串，退出循环
  if (!charsLen)
    return false;
  for (size_t i = 0; i < charsLen; i++)
  {
    T->ch[i] = chars[i];
  }

  T->length = charsLen;
  return true;
}

复制操作

bool StrCopy(SString *T, const SString S)
{
  if (!S.length)
    return false;

  for (size_t i = 0; i < S.length; i++)
  {
    T->ch[i] = S.ch[i];
  }

  // 若要赋值的长度大于原先字符串长度就增长
  if (S.length > T->length)
  {
    T->length = S.length;
  }

  return true;
}

判空操作

bool StrEmpty(const SString *S)
{
  return S->length == 0;
}

比较操作

int StrCompare(const SString S, const SString T)
{
  
  int i = 0;
  while (i != S.length || i != T.length)
  {
    if (S.ch[i] == T.ch[i])
    {
      i++;
    }
    else
    {
      //若S>T 返回大于0的数 若S<T 返回小于0的数
      return S.ch[i] - T.ch[i];
    }
  }
  //若结束循环没有比较出结果说明必有一个长度要更长
  return S.length - T.length;

}

求子串

// 求字串 Sub来返回串S的第pos个字符起长度为len的字串
bool SubString(SString *Sub, SString S, char pos, int len)
{
  if (S.length == 0)
    return false;
  int index = 0;
  for (size_t i = 0; i < S.length; i++)
  {
    if (S.ch[i] == pos)
    {
      // 记录pos字符在S中的起始位置
      index = i;
      break;
    }
  }
  // 判断len是否要长于S字符串中pos开始后的长度
  if (len > S.length - index)
    return false;
  for (size_t i = 0; i < len; i++)
  {
    Sub->ch[i] = S.ch[index];
    index++;
    Sub->length++;
  }
  return true;
}

串联结

// 用T返回由S1和S2拼接而成的新串，S2拼接在S1前
bool Concat(SString *T, SString S1, SString S2)
{
  for (size_t i = 0; i < S1.length; i++)
  {
    T->ch[i] = S1.ch[i];
    T->length++;
  }
  int index = 0;
  for (size_t i = S1.length; i < S1.length + S2.length; i++)
  {
    T->ch[i] = S2.ch[index];
    index++;
    T->length++;
  }

  return true;
}

定位操作（简单的模式匹配算法）

// 定位操作 若主串S中存在与串T值相同的字串，则返回它在S中第一次出现的位置，否则为0
int Index(SString S, SString T)
{
  // i和j分别为S和T的计数指针
  int i = 0, j = 0;
  if (S.length == 0 || T.length == 0)
    return i;
  while (i < S.length && j < T.length)
  {
    if (S.ch[i] == T.ch[j])
    {
      i++;
      j++;
    }
    else
    {
      // S的指针跳到下一个字符位置
      i = i - j + 1;
      j = 0;
    }
  }
  //若T的指针j扫描到最后一个元素说明都匹配上就返回第一个匹配上的地址
  if (j == T.length)
    return i - j;
  else
    return 0;
}

串的模式匹配算法—KMP算法

上方的暴力匹配算法中有许多重复的趟数会导致花不必要的时间来跑已经知道的结果，KMP算法就是用于解决这个问题，在KMP算法中，会采用一个next数组来记录子串是在主串第几个元素匹配失败的，下次可以通过next来直接重匹配失败的位置重新开始匹配。在KMP算法中，最主要的就是next数组的计算。

//S和T数组下标由1开始
// KMP算法 若主串S中存在与串T值相同的字串，则返回它在S中第一次出现的位置，否则为0
int Index_KMP(SString S, SString T, int next[])
{
  // i和j分别为S和T的计数指针
  int i = 1, j = 1;
  if (S.length == 0 || T.length == 0)
    return 0;
  while (i <= S.length && j <= T.length)
  {
    if (S.ch[i] == T.ch[j] || j == 0)
    {
      i++;
      j++;
    }
    else
    {
      // KMP算法只需根据计算出的next数组对j的值进行修改
      j = next[j];
    }
  }
  // 若T的指针j扫描到最后一个元素说明都匹配上就返回第一个匹配上的地址
  if (j > T.length)
    return i - T.length;
  else
    return 0;
}

// 求next数组
void get_next(SString T, int next[])
{
  int i = 1, j = 0;
  next[0] = 0;
  while (i < T.length)
  {
    if (j == 0 || T.ch[i] == T.ch[j])
    {
      ++i;
      ++j;
      next[i] = j;
    }
    else
      j = next[j];
  }
}