Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 1页第 5章 串和数组
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 2页
5.1 串的定义
串：由 0或多个字符组成的序列
s=“a1a2a3…a n”
串的长度 n
空串和空格串
子串及子串的位置
两个串相等
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 3页
2.串的抽象数据类型定义
ADT String {
数据对象,D={ai|ai∈ char,i=1,2,…,n,n≥0}
数据关系,R={<ai-1,ai>|ai-1,ai ∈ D,i=1,2,…,n,n≥0}
基本操作,
参见后面介绍
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 4页
StrAssign(&T,chars)
初始条件,chars是字符串常量。
操作结果,生成一个其值等于 chars的串 T。
StrCopy(&T,S)
初始条件,字符串 S已经存在。
操作结果,由串 S复制得串 T。
StrEmpty (S)
初始条件,字符串 S已经存在。
操作结果,若 S为空串，则返回 TRUE,否则返回 FALSE。
串的基本操作（ 1）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 5页
StrCompare(S,T)
初始条件,字符串 S和 T存在。
操作结果,若 S>T,则返回值 >0;若 S=T,则返回值 =0;否则返回值 <0。
StrLength(S)
初始条件,字符串 S已经存在。
操作结果,返回串 S元素个数，称为串的长度。
ClearString(&S)
初始条件,字符串 S已经存在。
操作结果,将串 S清为空串。
串的基本操作（ 2）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 6页串的基本操作（ 3）
Concat(&T,S1,S2)
初始条件,字符串 S1,S2已经存在。
操作结果,用 T返回由串 S1和 S2联结而成的新串。
Substring(&Sub,S,pos,len)
初始条件,串 S存在,1<=pos<=S的长度,
0<=len<=S的长度 -pos+1。
操作结果,用 Sub返回串 S的第 pos个字符起长度为 len的子串。
Index(S,T,pos)
初始条件,串 S和 T存在,T是非空串,1<=pos<=S的长度。
操作结果,若主串 S中存在和串 T相同的子串，则返回它在主串 S中第 pos个字符之后第一次出现的位置；否则返回
０。
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 7页串的基本操作（ 4）
Replace(&S,T,V)
初始条件,字符串 S,T,V已经存在,T是非空串。
操作结果,用 V替换主串 S中出现的所有与 T相等的不重叠的子串。
StrInsert(&S,pos,T)
初始条件,字符串 S,T存在,1<=pos<=S的长度 +1。
操作结果,在串 S的第 pos个字符之前插入串 T。
StrDelete(&S,pos,len)
初始条件,串 S存在,1<=pos<=S的长度 -len+1。
操作结果,从串 S中删除第 pos个字符起长度为 len的子串,
DestroyString(&S):把存在的串 S销毁
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 8页上述 13种基本操作中,下面 5种操作构成最小操作子集,
串赋值 StrAssign;
串比较 StrCompare;
求串长 StrLength;
串联结 Concat;
求子串 Substring;
其它操作可以用其实现串类型的最小操作子集
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 9页
C语言函数库中提供下列串处理函数：
gets(str) 输入一个串；
puts(str) 输出一个串；
strcat(str1,str2) 串联接函数；
strcpy(str1,str2,k) 串复制函数；
strcmp(str1,str2) 串比较函数；
strlen(str) 求串长函数；
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 10页
5.2 串的表示和实现
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 11页
5.2.1 定长顺序存储表示
#define MAXSTRLEN 255 //串长度最大为 255
char SString[MAXSTRLEN+1];
//0号单元存放串的长度,其最大值刚好是 255
当超出 255个字符时,串的多余内容被舍去（截断）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 12页算法 5.2
void Concat_Sq( char S1[ ],char S2[ ],char T[ ]) {
// 用 T返回由 S1和 S2联接而成的新串
j=0; k=0;
while ( S1[j] != '\0' ) T[k++] = S1[j++]; //复制串 S1
j = 0;
while ( S2[j] != '\0' ) T[k++] = S2[j++]; //接着复制串 S2
T[k] = '\0'; //置结果串 T的结束标志
} // Concat
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 13页算法 5.3
void SubString_Sq( char Sub[ ],char S,int pos,int len) {
// 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
// 其中,0≤pos<StrLength(S) 且 0≤len≤StrLength(S)-pos。
slen=StrLength_Sq(S); // 求取顺序存储表示的字符串 S的串长度
if (pos < 0 || pos > slen-1 || len < 0 || len > slen-pos)
ERROR( " 参数不合法 ");
for ( j = 0; j < len; j++ ) Sub[ j ] = S[ pos + j ];
// 向子串 Sub复制字符
Sub[len] = '\0'; // 置串 Sub的结束标志
} // SubString
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 14页
5.2.2 堆分配存储表示
用一组连续的存储单元存储串值的字符序列。
但存储空间是在程序执行过程中 动态 分配得到的。
C语言中,用字符,\0”表示串的终结,“\0”不计入串长
typedef struct{
char *ch; //字符串地址
int length; //串长度
}HString;
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 15页算法 字符串赋值 1
bool StrAssign1(HString &T,char *s){
//字符串赋值，指定存储空间大小为 MAXSIZE
int i=0;
T.ch =new char[Maxsize]; //分配空间
while(*s) T.ch[i++]=*s++; //赋值给存储空间
T.length =i; //字符个个数
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 16页算法 字符串赋值 2
bool StrAssign2(HString &T,char *s){
//字符串赋值（根据字符 s的大小分配存储空间）
int i=0;
char *p=s;
while(*p++) i++;
T.length =i; //字符个个数
T.ch =new char[T.length]; //分配空间
p=s; //指针回指
i=0;
while(*s) T.ch[i++]=*s++; //赋值给存储空间
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 17页算法 销毁字符串
bool DestroyString(HString &S){
//销毁字符串 S
delete []S.ch; //释存储字符的空间
S.length =0; //长度为 0
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 18页算法 5.4
void StrInsert_ HSq (char* S,int pos,char* T) {
// 1≤pos≤StrLength(S)＋ 1。在串 S的第 pos个字符之前插入串 T
slen=StrLength_HSq (S); tlen=StrLength_HSq (T); // 取得原串 S
和插入串 T的串长
char S1[slen +1] ; // S1作为辅助串空间用于暂存 S
if (pos < 1 || pos > slen+1) ERROR(" 插入位置不合法 ");
if (tlen>0) { // T非空，则为 S重新分配空间并插入 T
i=0;
while ((S1[i]=S[i]) != '\0') i++; // 暂存串 S
S = new char[strlen + strlen +1]; // 为 S重新分配空间
for ( i=0,k=0; i<pos-1; i++) S[k++] = S1[i]; // 保留插入位置之前的子串
j = 0;
while ( T[j]!= '\0' ) S[k++] = T[j++]; // 插入 T
while ( S1[i]!= '\0') S[k++] = S1[i++]; // 复制插入位置之后的子串
S[k] = '\0'; // 置串 S的结束标志
} // if
} // StrInsert
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 19页
5.3 正文模式匹配
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 20页
S a b b b a a
T
朴素的模式匹配过程
a b aa b a b aa b a
模式匹配的最简单的做法是：用 T中的字符依次与 S中的字符比较：如果 S0 = T0,S1 = T1,…,Sm-1 = Tm-1,则匹配成功,调用求子串的操作 subString(S,1,m)即是找到的子串 。
否则必有某个 i（ 0≤i≤m -1）,使得 Si ≠T i,这时可将 T右移一个字符,用 T中字符从头开始与 S中字符依次比较；如此反复执行,直到下面两种情况之一：或者到达某步时,Si =
T0,Si+1 = T1,…,Si+m-1 = Tm-1,匹 配 成 功,
subString(S,i+1,m)即是找到的 （ 第一个 ） 与模式 T相同的子串；或者一直将 T移到无法与 S继续比较为止,则匹配失败 。
a
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 21页算法 5.6
int Index_BF ( char S [ ],char T [ ],int pos ) {
// 若串 S 中，从第 pos 个字符起存在和串 T 相同的子串，
//则称匹配成功，返回第 一个这样的子串在串 S 中的位
//置，否则返回 -1
i = pos; j = 0;
while ( S[i+j] != '\0' && T[j] != '\0' )
if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符
else { i ++; j = 0; } // 重新开始新的一轮比较
if ( T[j] == '\0' ) return i; // 匹配成功
else return -1;
// 串 S中 (第 pos个字符起 )不存在和串 T相同的子串
}//Index_BF
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 1页第 5章 串和数组
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 2页
5.1 串的定义
串：由 0或多个字符组成的序列
s=“a1a2a3…a n”
串的长度 n
空串和空格串
子串及子串的位置
两个串相等
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 3页
2.串的抽象数据类型定义
ADT String {
数据对象,D={ai|ai∈ char,i=1,2,…,n,n≥0}
数据关系,R={<ai-1,ai>|ai-1,ai ∈ D,i=1,2,…,n,n≥0}
基本操作,
参见后面介绍
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 4页
StrAssign(&T,chars)
初始条件,chars是字符串常量。
操作结果,生成一个其值等于 chars的串 T。
StrCopy(&T,S)
初始条件,字符串 S已经存在。
操作结果,由串 S复制得串 T。
StrEmpty (S)
初始条件,字符串 S已经存在。
操作结果,若 S为空串，则返回 TRUE,否则返回 FALSE。
串的基本操作（ 1）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 5页
StrCompare(S,T)
初始条件,字符串 S和 T存在。
操作结果,若 S>T,则返回值 >0;若 S=T,则返回值 =0;否则返回值 <0。
StrLength(S)
初始条件,字符串 S已经存在。
操作结果,返回串 S元素个数，称为串的长度。
ClearString(&S)
初始条件,字符串 S已经存在。
操作结果,将串 S清为空串。
串的基本操作（ 2）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 6页串的基本操作（ 3）
Concat(&T,S1,S2)
初始条件,字符串 S1,S2已经存在。
操作结果,用 T返回由串 S1和 S2联结而成的新串。
Substring(&Sub,S,pos,len)
初始条件,串 S存在,1<=pos<=S的长度,
0<=len<=S的长度 -pos+1。
操作结果,用 Sub返回串 S的第 pos个字符起长度为 len的子串。
Index(S,T,pos)
初始条件,串 S和 T存在,T是非空串,1<=pos<=S的长度。
操作结果,若主串 S中存在和串 T相同的子串，则返回它在主串 S中第 pos个字符之后第一次出现的位置；否则返回
０。
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 7页串的基本操作（ 4）
Replace(&S,T,V)
初始条件,字符串 S,T,V已经存在,T是非空串。
操作结果,用 V替换主串 S中出现的所有与 T相等的不重叠的子串。
StrInsert(&S,pos,T)
初始条件,字符串 S,T存在,1<=pos<=S的长度 +1。
操作结果,在串 S的第 pos个字符之前插入串 T。
StrDelete(&S,pos,len)
初始条件,串 S存在,1<=pos<=S的长度 -len+1。
操作结果,从串 S中删除第 pos个字符起长度为 len的子串,
DestroyString(&S):把存在的串 S销毁
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 8页上述 13种基本操作中,下面 5种操作构成最小操作子集,
串赋值 StrAssign;
串比较 StrCompare;
求串长 StrLength;
串联结 Concat;
求子串 Substring;
其它操作可以用其实现串类型的最小操作子集
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 9页
C语言函数库中提供下列串处理函数：
gets(str) 输入一个串；
puts(str) 输出一个串；
strcat(str1,str2) 串联接函数；
strcpy(str1,str2,k) 串复制函数；
strcmp(str1,str2) 串比较函数；
strlen(str) 求串长函数；
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 10页
5.2 串的表示和实现
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 11页
5.2.1 定长顺序存储表示
#define MAXSTRLEN 255 //串长度最大为 255
char SString[MAXSTRLEN+1];
//0号单元存放串的长度,其最大值刚好是 255
当超出 255个字符时,串的多余内容被舍去（截断）
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 12页算法 5.2
void Concat_Sq( char S1[ ],char S2[ ],char T[ ]) {
// 用 T返回由 S1和 S2联接而成的新串
j=0; k=0;
while ( S1[j] != '\0' ) T[k++] = S1[j++]; //复制串 S1
j = 0;
while ( S2[j] != '\0' ) T[k++] = S2[j++]; //接着复制串 S2
T[k] = '\0'; //置结果串 T的结束标志
} // Concat
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 13页算法 5.3
void SubString_Sq( char Sub[ ],char S,int pos,int len) {
// 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
// 其中,0≤pos<StrLength(S) 且 0≤len≤StrLength(S)-pos。
slen=StrLength_Sq(S); // 求取顺序存储表示的字符串 S的串长度
if (pos < 0 || pos > slen-1 || len < 0 || len > slen-pos)
ERROR( " 参数不合法 ");
for ( j = 0; j < len; j++ ) Sub[ j ] = S[ pos + j ];
// 向子串 Sub复制字符
Sub[len] = '\0'; // 置串 Sub的结束标志
} // SubString
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 14页
5.2.2 堆分配存储表示
用一组连续的存储单元存储串值的字符序列。
但存储空间是在程序执行过程中 动态 分配得到的。
C语言中,用字符,\0”表示串的终结,“\0”不计入串长
typedef struct{
char *ch; //字符串地址
int length; //串长度
}HString;
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 15页算法 字符串赋值 1
bool StrAssign1(HString &T,char *s){
//字符串赋值，指定存储空间大小为 MAXSIZE
int i=0;
T.ch =new char[Maxsize]; //分配空间
while(*s) T.ch[i++]=*s++; //赋值给存储空间
T.length =i; //字符个个数
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 16页算法 字符串赋值 2
bool StrAssign2(HString &T,char *s){
//字符串赋值（根据字符 s的大小分配存储空间）
int i=0;
char *p=s;
while(*p++) i++;
T.length =i; //字符个个数
T.ch =new char[T.length]; //分配空间
p=s; //指针回指
i=0;
while(*s) T.ch[i++]=*s++; //赋值给存储空间
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 17页算法 销毁字符串
bool DestroyString(HString &S){
//销毁字符串 S
delete []S.ch; //释存储字符的空间
S.length =0; //长度为 0
return OK;
}
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 18页算法 5.4
void StrInsert_ HSq (char* S,int pos,char* T) {
// 1≤pos≤StrLength(S)＋ 1。在串 S的第 pos个字符之前插入串 T
slen=StrLength_HSq (S); tlen=StrLength_HSq (T); // 取得原串 S
和插入串 T的串长
char S1[slen +1] ; // S1作为辅助串空间用于暂存 S
if (pos < 1 || pos > slen+1) ERROR(" 插入位置不合法 ");
if (tlen>0) { // T非空，则为 S重新分配空间并插入 T
i=0;
while ((S1[i]=S[i]) != '\0') i++; // 暂存串 S
S = new char[strlen + strlen +1]; // 为 S重新分配空间
for ( i=0,k=0; i<pos-1; i++) S[k++] = S1[i]; // 保留插入位置之前的子串
j = 0;
while ( T[j]!= '\0' ) S[k++] = T[j++]; // 插入 T
while ( S1[i]!= '\0') S[k++] = S1[i++]; // 复制插入位置之后的子串
S[k] = '\0'; // 置串 S的结束标志
} // if
} // StrInsert
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 19页
5.3 正文模式匹配
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 20页
S a b b b a a
T
朴素的模式匹配过程
a b aa b a b aa b a
模式匹配的最简单的做法是：用 T中的字符依次与 S中的字符比较：如果 S0 = T0,S1 = T1,…,Sm-1 = Tm-1,则匹配成功,调用求子串的操作 subString(S,1,m)即是找到的子串 。
否则必有某个 i（ 0≤i≤m -1）,使得 Si ≠T i,这时可将 T右移一个字符,用 T中字符从头开始与 S中字符依次比较；如此反复执行,直到下面两种情况之一：或者到达某步时,Si =
T0,Si+1 = T1,…,Si+m-1 = Tm-1,匹 配 成 功,
subString(S,i+1,m)即是找到的 （ 第一个 ） 与模式 T相同的子串；或者一直将 T移到无法与 S继续比较为止,则匹配失败 。
a
Da
ta
Str
uc
tur
e
数据结构—
第
5
章串和数组胡建华 2009-7-24计算机教研室第 21页算法 5.6
int Index_BF ( char S [ ],char T [ ],int pos ) {
// 若串 S 中，从第 pos 个字符起存在和串 T 相同的子串，
//则称匹配成功，返回第 一个这样的子串在串 S 中的位
//置，否则返回 -1
i = pos; j = 0;
while ( S[i+j] != '\0' && T[j] != '\0' )
if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符
else { i ++; j = 0; } // 重新开始新的一轮比较
if ( T[j] == '\0' ) return i; // 匹配成功
else return -1;
// 串 S中 (第 pos个字符起 )不存在和串 T相同的子串
}//Index_BF
