数据结构课件第四章数据结构课件串.ppt

——是由零个或多个字符组成的有限序列。一般记为:S=‘a1a2…an’(n>=0)长度——串中字符的数目。空串——零个字符的串,用符号φ来表示空串。子串——串中任意个连续的字符组成的子序列。主串——包含子串的串。位置——字符在序列中的序号为该字符在串中的位置。例:a=‘bei’b=‘jing’c=‘beijing’d=‘beijing’则:a,b,c,d的长度分别为:3、4、7、8。a、b是c和d的子串。a在c和d中的位置都是1。b在c中的位置是4,在d中的位置是52相等——当两个串的长度相等,并且各个对应位置的字符都相等,则称两个串是相等的。空格串——由一个或多个空格组成的串称为空格串。注意:串值必须用一对单引号括起来,但单引号本身不属于串。例:x=‘123’;x=123;tsing=‘tsing’3串的抽象数据类型的定义:ADTString{数据对象: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复制得串TStrEmpty(S)串S存在则若S为空串,pare(S,T)串S和T存在,若S>T,则返回值>0,若S=T,则返回值=0,若S<T,则返回值<04StrLength(S)(&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个字符之后第一次出现的位置,否则函数值为0Replace(&S,T,V)串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串5StrInsert(&S,pos,T)串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串DestroyString(&S)串S存在,则串S被销毁}ADTString6例子:设: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)pare(s,t)判等函数。例:pare(a,b)返回值<pare(φ,φ)返回值=0(3)strlength(s)求长函数7(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)substring(&sub,s,pos,len)求子串函数。if1≦pos≦length(s)且0≦len≦length(s)-pos+1用sub返回从串s中第pos个字符起,长度为len的字符序列。else返回error例:substring(sub,d,1,3)Sub=‘bei’Substring(sub,d,4,0)sub=φ8(6)index(s,t,pos)定位函数。if在主串S中的第pos个位置之后存在和t相等的子串返回S中第一个这样的子串在主串S中的位置。else返回零例:index(d,b,1)=4index(d,c,1)=0(7)replace(&s,t,v)置换函数。以串v替换所有出现的和非空串t相等的不重叠的子串。例:replace(d,b,c)d=‘bei’例:设s=‘bbabbabba’t=‘ab’v=‘c’则replace(s,t,v)s=‘bbcbcba’index(d,b,5)=09(8)strsert(&s,pos,t)插入操作。if1≦pos≦length(s)+