串

一、串的定义

串( string)是由零个或多个字符组成的有限序列，又名叫字符串。

二、串的存储结构

1、定长顺序存储表示

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

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

2、堆分配存储表示

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

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

3、块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符， 也可以存放多个字符。每个结点称为块，整个链表称为块链结构。图(a)是结点大小为4 (即每个结点存放4个字符)的链表,最后一个结点占不满时通常用“#”补上;图(b)是结点大小为1的链表。

三、串的基本操作

• StrAssign(&T, chars): 赋值操作。把串T赋值为 chars
• Strcopy(&T, S): 复制操作。由串S复制得到串T。
• StrEmpty(S): 判空操作。若S为空串,则返回TRUE,否则返回 FALSE
• StrCompare(S,T): 比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。
• StrEngth(S): 求串长。返回串S的元素个数
• Substring(&Sub,S,pos,1en):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
• Concat(&T,S1,S2): 串联接。用T返回由S1和S2联接而成的新串。
• Index(S,T): 定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0
• Clearstring(&S): 清空操作。将S清为空串
• Destroystring(&S): 销毁串。将串S销毁

四、串的模式匹配（重点）

1、简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

int Index(SString S, SString T){
 int i = 1, j = 1;
 while(i <= S.length && j <= T.length){
  if(S.ch[i] == T.ch[j]){
   ++i; ++j; //继续比较后继字符
  }else{
   //指针后退重新开始匹配
   i = i-j+2;
   j = 1;
  }
 }
 if(j > T.length){
  return i - T.length;
 }else{
  return 0;
 }
}

2、KMP算法

在上面的简单匹配中，每趟匹配失败都是模式后移一位再从头开始比较。

KMP算法的特点就是：仅仅后移模式串，比较指针不回溯。很是牛掰。

KMP的方法: 利用子串的next数组, 得出在主串某个位置失配时, 主串指针不动, 子串滑动的距离(通常叫做字串指针回溯, 但这里叫子串滑动更直观易懂)

求next数组

void get_next(String T, int *next){
 int i = 1, j = 0;
 next[1] = 0;
 while (i < T.length){
  if(j==0 || T.ch[i]==T.ch[j]){ //ch[i]表示后缀的单个字符，ch[j]表示前缀的单个字符
   ++i; ++j;
   next[i] = j; //若pi = pj， 则next[j+1] = next[j] + 1
  }else{
   j = next[j]; //否则令j = next[j]，j值回溯，循环继续
  }
 }
}

kmp算法代码

int Index_KMP(String S, String T){
 int i=1, j=1;
 int next[255]; //定义next数组
 get_next(T, next); //得到next数组
 while(i<=S.length && j<=T.length){
  if(j==0 || S.ch[i] == T.ch[j]){ //字符相等则继续
   ++i; ++j;
  }else{
   j = next[j]; //模式串向右移动，i不变
  }
 }
 if(j>T.length){
  return i-T.length; //匹配成功
 }else{
  return 0;
 }
}

KMP算法的进一步优化

使用get_nextval 代替 next

void get_nextval(String T, int *nextval){
 int i = 1, j = 0;
 nextval[1] = 0;
 while (i < T.length){
  if(j==0 || T.ch[i]==T.ch[j]){ //ch[i]表示后缀的单个字符，ch[j]表示前缀的单个字符
   ++i; ++j;

   if(T.ch[i] != T.ch[j]){ //若当前字符与前缀字符不同
    nextval[i] = j; //则当前的j为nextval在i位置的值
   }else{
    //如果与前缀字符相同
    //则将前缀字符的nextval值给nextval在i位置上的值
    nextval[i] = nextval[j];
   }
  }else{
   j = nextval[j]; //否则令j = next[j]，j值回溯，循环继续
  }
 }
}