第四章串ppT.pptVIP

第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 * * 4.1.1 串的逻辑结构定义 串—— 是由零个或多个字符组成的有限序列。 一般记为： S=‘a1a2…an’ (n=0) 长度—— 串中字符的数目。 空串—— 零个字符的串，用符号φ来表示空串。 子串—— 串中任意个连续的字符组成的子序列。 主串—— 包含子串的串。 位置—— 字符在序列中的序号为该字符在串中的位置。 例：a=‘bei’ b=‘jing’ c=‘beijing’ d=‘bei jing’ 则：a,b,c,d的长度分别为：3、4、7、8。 a、b是c和d的子串。 a 在c和d中的位置都是1。 b在c中的位置是4，在d中的位置是5 相等—— 当两个串的长度相等，并且各个对应位置的字符都相等，则称两个串是相等的。 空格串—— 由一个或多个空格组成的串称为空格串。 注意：串值必须用一对单引号括起来，但单引号本身不 属于串。 例： x=‘123’; x=123; tsing=‘tsing’ 串的抽象数据类型的定义： ADT String{ 数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai(-D,i=2,...,n} 基本操作： StrAssign(T,chars) chars是字符常量。生成一个其值等于chars的串T。 StrCopy(T,S) 串S存在则由串S复制得串T StrEmpty(S) 串S存在则若S为空串,返回真否则返回假 StrCompare(S,T) 串S和T存在,若ST,则返回值0,若S=T,则返回值=0, 若ST,则返回值0 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=StrLength(S)且0=len=StrLength(S)-pos+1 用Sub返回串S的第pos个字符起长度为len的子串 Index(S,T,pos) 串S和T存在,T是非空,1=pos=StrLength(S),若主串S中存 在和串T值相同的子串,则返回它在主串S中第pos个字符之 后第一次出现的位置,否则函数值为0 Replace(S,T,V) 串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T 相等的不重叠的子串 StrInsert(S,pos,T) 串S和T存在,1=pos=StrLength(S)+1,在串S的第pos个 字符 之前插入串T StrDelete(S,pos,len) 串S存在,1=pos=StrLength(S)-len+1从串中删除第pos个 字符起长度为len的子串 DestroyString(S) 串S存在,则串S被销毁 }ADT String 例子： 设：s,t,v,a,b,c,d都为串名。 a=‘bei’ b=‘jing’ c=‘ ’ d=‘beijing’ (1)Strassign(s,ss)和strcopy(s,t)赋值操作。 例： strassign(s, ‘abcd’) S=‘ abcd’ 例： strcopy(s, d) S=‘beijing’ (2)strcompare(s,t) 判等函数。 例：strcompare(a,b) 返回值0 strcompare(φ, φ) 返回值=0 (3)strlength(s) 求长函数 (4)concat(t,s1,s2) 联接函数。 例 S1=‘S1S2…Sm’ s2=‘t1t2…tn’ 则: concat(t,s1,s2)? t=‘S1S2…Smt1t2…tn’ concat(t,s2,s1)? t=‘t1t2…tnS1S2…Sm’ (5)subs