第 4章 串
数据结构（ C++描述）
目录
4.1串的定义及运算
4.2 串的存储结构
4.3 串的运算的实现
结束放演
4.1串的定义及运算
4.1.1 基本概念
1,串的定义
串 ( string) 是由零个或多个字符组成的有限序列, 记作
s=“a1a2… an”,其中 s为串的名字, 用成对的双引号括起
来的字符序列为串的值, 但两边的双引号不算串值, 不
包含在串中 。 ai(1≤i≤n)可以是字母, 数字或其它字符 。 n
为串中字符的个数, 称为串的长度 。
2,空串
不含任何字符的串称为空串，它的长度 n=0，记为
s=“”。
3,空白串
含有一个空格的串, 称为空白串, 它的长度 n=1,记为
s=,” 或 s=,?”。
4,子串, 主串
若一个串是另一个串中连续的一段, 则这个串称为另
一个串的子串, 而另一个串相对于该串称为主串 。 例
如,串 s1=“abcdefg”,s2=“fabcdefghxyz”,则 s1为 s2的子
串, s2相对于 s1为主串 。
另外, 空串是任意串的子串, 任意串是自身的子串 。
若一个串的长度为 n,则它的子串数目为 +1,真子
串个数为 (除串本身以外的子串都称为真子串 )。2
1?n
21?n
4.1.2 串的运算
为描述方便, 假定用大写字母表示串名, 小写字母表
示组成串的字符 。
1,赋值 assign(&S,T)
表示将 T串的值赋给 S串。
2,联接 concat(&S,T)
表示将 S串和 T串联接起来, 使 T串接入 S串的后面 。
3,求串长度 length (T)
求 T串的长度 。
4.子串 substr(S,i,j,&T)
表示截取 S串中从第 i个字符开始连续 j个字符，作为
S的一个子串，存入 T串。
5,串比较大小 strcmp(S,T)
比较 S串和 T串的大小, 若 S<T,函数值为负, 若 S=T，
函数值为零, 若 S>T,函数值为正 。
6,串插入 insert (&S,i,T)
在 S串的第 i个位置扦入 T串。
7,串删除 delete(&S,i,j)
删除串 S中从第 i个字符开始连续 j个字符。
8,求子串位置 index(S,T)
求 T子串在 S主串中首次出现的位置, 若 T串不是 S串
的子串, 则位置为零 。
9,串替换 replace (&S,i,j,T)
将 S串中从第 i个位置开始连续 j个字符，用 T串替换。
4.1.3 串的抽象数据类型描述
串的抽象数据类型可描述为：
ADT strings IS
Data,含有 n个字符 a1,a2,a3,…,an
Operation,
Void assign(&S,T) //表示将 T串的值赋给 S串
Void concat(&S,T) //表示将 S串和 T串联接起来, 使 T
串接入 S串的后面 。
int length(T) //求 T串的长度 。
Void substr(S,i,j,&T) //表示截取 S串中从第 i个字符开始
连续 j个字符，作为 S的一个子串，存入 T串中。
int strcmp(S,T) //比较 S串和 T串的大小,若 S<T,函数值
为负,S=T,函数值为零,S>T,函数值为正 。
Void insert(&S,i,T) //在 S串的第 i个位置扦入 T串 。 Void
delete(&S,i,j) //删除 S中从第 i个字符开始连续 j个字符 。
int index(S,T) //求 T子串在 S主串中首次出现的位置,
若 T串不是 S串的子串, 则位置为零 。
Void replace(&S,i,j,T) //将 S串中从第 i个位置开始连续 j个
字符, 用 T串替换 。
End strings
4.2 串的存储结构
4.2.1 顺序存储
串的顺序存储结构, 也称为顺序串, 与第二章介绍的
顺序表类似 。 但由于串中元素全部为字符,故存放形式
与顺序表有所区别 。
1,串的非紧缩存储
一个存储单元中只存储一个字符，和顺序表中一个元素
占用一个存储单元类似。具体形式见图 4-1,设串 S=“How
do you do”。
H
o
w
d
o
y
o
u
d
o
图 4 - 1 S 串的非紧缩存储
2,串的紧缩存储
根据各机器字的长度, 尽可能将多个字符存放在一
个字中 。 假设一个字可存储 4个字符, 则紧缩存储具
体形式见图 4-2。
从上面介绍的两种存储方式可知, 紧缩存储能够节省大
量存储单元, 但对串的单个字符操作很不方便, 需要花
费较多的处理时间 。 而非紧缩存储的特点刚好相反, 操
作方便, 但将占用较多的内存单元 。
H o w
d o y
o u d
o
图 4 - 2 S 串的紧缩存储 ( 设一个字有 4 个字符位置 )
3,串的字节存储
前两种存储方法都是以字编址形式进行的, 而字节编
址方式是一个字符占用一个字节, 具体形式见图 4-3。
H o w d o y o u d o
图 4 - 3 S 串的字节编址存储（一个字符占一个字节）
4,顺序串的数据类型描述
const int maxsize=maxlen; //maxlen表示串
的最大容量
struct seqstring
{
char ch[maxsize]; //存放串的值的一维
数组
int curlen; //当前串的长度
}；
4.2.2 链式存储
1,结点大小为 1的链式存储
和前面介绍到的单链表一样，每个结点为一个字符，
链表也可以带头结点。
S=“abcdef”的存储结构具体形式见图 4-4。
头 a S b c d e f ^
图 4 - 4 S 串的链式存储示意图
2,结点大小为 K的链式存储
和紧缩存储类似，假设一个字中可以存储 K个字符，
则一个结点有 K个数据域和一个 指针域，若一个结点
中数据域少于 K个，用 ?代替。例如串 S=“abcdef”的存
储结构具体形式见图 4-5。假设 K=4，并且链表带头结
点。
a b c d e f ^ S
头结点
图 4 - 5 S 串的结点大小为 4 的链式存储
3．链串的数据类型描述
（ 1） 结点大小为 1的链串
与第二章单链表的定义类似, 只需将 data域的类型由
元素类型 elemtype改为字符类型 char即可 。
（ 2） 结点大小为 4的链串
具体描述形式见图 4-5。 数据类型描述为：
struct link 4
{ Char data [5]; // 仅使用 data[1]
到 data[4]存储空间
link4 * next ; }
4.2.3 索引存储
该方法是用串变量的名字作为关键字组织名字表 (索引
表 ),该表中存储的是串名和串值之间的对应关系 。 名字
表中包含的项目根据不同的需要来设置, 只要为存取串
值提供足够的信息即可 。 如果串值是以链接方式存储的,
则名字表中只要存入串名及其串值的链表的头指针即可 。
若串值是以顺序方式存放的, 则表中除了存入指示串值
存放的起始地址首指针外, 还必须有信息指出串值存放
的末地址 。 末地址的表示方法有几种：给出串长, 在串
值末尾设置结束符, 设置尾指针直接指向串值末地址等 。
具体介绍下面两种：
1,带长度的名字表
在表中给出串名、串存放的起始位置及串长度，具体
形式见图 4-6 。
图 4 - 6 带长度的名字表
S1 7
S2 3
a b c d e f g b c d
从图 4-6可知, S1的长度为 7,起始位置从 a开始, 故
S1=“abcdefg”,而 S2的长度为 3,起始位置从 g开始, 故
S2=”gbc”。
2,带末指针的名字表
在表中给出串的名字, 头指针及末指针, 具体形式见图
4-7。
S1
S2
a b c d e f g b c d
图 4 - 7 带末指针的名字表
从图 4-7可知，两个串的名字分别为 S1和 S2，而 S1的头
指针指向 a，末指针指向 g，故有 S1=”abcdefg”，而 S2的
头指针指向 g，末指针指向 c，故有 S2=”gbc”。
4.3 串的运算的实现
4.3.1 串扦入
1．顺序串上的扦入 insert(&S,i,T)
要将 T串扦入到 S串中第 i个位置，则 S串中第 i个位置开始，
一直到最后的字符，每个都要向后移动若干位，移动的
位数为 T串长度。具体实现过程参见图 4-8。
a b x y z c d e f
x y z
a b c d e f
x y z
T 串
S 串
T 串
S 串
(a) 扦入前 ( b ) 扦入后 ( i= 3)
图 4 - 8 顺序串的扦入
算法描述如下：
void Insert (seqstring &S,int i,seqstring T)
{ if ( S.curlen + T.curlen>=maxsize)
cout<<“overflow”;
else { for (int j=S.curlen; j>=i;j--)
S,ch[j+T.curlen]=s.ch[j]; //元素后移
for (j=1; j<=T.curlen; j++)
S,ch [j+i-1]=T.ch[j]; //扦入元素
S.curlen=S.curlen +T.curlen; //表长度增加
}}
设 n为 s串长度,m为 T串长度,则该算法时间复杂度为
0(n+m)。
2,链串的扦入 insert(&S,i,T)
仅考虑结点大小为 1的链串，要在第 i个位置扦入，先用
一个指针指向 S串的第 i-1个位置，然后在 T串中用另一
个指针指向最后，具体实现过程参见图 4-9
a b c d e f ^
P
头
q
头 x y
z ^
?
T
S
图 4 - 9 链串上的扦入 ( i= 3 )
算法描述如下：
void Insert (link *S,int i,link *T )
{ link *P,*Q ; int j=0 ; P=S ;
while (P!=NULL)&&(j<i-1) //查找第 i-1位置
{ j++ ; P=P->next; }
Q=T;
while (Q->next !=NULL)
Q=Q->next; //查找 T串最后一个元素
if (P!=NULL) //插入
{ Q->next=P->next; P->next=T->next;}
else cout <<“error!”} //找不到扦入位置
该算法花费的时间主要在查找上,时间复杂度为 O(n+m)。
4.3.2 串删除
1,顺序串的删除 delete(&S,i,j)
删除 S串中从第 i个位置开始连续 j个字符，可以分成三种
情形讨论,(1) 若 i值不在串值范围内，不能删除； (2) 从
i位置开始到最后的字符数目不足 j个，删除时,不需移动
元素，只需修改串长度即可； (3) i和 j都可以满足需求。
删除过程参见图 4-10，假设 i=4,j=5,
a b c i j k a b c d e f g h i j k
(a) 删除前 ( b ) 删除后
图 4 - 10 顺序串的删除 (i= 4,j= 5)
void delete (seqstring &S,int i,int j )
{ if ( i<1)||( i>s.curlen )
cont <<“error”; // i值不在串值范围内, 不能删除
else if ( s.curlen -i+1<j )
s.curlen =i-1; //从 i位置开始到最后的
字符数目不足 j个, 删除时,不需 ////移动元素, 只需修改
串长度即可
else {for (int k=i+j; k<=s.curlen ;k++)
s.ch [k-j]= s.ch [k]; //元素前移 i位
s.curlen =s.curlen –j ; }} //表长度减 j
该算法时间复杂度为 O(n)。
2,链串的删除 delete(&S,i,j)
和顺序串的删除一样，也可以分三种情形来讨论。删
除过程参见图 4-11，假设 i=2,j=3，
头 a b c d e f ^ S
P q
图 4 - 1 1 链串的删除 ( i=2,j =3 时的情形 )
算法描述如下：
void delete (link *S,int i,int j )
{link *P,*Q;int k=0;P=S;
while (P!=NULL) &&(k<i-1) //查找第 i-1位置
{ k++ ; P=P->next ;}
Q=P;
while (Q!=NULL)&&( k<i+j) //查找第 i+j位置
{ k++ ; Q=Q->next;}
if (P!=NULL) //保证 i合法
{ if (Q!=NULL) P->next=Q;else P->next =NULL;}
else cout <<“error”; }
该算法的时间复杂度为 O(n)。
4.3.3 子串定位
1,顺序串上 的子串定位运算 index(S,T)
子串的定位运算通常称为串的模式匹配, 是串处理中最
重 要 的 运 算 之 一 。 设串 s=“a1a2… an”, 串
T=“b1b2… bm”(m≤n),子串定位是要在主串 S中找出一个与
子串 T相同的子串 。 通常把主串 S称为目标, 把子串 T称为
模式, 把从目标 S中查找模式为 T的子串的过程称为, 模
式匹配, 。 匹配有两种结果出现：若 S中有模式为 T的子
串, 就返回该子串在 S中的位置, 当 S中有多个模式为 T的
子串, 通常只要找出第一个子串即可, 这种情况称为匹
配成功, 若 S中无模式为 T的子串, 返回值为零, 称为匹
配失败 。 模式匹配过程如图 4-12所示, 假设 S=“abababac”，
T=“abac”。
abababac
abac
abababac
abac
(a ) 第一趟匹配 s4 ? t 4 (b ) 第二趟匹配 s2 ? t1
abababac
abac
abababac
abac
(c ) 第三趟匹配 s6 ? t 4 (d ) 第四趟匹配 s4 ? t1
abababac
abac
(e ) 第五趟匹配成功
图 4 - 12 模式匹配过程
模式匹配算法如下：
int INDEX ( seqstring S,seqstring T)
{ int i=t,j=1;
while ( i<=S.curlen )&&(j<=T.curlen)
if (S.ch[i]==T.ch [j])
{ i++; j++ ; }
else
{ i=i-j+2 ; j=1;} //将 i指针回溯
if ( j>T.curlen ) return (i-T.curlen);
else return (0); } //匹配失败
该算法中,将 i指针回溯语句 i=i-j+2,可以这样理解：
在本趟匹配中, 有 si≠tj,但前面的字符都匹配, 即有 si-
1=tj-1,si-2=tj-2,…,si-j+1=t1,因此,下一趟匹配时,i应从 i-j+1
的下一位置开始, 即有 i=i-j+1+1,就是算法中的 i=i-j+2。
该算法的最好时间复杂度为 O(n+m),最坏时间复杂度
为 O(n?m)。
2,链串上的子串定位运算 index(S,T)
和顺序串上子串定位运算类似，但返回的值不是位置，
而是位置指针。若匹配成功，则返回 T串在 S串中的地址
（指针），若匹配不成功，则返回空指针。算法描述如
下：
link *index (link *S,link *T) //假设两个链串都带头
结点
{ link *P,*Q,*R;
P=S->next; Q=T->next ; R=P ;
while (P!=NULL)&&(Q!=NULL)
if (P->data==Q->data)
{ P=P->next ; Q=Q->next;}
else { R=R->next; //指针回溯
P=R ; Q=T->next ;}
if (Q==NULL) rerurn R; //匹配成功
else return NULL ; } //匹配失败
数据结构（ C++描述）
目录
4.1串的定义及运算
4.2 串的存储结构
4.3 串的运算的实现
结束放演
4.1串的定义及运算
4.1.1 基本概念
1,串的定义
串 ( string) 是由零个或多个字符组成的有限序列, 记作
s=“a1a2… an”,其中 s为串的名字, 用成对的双引号括起
来的字符序列为串的值, 但两边的双引号不算串值, 不
包含在串中 。 ai(1≤i≤n)可以是字母, 数字或其它字符 。 n
为串中字符的个数, 称为串的长度 。
2,空串
不含任何字符的串称为空串，它的长度 n=0，记为
s=“”。
3,空白串
含有一个空格的串, 称为空白串, 它的长度 n=1,记为
s=,” 或 s=,?”。
4,子串, 主串
若一个串是另一个串中连续的一段, 则这个串称为另
一个串的子串, 而另一个串相对于该串称为主串 。 例
如,串 s1=“abcdefg”,s2=“fabcdefghxyz”,则 s1为 s2的子
串, s2相对于 s1为主串 。
另外, 空串是任意串的子串, 任意串是自身的子串 。
若一个串的长度为 n,则它的子串数目为 +1,真子
串个数为 (除串本身以外的子串都称为真子串 )。2
1?n
21?n
4.1.2 串的运算
为描述方便, 假定用大写字母表示串名, 小写字母表
示组成串的字符 。
1,赋值 assign(&S,T)
表示将 T串的值赋给 S串。
2,联接 concat(&S,T)
表示将 S串和 T串联接起来, 使 T串接入 S串的后面 。
3,求串长度 length (T)
求 T串的长度 。
4.子串 substr(S,i,j,&T)
表示截取 S串中从第 i个字符开始连续 j个字符，作为
S的一个子串，存入 T串。
5,串比较大小 strcmp(S,T)
比较 S串和 T串的大小, 若 S<T,函数值为负, 若 S=T，
函数值为零, 若 S>T,函数值为正 。
6,串插入 insert (&S,i,T)
在 S串的第 i个位置扦入 T串。
7,串删除 delete(&S,i,j)
删除串 S中从第 i个字符开始连续 j个字符。
8,求子串位置 index(S,T)
求 T子串在 S主串中首次出现的位置, 若 T串不是 S串
的子串, 则位置为零 。
9,串替换 replace (&S,i,j,T)
将 S串中从第 i个位置开始连续 j个字符，用 T串替换。
4.1.3 串的抽象数据类型描述
串的抽象数据类型可描述为：
ADT strings IS
Data,含有 n个字符 a1,a2,a3,…,an
Operation,
Void assign(&S,T) //表示将 T串的值赋给 S串
Void concat(&S,T) //表示将 S串和 T串联接起来, 使 T
串接入 S串的后面 。
int length(T) //求 T串的长度 。
Void substr(S,i,j,&T) //表示截取 S串中从第 i个字符开始
连续 j个字符，作为 S的一个子串，存入 T串中。
int strcmp(S,T) //比较 S串和 T串的大小,若 S<T,函数值
为负,S=T,函数值为零,S>T,函数值为正 。
Void insert(&S,i,T) //在 S串的第 i个位置扦入 T串 。 Void
delete(&S,i,j) //删除 S中从第 i个字符开始连续 j个字符 。
int index(S,T) //求 T子串在 S主串中首次出现的位置,
若 T串不是 S串的子串, 则位置为零 。
Void replace(&S,i,j,T) //将 S串中从第 i个位置开始连续 j个
字符, 用 T串替换 。
End strings
4.2 串的存储结构
4.2.1 顺序存储
串的顺序存储结构, 也称为顺序串, 与第二章介绍的
顺序表类似 。 但由于串中元素全部为字符,故存放形式
与顺序表有所区别 。
1,串的非紧缩存储
一个存储单元中只存储一个字符，和顺序表中一个元素
占用一个存储单元类似。具体形式见图 4-1,设串 S=“How
do you do”。
H
o
w
d
o
y
o
u
d
o
图 4 - 1 S 串的非紧缩存储
2,串的紧缩存储
根据各机器字的长度, 尽可能将多个字符存放在一
个字中 。 假设一个字可存储 4个字符, 则紧缩存储具
体形式见图 4-2。
从上面介绍的两种存储方式可知, 紧缩存储能够节省大
量存储单元, 但对串的单个字符操作很不方便, 需要花
费较多的处理时间 。 而非紧缩存储的特点刚好相反, 操
作方便, 但将占用较多的内存单元 。
H o w
d o y
o u d
o
图 4 - 2 S 串的紧缩存储 ( 设一个字有 4 个字符位置 )
3,串的字节存储
前两种存储方法都是以字编址形式进行的, 而字节编
址方式是一个字符占用一个字节, 具体形式见图 4-3。
H o w d o y o u d o
图 4 - 3 S 串的字节编址存储（一个字符占一个字节）
4,顺序串的数据类型描述
const int maxsize=maxlen; //maxlen表示串
的最大容量
struct seqstring
{
char ch[maxsize]; //存放串的值的一维
数组
int curlen; //当前串的长度
}；
4.2.2 链式存储
1,结点大小为 1的链式存储
和前面介绍到的单链表一样，每个结点为一个字符，
链表也可以带头结点。
S=“abcdef”的存储结构具体形式见图 4-4。
头 a S b c d e f ^
图 4 - 4 S 串的链式存储示意图
2,结点大小为 K的链式存储
和紧缩存储类似，假设一个字中可以存储 K个字符，
则一个结点有 K个数据域和一个 指针域，若一个结点
中数据域少于 K个，用 ?代替。例如串 S=“abcdef”的存
储结构具体形式见图 4-5。假设 K=4，并且链表带头结
点。
a b c d e f ^ S
头结点
图 4 - 5 S 串的结点大小为 4 的链式存储
3．链串的数据类型描述
（ 1） 结点大小为 1的链串
与第二章单链表的定义类似, 只需将 data域的类型由
元素类型 elemtype改为字符类型 char即可 。
（ 2） 结点大小为 4的链串
具体描述形式见图 4-5。 数据类型描述为：
struct link 4
{ Char data [5]; // 仅使用 data[1]
到 data[4]存储空间
link4 * next ; }
4.2.3 索引存储
该方法是用串变量的名字作为关键字组织名字表 (索引
表 ),该表中存储的是串名和串值之间的对应关系 。 名字
表中包含的项目根据不同的需要来设置, 只要为存取串
值提供足够的信息即可 。 如果串值是以链接方式存储的,
则名字表中只要存入串名及其串值的链表的头指针即可 。
若串值是以顺序方式存放的, 则表中除了存入指示串值
存放的起始地址首指针外, 还必须有信息指出串值存放
的末地址 。 末地址的表示方法有几种：给出串长, 在串
值末尾设置结束符, 设置尾指针直接指向串值末地址等 。
具体介绍下面两种：
1,带长度的名字表
在表中给出串名、串存放的起始位置及串长度，具体
形式见图 4-6 。
图 4 - 6 带长度的名字表
S1 7
S2 3
a b c d e f g b c d
从图 4-6可知, S1的长度为 7,起始位置从 a开始, 故
S1=“abcdefg”,而 S2的长度为 3,起始位置从 g开始, 故
S2=”gbc”。
2,带末指针的名字表
在表中给出串的名字, 头指针及末指针, 具体形式见图
4-7。
S1
S2
a b c d e f g b c d
图 4 - 7 带末指针的名字表
从图 4-7可知，两个串的名字分别为 S1和 S2，而 S1的头
指针指向 a，末指针指向 g，故有 S1=”abcdefg”，而 S2的
头指针指向 g，末指针指向 c，故有 S2=”gbc”。
4.3 串的运算的实现
4.3.1 串扦入
1．顺序串上的扦入 insert(&S,i,T)
要将 T串扦入到 S串中第 i个位置，则 S串中第 i个位置开始，
一直到最后的字符，每个都要向后移动若干位，移动的
位数为 T串长度。具体实现过程参见图 4-8。
a b x y z c d e f
x y z
a b c d e f
x y z
T 串
S 串
T 串
S 串
(a) 扦入前 ( b ) 扦入后 ( i= 3)
图 4 - 8 顺序串的扦入
算法描述如下：
void Insert (seqstring &S,int i,seqstring T)
{ if ( S.curlen + T.curlen>=maxsize)
cout<<“overflow”;
else { for (int j=S.curlen; j>=i;j--)
S,ch[j+T.curlen]=s.ch[j]; //元素后移
for (j=1; j<=T.curlen; j++)
S,ch [j+i-1]=T.ch[j]; //扦入元素
S.curlen=S.curlen +T.curlen; //表长度增加
}}
设 n为 s串长度,m为 T串长度,则该算法时间复杂度为
0(n+m)。
2,链串的扦入 insert(&S,i,T)
仅考虑结点大小为 1的链串，要在第 i个位置扦入，先用
一个指针指向 S串的第 i-1个位置，然后在 T串中用另一
个指针指向最后，具体实现过程参见图 4-9
a b c d e f ^
P
头
q
头 x y
z ^
?
T
S
图 4 - 9 链串上的扦入 ( i= 3 )
算法描述如下：
void Insert (link *S,int i,link *T )
{ link *P,*Q ; int j=0 ; P=S ;
while (P!=NULL)&&(j<i-1) //查找第 i-1位置
{ j++ ; P=P->next; }
Q=T;
while (Q->next !=NULL)
Q=Q->next; //查找 T串最后一个元素
if (P!=NULL) //插入
{ Q->next=P->next; P->next=T->next;}
else cout <<“error!”} //找不到扦入位置
该算法花费的时间主要在查找上,时间复杂度为 O(n+m)。
4.3.2 串删除
1,顺序串的删除 delete(&S,i,j)
删除 S串中从第 i个位置开始连续 j个字符，可以分成三种
情形讨论,(1) 若 i值不在串值范围内，不能删除； (2) 从
i位置开始到最后的字符数目不足 j个，删除时,不需移动
元素，只需修改串长度即可； (3) i和 j都可以满足需求。
删除过程参见图 4-10，假设 i=4,j=5,
a b c i j k a b c d e f g h i j k
(a) 删除前 ( b ) 删除后
图 4 - 10 顺序串的删除 (i= 4,j= 5)
void delete (seqstring &S,int i,int j )
{ if ( i<1)||( i>s.curlen )
cont <<“error”; // i值不在串值范围内, 不能删除
else if ( s.curlen -i+1<j )
s.curlen =i-1; //从 i位置开始到最后的
字符数目不足 j个, 删除时,不需 ////移动元素, 只需修改
串长度即可
else {for (int k=i+j; k<=s.curlen ;k++)
s.ch [k-j]= s.ch [k]; //元素前移 i位
s.curlen =s.curlen –j ; }} //表长度减 j
该算法时间复杂度为 O(n)。
2,链串的删除 delete(&S,i,j)
和顺序串的删除一样，也可以分三种情形来讨论。删
除过程参见图 4-11，假设 i=2,j=3，
头 a b c d e f ^ S
P q
图 4 - 1 1 链串的删除 ( i=2,j =3 时的情形 )
算法描述如下：
void delete (link *S,int i,int j )
{link *P,*Q;int k=0;P=S;
while (P!=NULL) &&(k<i-1) //查找第 i-1位置
{ k++ ; P=P->next ;}
Q=P;
while (Q!=NULL)&&( k<i+j) //查找第 i+j位置
{ k++ ; Q=Q->next;}
if (P!=NULL) //保证 i合法
{ if (Q!=NULL) P->next=Q;else P->next =NULL;}
else cout <<“error”; }
该算法的时间复杂度为 O(n)。
4.3.3 子串定位
1,顺序串上 的子串定位运算 index(S,T)
子串的定位运算通常称为串的模式匹配, 是串处理中最
重 要 的 运 算 之 一 。 设串 s=“a1a2… an”, 串
T=“b1b2… bm”(m≤n),子串定位是要在主串 S中找出一个与
子串 T相同的子串 。 通常把主串 S称为目标, 把子串 T称为
模式, 把从目标 S中查找模式为 T的子串的过程称为, 模
式匹配, 。 匹配有两种结果出现：若 S中有模式为 T的子
串, 就返回该子串在 S中的位置, 当 S中有多个模式为 T的
子串, 通常只要找出第一个子串即可, 这种情况称为匹
配成功, 若 S中无模式为 T的子串, 返回值为零, 称为匹
配失败 。 模式匹配过程如图 4-12所示, 假设 S=“abababac”，
T=“abac”。
abababac
abac
abababac
abac
(a ) 第一趟匹配 s4 ? t 4 (b ) 第二趟匹配 s2 ? t1
abababac
abac
abababac
abac
(c ) 第三趟匹配 s6 ? t 4 (d ) 第四趟匹配 s4 ? t1
abababac
abac
(e ) 第五趟匹配成功
图 4 - 12 模式匹配过程
模式匹配算法如下：
int INDEX ( seqstring S,seqstring T)
{ int i=t,j=1;
while ( i<=S.curlen )&&(j<=T.curlen)
if (S.ch[i]==T.ch [j])
{ i++; j++ ; }
else
{ i=i-j+2 ; j=1;} //将 i指针回溯
if ( j>T.curlen ) return (i-T.curlen);
else return (0); } //匹配失败
该算法中,将 i指针回溯语句 i=i-j+2,可以这样理解：
在本趟匹配中, 有 si≠tj,但前面的字符都匹配, 即有 si-
1=tj-1,si-2=tj-2,…,si-j+1=t1,因此,下一趟匹配时,i应从 i-j+1
的下一位置开始, 即有 i=i-j+1+1,就是算法中的 i=i-j+2。
该算法的最好时间复杂度为 O(n+m),最坏时间复杂度
为 O(n?m)。
2,链串上的子串定位运算 index(S,T)
和顺序串上子串定位运算类似，但返回的值不是位置，
而是位置指针。若匹配成功，则返回 T串在 S串中的地址
（指针），若匹配不成功，则返回空指针。算法描述如
下：
link *index (link *S,link *T) //假设两个链串都带头
结点
{ link *P,*Q,*R;
P=S->next; Q=T->next ; R=P ;
while (P!=NULL)&&(Q!=NULL)
if (P->data==Q->data)
{ P=P->next ; Q=Q->next;}
else { R=R->next; //指针回溯
P=R ; Q=T->next ;}
if (Q==NULL) rerurn R; //匹配成功
else return NULL ; } //匹配失败
