1
第 4章 串（ String）
4.1 串
4.2 串 的 存储结构
4.3 串基本操作的实现 算法
4.4 串的模式匹配算法
2
记为,s =“s0,s1,……,s n-1” (n≥0 )
串名 串值（用,”括起来）
一、串的基本概念
１、串 （又称字符串）是由 n(n ≥0)个 字符 组成的 有限 序列。
（它是 数据元素为单个字符 的特殊线性表。）
4.1 串
隐含结束符 ‘ \0?,
即 ASCII码 NUL
为何要单独讨论“串”类型？
1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）
2） 程序设计中，处理对象很多都是串类型。
一般是字母、数学、标点符
号等可屏幕显示的字符
3
２、串长 串中字符的个数（ n≥0 ）。
３、空串 串中字符的个数为 0 时称为 空串 ? 。
４、空白串 由一个或多个 空格符 组成的串。
５、子串 串 S中 任意个连续的字符 序列叫 S的子串 ; S叫 主串 。
６、子串位置 子串的第一个字符在主串中的序号。
７,字符位置 字符在串中的序号。
８、串相等 串长度相等，且对应位置上字符相等。（即两个
串中的字符序列一一对应相等。）
问：空串和空白串有无区别？
答,有区别。
空串 (Null String)是指长度为零的串；
而空白串 (Blank String),是指包含一个或多个空白
字符 ‘ ’ (空格键 )的字符串,
4
例 1,现有以下 4个字符串：
a =“BEI” b =“JING” c =,BEIJING” d =,BEI JING”
问,① 他们各自的长度？
a是 c和 d的子串，在 c和 d中的位置都是 1
② a是哪个串的子串？在主串中的位置是多少？
a =3,b =4,c = 7,d=8
③ 空串是哪个串的子串？ a是不是自己的子串？
空串是任意串的子串；任意串 S都是 S本身的子
串，除 S本身外,S的其他子串称为 S的真子串。
注：串与字符的区别
? a” 串，长度为１的串。（它不仅要存储字符‘ a?，
还要存储该串的长度数据１）
‘ a? 字符 a。 (只存储字符‘ a?)
5
数据集合,串的数据集合可以表示为字符序列 s0,s1,……,s n-1，每
个数据元素的数据类型为字符类型。
操作集合：
(1)初始化串 Initiate(S)
(2)赋值 Assign(S,T)
(3)求串长度 Length(S)
(4)比较 Compare(S,T)
(5)插入 Insert(S,pos,T)
(6)删除 Delete(S,pos,len)
(7)取子串 SubString(S pos,len)
(8)查找子串 Search(S,start,T)
(9)替换子串 Replace(S,start,T,V)
二、串的抽象数据类型
6
三,C语言的串函数
串长度,int strlen(char *s);
串比较, int strcmp(char *str1,char *str2);
串拷贝, char * strcpy(char *str1,char *str2);
串连接,char * strcat(char *str1,char *str2);
子串 T定位,char *strchr(char *str,char ch);
子串查找, char *strstr(char *s1,char *s2);
……
注：用 C处理字符串时，要调用标准库函数 #include<string.h>
7
设 s =“I AM A STUDENT”,t =“GOOD”,
q=“WORKER” 。求：
例 1：
Length(s) ＝
Length(t) ＝
SubString( s,7,7)=
SubString( t,2,1)=
Replace( s,0,?STUDENT?,q )=
14
4
?STUDENT?
?O?
?I AM A WORKER?
8
解：因为
SubString(s,6,2)＝ ‘ A?；
SubString(s,7,8)＝ ‘ STUDENT?
strcat(,t,SubString(s,7,8))＝ ’ GOODSTUDENT?
所以：
strcat(,SubString(s,6,2),Concat(t,SubString(s,7,8)))
＝ ‘ AGOOD STUDENT?
例 2,设 s =“I AM A STUDENT”,t =“GOOD”,求：
Concat( SubString(s,5,2),Concat( t,SubString(s,7,8) ) ) ＝？
9
4.2 串的存储结构
? 定长顺序存储表示 （静态数组结构）
——用一组地址连续的存储单元存储串值的字
符序列，属 静态存储 方式。
? 堆分配存储表示 （动态数组结构）
——用一组地址连续的存储单元存储串值的字
符序列,但存储空间是在程序执行过程中 动态
分配 而得。
? 串的链式存储表结构
首先强调,串与线性表的运算有所不同，是以 ? 串的整体 ? 作
为操作对象，例如查找某子串，在主串某位置上插入一个子串
等。 串有两种机内表示方法：
顺序
存储
链式
存储
10
1、定长顺序存储特点,用一组连续的存储单元来存
放串，直接使用定长的字符数组来定义，数组的 上界预先
给出,故称为 静态存储 分配。
串的静态数组结构体可定义为：
typedef struct
{ char str[MaxSize];
int length;
}String;
11
思路,利用 malloc函数合理预设串长空间。
typedef struct
{
char *str;
int maxLength;
int length;
}Dstring;
２、堆分配存储特点,仍用一组连续的存储单元来存
放串，但存储空间是在程序执行过程中 动态分配 而得。
串的动态数组结构体定义如下：
12
３、串的链式存储结构
它分为单字符结点和块链两种。
(1)单字符结点链 (2)块链
typedef struct Node typedef struct Nod
{ {
char str; char str[Number];
struct Node *next; struct Node *next;
}SCharNode; } NCharNode;
13
注意：若 数据元素很多，用法 2存储更优 —称为 块链结构
链式存储特点 用链表存储串值，易插入和删除。
法 1,链表结点的数据分量长度取 1（个字符）
法 2,链表结点（数据域）大小取 n(例如 n=4)
A ? B ? C ? I NULLhead
head A B C D ? E F G H ? I # # # NULL
14
4.3 串基本操作的实现算法
１、静态数组下串基本操作的实现算法
(1)初始化操作
void Initiate(String *s)
{
S->length=0;
}
15
（ 2）插入子串操作
int Insert(String *S,int pos,String T)
{ int i;
if(pos < 0||pos>S->length)
{ printf(“参数 pos出错！” ); return 0; }
else if(S->length + T.length > MaxSize)
{ printf("数组空间不足无法插入！ "); return 0; }
else{ for(i = S->length-1; i >= pos; i--)
S->str[i+T.length] = S->str[i];
for(i = 0; i < T.length; i++)
S->str[pos+i] = T.str[i];
S->length += T.length; return 1;}
}
16
(3)删除子串操作
int Delete(String *S,int pos,int len)
{ int i;
if(S->length <= 0)
{ printf("数组中未存放字符无元素可删 ! \n");
return 0; }
else if(pos < 0 || len < 0 || pos+len > S->length)
{ printf("参数 pos和 len出错 "); return 0; }
else{
for(i = pos+len; i <= S->length-1; i++)
S->str[i-len] = S->str[i];
S->length -= len; return 1; }
}
17
２、动态数组下串基本操作的实现算法
(1)初始化
void Initiate(DString *S,int max,char *string)
{ int i;
S->str = (char *)malloc(sizeof(char)*max);
S->maxLength = max;
S->length = strlen(string);
for(i = 0; i < S->length; i++)
S->str[i] = string[i];
}
18
(2)插入子串操作
int Insert(DString *S,int pos,DString T)
{ int i; char *p;
if(pos < 0){
printf("参数 pos出错！ ");
return 0; }
else{
if(S->length + T.length > S->maxLength)
{ p = (char *)realloc (S-
>str,(S->length+T.length)*sizeof(char));
if(p == NULL)
｝
19
if(p == NULL)
{ printf("内存空间不足！ "); }
for(i = S->length-1; i >= pos; i--)
S->str[i+T.length] = S->str[i];
for(i = 0; i < T.length; i++)
S->str[pos+i] = T.str[i];
S->length += T.length;
return 1;
｝
}
第 4章 串（ String）
4.1 串
4.2 串 的 存储结构
4.3 串基本操作的实现 算法
4.4 串的模式匹配算法
2
记为,s =“s0,s1,……,s n-1” (n≥0 )
串名 串值（用,”括起来）
一、串的基本概念
１、串 （又称字符串）是由 n(n ≥0)个 字符 组成的 有限 序列。
（它是 数据元素为单个字符 的特殊线性表。）
4.1 串
隐含结束符 ‘ \0?,
即 ASCII码 NUL
为何要单独讨论“串”类型？
1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）
2） 程序设计中，处理对象很多都是串类型。
一般是字母、数学、标点符
号等可屏幕显示的字符
3
２、串长 串中字符的个数（ n≥0 ）。
３、空串 串中字符的个数为 0 时称为 空串 ? 。
４、空白串 由一个或多个 空格符 组成的串。
５、子串 串 S中 任意个连续的字符 序列叫 S的子串 ; S叫 主串 。
６、子串位置 子串的第一个字符在主串中的序号。
７,字符位置 字符在串中的序号。
８、串相等 串长度相等，且对应位置上字符相等。（即两个
串中的字符序列一一对应相等。）
问：空串和空白串有无区别？
答,有区别。
空串 (Null String)是指长度为零的串；
而空白串 (Blank String),是指包含一个或多个空白
字符 ‘ ’ (空格键 )的字符串,
4
例 1,现有以下 4个字符串：
a =“BEI” b =“JING” c =,BEIJING” d =,BEI JING”
问,① 他们各自的长度？
a是 c和 d的子串，在 c和 d中的位置都是 1
② a是哪个串的子串？在主串中的位置是多少？
a =3,b =4,c = 7,d=8
③ 空串是哪个串的子串？ a是不是自己的子串？
空串是任意串的子串；任意串 S都是 S本身的子
串，除 S本身外,S的其他子串称为 S的真子串。
注：串与字符的区别
? a” 串，长度为１的串。（它不仅要存储字符‘ a?，
还要存储该串的长度数据１）
‘ a? 字符 a。 (只存储字符‘ a?)
5
数据集合,串的数据集合可以表示为字符序列 s0,s1,……,s n-1，每
个数据元素的数据类型为字符类型。
操作集合：
(1)初始化串 Initiate(S)
(2)赋值 Assign(S,T)
(3)求串长度 Length(S)
(4)比较 Compare(S,T)
(5)插入 Insert(S,pos,T)
(6)删除 Delete(S,pos,len)
(7)取子串 SubString(S pos,len)
(8)查找子串 Search(S,start,T)
(9)替换子串 Replace(S,start,T,V)
二、串的抽象数据类型
6
三,C语言的串函数
串长度,int strlen(char *s);
串比较, int strcmp(char *str1,char *str2);
串拷贝, char * strcpy(char *str1,char *str2);
串连接,char * strcat(char *str1,char *str2);
子串 T定位,char *strchr(char *str,char ch);
子串查找, char *strstr(char *s1,char *s2);
……
注：用 C处理字符串时，要调用标准库函数 #include<string.h>
7
设 s =“I AM A STUDENT”,t =“GOOD”,
q=“WORKER” 。求：
例 1：
Length(s) ＝
Length(t) ＝
SubString( s,7,7)=
SubString( t,2,1)=
Replace( s,0,?STUDENT?,q )=
14
4
?STUDENT?
?O?
?I AM A WORKER?
8
解：因为
SubString(s,6,2)＝ ‘ A?；
SubString(s,7,8)＝ ‘ STUDENT?
strcat(,t,SubString(s,7,8))＝ ’ GOODSTUDENT?
所以：
strcat(,SubString(s,6,2),Concat(t,SubString(s,7,8)))
＝ ‘ AGOOD STUDENT?
例 2,设 s =“I AM A STUDENT”,t =“GOOD”,求：
Concat( SubString(s,5,2),Concat( t,SubString(s,7,8) ) ) ＝？
9
4.2 串的存储结构
? 定长顺序存储表示 （静态数组结构）
——用一组地址连续的存储单元存储串值的字
符序列，属 静态存储 方式。
? 堆分配存储表示 （动态数组结构）
——用一组地址连续的存储单元存储串值的字
符序列,但存储空间是在程序执行过程中 动态
分配 而得。
? 串的链式存储表结构
首先强调,串与线性表的运算有所不同，是以 ? 串的整体 ? 作
为操作对象，例如查找某子串，在主串某位置上插入一个子串
等。 串有两种机内表示方法：
顺序
存储
链式
存储
10
1、定长顺序存储特点,用一组连续的存储单元来存
放串，直接使用定长的字符数组来定义，数组的 上界预先
给出,故称为 静态存储 分配。
串的静态数组结构体可定义为：
typedef struct
{ char str[MaxSize];
int length;
}String;
11
思路,利用 malloc函数合理预设串长空间。
typedef struct
{
char *str;
int maxLength;
int length;
}Dstring;
２、堆分配存储特点,仍用一组连续的存储单元来存
放串，但存储空间是在程序执行过程中 动态分配 而得。
串的动态数组结构体定义如下：
12
３、串的链式存储结构
它分为单字符结点和块链两种。
(1)单字符结点链 (2)块链
typedef struct Node typedef struct Nod
{ {
char str; char str[Number];
struct Node *next; struct Node *next;
}SCharNode; } NCharNode;
13
注意：若 数据元素很多，用法 2存储更优 —称为 块链结构
链式存储特点 用链表存储串值，易插入和删除。
法 1,链表结点的数据分量长度取 1（个字符）
法 2,链表结点（数据域）大小取 n(例如 n=4)
A ? B ? C ? I NULLhead
head A B C D ? E F G H ? I # # # NULL
14
4.3 串基本操作的实现算法
１、静态数组下串基本操作的实现算法
(1)初始化操作
void Initiate(String *s)
{
S->length=0;
}
15
（ 2）插入子串操作
int Insert(String *S,int pos,String T)
{ int i;
if(pos < 0||pos>S->length)
{ printf(“参数 pos出错！” ); return 0; }
else if(S->length + T.length > MaxSize)
{ printf("数组空间不足无法插入！ "); return 0; }
else{ for(i = S->length-1; i >= pos; i--)
S->str[i+T.length] = S->str[i];
for(i = 0; i < T.length; i++)
S->str[pos+i] = T.str[i];
S->length += T.length; return 1;}
}
16
(3)删除子串操作
int Delete(String *S,int pos,int len)
{ int i;
if(S->length <= 0)
{ printf("数组中未存放字符无元素可删 ! \n");
return 0; }
else if(pos < 0 || len < 0 || pos+len > S->length)
{ printf("参数 pos和 len出错 "); return 0; }
else{
for(i = pos+len; i <= S->length-1; i++)
S->str[i-len] = S->str[i];
S->length -= len; return 1; }
}
17
２、动态数组下串基本操作的实现算法
(1)初始化
void Initiate(DString *S,int max,char *string)
{ int i;
S->str = (char *)malloc(sizeof(char)*max);
S->maxLength = max;
S->length = strlen(string);
for(i = 0; i < S->length; i++)
S->str[i] = string[i];
}
18
(2)插入子串操作
int Insert(DString *S,int pos,DString T)
{ int i; char *p;
if(pos < 0){
printf("参数 pos出错！ ");
return 0; }
else{
if(S->length + T.length > S->maxLength)
{ p = (char *)realloc (S-
>str,(S->length+T.length)*sizeof(char));
if(p == NULL)
｝
19
if(p == NULL)
{ printf("内存空间不足！ "); }
for(i = S->length-1; i >= pos; i--)
S->str[i+T.length] = S->str[i];
for(i = 0; i < T.length; i++)
S->str[pos+i] = T.str[i];
S->length += T.length;
return 1;
｝
}
