第四章串 4.1串类型的定义 4.2串的表示和实现 4.2.1定长顺序存储表示 4.2.2堆分配存储表示 4.3串的模式匹配算法 讨论基本的串处理操作和两种存储结构
第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.3 串的模式匹配算法 讨论基本的串处理操作和两种存储结构
4.1串类型的定义 非数值处理的对象基本上是字符串数据 串( string)(或称字符串) 由零个或多个字符组成的有限序列 己为 (n>=0) a1(1<=i<=n)是字母,数字或其它字符 n称为串的长度,n=0的串称为空串( Null string) 子串一串中任意个连续字符组成的子序列 包含子串的串叫主串 子串在主串中的位置 子串的第一个字符在主串中的序号
4.1 串类型的定义 非数值处理的对象基本上是字符串数据 串(string)(或称字符串)---- • 由零个或多个字符组成的有限序列 • 记为: s = ‘ a1a2...an ’ (n>=0) • ai(1<=i<=n)是字母,数字或其它字符 • n称为串的长度,n=0的串称为空串(Null string) 子串----串中任意个连续字符组成的子序列 • 包含子串的串叫主串 • 子串在主串中的位置 ---- • 子串的第一个字符在主串中的序号
串的例子 例如: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,而b在d中的位置是5 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 当且仅当这两个串每个字符对应相等
串的例子 例如: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,而b在d中的位置是5 • 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 --- • 当且仅当这两个串每个字符对应相等
串的抽象数据类型 数据对象为字符集的线性表 ADT String i 数据对象:D={a1|a1 Characteset,i=1,2 数据关系:R={1a1D,i=2,…n} 基本操作: StrAssign(&T, chars); StrCopy(&T, s); StrEmpty(S); StrCompare(s, T) StrEngth(s) ClearString(&s); Concat(&T, S1, S2); Substring(&Sub, S, pos,len); Index(s,T, pos); Replace(&s,T, v) StrInsert(&S, pos,T); StrDelete(&S, pos, len) DestroyString(&s) JADT String
串 的 抽 象 数 据 类 型 --- 数据对象为字符集的线性表 ADT String { 数据对象：D = {ai | ai CharacteSet,i=1,2,...n, n>=0} 数据关系： R1 = {＜ ai-1. , aj＞| ai D, i=2,...n}。 基本操作： • StrAssign(&T,chars); StrCopy(&T,S); • StrEmpty (S); StrCompare(S,T); • StrLength(S); ClearString(&S); • Concat(&T,S1,S2); Substring(&Sub,S,pos,len); • Index(S,T,pos); Replace(&S,T,V); • StrInsert(&S,pos,T); StrDelete(&S,pos,len); • DestroyString(&S) }ADT String
基本操作的功能说明1 StrAssign(&t, chars) 初始条件: chars是字符串常量 操作结果:生成一个其值等于 chars的串T StrCopy(&t,s) 初始条件:字符串S已经存在 操作结果:由串S复制得串T。 StrEmpty (s) 初始条件:字符串S已经存在。 操作结果:若S为空串,则返回TRUE,否则返回 FALSE StrCompare(s,T) 初始条件:字符串S和T存在。 作结果:若ST,则返回值>0;若S=T,则返回值=0;否则返回
基本操作的功能说明1 StrAssign(&T,chars) • 初始条件: chars是字符串常量。 • 操作结果: 生成一个其值等于chars的串T。 StrCopy(&T,S) • 初始条件: 字符串S已经存在。 • 操作结果: 由串S复制得串T。 StrEmpty (S) • 初始条件: 字符串S已经存在。 • 操作结果: 若S为空串，则返回TRUE,否则返回FALSE。 StrCompare(S,T) • 初始条件: 字符串S和T存在。 • 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;否则返回 值<0
基本操作的功能说明2 StrEngth(s) 初始条件:字符串S已经存在。 操作结果:返回串S元素个数,称为串的长度。 ClearString(&s) 初始条件:字符串S已经存在。 操作结果:将串S清为空串。 Concat(&T,s1, s2) 初始条件:字符串S1,S2已经存在 操作结果:用T返回由串S1和S2联结而成的新串。 Substring(&sub, S, pos,len) 初始条件:串S存在,1<=p0s<=S的长度,0<=1en<=S的长度pos+1。 操作结果:用Sub返回串S的第pos个字符起长度为len的子串
基本操作的功能说明2 StrLength(S) • 初始条件: 字符串S已经存在。 • 操作结果: 返回串S元素个数，称为串的长度。 ClearString(&S) • 初始条件: 字符串S已经存在。 • 操作结果: 将串S清为空串。 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的子串
基本操作的功能说明3 Index(s,,pos) 初始条件:串S和T存在,T是非空串,1<pos<=S的长度。 操作结果:若主串S中存在和串T相同的子串,则返回它在主串 中第pos个字符之后第一次出现的位置;否则返回0。 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的长度-1en+1 操作结果:从串S中删除第pos个字符起长度为len的子串 DestroyString(&S):把存在的串S销毁
基本操作的功能说明3 Index(S,T,pos) • 初始条件: 串S和T存在,T是非空串，1<=pos<=S的长度。 • 操作结果: 若主串S中存在和串T相同的子串，则返回它在主串 S中第pos个字符之后第一次出现的位置；否则返回０。 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销毁
串类型的最小操作子集 上述13种基本操作中,下面5种操作构成最小操作子集: 串赋值 StrAssign; 串比较 StrCompare; int Index(String S, String T,, int pos) 球Smgh i int i,n, m; String sub if(pos>03 n=StrEngth(S) 求子串 Substring m= StrEngth -pos, 其它操作可以用其实现| while(i=nm+1 例如定位函数 SubString(sub,s, i, m) ndex(s, T, pos) f( StrCompare(sub, T)=0)++i; else return 的算法如右 //while return 0; }∥ndex
串类型的最小操作子集 上述13种基本操作中,下面5种操作构成最小操作子集: • 串赋值 StrAssign; • 串比较 StrCompare; • 求串长 StrLength; • 串联结 Concat; • 求子串 Substring; 其它操作可以用其实现 例如定位函数 Index(S,T,pos) 的算法如右: int Index(String S, String T, int pos) { int i,n,m; String sub; if(pos > 0){ n = StrLength(S); m = StrLength(T); i = pos; while(i<=n-m+1){ SubString(sub,S,i,m); if(StrCompare(sub,T)!=0)++i; else return i; } //while } // if return 0; } // Index
4.2串的表示和实现(一) 4.2.1定长顺序存储表示 用一组连续的存储单元存储串值的字符序列 在C语言中,用字符“\0”表示串的终结,“\0”不计入串长 另一种方法是定长数组表示一个串 define MAXStRLEn255/串的长度最大为255 ypedef unsigned char SString[MAXSTRLEN+1 ∥0号单元存放串的长度,其最大值刚好是255 当超出255个字符时,串的多余内容被舍去,叫做“截断” 以下用串联结和求子串为例介绍这种存储
4.2 串的表示和实现(一) 4.2.1 定长顺序存储表示 用一组连续的存储单元存储串值的字符序列. 在C语言中,用字符“\0”表示串的终结, “\0”不计入串长. 另一种方法是定长数组表示一个串: #define MAXSTRLEN 255 // 串的长度最大为255 typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度, 其最大值刚好是255. 当超出255个字符时,串的多余内容被舍去,叫做“截断” 以下用串联结和求子串为例介绍这种存储
1.串联结 Concat(&T,S1,S2)的算法 status Concat(SString &T, SString Sl, SString S2) )T返回由串S1和S2联结而成的新串。若未被截断,则返回1;否则返回0。 if 0]= MAXSTRLEN( 未被截断 s1o=S11.s10 ∥/示意赋值,非C语句 0]+1.S10J+S2[0]=S2[1.S2[0],∥示意赋值 1[o]+S2[0 uncut Jelseif(s1o< MAXstrlend( ∥截断 SIOJ+I. MAXSTRLENI=S21. MAXSTRLEN-SI1OJI MAXSTRLEN uncut=0 }else{∥截断(仅取S1) TIO.. MAXSTRLENI-SI1O. MAXSTRLENI uncut=0 3//if return uncut }∥ Concat
1.串联结 Concat(&T,S1,S2)的算法 status Concat(SString &T, SString S1, SString S2) {//用T返回由串S1和S2联结而成的新串。若未被截断,则返回1;否则返回0。 if ( S1[0]+S2[0] <= MAXSTRLEN) { //未被截断 T[1..S1[0]] = S1[1..S1[0]]; // 示意赋值，非C语句 T[S1[0]+1.. S1[0]+S2[0]] = S2[1..S2[0]]; // 示意赋值 T[0] = S1[0]+S2[0]; uncut = 1; }elseif (S1[0] < MAXSTRLEN) { // 截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1.. MAXSTRLEN] = S2[1.. MAXSTRLEN-S1[0]]; T[0] = MAXSTRLEN; uncut = 0; }else{ // 截断(仅取S1) T[0.. MAXSTRLEN] = S1[0.. MAXSTRLEN]; uncut = 0; } // if return uncut; } // Concat