第 4章 字符串
4.2 字符串的存储方式
4.3 字符串的模式匹配算法
4.4 本章小结
4.1 字符串的基本概念
4.1 字符串的基本概念
1,基本概念
? 字符串, 字符组成的有限序列, 用一对 双引号 的
分界符括起来 。
? 字符串的长度,字符串中包含的字符数目。
? 空字符串,简称空串，长度为零的字符串。可用
“”表示。
请注意：字符的
界符为单引号
? 子串, 一个串中的任意连续字符组成的子序列。
? 主串,相应的，称包含子串的那个串为主串。
? 字符在串中的位置, 指该字符在字符序列中的位置 。
? 串相等,长度相等，并且这两个串对应位置上的字
符全部相等。
2.串的 ADT声明
从逻辑结构上看，串非常类似于线性表；在基本操作上，
串与线性表有较大的区别：
ADT String
{ 数据对象内容限定为字符集合：
D={ai | ai ∈ 字符集合, i=1,2,…,n,
n≥ 0}
数据间的线性关系：
R={<ai,ai+1>| ai ∈ D,i=1,2,…,n-1}
几种基本操作：
strAssign (&str,origin)
strCompare (str1,str2)
strLength(str)
用 origin这个字符数组
来构造一个串 str
按字典序比较两个串
str1和 str2
求串 str1的长度
strConcatenate(str1,str2,&str)
strSubstring(str,pos,length,&sub)
strClear(&str)
strDestroy(&str)
}
顺序连接 str1和 str2两
个字符串，得到串 str
从串 str的第 pos个位置开始
连续取长度为 length个字符
构成的子串 sub
将串 str清空
将串 str销毁并回
收空间
4.2 字符串的存储方式
4.2.2 串的堆分配存储表示
4.2.3 块链存储表示
4.2.1 定长顺序存储表示
基本思想,
预先划定数组的容量，待存储的字
符串长度只要不大于数组的容量即可。
如果串的长度超出了预定空间大小，
超出的字符串内容通过,截断,的方法
直接舍去。
引入 字符串长度 或者 字符串结束符
以明确存储空间内哪些是字符串的有效
内容。
4.2.1 定长顺序存储表示
//FixedLengthString.h
#define CAPACITY 256
class FLString
{ private:
int length;
char *content;
void strCopy(int offset1,char
*origin,int offset2,int len);
public:
FLString();
FLString(char *origin);
从字符数组 origin偏移
量为 offset2的字符开始,
连续拷贝 len个字符到本
串从偏移量 offset1处开
始的地方
构造函数, 用于创建一个空串
构造函数, 由 origin字符数组
的内容构造串
int strCompare(FLString str);
int strLength();
bool strConcatenate(FLString str1,
FLString str2);
//当前串与串 str比较大小
当前串与串 str比较大小
将串 str1与串 str2拼接后存
入当前串中
bool strSubstring(int pos,int len,
FLString &sub);
void strClear();
~FLString();
};
从当前串偏移量为 offset的字
符开始, 将长度为 len的一段
连续字符复制到串 sub中
串的清空操作
析构函数，用于销毁串
定长顺序存储表示的不足,
只要在操作中发现字符串长度大于预定义的最大
容量，就采取, 截断, 的方法，这样操作的结果会引
起 信息的损失 。
如果字符串长度远远小于预定义的最大容量，则
又会 浪费空间 。
改进方法：
不再事先预定好串的存储空间，而是根据串的
大小 实时分配空间 。这种更灵活的连续存储方式就
是, 堆分配存储表示, 。
4.2.2 串的堆分配存储表示
基本思想,
“按需分配”。
当字符串有效内容的长度发生变
化，原来的空间就会释放掉，同时
重新开辟一个和新内容长度一样的
字符数组来存储新的字符串。
串的, 堆分配存储表示, 与,定长顺序存储表
示,同 属采用数组进行的连续存储方式, 实现方法类
似，其区别体现在以下方法的实现过程：
//HeapString.h
class HString
{ private:
......
public:
//构造函数, 用于创建一个空串
HString();
//构造函数, 由 origin字符数组的内容构造串
HString(char *origin);
//当前串与串 str比较大小
int strCompare(HString str);
......
//将串 str1与串 str2拼接后存入当前串中
void strConcatenate(HString str1,HString
str2);
//从当前串偏移量为 offset的字符开始, 将长度为 len的
一段连续字符复制到串 sub中
void strSubstring(int pos,int len,HString
&sub);
......
//析构函数, 用于销毁串
~HString();
};
顺序存储表示小结,
对于以数组连续存储的字符串来说，其实现一
种是预先定义好的定长方式，即定长存储，其特点在
于,灵活性较差，但是较简单 ；
另一种方式则是根据字符串长度动态分配的，
即堆分配存储，其特点在于,不会造成空间的浪费，
但实现的时候要麻烦一些。
说明：
上面两种方式在实现时都使用了内存的 动态分
配方式,是在运行时为相应的变量分配的空间；相
对应的，在编译时就已经能够确定变量存储空间大
小的，叫做内存的 静态分配方式 。
4.2.3 块链存储表示
基本思想,
按照链表的方式进行存储 。
考虑使用链表后，指针所占的空间会增
加一定的空间开销。因此，为了减少开销，
应该尽量做到在一个节点中多存储一些字符。
这时，节点当中好像存储的是一, 块, 数据，
而不再是一, 个, 数据，所以形象地称其为
,块链, 。
引入, 存储密度, 这个概念来衡量开销的大小：
存储密度 =串中内容所占的存储位 /实际分配的存储位
节点大小不同的块链存储方式,
‘A’ ‘B’ ‘C’ ‘D’ ‘E’ - - - ∧
‘A’ ‘B’ ‘C’ - ‘D’ - - ‘E’ ∧
‘A’ ‘B’ ‘C’ ‘D’ ‘E’ ∧
( a ) 节点大小为4 的块链存储方式的一种情况
( b ) 节点大小为4 的块链存储方式的另一种情况
( c ) 节点大小为1 的块链存储方式的一种情况
图4, 3 串“A B C D E,的块链存储方式
head
head
head
块链存储方式表示的优劣分析：
优点,存取灵活
不足,空间开销相对较大，而且
实现也是相当复杂繁琐的。
一般只有在特殊的应用场合（如
所处理的字符串平均长度非常大时）才
会使用 块链存储 。
4.3 字符串的模式匹配算法
? 4.3.1 串模式匹配的基本算法
? 4.3.2 串模式匹配的改进算法
关于串的模式匹配的相关术语,
字符串的模式匹配,在目标区域内的
字符串中进行从前到后的扫描，看有没有一段
连续的字符与待查找的字符串完全匹配。
其中：
主串,查找的目标区域的字符串。
模式,相应地，待查找的串可以称为
,模式, 。
4.3.1 串模式匹配的基本算法
匹配算法功能：
找到在主串中第一次出现模式串的位
置。
基本思想,
模式串从字符串首位置开始，依次与主串相应
位置比较，不成功则整体后移一位。即对于主串
来说，第一趟从第一个字符开始，第二趟从第二
个字符开始，依此类推。
‘a ’ ‘b ’ ‘a ’ ‘a ’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b ’ ‘a ’ ‘a ’ ‘b ’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a ’ ‘a ’ ‘b ’ ‘a ’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a ’ ‘b ’ ‘a ’ ‘d ’
‘a’ ‘b’ ‘a’ ‘c’
( c ) 第三趟比较 （d ）第四趟比较
( a ) 第一趟比较 （b ）第二趟比较
图4.4 串模式匹配的基本算法
分析可知,
如果主串长度为 m，模式串长度为 n，则最多
的比较趟数为 m-n+1。在最差情况下，这种算法的
复杂度为 (m-n+1)*n，属于 O(N2)级别。
4.3.2 串模式匹配的改进算法
串模式匹配的基本算法简单易懂，
但是由于某趟比较失败而进入下一趟比
较时，主串有可能会 回退 到以前比较过
的某个字符以便重新和模式串比较，这
就在很大程度上影响了算法的效率。
为解决主串的回退问题，可以对算
法进行改进：
假设主串为 s=s1s2…s m-1sm，模式串为
t=t1t2…t n-1tn，其中 si（ 1≤ i≤ m）和 tj（ 1≤ j≤ n）都
是字符元素，在图 4.5中描述了匹配过程中字符串
的比较情况。
i=p
j=q
s
1
s
2
t
1
..,s
p-q+1
..,s
p-r+1
..,s
p
s
p+1
...
..,t
q-r+1
..,t
q
t
q+1
...
t
1
..,t
r
t
r+1
...
i=p
s
1
s
2
..,s
p-q+1
..,s
p-r+1
..,s
p
s
p+1
...
j=r
（a ） i = p,j = q 时出现不匹配
（b ） 子串右移后，i = p,j = r 时进行比较
图4, 5 改进的模式匹配算法主串比较时不用回退
引入标记 next[q]表示：当模式串
偏移量为 q的字符与主串字符比较不
等时，应该用模式串偏移量为 new[q]
的字符与主串原字符比较。则有：
n e x t [ q ] =
- 1 （ q =0 ）
M a x i m u m { r | t
1
,.,t
r
= t
q -r + 1
,.,t
q
∧ 1 ≤ r ≤q - 1 } （ q ≠ 0,集合不为空）
0 （ q ≠ 0,集合为空）
{
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
( a ) 向右移动子串之前 （b ）第一次向右移动子串
图4,6 串模式匹配的改进算法实例
i=0
（c ）第二次向右移动子串
j=0
i=1
j=1
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=2
j=2
i=3
j=3
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=3
j=0
i=4
j=1
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=5
j=2
i=6
j=3
i=3
j=1
串模式匹配的改进算法实例：
此改进算法是由 D.E.Knuth、
J.H.Morris和 V.R.Pratt同时发现的，
我们简称此算法为 KMP算法。由
于匹配过程中主串不会出现回退
的情况，所以此算法的算法复杂
度的数量级为 O（ m+n），其中
m和 n分别为主串与模式串的长度。
4.4 本章小结
?基本内容：
1.字符串的基本概念
2,字符串的三种表示形式及相
应的典型操作的实现
3,字符串的基本模式匹配算法
及其改进
? 基本要求：
熟悉串的七种基本操作的定义, 并能
利用这些基本操作实现串的其他各种操
作 。
熟练掌握在串的定长顺序存储结构,
堆存储结构上实现串的各种操作的方法 。
掌握串的块链存储结构以及在其上实
现串操作的基本方法 。
理解串匹配的 KMP算法，熟悉 next函
数的定义，学会手工计算给定模式串的
next函数值。
4.2 字符串的存储方式
4.3 字符串的模式匹配算法
4.4 本章小结
4.1 字符串的基本概念
4.1 字符串的基本概念
1,基本概念
? 字符串, 字符组成的有限序列, 用一对 双引号 的
分界符括起来 。
? 字符串的长度,字符串中包含的字符数目。
? 空字符串,简称空串，长度为零的字符串。可用
“”表示。
请注意：字符的
界符为单引号
? 子串, 一个串中的任意连续字符组成的子序列。
? 主串,相应的，称包含子串的那个串为主串。
? 字符在串中的位置, 指该字符在字符序列中的位置 。
? 串相等,长度相等，并且这两个串对应位置上的字
符全部相等。
2.串的 ADT声明
从逻辑结构上看，串非常类似于线性表；在基本操作上，
串与线性表有较大的区别：
ADT String
{ 数据对象内容限定为字符集合：
D={ai | ai ∈ 字符集合, i=1,2,…,n,
n≥ 0}
数据间的线性关系：
R={<ai,ai+1>| ai ∈ D,i=1,2,…,n-1}
几种基本操作：
strAssign (&str,origin)
strCompare (str1,str2)
strLength(str)
用 origin这个字符数组
来构造一个串 str
按字典序比较两个串
str1和 str2
求串 str1的长度
strConcatenate(str1,str2,&str)
strSubstring(str,pos,length,&sub)
strClear(&str)
strDestroy(&str)
}
顺序连接 str1和 str2两
个字符串，得到串 str
从串 str的第 pos个位置开始
连续取长度为 length个字符
构成的子串 sub
将串 str清空
将串 str销毁并回
收空间
4.2 字符串的存储方式
4.2.2 串的堆分配存储表示
4.2.3 块链存储表示
4.2.1 定长顺序存储表示
基本思想,
预先划定数组的容量，待存储的字
符串长度只要不大于数组的容量即可。
如果串的长度超出了预定空间大小，
超出的字符串内容通过,截断,的方法
直接舍去。
引入 字符串长度 或者 字符串结束符
以明确存储空间内哪些是字符串的有效
内容。
4.2.1 定长顺序存储表示
//FixedLengthString.h
#define CAPACITY 256
class FLString
{ private:
int length;
char *content;
void strCopy(int offset1,char
*origin,int offset2,int len);
public:
FLString();
FLString(char *origin);
从字符数组 origin偏移
量为 offset2的字符开始,
连续拷贝 len个字符到本
串从偏移量 offset1处开
始的地方
构造函数, 用于创建一个空串
构造函数, 由 origin字符数组
的内容构造串
int strCompare(FLString str);
int strLength();
bool strConcatenate(FLString str1,
FLString str2);
//当前串与串 str比较大小
当前串与串 str比较大小
将串 str1与串 str2拼接后存
入当前串中
bool strSubstring(int pos,int len,
FLString &sub);
void strClear();
~FLString();
};
从当前串偏移量为 offset的字
符开始, 将长度为 len的一段
连续字符复制到串 sub中
串的清空操作
析构函数，用于销毁串
定长顺序存储表示的不足,
只要在操作中发现字符串长度大于预定义的最大
容量，就采取, 截断, 的方法，这样操作的结果会引
起 信息的损失 。
如果字符串长度远远小于预定义的最大容量，则
又会 浪费空间 。
改进方法：
不再事先预定好串的存储空间，而是根据串的
大小 实时分配空间 。这种更灵活的连续存储方式就
是, 堆分配存储表示, 。
4.2.2 串的堆分配存储表示
基本思想,
“按需分配”。
当字符串有效内容的长度发生变
化，原来的空间就会释放掉，同时
重新开辟一个和新内容长度一样的
字符数组来存储新的字符串。
串的, 堆分配存储表示, 与,定长顺序存储表
示,同 属采用数组进行的连续存储方式, 实现方法类
似，其区别体现在以下方法的实现过程：
//HeapString.h
class HString
{ private:
......
public:
//构造函数, 用于创建一个空串
HString();
//构造函数, 由 origin字符数组的内容构造串
HString(char *origin);
//当前串与串 str比较大小
int strCompare(HString str);
......
//将串 str1与串 str2拼接后存入当前串中
void strConcatenate(HString str1,HString
str2);
//从当前串偏移量为 offset的字符开始, 将长度为 len的
一段连续字符复制到串 sub中
void strSubstring(int pos,int len,HString
&sub);
......
//析构函数, 用于销毁串
~HString();
};
顺序存储表示小结,
对于以数组连续存储的字符串来说，其实现一
种是预先定义好的定长方式，即定长存储，其特点在
于,灵活性较差，但是较简单 ；
另一种方式则是根据字符串长度动态分配的，
即堆分配存储，其特点在于,不会造成空间的浪费，
但实现的时候要麻烦一些。
说明：
上面两种方式在实现时都使用了内存的 动态分
配方式,是在运行时为相应的变量分配的空间；相
对应的，在编译时就已经能够确定变量存储空间大
小的，叫做内存的 静态分配方式 。
4.2.3 块链存储表示
基本思想,
按照链表的方式进行存储 。
考虑使用链表后，指针所占的空间会增
加一定的空间开销。因此，为了减少开销，
应该尽量做到在一个节点中多存储一些字符。
这时，节点当中好像存储的是一, 块, 数据，
而不再是一, 个, 数据，所以形象地称其为
,块链, 。
引入, 存储密度, 这个概念来衡量开销的大小：
存储密度 =串中内容所占的存储位 /实际分配的存储位
节点大小不同的块链存储方式,
‘A’ ‘B’ ‘C’ ‘D’ ‘E’ - - - ∧
‘A’ ‘B’ ‘C’ - ‘D’ - - ‘E’ ∧
‘A’ ‘B’ ‘C’ ‘D’ ‘E’ ∧
( a ) 节点大小为4 的块链存储方式的一种情况
( b ) 节点大小为4 的块链存储方式的另一种情况
( c ) 节点大小为1 的块链存储方式的一种情况
图4, 3 串“A B C D E,的块链存储方式
head
head
head
块链存储方式表示的优劣分析：
优点,存取灵活
不足,空间开销相对较大，而且
实现也是相当复杂繁琐的。
一般只有在特殊的应用场合（如
所处理的字符串平均长度非常大时）才
会使用 块链存储 。
4.3 字符串的模式匹配算法
? 4.3.1 串模式匹配的基本算法
? 4.3.2 串模式匹配的改进算法
关于串的模式匹配的相关术语,
字符串的模式匹配,在目标区域内的
字符串中进行从前到后的扫描，看有没有一段
连续的字符与待查找的字符串完全匹配。
其中：
主串,查找的目标区域的字符串。
模式,相应地，待查找的串可以称为
,模式, 。
4.3.1 串模式匹配的基本算法
匹配算法功能：
找到在主串中第一次出现模式串的位
置。
基本思想,
模式串从字符串首位置开始，依次与主串相应
位置比较，不成功则整体后移一位。即对于主串
来说，第一趟从第一个字符开始，第二趟从第二
个字符开始，依此类推。
‘a ’ ‘b ’ ‘a ’ ‘a ’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b ’ ‘a ’ ‘a ’ ‘b ’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a ’ ‘a ’ ‘b ’ ‘a ’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a ’ ‘b ’ ‘a ’ ‘d ’
‘a’ ‘b’ ‘a’ ‘c’
( c ) 第三趟比较 （d ）第四趟比较
( a ) 第一趟比较 （b ）第二趟比较
图4.4 串模式匹配的基本算法
分析可知,
如果主串长度为 m，模式串长度为 n，则最多
的比较趟数为 m-n+1。在最差情况下，这种算法的
复杂度为 (m-n+1)*n，属于 O(N2)级别。
4.3.2 串模式匹配的改进算法
串模式匹配的基本算法简单易懂，
但是由于某趟比较失败而进入下一趟比
较时，主串有可能会 回退 到以前比较过
的某个字符以便重新和模式串比较，这
就在很大程度上影响了算法的效率。
为解决主串的回退问题，可以对算
法进行改进：
假设主串为 s=s1s2…s m-1sm，模式串为
t=t1t2…t n-1tn，其中 si（ 1≤ i≤ m）和 tj（ 1≤ j≤ n）都
是字符元素，在图 4.5中描述了匹配过程中字符串
的比较情况。
i=p
j=q
s
1
s
2
t
1
..,s
p-q+1
..,s
p-r+1
..,s
p
s
p+1
...
..,t
q-r+1
..,t
q
t
q+1
...
t
1
..,t
r
t
r+1
...
i=p
s
1
s
2
..,s
p-q+1
..,s
p-r+1
..,s
p
s
p+1
...
j=r
（a ） i = p,j = q 时出现不匹配
（b ） 子串右移后，i = p,j = r 时进行比较
图4, 5 改进的模式匹配算法主串比较时不用回退
引入标记 next[q]表示：当模式串
偏移量为 q的字符与主串字符比较不
等时，应该用模式串偏移量为 new[q]
的字符与主串原字符比较。则有：
n e x t [ q ] =
- 1 （ q =0 ）
M a x i m u m { r | t
1
,.,t
r
= t
q -r + 1
,.,t
q
∧ 1 ≤ r ≤q - 1 } （ q ≠ 0,集合不为空）
0 （ q ≠ 0,集合为空）
{
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
( a ) 向右移动子串之前 （b ）第一次向右移动子串
图4,6 串模式匹配的改进算法实例
i=0
（c ）第二次向右移动子串
j=0
i=1
j=1
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=2
j=2
i=3
j=3
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=3
j=0
i=4
j=1
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
‘a’ ‘b’ ‘a’ ‘a’ ‘b’ ‘a’ ‘d’
‘a’ ‘b’ ‘a’ ‘c’
i=5
j=2
i=6
j=3
i=3
j=1
串模式匹配的改进算法实例：
此改进算法是由 D.E.Knuth、
J.H.Morris和 V.R.Pratt同时发现的，
我们简称此算法为 KMP算法。由
于匹配过程中主串不会出现回退
的情况，所以此算法的算法复杂
度的数量级为 O（ m+n），其中
m和 n分别为主串与模式串的长度。
4.4 本章小结
?基本内容：
1.字符串的基本概念
2,字符串的三种表示形式及相
应的典型操作的实现
3,字符串的基本模式匹配算法
及其改进
? 基本要求：
熟悉串的七种基本操作的定义, 并能
利用这些基本操作实现串的其他各种操
作 。
熟练掌握在串的定长顺序存储结构,
堆存储结构上实现串的各种操作的方法 。
掌握串的块链存储结构以及在其上实
现串操作的基本方法 。
理解串匹配的 KMP算法，熟悉 next函
数的定义，学会手工计算给定模式串的
next函数值。
