1北京邮电大学自动化学院
第四章 串
?4.1 串类型的定义
?4.2 串的表示和实现
? 1 定长顺序存储表示
? 2 堆分配存储表示
? 3 串的块链存储表示
?4.3 串的模式匹配算法
?4.4 串操作应用举例
2北京邮电大学自动化学院
? 一、串和基本概念
4.1 串类型的定义
? 1、串 (String)
? 串是零个或多个字符组成的有限序列。一般记作
S= ?a1a2a3…a n?，其中 S 是串名，单引号括起来的字符序列
是串值； ai(1≦ i≦ n)可以是字母、数字或其它字符；串中所
包含的字符个数称为该 串的长度 。
? 长度为零的串称为 空串 (NULL String)，它不包含任何字符。
? 注意,空串和空白串的不同，例如‘ ’和‘’分别表示长度
为 1的空白串和长度为 0的空串。
? 通常将仅由一个或多个空格组成的串称为 空白串 (Blank
String)。
3北京邮电大学自动化学院
? 串中任意个连续字符组成的子序列称为该串的 子串,包含子串
的串相应地称为 主串 。
一、串和基本概念
? 通常将子串在主串中首次出现时的该子串的首字符对应的主
串中的序号，定义为子串在主串中的序号（或位置）。
? 例如，设 a,b,c,d为如下的四个串：
? a=?BEI?, b=?JING?,c=?BEIJING?,d=?BEI JING?
? 则它们的长度分别为 3,4,7,8；并且 a和 b都是 c和 d的子
串,a在 c和 d中的位置都是 1，而 b在 c的位置是 4，在 d中的
位置则是 5。
? 特别地，空串是任意串的子串,任意串是其自身的子串。
4北京邮电大学自动化学院
? 当且仅当两个串的值相等，称两个串是相等 。也就是说，只
有两个串的长度相等，并且各对应位置的字符都相等时才相
等。例如上例中的串 a,b,c和 d彼此都不是相等。
一、串和基本概念
? 串值必须用一对单引号扩起来但单引号本身不属于串，它的
作用只是为了避免于变量名或数的常量混淆而已。
? 通常在程序中使用的串可分为两种：串变量和串常量。串常
量和整常数、实常数一样，在程序中只能被引用但不能不能
改变其值，即只能读不能写。
? 通常串常量是由直接量来表示的，例如语句
Error(“overflow”)中,overflow”是直接量。但有的语言允
许对串常量命名，以使程序易读、易写。如 C++中，可定义
?const char path[]=“dir/bin/appl”;
5北京邮电大学自动化学院
? const char path[]=“dir/bin/appl”;
? 这里 path是一个串常量，对它只能读不能写。串变量和其它
类型的变量一样，其取值是可以改变的。
一、串和基本概念
? 串的逻辑结构和线性表极为相似,区别仅在于串的数据对象
约束为 字符集。 然而，串的基本操作和线性表有很大差别。
? 在线性表中的基本操作中，大多数以,单个元素” 作为操作
对象。例如在线性表中查找某个元素、求取某个元素、在某
个位置上插入一个元素和删除一个元素等；
? 而在串的基本操作中，通常以,串的整体”作为操作对象,
例如在串中查找某个子串、求取一个子串、在串的某个位置
上插入一个子串以及删除一个子串等。
6北京邮电大学自动化学院
? ADT String {
D＝ { ai |ai∈ CharacterSet,i=1,2,...,n,≥0 }
? 数据关系,R1＝ { < ai-1,ai > | ai-1,ai ∈ D,i=2,...,n }
二、串的抽象数据定义
? 基本操作, ? StrAssign (&T,chars)//串赋值
? 初始条件,chars 是字符串常量。
? 操作结果：把 chars 赋为 T 的值。
? StrCopy (&T,S)//串复制
? 初始条件：串 S 存在。
? 操作结果：由串 S复制到串 T。
? 数据对象：
7北京邮电大学自动化学院
? StrCompare (S,T)//串比较
?初始条件：串 S 和 T 存在。
? 操作结果：若 S ? T，则返回值 ? 0；
? 若 S ? T，则返回值 ? 0；
? 若 S ? T，则返回值 ? 0。
二、串的抽象数据定义
? StrLength (S) //求串长
? 初始条件：串 S 存在。
? 操作结果：返回 S 的元素个数,称为串的长度。
8北京邮电大学自动化学院
? Concat (&T,S1,S2)//串连接
? 初始条件：串 S1 和 S2 存在。
? 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。
二、串的抽象数据定义
? SubString (&Sub,S,pos,len)
?初始条件：串 S 存在,1≤pos≤StrLength(S),且
0≤len≤StrLength(S)-pos+1。
?操作结果：用 Sub 返回串 S 的第 pos 个字符起长度
为 len 的子串。
9北京邮电大学自动化学院
? DestroyString (&S)
? 初始条件：串 S 存在。
? 操作结果：串 S 被销毁。
二、串的抽象数据定义
? StrEmpty (S)
? 初始条件：串 S存在。
? 操作结果：若 S 为空串,则返
回 true,否则返回 false。
? ClearString (&S)
? 初始条件：串 S存在。
? 操作结果：将 S清为空串。
? } ADT String
10北京邮电大学自动化学院
? 在上述抽象数据类型定义的 13种操作中，
三、串的基本操作
? 串赋值 StrAssign、
? 串比较 StrCompare、
? 求串长 StrLength、
? 串联接 Concat
? 求子串 SubString
? 等五种操作构成串类型的最小操作子集。即：这些操作不可
能利用其他串操作来实现,反之，其他串操作（除串清除
ClearString和串销毁 DestroyString外）可在这个最小操作
子集上实现。
11北京邮电大学自动化学院
? 对于串的基本操作，许多高级语言均提供了相应的运算或
标准库函数来实现。下面仅介绍几种在 C语言中常用的串
运算，其它的串操作见相应的文件。
三、串的基本操作
? 定义下列几个变量：
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? （ 1）求串长 (length)
? int strlen(char s); //求串的长度
? 例如,printf(“%d”,strlen(s1)); 输出 13
12北京邮电大学自动化学院
? （ 2）串复制 (copy)
? char *strcpy(char to,char from);
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? 该函数将串 from复制到串 to中，并且返回一个指
向串 to的开始处的指针。
? 例如,strcpy(s3,s1); //s3=“dirtreeformat”
13北京邮电大学自动化学院
? （ 3）联接 (concatenation)
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
三、串的基本操作
? char strcat(char to,char from)
? 该函数将串 from复制到串 to的末尾，并且返回一指向串
to的开始处的指针。
? 例如,strcat(s3,”/”)
? strcat(s3,s2); //s3=“dirtreeformat/file.mem”
14北京邮电大学自动化学院
? (4)串比较（ compare)
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? int strcmp(chars1,char s2);
? 该函数比较串 s1和串 s2的大小，当返回值小于 0，等于 0或大于
0时，分别表示 s1<s2,s1=s2或 s1>s2
? 例如,result=strcmp(“baker”,”bake”) result>0
? result=strcmp(“12”,”12”); result=0
? result=strcmp(“Joe”,“Joseph”); result<0
15北京邮电大学自动化学院
? （ 5）字符定位 (index)
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? char strchr(char s,char c);
? 该函数是找 c在字符串中第一次出现的位置，若找到则返回该
位置，否则返回 NULL。
? if(p) strcpy( p,“.cpp”); s2=“file.cpp”
? 例如,p=strchr(s2,“.”); p 指向,file”之后的位置
16北京邮电大学自动化学院
? 上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由
这些基本操作组合而成。
例 1、求子串
? 例 1、求子串 求子串的过程即为复制字符序列的过程，将串
S中的第 pos个字符开始长度为 len的字符复制到串 T中。
? void substr(string sub,string s,int pos,int len) {
? if(pos<0 || pos>strlen(s)-1 || len<0)
? error(“parameter error”)
? strncpy(sub,&s[pos],len); }
17北京邮电大学自动化学院
? 例 2、可利用 串比较,求串长和求子串等操作实现定位函数
Index( S,T,pos )串的定位。
例 2、串的定位
? Index (S,T,pos)
? 初始 条件,串 S和 T存在,T是非空串，
1≤pos≤StrLength(S)。
? 操作结果,若主串 S 中第 pos个字符之后存在和串 T 值相同
的子串,则返回它在主串 S 中第 pos个字符之后第一次出现
的位置；否则函数值为 0。
18北京邮电大学自动化学院
?“子串在主串中的位置”是指子串中的第一个字
符在主串中的位序。
例 2、串的定位
?假设 S = ?abcaabcaaabc ?,T = ?bca ?
?Index(S,T,1) = 2;
?Index(S,T,3) = 6;
?Index(S,T,8) = 0;
19北京邮电大学自动化学院
算法的基本思想为：
StrCompare(SubString(S,i,StrLength(T)),T )
S 串
T 串 T 串
i
pos n-m+1
0
例 2、串的定位
20北京邮电大学自动化学院
? int Index (String S,String T,int pos) {
? // T为非空串。若主串 S中第 pos个字符之后存在与 T相等的子串，
? // 则返回第一个这样的子串在 S中的 位置，否则返回 0
? If (pos>0) { n = StrLength(S); m = StrLength(T); i = pos;
? while ( i <= n-m+1) {
? SubString (sub,S,i,m);
? return 0; // S中不存在与 T相等的子串
? } // Index
? if (StrCompare(sub,T) != 0) ++i ;
? else return i ; } // while } // if
21北京邮电大学自动化学院
? 因为串是特殊的线性表，故其存储结构与线性表的存储结构
类似。只不过由于组成串的结点是单个字符。串有三种机内
表示方法，下面分别介绍。
4.2 串的表现和实现
? 1、定长顺序存储表示
? 定长顺序存储表示,类似于线性表的顺序存储结构，是用一
组地址连续的存储单元存储串值的字符序列。在串的定长顺
序存储结构中，按照预定义的大小，为每个定义的串变量分
配一个固定长度的存储区，则可用定长数组来如下描述。
? #define maxstrlen 255 //用户可在 255以内定义最大串长
? typedef unsigned char SString[MAXSTRLEN+1];
? //0号单元存放串长
22北京邮电大学自动化学院
? 串的实际长度可在这预定义长度的范围内随意，超过预定义
长度的值则被舍去，称之为,截断” 。
? 对于串长有两种办法：
? 一是如上述定义描述的那样以下标为 0的数组分量存放串的
实际长度； 用一个整数来表示串的长度，那么该长度减 1的
位置就是串值的最后一个字符的位置。此时顺序串的类型定
义和顺序表类似,
? 二是在串值后面加入一个不计入串长的结束标记符，例
如,C语言中以字符 ‵ \0′表示串值的终结,
1、定长顺序存储表示
23北京邮电大学自动化学院
1、定长顺序存储表示
? 求子串 SubString(&Sub,S,pos,len),求子串的过程即为复
制字符序列的过程，将串 S中从第 pos各字符开始长度为 len
的字符序列复制到串 Sub中。
? 显然，本操作不会有需要截断的情况，但有可能产生用户给
出的参数不符合操作的初始条件，当参数非法时，返回
ERROR。
? typedef struct{
? char ch[maxstrlen];
? int length;
? }SString; //其优点是涉及到串长操作时速度快。
24北京邮电大学自动化学院
? Status SubString (SString &S,SString S,int pos,int len) {
? //用 Sub返回串 S的第 pos个字符起长度为 len的子串。
? //其中,1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-
pos+1.
? If (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
? return ERROR;
? Sub[1..len]=S[pos..pos+len-1];
? } // SubString
? Sub[0]=len
? return OK;
求子串 SubString(&Sub,S,pos,len)
25北京邮电大学自动化学院
? 这种存储表示的特点是，仍以一组地址连续的存储单元存放串
值字符序列，但它们的存储空间是在程序执行过程中动态分配
而得。所以也称为 动态存储分配的顺序表 。
2、堆分配存储表示
? 在顺序存储结构中，实现串操作的原操作为“字符序列的复
制”，操作的时间复杂度基于复制的字符序列的长度。
? 克服这个弊病惟有不限定串长的最大长度，即动态分配串的
存储空间。
1、定长顺序存储表示
? 如果在操作中出现串值序列的长度超过上界 MAXSTRLEN
时,约定用截尾法处理,这种情况不仅在求连接串时可能发
生，在串的其它操作中，如插入、置换等也可能发生。
26北京邮电大学自动化学院
? 在 C语言中，存在一个称之为“堆”的自由存储区，并由 C语言
的动态分配函数 malloc()和 free()来管理。利用函数 malloc()为
每个新产生的串分配一块实际串长所需的存储空间，若分配成
功，则返回一个指向起始地址的指针，作为串的基址，同时，
为了以后处理方便，约定串长也作为存储结构的一部分。
? //串的堆分配存储表示
? typedef struct{
? char *ch;//若是非空串，则按串长分配存储区，否
则 ch为 NULL
? int length;/串长度
? }HString;
27北京邮电大学自动化学院
? 这种存储结构表示时的串操作仍是基于“字符序列的复制”
进行的。例如，串复制操作 StrCopy(&T,S)的实现算法是,若
串 T已存在，则先释放串 T所占空间，当串 S不空时，首先为
串 T分配大小和串 S长度相等的存储空间，然后将串的值复制
到串 T中；
? 又如串插入操作 StrInsert(&S,pos,T)的实现算法是，为串 S重
新分配大小等于串 S和串 T长度之和的存储空间，然后进行串
值复制。
2、堆分配存储表示
28北京邮电大学自动化学院
? Status SubInsert (HString &S,int pos,HString T) {
? //1≤pos≤StrLength(S)+1.在串 S的第 pos个字符之前插入串 T.
? If (pos<1 || pos>S.length+1) return ERROR;//pos不合法
? If (T.length){ //T非空，则重新分配空间，插入 T
? If(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(ch
ar)))) exit (OVERFLOW);
? S.ch[pos-1..pos＋ T.length-2]=T.ch[0..T.length-1]; //插入 T
? for(i=S.length-1;i>=pos-1;--i)//为插入 T而腾出位置
? S.ch[i+T.length]=S.ch[i];
2、堆分配存储表示
29北京邮电大学自动化学院
? S.length+=T.length;
? }
? Return OK;
? }//StrInsert
? 只含最小操作子集的 HString串类型的模块说明见 P76～
77。
2、堆分配存储表示
? 以上两种存储表示通常为高级程序设计语言所采用
? 由于堆分配存储结构的串既有顺序存储结构的特点，处理方
便，操作中对串长没有任何限制，更显灵活，因此在串处理
的应用程序中也常被选用。
30北京邮电大学自动化学院
? 顺序串上的插入和删除操作不方便，需要移动大量的字符。因
此，我们可用单链表方式来存储串值,串的这种链式存储结构
简称为链串。
3、串的链式存储结构
? typedef struct node{
? char data;
? struct node *next;
? }Lstring;
? 一个链串由头指针唯一确定。
? 这种结构便于进行插入和删除运算，但总的来说不如顺
序存储结构灵活，它占用存储量大且操作复杂。
31北京邮电大学自动化学院
? 为了提高存储密度，可使每个结点存放多个字符。通常将 结
点数据域存放的字符个数定义为结点的大小,显然，当结点
大小大于 1时，串的长度不一定正好是结点的整数倍，因此
要用特殊字符来填充最后一个结点，以表示串的终结。
? 对于结点大小不为 1
的链串，其类型定
只需对上述的结点
类型做简单的修改
即可。
? #define nodesize 80
? typedef struct node{
? char data[nodesize];
? struct node *next;
? }Lstring;
3、串的链式存储结构
32北京邮电大学自动化学院
? 显然，存储密度小（如节点大小为 1时），运算处理方便，然
而，存储占用量大。如果在串处理过程中需进行内、外存交
换的话，则会因为内外存交换操作过多而影响处理的总效
率。
存储密度 = 串值所占的存储位 实际分配的存储位
? 在链式存储方式中，节点大小的选择和顺序存储方式的格式
选择一样都很重要，它直接影响着串处理的效率。在各种串
的处理系统中，所处理的串往往很长或很多，这要求我们考
虑串值的存储密度。存储密度可定义为：
3、串的链式存储结构
33北京邮电大学自动化学院
? 实际应用时，可以根据问题所需来设置结点的大小。例
如, 在编辑系统中，整个文本编辑区可以看成是一个串，
每一行是一个子串，构成一个结点。即, 同一行的串用定
长结构 (80个字符 ),行和行之间用指针相联接。
? 串值的链式存储结构对某些操作，如联接操作等有一定方
便之处，但 总的说来不如另外两种存储结构灵活，它占用
存储量大且操作复杂。
? 此外，串值在链式存储结构时串操作的实现和线性表在链
表存储结构中的操作类似。
3、串的链式存储结构
34北京邮电大学自动化学院
? 这是串的一种重要操作，很多软件，若有“编辑”菜单项的
话,则其中必有“查找”子菜单项。首先，回忆一下串匹
配 (查找 )的定义,
4.3 串的模式匹配算法
? INDEX (S,T,pos)
? 初始条件,串 S 和 T 存在,T 是非空串，
1≤pos≤StrLength(S)。
? 操作结果,若主串 S 中存在和串 T 值相同的子串返回它在
主串 S 中第 pos 个字符之后第一次出 现 的位置 ; 否则函数值
为 0。
35北京邮电大学自动化学院
1、简单算法
? 模式匹配的最简单的做法是,用模式串 T中的字符依次与主
串 S的字符比较：
? t1 t2 t3 … t m
t1 t2 t3 … t m
? 如此反复比较，直至
主串 S中找到模式串 t
或者确定该模式不存
在为止。
? S1 S2 S3 … S m Sn
? 如果 t1=s1,t2=s2,…, tm=sm则匹配成功。否则必有某个
i(1<i<m)，使得 ti不等于 si，这时可从主串 s中与 t1比较的字
符的下一个字符起（将串 t右移一个字符）再重新与模式串 t
中字符依次比较：
? S1 S2 S3 … S m Sm+1… S n
36北京邮电大学自动化学院
? 设 S=“abbaba”,T=“aba”，用上述做法进行模式匹配的过
程见下图：
? S,a b b a b a ? S:a b b a b a
(a) T3 ? S3
? S,a b b a b a
? T,a b a
(b) T1 ? S2
? ? T1 ? S3 ? (d)找到模式串
? T,a b a
? S,a b b a b a
? T,a b a
? T,a b a
37北京邮电大学自动化学院
S 串
T 串 T 串
i
pos n-m+1
S 串
T 串 T 串
i
j j>m
i
j
i
j
i
j
i>n
j
串
简单算法示意图
38北京邮电大学自动化学院
? int Index(SString S,SString T,int pos) {
? // 返回子串 T在主串 S中第 pos个字符之后的位置。若不存在，
则函数值为 0。 其中,T非空,0≤pos≤StrLength(S)。
? i = pos; j = 1;
? while (i <= S[0] && j <= T[0]) {
? if (S[i] == T[j]) { ++i; ++j; }// 继续比较后继字符
? else { i = i-j+2; j = 1; } // 指针后退重新开始匹配 }
? if (j > T[0]) return i-T[0];
? else return 0; } // Index
简单算法
39北京邮电大学自动化学院
2、简单模式算法分析
?上页的匹配过程易于理解，且在某些应用场合，如
文本编辑等，效率也较高，例如，在检查模式
,STING”是否存在于下列主串中时，,A STRING
SEARCHING EXAMPLE CONSISTING OF
SIMPLE TEXT”
?上述算法中的 while循环次数（即进行单个字符比较
的次数）为 41，恰好为（ Index+T[0]-1)+4）,这就是
说，除了主串中呈红色的四个字符，其它字符均只
和模式进行一次比较。在这种情况下，此算法的时
间复杂度为 O（ n+m)。
40北京邮电大学自动化学院
? 例题 2，设主串 s=“ababcabcacbab”，模式 t=“abcac”，匹
配过程如下图所示。
? 第一趟
? 第二趟
? 第三趟
? 第四趟
? 第五趟
? 第六趟
41北京邮电大学自动化学院
? 然而，在有些情况下，该算法的效率却很低。
? 例如,当模式串,00000001”，而主串为,00000000000
000000000000000000000000000000000000000001”时，由
于模式中前 7个字符均为,0”，又，主串中前 52个字符均为
,0”，每趟比较都在模式的最后一个字符出现不等，此时需
将指针 i回溯到 i-6的位置上，并从模式的第一个字符开始重新
比较，整个匹配过程中指针需要回溯 45次，则 while的循环次
数为 46*8。可见算法在最坏情况下的时间复杂度为 O(n*m)。
? 这种情况在只有 0,1两种字符的文本串处理中经常出现，因
为在主串中可能存在多个和模式串“部分匹配”的子串，因
而引起指针 i的多次回溯。
? 0,1串可以用在许多应用之中。（需要改进）
42北京邮电大学自动化学院
3、模式匹配的改进算法
?这种改进算法是 D.E.Knuth,V.R.Pratt和 J.H.Morris
同时发现的，因此人们称它为 克努特 —莫里斯 —普
拉特操作（简称为 KMP算法） 。此算法可以在 O
（ n+m)的时间数量级上完成串的模式匹配操作。
?改进算法,每当一趟匹配过程中出现字符比较不等
时，不需回溯 i指针，而是利用已经得到的“部分匹
配”的结果将模式 向右“滑动”尽可能远的一段距
离后,继续进行比较。
?下面先从具体例子看起。
43北京邮电大学自动化学院
? 回顾例 2中的匹配过程,在第三趟匹配过
程中,s3 ~ s6和 t1~ t4是匹配成功的,s7≠t5
匹配失败，又从 i=4,j=1开始重新开始
比较。
? 因为从第 3趟部分匹配的结果就可得出，主串中第 4,5和 6个
字符必然是’ b?、’ c?和’ a?。因为模式中的第 1个字符
是’ a?，因此它无需再和这 3个字符进行比较,而仅需将模式
向右滑动 3个字符的位置继续进行 i=7,j=2时的字符比较即
可。
? i=4,j=1
? i=5,j=1
? i=6,j=1
44北京邮电大学自动化学院
? 同理，在第 1趟匹配中出现字符不等时 仅需将模式向右移动二个
字符的位置继续进行 i=3,j=1的字符比较。
? 由此在整个匹配的过程中 i 指
针没有回溯。
? 改进算法的匹配过程如下图
所示。
45北京邮电大学自动化学院
?现在讨论一般情况。假设主串为,S1,S2
S3,…S n”，模式串为,t1 t2 … t m”，为了实现改
进算法，需要解决下述问题：
?当匹配过程中产生“失配”（即 Si不等于 tj)时，模式
串“向右滑动”可行的距离多远，换句话说,当主
串中第 i个字符和模式中第 j个字符“失配”（即比较
不等 )时，主串中第 i字符（指针 i不回溯）应与模式
中的哪个字符再比较？
3、模式匹配的改进算法
46北京邮电大学自动化学院
? 假设此时应与模式中第 k (k<j)个字符继续比较，则模式中前 k-
1个字符的子串必须满足下列关系式 (4-1)，且不可能存在 k?>k
满足下列关系式（ 4-1）：
? 而本趟匹配失败是在 si和 tj之处，已经得到的部分匹配结果是
?,t1 t2 … t k-1, =“si-k+1 si-k+2 … s i-1” (4-1)
? (4-1)式左边是 tk前面的 k-1个字符，右边是 si 前面的 k-1个字符。
?,t1 t2 … t j-1” =“si-j+1 si-j+2 … si-1” (4-2)
? 因为 k<j，所以有：
?,tj-k+1 tj-k+2 … t j-1” =“si-k+1 si-k+2 …s i-1” (4-3)
3、模式匹配的改进算法
47北京邮电大学自动化学院
?,tj-k+1 tj-k+2… t j-1” =“si-k+1 si-k+2…s i-1” (4-3)
? 反之，若模式串中存在满足（ 4-4）的两个子串，则当匹配
过程中，主串第 i个字符与模式中第 j个字符比较不等时，仅
需将模式向右滑动至模式中第 k个字符和主串中第个 i字符对
齐。
? （ 4-3）式左边是 tj前面的 k-1个字符，右边是 si前面的 k-1个字
符，通过 (4-1)和 (4-3)得到关系：
?,t1 t2 … t k-1” =“tj-k+1 tj-k+2 … t j-1” (4-4)
?,t1 t2 … t k-1, =“si-k+1 si-k+2 … s i-1” (4-1)
3、模式匹配的改进算法
48北京邮电大学自动化学院
?,t1 t2 … t k-1” =“tj-k+1 tj-k+2 … t j-1” (4-4)
? 反之，若模式串中存在满足（ 4-4）的两个子串，则当匹配
过程中，主串第 i个字符与模式中第 j个字符比较不等时，仅
需将模式向右滑动至模式中第 k个字符和主串中第个 i字符对
齐。
? 此时，模式中头 k-1个字符的子串,t1 t2 … t k-1, 必定与主
串中第 i个字符之前长度为 k-1的字串,si-k+1 si-k+2 …s i-1,
相等，由此，匹配仅需从模式中第 k个字符与主串中第 i个字
符处，继续进行比较。
3、模式匹配的改进算法
49北京邮电大学自动化学院
?若令 next[j]=k，则 next[j]表明当模式中第 j个字符与
主串中相应字符“失配”时，在模式中需要重新和
主串中该字符进行比较的位置。由此可引出模式串
的 next函数的定义：
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
??
?
?
其他情况
时当
1
"
11
""
11
"1|m a x
10
][
j
t
kj
t
k
ttjkk
j
jn ext ??
?在求得模式的 next函数后，匹配可如下进行,假设以
指针 i和 j分别指示主串和模式中正待比较的字符，令 i
的初值为 pos,j的初值为 1。
3、模式匹配的改进算法
50北京邮电大学自动化学院
? 若在匹配过程中 si=tj，则 i和 j分别增１ ;
? 若 si≠tj 匹配失败后，则 i不变,j退到 next[j]位置再比较，
? 若相等，则指针各自增１，
? 否则 j再退到下一个 next值的位置，依此类推。直至
下列两种情况：
? 一种是 j退到某个 next值时字符比较相等，则 i和 j分别增１继
续进行匹配 ;
? 另一种是 j退到值为零（即模式的第一个字符“失配”），
则此时 i和 j也要分别增１，表明从主串的下一个字符起和模
式重新开始匹配。
3、模式匹配的改进算法
51北京邮电大学自动化学院
? while (i <= S[0] && j <= T[0]) {
? if (j = 0 || S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符
3、模式匹配的改进算法
? int Index_KMP(SString S,SString T,int pos) {
? // 1≤pos≤StrLength(S)
? i = pos; j = 1;
? else j = next[j]; // 模式串向右移动
? }//while
? if (j > T[0]) return i-T[0]; // 匹配成功
? else return 0; } // Index_KMP
52北京邮电大学自动化学院
? 由以上讨论知,next函数值仅取决于模式本身而和主串无
关。我们可以从分析 next函数的定义出发用递推的方法求得
next函数值。
4,next 函数值
? 由定义知,next[1]=0 (4-5)
? 设 next[j]=k，这表明在模式串中存在下列关系：
?,t1 t2 … t k-1, =“tj-k+1 tj-k+2 … t j-1, (4-6)
? 其中 k为满足 1<k<j的某个值，并且不可能存在 k?>k满足上
式，此时 next[j+1]=? 可能有两种情况：
53北京邮电大学自动化学院
? 第一种情况：若 tk ＝ tj 则表明在模式串中
? 第二种情况：若 tk≠tj 则表明在模式串中
? 此时可把求 next函数值的问题看成是一个模式匹配问题，整
个模式串既是主串又是模式，而当前在匹配的过程中,已有
(4-6)式成立，则当 tk≠tj 时应将模式向右滑动，使得第
next[k]个字符和“主串”中的第 j个字符相比较。
?,t1 t2 … t k, =“tj-k+1 tj-k+2 … t j, (4-7)
? 即 next[j+1]=next[j]+1 (4-8)
?,t1 t2 … t k”≠“tj-k+1 tj-k+2 … t j, (4-9)
4,next 函数值
?,t1 t2 … t k-1, =“tj-k+1 tj-k+2 … t j-1, (4-6)
54北京邮电大学自动化学院
? 因此,next[j+1]=next[k]+1 (4-11)
? 若 next[k]=k′，且 t k?＝ tj，则说明在主串中第 j+1个字符之前
存在一个最大长度为 k′的子串，使得
?,t1t2…t k?”=“tj-k?+1 t j- k?+2 …t j” (4-10)
? 同理若 t k′ ≠tj，则将模式继续向右滑动至使第 next[k′]个字符
和 tj 对齐。
? 依此类推，直至 tj 和模式中的某个字符匹配成功或者不存在
任何 k′(1< k′<k <…<j) 满足 (4.10)，则有：
? next[j+1]=1 (4-12)
4,next 函数值
55北京邮电大学自动化学院
? 例题：已知模式串 t=“abcaababc”中前 6个字符的 next
函数值，求 next[7],next[8]
j 1 2 3 4 5 6 7 8
模式 a b a a b c a c
Next[j] 0 1 1 2 2 3 1 2
? Next[6]=3,t6 ≠ t3，则需要比较 t6和 t1(next[3]=1)，这相当于将
子串模式向右滑动。又由于 t6≠ t1，而且 next[1]=0，所以
next[7]=1
? Next[7]=1,t7=t1,则 ? Next[8]=next[7]+1=8
4,next 函数值
56北京邮电大学自动化学院
? void get_next(SString &T,int &next[] ) {
? // 求模式串 T的 next函数值并存入数组 next。
? i = 1; next[1] = 0; j = 0;
? while (i < T[0]) {
? if (j == 0 || T[i] == T[j])
? {++i; ++j; next[i] = j; }
? else j = next[j]; }
? } // get_next
4,next 函数值
57北京邮电大学自动化学院
? next存在的问题，例如：
? S = ?aaabaaabaaabaaabaaab?
? T = ?aaaab?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
4
2
4
3
4
j
i
j
i
j
i
? i=4,j=4时,S4≠ t4，由 next[j]的指示还需要进行
? 等三次比较
? 实际上，因为模式中第 1,2,3个字符和第 4个字符都相等，
因此不需要再和这主串第 4个字符比较，而可以将模式一气向
右滑动 4个字符的位置直接进行 i=5,j=1时的字符比较。
4,next 函数值
? next[j]= 01234,nextval[j]=00004
58北京邮电大学自动化学院
? 实际上，因为模式中第 1,2,3个字符和第 4个字符都相等，
因此不需要再和这主串第 4个字符比较，而可以将模式一气
向右滑动 4个字符的位置直接进行 i=5,j=1时的字符比较。
next[j]= 01234,nextval[j]=00004
? 这就是说，若按上述定义得到 next[j]=k，而模式中 tj=tk，则
当主串中字符 si和 tj比较不相等时，不需要再和 tk进行比较，
而直接和 next[k]进行比较，换句话说，此时的 next[j]应和
next[k]相同。
? 由此可得计算 next函数修正值的算法。
4,next 函数值
59北京邮电大学自动化学院
? void get_nextval(SString &T,int &nextval[]) { i = 1;
nextval[1] = 0; j = 0;
? while (i < T[0]) {
? if (j == 0 || T[i] == T[j]) {
? ++i; ++j;
? if (T[i] != T[j]) nextval[i] = j;
? else nextval[i] = nextval[j]; }
? else j = nextval[j]; }
? } // get_nextval
4,next 函数值
60北京邮电大学自动化学院
4.4 串操作应用举例
? 1、文本编辑
? 文本编辑程序是一个面向用户的系统服务程序，广泛用于
源程序的输入和修改。文本编辑的实质就是修改数据的形
式和或格式。虽然各种文本编辑程序的功能不同，但其基
本操作是一致的，一般都包括串的查找、插入和删除等基
本操作。
? 为了编辑的方便，用户可以利用换页符和换行符把文本划
分为若干页。每页有若干行。我们可以把文本看成是一个
字符串，称为文本串。页则是文本串的子串，行又是页的
子串。
61北京邮电大学自动化学院
? 图中 ?为换行符。
本文编辑
? 比如有下列一段源程序
? Main(){
? Float a,b,max;
? Scanf(“%f,%f”,&a,&b);
? If a>b max=a;
? Else max=b;
? };
62北京邮电大学自动化学院
行 号 起 始 地 址 长 度
100 201 8
101 209 17
102 226 24
103 267 17
104 282 15
105 282 2
? 为了管理文本串的页和行，在进入文本编辑的时候，编辑程序
先为文本串建立相应的页表和行表，即建立各子串的存储映
像。页表的每一项给出了页号和该页的起始行号。而行表的每
一项则指示每一行的行号、起始地址和该行子串的长度。
? 假设上页所示文本只占一页，且起始行号为 100，则该文本
串的行表如下图所示。
本文编辑
63北京邮电大学自动化学院
? 文本编辑程序中设立页指针、行指针和字符指针，分别指示当
前操作的页、行和字符。
? 如果在某行内插入或删除若干字符，则要修改行表中该行的
长度。若该行的长度超出了分配给它的存储空间，则要为该
行重新分配存储空间，同时还要修改该行的起始位置。
本文编辑
? 如果要插入或删除一行，就要涉及行表的插入和删除。若被
删除的行是所在页的起始行，则还要修改页表中相应页的起
始行号（修改为下一行的行号）。
? 为了查找方便，行表是按行号递增顺序存储的，因此，对行
表进行的插入或删除运算需移动操作位置以后的全部表项。
64北京邮电大学自动化学院
?1、掌握串的相关概念
?2、掌握串的存储结构及基本运算的实现
?3,熟练掌握 KMP算法的基本思想及模式匹配过程。
?4、灵活运用串的特点解决复杂的应用问题。
第四章 学习要点
65北京邮电大学自动化学院
第四章 作业
? 一、选择题
? 1、空串与空白串是相同的，这种说法 B 。
? （ A）正确 （ B）不正确
? 2、串是一种特殊的线性表，其特殊性体现在 D 。
? （ A）可以顺序存储 （ B）数据元素是一个字符
? （ C）可以链接存储 （ D）数据元素可以是多个字符
? 3,D 是 C语言中” abcd321ABCD”的子串。
? （ A） abcd （ B） 321AB（ C）” abcABC” (D)”21AB”
66北京邮电大学自动化学院
?二、填空题
?1、两个串相等的充分必要条件 是 。
?2、空串是,其长度等于 。
?3、空白串是 其长度等于 。
?4、模式串 t=?abaabcac”的 next函数值序列
为, nextval函数值序列为 。
第四章 作业
第四章 串
?4.1 串类型的定义
?4.2 串的表示和实现
? 1 定长顺序存储表示
? 2 堆分配存储表示
? 3 串的块链存储表示
?4.3 串的模式匹配算法
?4.4 串操作应用举例
2北京邮电大学自动化学院
? 一、串和基本概念
4.1 串类型的定义
? 1、串 (String)
? 串是零个或多个字符组成的有限序列。一般记作
S= ?a1a2a3…a n?，其中 S 是串名，单引号括起来的字符序列
是串值； ai(1≦ i≦ n)可以是字母、数字或其它字符；串中所
包含的字符个数称为该 串的长度 。
? 长度为零的串称为 空串 (NULL String)，它不包含任何字符。
? 注意,空串和空白串的不同，例如‘ ’和‘’分别表示长度
为 1的空白串和长度为 0的空串。
? 通常将仅由一个或多个空格组成的串称为 空白串 (Blank
String)。
3北京邮电大学自动化学院
? 串中任意个连续字符组成的子序列称为该串的 子串,包含子串
的串相应地称为 主串 。
一、串和基本概念
? 通常将子串在主串中首次出现时的该子串的首字符对应的主
串中的序号，定义为子串在主串中的序号（或位置）。
? 例如，设 a,b,c,d为如下的四个串：
? a=?BEI?, b=?JING?,c=?BEIJING?,d=?BEI JING?
? 则它们的长度分别为 3,4,7,8；并且 a和 b都是 c和 d的子
串,a在 c和 d中的位置都是 1，而 b在 c的位置是 4，在 d中的
位置则是 5。
? 特别地，空串是任意串的子串,任意串是其自身的子串。
4北京邮电大学自动化学院
? 当且仅当两个串的值相等，称两个串是相等 。也就是说，只
有两个串的长度相等，并且各对应位置的字符都相等时才相
等。例如上例中的串 a,b,c和 d彼此都不是相等。
一、串和基本概念
? 串值必须用一对单引号扩起来但单引号本身不属于串，它的
作用只是为了避免于变量名或数的常量混淆而已。
? 通常在程序中使用的串可分为两种：串变量和串常量。串常
量和整常数、实常数一样，在程序中只能被引用但不能不能
改变其值，即只能读不能写。
? 通常串常量是由直接量来表示的，例如语句
Error(“overflow”)中,overflow”是直接量。但有的语言允
许对串常量命名，以使程序易读、易写。如 C++中，可定义
?const char path[]=“dir/bin/appl”;
5北京邮电大学自动化学院
? const char path[]=“dir/bin/appl”;
? 这里 path是一个串常量，对它只能读不能写。串变量和其它
类型的变量一样，其取值是可以改变的。
一、串和基本概念
? 串的逻辑结构和线性表极为相似,区别仅在于串的数据对象
约束为 字符集。 然而，串的基本操作和线性表有很大差别。
? 在线性表中的基本操作中，大多数以,单个元素” 作为操作
对象。例如在线性表中查找某个元素、求取某个元素、在某
个位置上插入一个元素和删除一个元素等；
? 而在串的基本操作中，通常以,串的整体”作为操作对象,
例如在串中查找某个子串、求取一个子串、在串的某个位置
上插入一个子串以及删除一个子串等。
6北京邮电大学自动化学院
? ADT String {
D＝ { ai |ai∈ CharacterSet,i=1,2,...,n,≥0 }
? 数据关系,R1＝ { < ai-1,ai > | ai-1,ai ∈ D,i=2,...,n }
二、串的抽象数据定义
? 基本操作, ? StrAssign (&T,chars)//串赋值
? 初始条件,chars 是字符串常量。
? 操作结果：把 chars 赋为 T 的值。
? StrCopy (&T,S)//串复制
? 初始条件：串 S 存在。
? 操作结果：由串 S复制到串 T。
? 数据对象：
7北京邮电大学自动化学院
? StrCompare (S,T)//串比较
?初始条件：串 S 和 T 存在。
? 操作结果：若 S ? T，则返回值 ? 0；
? 若 S ? T，则返回值 ? 0；
? 若 S ? T，则返回值 ? 0。
二、串的抽象数据定义
? StrLength (S) //求串长
? 初始条件：串 S 存在。
? 操作结果：返回 S 的元素个数,称为串的长度。
8北京邮电大学自动化学院
? Concat (&T,S1,S2)//串连接
? 初始条件：串 S1 和 S2 存在。
? 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。
二、串的抽象数据定义
? SubString (&Sub,S,pos,len)
?初始条件：串 S 存在,1≤pos≤StrLength(S),且
0≤len≤StrLength(S)-pos+1。
?操作结果：用 Sub 返回串 S 的第 pos 个字符起长度
为 len 的子串。
9北京邮电大学自动化学院
? DestroyString (&S)
? 初始条件：串 S 存在。
? 操作结果：串 S 被销毁。
二、串的抽象数据定义
? StrEmpty (S)
? 初始条件：串 S存在。
? 操作结果：若 S 为空串,则返
回 true,否则返回 false。
? ClearString (&S)
? 初始条件：串 S存在。
? 操作结果：将 S清为空串。
? } ADT String
10北京邮电大学自动化学院
? 在上述抽象数据类型定义的 13种操作中，
三、串的基本操作
? 串赋值 StrAssign、
? 串比较 StrCompare、
? 求串长 StrLength、
? 串联接 Concat
? 求子串 SubString
? 等五种操作构成串类型的最小操作子集。即：这些操作不可
能利用其他串操作来实现,反之，其他串操作（除串清除
ClearString和串销毁 DestroyString外）可在这个最小操作
子集上实现。
11北京邮电大学自动化学院
? 对于串的基本操作，许多高级语言均提供了相应的运算或
标准库函数来实现。下面仅介绍几种在 C语言中常用的串
运算，其它的串操作见相应的文件。
三、串的基本操作
? 定义下列几个变量：
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? （ 1）求串长 (length)
? int strlen(char s); //求串的长度
? 例如,printf(“%d”,strlen(s1)); 输出 13
12北京邮电大学自动化学院
? （ 2）串复制 (copy)
? char *strcpy(char to,char from);
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? 该函数将串 from复制到串 to中，并且返回一个指
向串 to的开始处的指针。
? 例如,strcpy(s3,s1); //s3=“dirtreeformat”
13北京邮电大学自动化学院
? （ 3）联接 (concatenation)
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
三、串的基本操作
? char strcat(char to,char from)
? 该函数将串 from复制到串 to的末尾，并且返回一指向串
to的开始处的指针。
? 例如,strcat(s3,”/”)
? strcat(s3,s2); //s3=“dirtreeformat/file.mem”
14北京邮电大学自动化学院
? (4)串比较（ compare)
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? int strcmp(chars1,char s2);
? 该函数比较串 s1和串 s2的大小，当返回值小于 0，等于 0或大于
0时，分别表示 s1<s2,s1=s2或 s1>s2
? 例如,result=strcmp(“baker”,”bake”) result>0
? result=strcmp(“12”,”12”); result=0
? result=strcmp(“Joe”,“Joseph”); result<0
15北京邮电大学自动化学院
? （ 5）字符定位 (index)
三、串的基本操作
? char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
? char s3[30],*p; int result;
? char strchr(char s,char c);
? 该函数是找 c在字符串中第一次出现的位置，若找到则返回该
位置，否则返回 NULL。
? if(p) strcpy( p,“.cpp”); s2=“file.cpp”
? 例如,p=strchr(s2,“.”); p 指向,file”之后的位置
16北京邮电大学自动化学院
? 上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由
这些基本操作组合而成。
例 1、求子串
? 例 1、求子串 求子串的过程即为复制字符序列的过程，将串
S中的第 pos个字符开始长度为 len的字符复制到串 T中。
? void substr(string sub,string s,int pos,int len) {
? if(pos<0 || pos>strlen(s)-1 || len<0)
? error(“parameter error”)
? strncpy(sub,&s[pos],len); }
17北京邮电大学自动化学院
? 例 2、可利用 串比较,求串长和求子串等操作实现定位函数
Index( S,T,pos )串的定位。
例 2、串的定位
? Index (S,T,pos)
? 初始 条件,串 S和 T存在,T是非空串，
1≤pos≤StrLength(S)。
? 操作结果,若主串 S 中第 pos个字符之后存在和串 T 值相同
的子串,则返回它在主串 S 中第 pos个字符之后第一次出现
的位置；否则函数值为 0。
18北京邮电大学自动化学院
?“子串在主串中的位置”是指子串中的第一个字
符在主串中的位序。
例 2、串的定位
?假设 S = ?abcaabcaaabc ?,T = ?bca ?
?Index(S,T,1) = 2;
?Index(S,T,3) = 6;
?Index(S,T,8) = 0;
19北京邮电大学自动化学院
算法的基本思想为：
StrCompare(SubString(S,i,StrLength(T)),T )
S 串
T 串 T 串
i
pos n-m+1
0
例 2、串的定位
20北京邮电大学自动化学院
? int Index (String S,String T,int pos) {
? // T为非空串。若主串 S中第 pos个字符之后存在与 T相等的子串，
? // 则返回第一个这样的子串在 S中的 位置，否则返回 0
? If (pos>0) { n = StrLength(S); m = StrLength(T); i = pos;
? while ( i <= n-m+1) {
? SubString (sub,S,i,m);
? return 0; // S中不存在与 T相等的子串
? } // Index
? if (StrCompare(sub,T) != 0) ++i ;
? else return i ; } // while } // if
21北京邮电大学自动化学院
? 因为串是特殊的线性表，故其存储结构与线性表的存储结构
类似。只不过由于组成串的结点是单个字符。串有三种机内
表示方法，下面分别介绍。
4.2 串的表现和实现
? 1、定长顺序存储表示
? 定长顺序存储表示,类似于线性表的顺序存储结构，是用一
组地址连续的存储单元存储串值的字符序列。在串的定长顺
序存储结构中，按照预定义的大小，为每个定义的串变量分
配一个固定长度的存储区，则可用定长数组来如下描述。
? #define maxstrlen 255 //用户可在 255以内定义最大串长
? typedef unsigned char SString[MAXSTRLEN+1];
? //0号单元存放串长
22北京邮电大学自动化学院
? 串的实际长度可在这预定义长度的范围内随意，超过预定义
长度的值则被舍去，称之为,截断” 。
? 对于串长有两种办法：
? 一是如上述定义描述的那样以下标为 0的数组分量存放串的
实际长度； 用一个整数来表示串的长度，那么该长度减 1的
位置就是串值的最后一个字符的位置。此时顺序串的类型定
义和顺序表类似,
? 二是在串值后面加入一个不计入串长的结束标记符，例
如,C语言中以字符 ‵ \0′表示串值的终结,
1、定长顺序存储表示
23北京邮电大学自动化学院
1、定长顺序存储表示
? 求子串 SubString(&Sub,S,pos,len),求子串的过程即为复
制字符序列的过程，将串 S中从第 pos各字符开始长度为 len
的字符序列复制到串 Sub中。
? 显然，本操作不会有需要截断的情况，但有可能产生用户给
出的参数不符合操作的初始条件，当参数非法时，返回
ERROR。
? typedef struct{
? char ch[maxstrlen];
? int length;
? }SString; //其优点是涉及到串长操作时速度快。
24北京邮电大学自动化学院
? Status SubString (SString &S,SString S,int pos,int len) {
? //用 Sub返回串 S的第 pos个字符起长度为 len的子串。
? //其中,1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-
pos+1.
? If (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
? return ERROR;
? Sub[1..len]=S[pos..pos+len-1];
? } // SubString
? Sub[0]=len
? return OK;
求子串 SubString(&Sub,S,pos,len)
25北京邮电大学自动化学院
? 这种存储表示的特点是，仍以一组地址连续的存储单元存放串
值字符序列，但它们的存储空间是在程序执行过程中动态分配
而得。所以也称为 动态存储分配的顺序表 。
2、堆分配存储表示
? 在顺序存储结构中，实现串操作的原操作为“字符序列的复
制”，操作的时间复杂度基于复制的字符序列的长度。
? 克服这个弊病惟有不限定串长的最大长度，即动态分配串的
存储空间。
1、定长顺序存储表示
? 如果在操作中出现串值序列的长度超过上界 MAXSTRLEN
时,约定用截尾法处理,这种情况不仅在求连接串时可能发
生，在串的其它操作中，如插入、置换等也可能发生。
26北京邮电大学自动化学院
? 在 C语言中，存在一个称之为“堆”的自由存储区，并由 C语言
的动态分配函数 malloc()和 free()来管理。利用函数 malloc()为
每个新产生的串分配一块实际串长所需的存储空间，若分配成
功，则返回一个指向起始地址的指针，作为串的基址，同时，
为了以后处理方便，约定串长也作为存储结构的一部分。
? //串的堆分配存储表示
? typedef struct{
? char *ch;//若是非空串，则按串长分配存储区，否
则 ch为 NULL
? int length;/串长度
? }HString;
27北京邮电大学自动化学院
? 这种存储结构表示时的串操作仍是基于“字符序列的复制”
进行的。例如，串复制操作 StrCopy(&T,S)的实现算法是,若
串 T已存在，则先释放串 T所占空间，当串 S不空时，首先为
串 T分配大小和串 S长度相等的存储空间，然后将串的值复制
到串 T中；
? 又如串插入操作 StrInsert(&S,pos,T)的实现算法是，为串 S重
新分配大小等于串 S和串 T长度之和的存储空间，然后进行串
值复制。
2、堆分配存储表示
28北京邮电大学自动化学院
? Status SubInsert (HString &S,int pos,HString T) {
? //1≤pos≤StrLength(S)+1.在串 S的第 pos个字符之前插入串 T.
? If (pos<1 || pos>S.length+1) return ERROR;//pos不合法
? If (T.length){ //T非空，则重新分配空间，插入 T
? If(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(ch
ar)))) exit (OVERFLOW);
? S.ch[pos-1..pos＋ T.length-2]=T.ch[0..T.length-1]; //插入 T
? for(i=S.length-1;i>=pos-1;--i)//为插入 T而腾出位置
? S.ch[i+T.length]=S.ch[i];
2、堆分配存储表示
29北京邮电大学自动化学院
? S.length+=T.length;
? }
? Return OK;
? }//StrInsert
? 只含最小操作子集的 HString串类型的模块说明见 P76～
77。
2、堆分配存储表示
? 以上两种存储表示通常为高级程序设计语言所采用
? 由于堆分配存储结构的串既有顺序存储结构的特点，处理方
便，操作中对串长没有任何限制，更显灵活，因此在串处理
的应用程序中也常被选用。
30北京邮电大学自动化学院
? 顺序串上的插入和删除操作不方便，需要移动大量的字符。因
此，我们可用单链表方式来存储串值,串的这种链式存储结构
简称为链串。
3、串的链式存储结构
? typedef struct node{
? char data;
? struct node *next;
? }Lstring;
? 一个链串由头指针唯一确定。
? 这种结构便于进行插入和删除运算，但总的来说不如顺
序存储结构灵活，它占用存储量大且操作复杂。
31北京邮电大学自动化学院
? 为了提高存储密度，可使每个结点存放多个字符。通常将 结
点数据域存放的字符个数定义为结点的大小,显然，当结点
大小大于 1时，串的长度不一定正好是结点的整数倍，因此
要用特殊字符来填充最后一个结点，以表示串的终结。
? 对于结点大小不为 1
的链串，其类型定
只需对上述的结点
类型做简单的修改
即可。
? #define nodesize 80
? typedef struct node{
? char data[nodesize];
? struct node *next;
? }Lstring;
3、串的链式存储结构
32北京邮电大学自动化学院
? 显然，存储密度小（如节点大小为 1时），运算处理方便，然
而，存储占用量大。如果在串处理过程中需进行内、外存交
换的话，则会因为内外存交换操作过多而影响处理的总效
率。
存储密度 = 串值所占的存储位 实际分配的存储位
? 在链式存储方式中，节点大小的选择和顺序存储方式的格式
选择一样都很重要，它直接影响着串处理的效率。在各种串
的处理系统中，所处理的串往往很长或很多，这要求我们考
虑串值的存储密度。存储密度可定义为：
3、串的链式存储结构
33北京邮电大学自动化学院
? 实际应用时，可以根据问题所需来设置结点的大小。例
如, 在编辑系统中，整个文本编辑区可以看成是一个串，
每一行是一个子串，构成一个结点。即, 同一行的串用定
长结构 (80个字符 ),行和行之间用指针相联接。
? 串值的链式存储结构对某些操作，如联接操作等有一定方
便之处，但 总的说来不如另外两种存储结构灵活，它占用
存储量大且操作复杂。
? 此外，串值在链式存储结构时串操作的实现和线性表在链
表存储结构中的操作类似。
3、串的链式存储结构
34北京邮电大学自动化学院
? 这是串的一种重要操作，很多软件，若有“编辑”菜单项的
话,则其中必有“查找”子菜单项。首先，回忆一下串匹
配 (查找 )的定义,
4.3 串的模式匹配算法
? INDEX (S,T,pos)
? 初始条件,串 S 和 T 存在,T 是非空串，
1≤pos≤StrLength(S)。
? 操作结果,若主串 S 中存在和串 T 值相同的子串返回它在
主串 S 中第 pos 个字符之后第一次出 现 的位置 ; 否则函数值
为 0。
35北京邮电大学自动化学院
1、简单算法
? 模式匹配的最简单的做法是,用模式串 T中的字符依次与主
串 S的字符比较：
? t1 t2 t3 … t m
t1 t2 t3 … t m
? 如此反复比较，直至
主串 S中找到模式串 t
或者确定该模式不存
在为止。
? S1 S2 S3 … S m Sn
? 如果 t1=s1,t2=s2,…, tm=sm则匹配成功。否则必有某个
i(1<i<m)，使得 ti不等于 si，这时可从主串 s中与 t1比较的字
符的下一个字符起（将串 t右移一个字符）再重新与模式串 t
中字符依次比较：
? S1 S2 S3 … S m Sm+1… S n
36北京邮电大学自动化学院
? 设 S=“abbaba”,T=“aba”，用上述做法进行模式匹配的过
程见下图：
? S,a b b a b a ? S:a b b a b a
(a) T3 ? S3
? S,a b b a b a
? T,a b a
(b) T1 ? S2
? ? T1 ? S3 ? (d)找到模式串
? T,a b a
? S,a b b a b a
? T,a b a
? T,a b a
37北京邮电大学自动化学院
S 串
T 串 T 串
i
pos n-m+1
S 串
T 串 T 串
i
j j>m
i
j
i
j
i
j
i>n
j
串
简单算法示意图
38北京邮电大学自动化学院
? int Index(SString S,SString T,int pos) {
? // 返回子串 T在主串 S中第 pos个字符之后的位置。若不存在，
则函数值为 0。 其中,T非空,0≤pos≤StrLength(S)。
? i = pos; j = 1;
? while (i <= S[0] && j <= T[0]) {
? if (S[i] == T[j]) { ++i; ++j; }// 继续比较后继字符
? else { i = i-j+2; j = 1; } // 指针后退重新开始匹配 }
? if (j > T[0]) return i-T[0];
? else return 0; } // Index
简单算法
39北京邮电大学自动化学院
2、简单模式算法分析
?上页的匹配过程易于理解，且在某些应用场合，如
文本编辑等，效率也较高，例如，在检查模式
,STING”是否存在于下列主串中时，,A STRING
SEARCHING EXAMPLE CONSISTING OF
SIMPLE TEXT”
?上述算法中的 while循环次数（即进行单个字符比较
的次数）为 41，恰好为（ Index+T[0]-1)+4）,这就是
说，除了主串中呈红色的四个字符，其它字符均只
和模式进行一次比较。在这种情况下，此算法的时
间复杂度为 O（ n+m)。
40北京邮电大学自动化学院
? 例题 2，设主串 s=“ababcabcacbab”，模式 t=“abcac”，匹
配过程如下图所示。
? 第一趟
? 第二趟
? 第三趟
? 第四趟
? 第五趟
? 第六趟
41北京邮电大学自动化学院
? 然而，在有些情况下，该算法的效率却很低。
? 例如,当模式串,00000001”，而主串为,00000000000
000000000000000000000000000000000000000001”时，由
于模式中前 7个字符均为,0”，又，主串中前 52个字符均为
,0”，每趟比较都在模式的最后一个字符出现不等，此时需
将指针 i回溯到 i-6的位置上，并从模式的第一个字符开始重新
比较，整个匹配过程中指针需要回溯 45次，则 while的循环次
数为 46*8。可见算法在最坏情况下的时间复杂度为 O(n*m)。
? 这种情况在只有 0,1两种字符的文本串处理中经常出现，因
为在主串中可能存在多个和模式串“部分匹配”的子串，因
而引起指针 i的多次回溯。
? 0,1串可以用在许多应用之中。（需要改进）
42北京邮电大学自动化学院
3、模式匹配的改进算法
?这种改进算法是 D.E.Knuth,V.R.Pratt和 J.H.Morris
同时发现的，因此人们称它为 克努特 —莫里斯 —普
拉特操作（简称为 KMP算法） 。此算法可以在 O
（ n+m)的时间数量级上完成串的模式匹配操作。
?改进算法,每当一趟匹配过程中出现字符比较不等
时，不需回溯 i指针，而是利用已经得到的“部分匹
配”的结果将模式 向右“滑动”尽可能远的一段距
离后,继续进行比较。
?下面先从具体例子看起。
43北京邮电大学自动化学院
? 回顾例 2中的匹配过程,在第三趟匹配过
程中,s3 ~ s6和 t1~ t4是匹配成功的,s7≠t5
匹配失败，又从 i=4,j=1开始重新开始
比较。
? 因为从第 3趟部分匹配的结果就可得出，主串中第 4,5和 6个
字符必然是’ b?、’ c?和’ a?。因为模式中的第 1个字符
是’ a?，因此它无需再和这 3个字符进行比较,而仅需将模式
向右滑动 3个字符的位置继续进行 i=7,j=2时的字符比较即
可。
? i=4,j=1
? i=5,j=1
? i=6,j=1
44北京邮电大学自动化学院
? 同理，在第 1趟匹配中出现字符不等时 仅需将模式向右移动二个
字符的位置继续进行 i=3,j=1的字符比较。
? 由此在整个匹配的过程中 i 指
针没有回溯。
? 改进算法的匹配过程如下图
所示。
45北京邮电大学自动化学院
?现在讨论一般情况。假设主串为,S1,S2
S3,…S n”，模式串为,t1 t2 … t m”，为了实现改
进算法，需要解决下述问题：
?当匹配过程中产生“失配”（即 Si不等于 tj)时，模式
串“向右滑动”可行的距离多远，换句话说,当主
串中第 i个字符和模式中第 j个字符“失配”（即比较
不等 )时，主串中第 i字符（指针 i不回溯）应与模式
中的哪个字符再比较？
3、模式匹配的改进算法
46北京邮电大学自动化学院
? 假设此时应与模式中第 k (k<j)个字符继续比较，则模式中前 k-
1个字符的子串必须满足下列关系式 (4-1)，且不可能存在 k?>k
满足下列关系式（ 4-1）：
? 而本趟匹配失败是在 si和 tj之处，已经得到的部分匹配结果是
?,t1 t2 … t k-1, =“si-k+1 si-k+2 … s i-1” (4-1)
? (4-1)式左边是 tk前面的 k-1个字符，右边是 si 前面的 k-1个字符。
?,t1 t2 … t j-1” =“si-j+1 si-j+2 … si-1” (4-2)
? 因为 k<j，所以有：
?,tj-k+1 tj-k+2 … t j-1” =“si-k+1 si-k+2 …s i-1” (4-3)
3、模式匹配的改进算法
47北京邮电大学自动化学院
?,tj-k+1 tj-k+2… t j-1” =“si-k+1 si-k+2…s i-1” (4-3)
? 反之，若模式串中存在满足（ 4-4）的两个子串，则当匹配
过程中，主串第 i个字符与模式中第 j个字符比较不等时，仅
需将模式向右滑动至模式中第 k个字符和主串中第个 i字符对
齐。
? （ 4-3）式左边是 tj前面的 k-1个字符，右边是 si前面的 k-1个字
符，通过 (4-1)和 (4-3)得到关系：
?,t1 t2 … t k-1” =“tj-k+1 tj-k+2 … t j-1” (4-4)
?,t1 t2 … t k-1, =“si-k+1 si-k+2 … s i-1” (4-1)
3、模式匹配的改进算法
48北京邮电大学自动化学院
?,t1 t2 … t k-1” =“tj-k+1 tj-k+2 … t j-1” (4-4)
? 反之，若模式串中存在满足（ 4-4）的两个子串，则当匹配
过程中，主串第 i个字符与模式中第 j个字符比较不等时，仅
需将模式向右滑动至模式中第 k个字符和主串中第个 i字符对
齐。
? 此时，模式中头 k-1个字符的子串,t1 t2 … t k-1, 必定与主
串中第 i个字符之前长度为 k-1的字串,si-k+1 si-k+2 …s i-1,
相等，由此，匹配仅需从模式中第 k个字符与主串中第 i个字
符处，继续进行比较。
3、模式匹配的改进算法
49北京邮电大学自动化学院
?若令 next[j]=k，则 next[j]表明当模式中第 j个字符与
主串中相应字符“失配”时，在模式中需要重新和
主串中该字符进行比较的位置。由此可引出模式串
的 next函数的定义：
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
??
?
?
其他情况
时当
1
"
11
""
11
"1|m a x
10
][
j
t
kj
t
k
ttjkk
j
jn ext ??
?在求得模式的 next函数后，匹配可如下进行,假设以
指针 i和 j分别指示主串和模式中正待比较的字符，令 i
的初值为 pos,j的初值为 1。
3、模式匹配的改进算法
50北京邮电大学自动化学院
? 若在匹配过程中 si=tj，则 i和 j分别增１ ;
? 若 si≠tj 匹配失败后，则 i不变,j退到 next[j]位置再比较，
? 若相等，则指针各自增１，
? 否则 j再退到下一个 next值的位置，依此类推。直至
下列两种情况：
? 一种是 j退到某个 next值时字符比较相等，则 i和 j分别增１继
续进行匹配 ;
? 另一种是 j退到值为零（即模式的第一个字符“失配”），
则此时 i和 j也要分别增１，表明从主串的下一个字符起和模
式重新开始匹配。
3、模式匹配的改进算法
51北京邮电大学自动化学院
? while (i <= S[0] && j <= T[0]) {
? if (j = 0 || S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符
3、模式匹配的改进算法
? int Index_KMP(SString S,SString T,int pos) {
? // 1≤pos≤StrLength(S)
? i = pos; j = 1;
? else j = next[j]; // 模式串向右移动
? }//while
? if (j > T[0]) return i-T[0]; // 匹配成功
? else return 0; } // Index_KMP
52北京邮电大学自动化学院
? 由以上讨论知,next函数值仅取决于模式本身而和主串无
关。我们可以从分析 next函数的定义出发用递推的方法求得
next函数值。
4,next 函数值
? 由定义知,next[1]=0 (4-5)
? 设 next[j]=k，这表明在模式串中存在下列关系：
?,t1 t2 … t k-1, =“tj-k+1 tj-k+2 … t j-1, (4-6)
? 其中 k为满足 1<k<j的某个值，并且不可能存在 k?>k满足上
式，此时 next[j+1]=? 可能有两种情况：
53北京邮电大学自动化学院
? 第一种情况：若 tk ＝ tj 则表明在模式串中
? 第二种情况：若 tk≠tj 则表明在模式串中
? 此时可把求 next函数值的问题看成是一个模式匹配问题，整
个模式串既是主串又是模式，而当前在匹配的过程中,已有
(4-6)式成立，则当 tk≠tj 时应将模式向右滑动，使得第
next[k]个字符和“主串”中的第 j个字符相比较。
?,t1 t2 … t k, =“tj-k+1 tj-k+2 … t j, (4-7)
? 即 next[j+1]=next[j]+1 (4-8)
?,t1 t2 … t k”≠“tj-k+1 tj-k+2 … t j, (4-9)
4,next 函数值
?,t1 t2 … t k-1, =“tj-k+1 tj-k+2 … t j-1, (4-6)
54北京邮电大学自动化学院
? 因此,next[j+1]=next[k]+1 (4-11)
? 若 next[k]=k′，且 t k?＝ tj，则说明在主串中第 j+1个字符之前
存在一个最大长度为 k′的子串，使得
?,t1t2…t k?”=“tj-k?+1 t j- k?+2 …t j” (4-10)
? 同理若 t k′ ≠tj，则将模式继续向右滑动至使第 next[k′]个字符
和 tj 对齐。
? 依此类推，直至 tj 和模式中的某个字符匹配成功或者不存在
任何 k′(1< k′<k <…<j) 满足 (4.10)，则有：
? next[j+1]=1 (4-12)
4,next 函数值
55北京邮电大学自动化学院
? 例题：已知模式串 t=“abcaababc”中前 6个字符的 next
函数值，求 next[7],next[8]
j 1 2 3 4 5 6 7 8
模式 a b a a b c a c
Next[j] 0 1 1 2 2 3 1 2
? Next[6]=3,t6 ≠ t3，则需要比较 t6和 t1(next[3]=1)，这相当于将
子串模式向右滑动。又由于 t6≠ t1，而且 next[1]=0，所以
next[7]=1
? Next[7]=1,t7=t1,则 ? Next[8]=next[7]+1=8
4,next 函数值
56北京邮电大学自动化学院
? void get_next(SString &T,int &next[] ) {
? // 求模式串 T的 next函数值并存入数组 next。
? i = 1; next[1] = 0; j = 0;
? while (i < T[0]) {
? if (j == 0 || T[i] == T[j])
? {++i; ++j; next[i] = j; }
? else j = next[j]; }
? } // get_next
4,next 函数值
57北京邮电大学自动化学院
? next存在的问题，例如：
? S = ?aaabaaabaaabaaabaaab?
? T = ?aaaab?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
4
2
4
3
4
j
i
j
i
j
i
? i=4,j=4时,S4≠ t4，由 next[j]的指示还需要进行
? 等三次比较
? 实际上，因为模式中第 1,2,3个字符和第 4个字符都相等，
因此不需要再和这主串第 4个字符比较，而可以将模式一气向
右滑动 4个字符的位置直接进行 i=5,j=1时的字符比较。
4,next 函数值
? next[j]= 01234,nextval[j]=00004
58北京邮电大学自动化学院
? 实际上，因为模式中第 1,2,3个字符和第 4个字符都相等，
因此不需要再和这主串第 4个字符比较，而可以将模式一气
向右滑动 4个字符的位置直接进行 i=5,j=1时的字符比较。
next[j]= 01234,nextval[j]=00004
? 这就是说，若按上述定义得到 next[j]=k，而模式中 tj=tk，则
当主串中字符 si和 tj比较不相等时，不需要再和 tk进行比较，
而直接和 next[k]进行比较，换句话说，此时的 next[j]应和
next[k]相同。
? 由此可得计算 next函数修正值的算法。
4,next 函数值
59北京邮电大学自动化学院
? void get_nextval(SString &T,int &nextval[]) { i = 1;
nextval[1] = 0; j = 0;
? while (i < T[0]) {
? if (j == 0 || T[i] == T[j]) {
? ++i; ++j;
? if (T[i] != T[j]) nextval[i] = j;
? else nextval[i] = nextval[j]; }
? else j = nextval[j]; }
? } // get_nextval
4,next 函数值
60北京邮电大学自动化学院
4.4 串操作应用举例
? 1、文本编辑
? 文本编辑程序是一个面向用户的系统服务程序，广泛用于
源程序的输入和修改。文本编辑的实质就是修改数据的形
式和或格式。虽然各种文本编辑程序的功能不同，但其基
本操作是一致的，一般都包括串的查找、插入和删除等基
本操作。
? 为了编辑的方便，用户可以利用换页符和换行符把文本划
分为若干页。每页有若干行。我们可以把文本看成是一个
字符串，称为文本串。页则是文本串的子串，行又是页的
子串。
61北京邮电大学自动化学院
? 图中 ?为换行符。
本文编辑
? 比如有下列一段源程序
? Main(){
? Float a,b,max;
? Scanf(“%f,%f”,&a,&b);
? If a>b max=a;
? Else max=b;
? };
62北京邮电大学自动化学院
行 号 起 始 地 址 长 度
100 201 8
101 209 17
102 226 24
103 267 17
104 282 15
105 282 2
? 为了管理文本串的页和行，在进入文本编辑的时候，编辑程序
先为文本串建立相应的页表和行表，即建立各子串的存储映
像。页表的每一项给出了页号和该页的起始行号。而行表的每
一项则指示每一行的行号、起始地址和该行子串的长度。
? 假设上页所示文本只占一页，且起始行号为 100，则该文本
串的行表如下图所示。
本文编辑
63北京邮电大学自动化学院
? 文本编辑程序中设立页指针、行指针和字符指针，分别指示当
前操作的页、行和字符。
? 如果在某行内插入或删除若干字符，则要修改行表中该行的
长度。若该行的长度超出了分配给它的存储空间，则要为该
行重新分配存储空间，同时还要修改该行的起始位置。
本文编辑
? 如果要插入或删除一行，就要涉及行表的插入和删除。若被
删除的行是所在页的起始行，则还要修改页表中相应页的起
始行号（修改为下一行的行号）。
? 为了查找方便，行表是按行号递增顺序存储的，因此，对行
表进行的插入或删除运算需移动操作位置以后的全部表项。
64北京邮电大学自动化学院
?1、掌握串的相关概念
?2、掌握串的存储结构及基本运算的实现
?3,熟练掌握 KMP算法的基本思想及模式匹配过程。
?4、灵活运用串的特点解决复杂的应用问题。
第四章 学习要点
65北京邮电大学自动化学院
第四章 作业
? 一、选择题
? 1、空串与空白串是相同的，这种说法 B 。
? （ A）正确 （ B）不正确
? 2、串是一种特殊的线性表，其特殊性体现在 D 。
? （ A）可以顺序存储 （ B）数据元素是一个字符
? （ C）可以链接存储 （ D）数据元素可以是多个字符
? 3,D 是 C语言中” abcd321ABCD”的子串。
? （ A） abcd （ B） 321AB（ C）” abcABC” (D)”21AB”
66北京邮电大学自动化学院
?二、填空题
?1、两个串相等的充分必要条件 是 。
?2、空串是,其长度等于 。
?3、空白串是 其长度等于 。
?4、模式串 t=?abaabcac”的 next函数值序列
为, nextval函数值序列为 。
第四章 作业
