4.1 串

1 定义

串（String）：由零个或多个字符组成的有限序列。

$S\doteq \left \{ a_{1} a_{2} ... a_{n} \right \} \left ( n\geq 0 \right )$

S——串名
"a1a2…an"——串值
n——串长
n=0——空串?? $\o$

?子串：串中任意个连续字符组成的子序列。
真空串：不包含自身的所有子串。
主串：包含子串的串。
字符位置：字符在序列中的序号为该字符在串中的位置。
子串位置：子串第一个字符在主串中的位置。
空格串：由一个或多个空格组成的串。
空串：? $\o$ ? （所有空串相等）
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串相等。

4.2 案例引入

4.3 串的运算

4.3.1 串的抽象类型定义

ADT String{
? ? 数据对象： $a_{i} \in CharacterSet$ ?
? ? 数据关系：R1? 一对一
? ? 基本操作：

StrAssign——串赋值
StrCompare——串比较
StrLength——求串长
Concat——串连结
SubString——求子串
StrCopy——串拷贝
StrEmpty——串判空
ClearString——清空串
Index——子串的位置
Replace——串替换
StrInsert——子串插入
StrDelete——子串删除
DestroyString——串销毁

}ADT String

4.3.2 串的存储结构

1 顺序串

#define MAXLEN 255         //串的最大长度
typedef struct{
    char ch[MAXLEN+1];     //存储串的一维数组 【0—255】共256个
    int length;            //串的当前长度
}SString;

2 链串

优点：操作方便?
缺点：存储密度低??

改进：存放多个字符在一个结点中。

存储密度=串值所占的存储? /? 实际分配的存储

块链结构：

#define CHUNKSIZE 80    //块的大小可由用户定义
typedef struct Chunk{   //结点结构
    char ch[CHUNKSIZE]; //数据域
    struct Chunk*next;  //指针域
}Chunk;

typedef struct{         //串的链表结构
    Chunk *head,*tail;  //串的头指针和尾指针
    int curlen;         //串的当前长度
}LString;               //字符串的块链结构

4.3.3 串的模式匹配算法（串匹配）

算法目的：确定主串S（正文串）中所含子串T（模式串）第一次出现的位置，在主串中查找与模式串相匹配的子串。

算法应用：搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：

BF算法（Brute-Force) 穷举法，简单匹配算法
KMP算法：速度快

1 BF算法

【设计思想】Index(S,T,pos)

将主串的第pos个字符和模式串的第一个字符比较
若相等，继续逐个比较后续字符
若不等，从主串的下一字符起，重新与模式串的第一个字符比较。

int Index_BF (SString S ,SString T ,int pos)
   i=pos;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;                         //匹配失败
}

【例】