1、第四章第四章 字符串字符串 字符串的基本概念字符串的基本概念 字符串的基本运算字符串的基本运算 字符串的存储结构字符串的存储结构 关于字符串的几个常用算法关于字符串的几个常用算法 5.1 字符串的基本概念字符串的基本概念例如例如:S1=“abc”S2=“FORTRAN_77”S3=“”=(空串空串)字符串是由字符串是由n 0个字符组成的有限序列个字符组成的有限序列,通常记为通常记为 S=“a1 a2 a3 an-1 an”其中其中,S表示串名表示串名(也称串变量也称串变量),),一对引号括起来的字一对引号括起来的字 符序列称为串值符序列称为串值,ai可以是字母、数字或其他允许的字可以是字母、数
2、字或其他允许的字 符。符。n 为串的长度为串的长度,长度为长度为0的串称为空串。的串称为空串。一一.字符串的定义字符串的定义 1.串值须用一对引号括起来，但引号不属于串值。串值须用一对引号括起来，但引号不属于串值。说明说明2.要区分空串与由空格字符组成的串的不同。要区分空串与由空格字符组成的串的不同。String=“String”1.子串：子串：串中若干个连续的字符组成的子序列串中若干个连续的字符组成的子序列。例如例如:S=“Beijing&Shanghai”T=“jing”2.主串主串:包含子串的串包含子串的串。3.位置：位置：(1).单个字符在主串中的位置单个字符在主串中的位置(2).).
3、子串在主串中的位置子串在主串中的位置 被定义为该被定义为该 字符在串中的序号。字符在串中的序号。被定义为主串中被定义为主串中 首次出现的该子串的第一个字符在主首次出现的该子串的第一个字符在主 串中的位置。串中的位置。例如例如:S=“Beijing&Nanjing&Shanghai”T=“jing”位置为位置为4 4二二.几个名词概念几个名词概念 的充分必要条件为两个字符串的长的充分必要条件为两个字符串的长度相等，度相等，并且对应位置上的字符相同。并且对应位置上的字符相同。4.两个字符串相等两个字符串相等“abcd”“bacd”“abcd”=“abcd”5.2 字符串的基本操作字符串的基本操作1
4、.String createNullStr(void)创建一个空串创建一个空串 2int IsNullStr(String s)判断串判断串s是否为空串，若为空串是否为空串，若为空串,则返回则返回1,否则返回否则返回0。3int length(String s)返回串返回串s的长度。的长度。4void Strassign(String&s,String t)将串将串t的值赋给串的值赋给串s，串，串s中的原值被覆盖掉。中的原值被覆盖掉。5void concat(String&s,String s1,String s2)返回将串返回将串s1和和s2拼接在一起构成一个新串拼接在一起构成一个新串s。6
5、String subStr(String s,int i,int j)在串在串s中中,求从串的第求从串的第i个字符开始连续个字符开始连续j个字符所构成的子串。个字符所构成的子串。7.int index(String s1,String s2)如果串如果串s2是是sl的子串的子串,则可求串则可求串s2在串在串s1中第一次出现的位置。中第一次出现的位置。8void replace(String&r,String s,String t)用串用串t替换主串替换主串r中的子串中的子串s。例如例如:S=“DATA STRUCTURE”5.3 串的存储结构串的存储结构一一.串的顺序存储结构串的顺序存储结构A
6、 TSAT R UUTCDR E#define MAXLEN 100 /串允许的最大字符个数串允许的最大字符个数struct SeqString /顺序串的类型顺序串的类型 char cMAXLEN+1;int length;求从求从s s所指的顺序串中第所指的顺序串中第i(i0)i(i0)个字符开始连续取个字符开始连续取j j个字个字符所构成的子串。符所构成的子串。求顺序表示串的子串求顺序表示串的子串SeqString substr(SeqString s,int i,int j)SeqString s1;if(i0)&(i0)if(s.lengthi+j-1)j=s.length-i+1;
7、/若从若从i开始取不够开始取不够j个字符，则能取几个就取几个个字符，则能取几个就取几个 for(k=1;kMAXLEN，需要将需要将t t的一部分截断，得到的的一部分截断，得到的 串串r r只包含只包含s s和和t t的一个子串；的一个子串；假设假设r,s,t都是前面定义的都是前面定义的string型变量，且型变量，且r是是s与与t连接后连接后得到的串，则连接运算得到的串，则连接运算concat(r,s,t)是将是将s与与t的串值分别传送的串值分别传送到到r相应的位置上。相应的位置上。void concat(SeqString&r,s,t,bool&p)if(s.length+t.length
8、MAXLEN)p=true;movch(r,s,1,1,s.length);movch(r,t,s.length+1,1,MaxLength-s.length);r.length=MAXLEN;void movch(SeqString&t,SeqString s,int i,int j,int num)for(k=0;k=num 1;k+)ti+k=sj+k;二二.求子串在串中的序号的运算求子串在串中的序号的运算 由于求子串在串中序号的运算由于求子串在串中序号的运算index(s,t)index(s,t)，其主要工作是，其主要工作是确定已知串确定已知串s s中有无给定的子串中有无给定的子串t
9、t，因此，这个运算也称串的模，因此，这个运算也称串的模式匹配运算。式匹配运算。int index_bf(SeqString s,SeqString t,int&ind)/求子串求子串t在主串在主串s中的序号，从中的序号，从ind开始开始 i=ind;j=1;do if(s.chi=t.chj)i=i+1;j=j+1;else i=i-j+2;j=1;while(i=s.length)&(jt.length)return(i-t.length);else return(0);三三.子符串的置换运算子符串的置换运算 字符串的置换元算字符串的置换元算Replace(r,s,t),Replace(r,s,t),在在r r中查找有无和中查找有无和s s相同相同的子串，如果有则用的子串，如果有则用t t替换它，得到一个新串赋给替换它，得到一个新串赋给r r，再从合适，再从合适的位置重复上述过程，直到的位置重复上述过程，直到r r中已找不到和中已找不到和s s相同的子串为止。相同的子串为止。void Replace(SeqString&r,SeqString s,SeqString t)n=r.length;m=s.length;k=t.length;if(nn-m+1);
