数据结构6串.ppt

文档介绍：(string)(或称字符串)----由零个或多个字符组成的有限序列记为:s=‘a1a2...an’(n>=0)ai(1<=i<=n)是字母,数字或其它字符n称为串的长度,n=0的串称为空串(Nullstring)子串----串中任意个连续字符组成的子序列包含子串的串叫主串子串在主串中的位置----子串的第一个字符在主串中的序号串的例子例如:a,b,c,d四个字符串为a=‘BEI’,b=‘JING’c=‘BEIJING’,d=‘BEIJING’它们的长度分别为3,4,7,8a和b都是c和d的子串a在c和d中的位置都是1b在c中的位置是4,而b在d中的位置是5注意:单引号是为字符串区别于变量名而设,它不是字符串的内容称两个串是相等的---当且仅当这两个串每个字符对应相等串的抽象数据类型---数据对象为字符集的线性表ADTString{数据对象: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);pare(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)}ADTString基本操作的功能说明1StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个其值等于chars的串T。StrCopy(&T,S)初始条件:字符串S已经存在。操作结果:由串S复制得串T。StrEmpty(S)初始条件:字符串S已经存在。操作结果:若S为空串,则返回TRUE,否则返回FALSE。pare(S,T)初始条件:字符串S和T存在。操作结果:若S>T,则返回值>0;若S=T,则返回值=0;否则返回值<0。基本操作的功能说明2StrLength(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的子串。基本操作的功能说明3Index(S,T,pos)初始条件:串S和T存在,T是非空串,1<=pos<=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<=S的长度+1。操作结果:在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件:串S存在,1<=pos<=S的长度-len+1。操作结果:从串S中删除第pos个字符起长度为len的子串。DestroyString(&S): 把存在的串S销毁。串类型的最小操作子集上述13种基本操作中,下面5种操作构成最小操作子集:串赋值StrAssign;pare;求串长StrLength;串联结Concat;求子串Substring;其它操作可以用其实现例如定位函数Index(S,T,pos)的算法如右:intIndex(StringS,StringT,intpos){inti,n,m;Stringsub;if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(pare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;}//(一),用字符