1
第四章 串
串的定义
串的操作
数
据
结
构
之
串
2
4.1 串的定义
?串：由零个或多个字符组成的有限序列，
记为S= “a
1
a
2
a
3
……a
n
”。
?主串、子串、串名、串长；
S=“How are you,everybody!”
?空串、空格串；
?字符在串中的位置、子串在串中的位置；
?两个串相等,当且仅当两个串值相等，即
长度，位置相等；
2
数
据
结
构
之
串
3
4.2 串的基本操作
? StrAssign(&T,chars)
? StrCompare(S,T): S、T相等返回true，否则返
回faule；
? StrLength(S) : 求串中字符的个数；
? ConCat(S,T) : 将串T的值紧接着放在串S的末尾，
组成一个新串；
? SubString(Sub,S,start,length): 求S从start位置开
始，长度为length 的子串；
数
据
结
构
之
串
4
? SetEmpty(&T) : 设置空串
? StrCopy(S,T): 把T值赋给S；
? Index(S,T,pos): 求子串在主串中位置的定位函数；
? Replace(S,T,v): 以v替换所有在S中出现的和T相
等的串；
? StrInsert(S,Pos,T): 在串S的第Pos个字符之前插
入串T；
? StrDelete(S,Pos,len): 从串S中删除Pos个字符起
长度为len的子串；
3
数
据
结
构
之
串
5
4.3 串的表示和实现
?定长顺序存储表示
?紧缩格式：在一个存储单元中存放多个字符
?非紧缩格式：一个存储单元中只存放一个字符，
所需存储单元个数即串的长度
例：如一个单元存放k个字符，长度为n，则此
串值占[n/k]个存储单元。
D
T
A
:
S
A
ADTA
SWTR
CUTU
EFS
一个存储单元
数
据
结
构
之
串
6
?动态分配串值的存储空间；
?动态串的类型定义：
typedef struct{
char *ch ;
int length; //串的长度
}HS;
4
数
据
结
构
之
串
7
?串的链式存储
#define CHUNKSIZE 80 /*由用户定义的块长度*/
typedef struct Chunk {
char ch[CHUNKSIZE]; /*字符串块*/
struct Chunk *next; /*指向下一个字符串块*/
}Chunk; /*结构名称*/
typedef struct {
Chunk *head, *tail; /*指向头尾的指针*/
int curlen; /*串的当前长度*/
} LString; /*串名称*/
F
A B C 1 ^
A B C D E F G H 1 # # # ^
F
数
据
结
构
之
串
8
?串基本操作的实现
?将串S1和串S2联接成新串
?算法描述：
?给T分配存储空间，存储空间大小为S1和S2长度
之和。
?将S1中的每一个字符拷贝到T中。
?修改T的长度。
?将S2中的所有字符拷贝到T剩余的存储空间中。
?返回。
?程序如下：
5
数
据
结
构
之
串
9
Status Concat(Hstring T, Hstring S1, Hstring S2){
int count;
if(T.ch) free(T.ch); /*如果T.ch非空，则释放其存储空间*/
if(!(T.ch=(char *)malloc(S1.length+S2.length+1)*sizeof(char))))
/*分配空间*/
return OVERFLOW; /*若分配失败，则返回溢出信息*/
for(count=0;count<S1.length;count++)
T.ch[count]=S1.ch[count]; /*将S1中字符拷贝到T中*/
T.length=S1.length+S2.length; /*修改长度*/
for(count=S1.length;count<T.length;count++)
T.ch[count]=S2.ch[count- S1.length]; /*将S2中所有字符
拷贝到T中*/
T.ch[T.length] = ‘\0’;
return OK; /*返回*/ }
数
据
结
构
之
串
10
?求子串T在主串S中的位置
?算法思想：从主串S的第一个字符
起和模式串（子串）的第一个字符
比较，相等则继续，否则从主串的
第二个字符起重新和模式比较，直
至比较完毕为止。
?图示
S = “a b a b c a b c a c b a b”
T = “a b c a c”
6
数
据
结
构
之
串
11
第一趟匹配：a b a b c a b c a c b a b
a b c
j=3
i=3
第二趟匹配：a b a b c a b c a c b a b
a
j=1
i=2
第三趟匹配：a b a b c a b c a c b a b
a b c a c
j=5
i=7
数
据
结
构
之
串
12
第四趟匹配：a b a b c a b c a c b a b
a
j=1
i=4
第五趟匹配：a b a b c a b c a c b a b
a
j=1
i=5
第六趟匹配：a b a b c a b c a c b a b
a b c a c
j=6
i=11
7
数
据
结
构
之
串
13
int Index(HS S , HS T , int pos) {
k= i = pos-1 ; j=0;
while(k<=S.length && j<=T.length){
if(S.ch[ k ]==T.ch[ j ]) {k++;j++;}
else { i++; k=i ; j=0;} }
if( j >T.length) return ( i+1 );
else return (0); }
数
据
结
构
之
串
14
?模式匹配的KMP算法
请同学们参照演示程序和教材
中的相关内容进行钻研
8
数
据
结
构
之
串
15
串的 算法练习
1.完成动态串的基本操作，page 71;
2. Status StrInsert( HS &S , int pos , HS T){
…….
}
3. Status StrDelete(HS &S,int pos,int len,HS
&T)
{
…….
}
数
据
结
构
之
串
16
?本章重点
?串的基本概念
?串的基本操作
?串的查找
