第5章(串)

华电计算机系NorthChinaElectricPowerUniversity第五章字符串北航计算机系华电计算机系NorthChinaElectricPowerUniversity5.1字符串的基本概念5.2字符串的基本操作5.3字符串的存储结构5.4关于字符串的几个算法北航计算机系华电计算机系NorthChinaElectricPowerUniversity5.1字符串的基本概念例如:S1=“abc”S2=“FORTRAN_77”S3=“”=(空串)串是由n0个字符组成的有限序列,通常记为S=“a1a2a3…an-1an”其中,S表示串名(也称串变量),一对引号括起来的字符序列称为串值,ai可以是字母、数字或其他允许的字符。n为串的长度,长度为0的串称为空串。一.字符串的定义北航计算机系华电计算机系NorthChinaElectricPowerUniversity1.串值须用一对引号括起来，但引号不属于串值。说明2.要区分空串与由空格字符组成的串的不同。String=“String”北航计算机系华电计算机系NorthChinaElectricPowerUniversity1.子串：串中若干个连续的字符组成的子序列。例如:S=“Beijing&Shanghai”T=“jing”2.主串:包含子串的串。3.位置：(1).单个字符在主串中的位置(2).子串在主串中的位置被定义为该字符在串中的序号。被定义为主串中首次出现的该子串的第一个字符在主串中的位置。例如:S=“Beijing&Nanjing&Shanghai”T=“jing”位置为4二.几个名词概念北航计算机系华电计算机系NorthChinaElectricPowerUniversity的充分必要条件为两个字符串的长度相等，4.两个字符串相等“abcd”“bacd”“abcd”=“abcd”北航计算机系并且对应位置上的字符相同。华电计算机系NorthChinaElectricPowerUniversity5.2字符串的基本操作1.StringcreateNullStr(void)创建一个空串2．intIsNullStr(Strings)判断串s是否为空串，若为空串,则返回1,否则返回0。3．intlength(Strings)返回串s的长度。4．StringStrassign(Strings,Stringt)将串t的值赋给串s，串s中的原值被覆盖掉。5．Stringconcat(Strings1,Strings2)返回将串s1和s2拼接在一起构成一个新串。6．StringsubStr(Strings,inti,intj)在串s中,求从串的第i个字符开始连续j个字符所构成的子串。7.intindex(Strings1,Strings2)如果串s2是sl的子串,则可求串s2在串s1中第一次出现的位置。8．Stringreplace(Strings,Stringt,Stringv)用串v替换主串s中的子串t。华电计算机系NorthChinaElectricPowerUniversity1.非紧缩格式(设每个字有4个字节)例如:S=“DATASTRUCTURE”DASTRUCTATURE@DATASTRUCTURE@2.紧缩格式3.单字节方式5.3串的存储结构一.串的顺序存储结构北航计算机系ATSATRUUTCDRE@华电计算机系NorthChinaElectricPowerUniversity求从s所指的顺序串中第i(i0)个字符开始连续取j个字符所构成的子串求顺序表示串的子串#defineMAXNUM100//串允许的最大字符个数structSeqString//顺序串的类型{charc[MAXNUM];intn;};华电计算机系NorthChinaElectricPowerUniversityPseqStringsubStr_seq(PseqStrings,inti,intj){PseqStrings1;intk;s1=createNullStr_seq();if(s1==NULL)return(NULL);if(i0&&i=s-n&&j0){if(s-ni+j-1)j=s-n-i+1;//若从i开始取不够j个字符，则能取几个就取几个for(k=0;kj;k++)s1-c[k]=s-c[i+k-1];s1-n=j;}return(s1);}华电计算机系NorthChinaElectricPowerUniversitySDATE^……说明：所谓链结点大小是指每个链结点的数据域中存放的字符的个数。DATATRURE@@……S^二.串的链式存储结构结点大小为4的链表结点大小为1的链表北航计算机系华电计算机系NorthChinaElectricPowerUniversity5.4串的几个算法一.串的定义#defineMAXNUM100//串允许的最大字符个数structSeqString//顺序串的类型{charc[MAXNUM];intn;};用单链表示串，结点的结构可说明为：structStrNode;//链串的结点typedefstructStrNode*PstrNode;//结点指针类型structStrNode{charc;PStrNodelink;};华电计算机系NorthChinaElectricPowerUniversity1)s.curlen+t.curlen≤maxlen，这时得到的串r是连接所要求的正确结果；2)s.curlen+t.curlenmaxlen，需要将t的一部分截断，得到的串r只包含s和t的一个子串；3)s.curlenmaxlen，这时需要对s进行截断，得到的串r仅是s的一个子串；子过程：voidmovch(t,s,i,j,num);{for(k=0;k=num–1;j++)t[i+k]=s[j+k];}假设r,s,t都是上面定义的string型变量，且r是s与t连接后得到的串，则连接运算concat(r,s,t)是将s与t的串值分别传送到r相应的位置上。二.串的连接华电计算机系NorthChinaElectricPowerUniversityvoidconcat(varr,s,t:string;varp:boolean);{if(s.curlen+t.curlen=maxlen){p=false;movch(r,s,1,1,s.curlen);movch(r,t,s.curlen+1,1,t.curlen);r.curlen=s.curlen+t.curlen;}if((s.curlen+t.curlenmaxlen)&&(s.curlenmaxlen)){p=true;movch(r,s,1,1,s.curlen);movch(r,t,s.curlen+1,1,maxlen-s.curlen);r.curlen=maxlen;}if(s.curlen=maxlen){p=true;movch(r,s,1,1,maxlen);r.curlen=maxlen;}}华电计算机系NorthChinaElectricPowerUniversity三.求子串的运算求子串的过程sub(r,s,fir,length)也是移动字符序列的过程，它将串s中从第fir位置开始的长度为length的子串赋给r。voidsub(r,s,fir,lenth);{if(fir+length-1s.curlen)||(fir1)||(length0){write(‘inproperlyspecifiedsubstringinsubproc’);exit;}else{movch(r,s,1,fir,length);r.curlen=length;}}华电计算机系NorthChinaElectricPowerUniversity四.求子串在串中的序号的运算由于求子串在串中序号的运算index(s,t)，其主要工作是确定已知串s中有无给定的子串t，因此，这个运算也称串的模式匹配运算。根据前面算法的思想，对于采用数组结构的串变量，给出一个不依赖其他串运算，完全独立的模式匹配算法。Voidindex_bf(s,t,ind);{i=1;j=1;repeatif(s.ch[i]=t.ch[j]){i=i+1;j=j+1;}else{i=i-j+2;j=1;}until(is.curlen)or(jt.curlen);if(jt.curlen)ind=i-t.curlenelseind=0;}华电计算机系NorthChinaElectricPowerUniversityS1=“a1a2a3a4a5…an”S2=“b1b2b3b4b5…bm”五.判断两个字符串是否相等功能:在单字节方式中，两个字符串分别存放于数组S1与S2中,并且都以@作为串的结束标志；判断两个串是否相等，若相等返回信息1，否则，返回信息0。北航计算机系华电计算机系NorthChinaElectricPowerUniversityfunctionEQUAL(S1,S2){i=1;while(S1[i]!=“@”andS2[i]!=“@”){if(S1[i]!=S2[i])return（0）;i++;}if(S1[i]=“@”andS2[i]=“@”)thenreturn（1）return（0）}算法北航计算机系华电计算机系NorthChinaElectricPowerUniversity六.串的插入功能：在字符串S的第i个字符后面插入字符串T。前提:字符串S与T分别采用结点大小为1的线性链表存储结构(设S与T分别指向链表的第一个链结点)。约定：1.当i=0时，将T插在S的最前面。2.结果串由S指出。北航计算机系华电计算机系NorthChinaElectricPowerUniversity……^T……S^第i个结点需要做的工作:1.找到S的第i个字符的位置(即S的第i个链结点的地址).2.找到S的第i+1个字符的位置(即S的第i+1个链结点的地址).3.找到T的最后那个字符的位置(即T的尾结点的地址).北航计算机系华电计算机系NorthChinaElectricPowerUniversity……S^第i个结点……^TpqrSp=p-linkq=p-linkr=r-link北航计算机系华电计算机系NorthChinaElectricPowerUniversity算法voidINSERTS(S,T,i){if(T=nil)若T串为空return;if(S=nil){S=T;若S串为空return;}if(i0){callERROR(‘positionerror!’)return}p=S;for(j=1;j=i–1;j++){p=p-link;if(p=nil)then{callERROR(‘Thepositionerror!’);return;}p指向S的第i个字符北航计算机系华电计算机系NorthChinaElectricPowerUniversityr=T;while(r-link!=nil)r=r-link;r指向T的最后那个字符if(i=0){r-link=S;S=T;}将T插在S的最前面else{p-link=T;r-link=q;}将T插在S的第i个字符后面}北航计算机系q=p-link;q指向S的第i+1个字符