串
(一)、串类型的定义
1.串的基本概念
(1)串(字符串):零个或多个字符组成的有限序列。
记作： S=“a1a2a3…”，其中S是串名，ai(1≦i≦n)是单个，可以是字母、数字或其它字符。
(2)串值:双引号括起来的字符序列是串值。
(3)串长：串中所包含的字符个数称为该串的长度。
(4)空串(空的字符串)：长度为零的串，它不包含任何字符。
(5)空格串(空白串)：构成串的所有字符都是空格的串。
(6)子串(substring)：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
(7)子串的序号：将子串在主串中首次出现时的该子串的首字符对应在主串中的序号，称为子串在主串中的序号（或位置）。
(8)串相等：两个串的串值相等。
(9)在程序中使用的串可分为两种：串变量和串常量。
串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值。
串变量和其它类型的变量一样，其值是可以改变。
2.串的抽象数据类型定义
ADT String{
数据对象：D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 }
数据关系：R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n }
基本操作：
StrAssign(t , chars)
初始条件： chars是一个字符串常量。
操作结果：生成一个值为chars的串t 。
StrConcat(s, t)
初始条件：串s, t 已存在。
操作结果：将串t联结到串s后形成新串存放到s中。
StrLength(t)
初始条件：字符串t已存在。
操作结果：返回串t中的元素个数，称为串长。
SubString (s, pos, len, sub)
初始条件：串s, 已存在, 1≦pos≦StrLength(s)且 0≦len
≦StrLength(s) –pos+1。
操作结果：用sub返回串s的第pos个字符起长度为len的
子串。
……
} ADT String
(二)、串的存储表示和实现
串的存储方式取决于将要对串所进行的操作。串在计算机中有3种表示方式：
(1)定长顺序存储方式：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。
(2)堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。
(3)块链存储方式：是一种链式存储结构表示。
1.串的定长顺序存储表示
定长顺序存储结构使用定长的字符数组来定义，数组的上界预先确定。
(1)定长顺序存储结构定义为：
#define MAX_STRLEN 256
typedef struct
{ char str[MAX_STRLEN] ;
int length;
} StringType ;(2)串的联结操作
Status StrConcat(StringType s, StringType t)
/* 将串t联结到串s之后，结果仍然保存在s中 */
{
int i, j;
if ((s.length + t.length) > MAX_STRLEN)
{
return ERROR; /* 联结后长度超出范围 */
}
for (i = 0; i < t.length; i++)
{
s.str[s.length + i] = t.str[i]; /* 串t联结到串s之后 */
}
s.length = s.length + t.length; /* 修改联结后的串长度 */
return OK;
}(3)求子串操作
Status SubString(SString &Sub, SString S, int pos, int len) {
Status SubString(StringType& Sub, StringType S, int pos, int len) {
// 算法4.3
// 用Sub返回串S的第pos个字符起长度为len的子串。
// 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。
int i;
if (pos < 1 || pos > S.str[0] || len < 0 || len > S.str[0] - pos + 1)
{
return ERROR;
}
for (i = 1; i <= len; i++)
{
Sub.str[i] = S.str[pos + i - 1];
}
Sub.str[0] = len;
return OK;
} // SubString2.串的堆分配存储表示、
(1)实现方法：系统提供一个空间足够大且地址连续的存储空间(称为“堆”)供串使用。可使用C语言的动态存储分配函数malloc()和free()来管理。
(2)串的堆式存储结构的类型定义
typedef struct
{
char *ch; /* 若非空，按长度分配，否则为NULL */
int length; /* 串的长度 */
} HString ;(3)串的联结操作
3.串的链式存储表示
串的链式存储结构采用单链表来存储串，结点构成：
data域：存放字符，data域可存放的字符个数称为结点的大小；
next域：存放指向下一结点的指针。为节省存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为块链结构。
串的块链式存储的类型定义包括：
⑴ 块结点的类型定义
#define BLOCK_SIZE 4
typedef struct Blstrtype
{ char data[BLOCK_SIZE] ;
struct Blstrtype *next;
}BNODE ;(2) 块链串的类型定义
typedef struct
{ BNODE head; /* 头指针 */
int Strlen ; /* 当前长度 */
} Blstring ;当一个块(结点)内存放多个字符时，往往会使操作过程变得较为复杂，如在串中插入或删除字符操作时通常需要在块间移动字符。
(三)、串的模式匹配算法
模式匹配(模范匹配)：子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。
1. Brute-Force模式匹配算法
设S为目标串，T为模式串，且不妨设：
S=“s0s1s2…sn-1” ， T=“t0t1t2 …tm-1”
串的匹配实际上是对合法的位置0≦i≦n-m依次将目标串中的子串s[i…i+m-1]和模式串t[0…m-1]进行比较。
串匹配问题可简化为找出某给定模式T在给定目标串S中首次出现的有效位置。
2.模式匹配的一种改进算法
该改进算法是由D.E.Knuth ，J.H.Morris和 V.R.Pratt提出来的，简称为KMP算法。其改进在于：每当一趟匹配过程出现字符不相等时，主串指示器不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指示器向右“滑动”尽可能远的一段距离后，继续进行比较。
Comments NOTHING