字符串定义.ppt

1、字符串定义 字符串的顺序表示及操作的实现 字符串的模式匹配,第四章 字符串,字符串 (String),字符串是 n ( 0 ) 个字符的有限序列， 记作 S : “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci 是串中字符 n 是串的长度。 例如, S = “Tsinghua University”,在C中常用的字符串操作,字符串初始化 char name12 = “Tsinghua”; char name = “Tsinghua”; char name12 = T,s,i,n,g,h,u,a; char name = T,s,i,n,g,h,u,a,0; char

2、*name = “Tsinghua”; char name12; name = “Tsinghua”; 因数组名是地址常量,单个字符串的输入函数 gets (str) 例 char name12; gets (name); 多个字符串的输入函数 scanf 例 char name112, name220; scanf (“%s%sn”, name1, name2); 字符串输出函数 puts (str) 例 char name12; gets(name); puts(name); 字符串求长度函数 strlen(str) 字符串长度不包括“0”和分界符,字符串连接函数 strcat (str1

3、, str2) 例 str1 “Tsinghua0” /连接前 str2 “University0” /连接前 str1 “TsinghuaUniversity0” /连接后 str2 “University0” /不变 字符串比较函数 strcmp (str1, str2) /从两个字符串第 1 个字符开始，逐个对 /应字符进行比较，全部字符相等则函数返 /回0，否则在不等字符处停止比较，函数 /返回其差值 ASCII代码 例 str1 “University” i 的代码值105 str2 “Universal” a 的代码值97，差8,字符串类型的主要操作,void SetString

4、( String *S ); /创建一个空的字符串S int StrLength ( String *S ); /求字符串S的长度（字符个数） int StrEmpty ( String *S ); /判断字符串S空否。空返回1，否则返回0 char StrGetData ( String *S, int pos ); /读取字符串S中第pos个字符 int StrCompare ( String *S, String *T); /比较字符串S与T。,char *Trans ( String *S ); /指针转换：求串S中存储堆的首地址 void StrAssign ( String *S,

5、 char *cs ); /从字符数组cs创建字符串S void StrConcat ( String *S, String *S1, String *S2 ); /字符串S2连接于S1后面, 结果存于S中 void SubString ( String *T, String *S, int pos, int count ); /从串S中第pos字符起连续取count个字符，/由串T返回,void StrInsert ( String *S, char *cs, int pos ); /插入字符数组cs到串S的第pos位置 void StrInsert1( String *S, String

6、*CS, int pos ); /插入串CS到串S的第pos位置 void StrDelete ( String *S, int pos, int count ); /从pos位置起在串S中连续删除count个字符 void FreeString ( String *S ); /释放串S的空间 void ClearString ( String *S ); /清空字符串,利用串的操作实现串的定位算法,此算法就是求子串P在串T中首次出现的位置,第1趟 T a b b a b a P a b a 第2趟 T a b b a b a P a b a 第3趟 T a b b a b a P a b a

7、 第4趟 T a b b a b a P a b a ,int index ( string *T, string *P ) /在串T中寻找与串P相匹配的子串。若有， /函数返回子串在串中位置，若无，返回-1。 int LT = StrLength (T), LP = StrLength (P); string *subStr; int i = 0; while ( i = LT - LS ) SubString ( subStr, T, i, LP ); if ( !StrCompare ( SubStr, P ) ) return i; else i+; return -1; ,const

8、 int maxLen = 128; typedef struct char *ch; /串的存储数组 int curLen; /串的当前长度 HString;,字符串的顺序方式(堆)定义,ch,curLen,void SetString ( HString *S ) /创建一个空的字符串S S-ch = ( char *) malloc ( maxLen *sizeof (char) ); if ( S-ch = NULL ) printf (overflow); exit (1); *(S-ch) = 0; S-curLen = 0; ,int StrLength ( HString *S

9、) /求字符串S的长度 return S-curLen; int StrEmpty ( HString *S ) /判断字符串S空否。空返回1，否则返回0 return S-curLen = 0; /等价于 if ( S-curLen = 0 ) return 1; / else return 0;,char StrGetData ( HString *S, int pos) /读取字符串S中第pos个字符 if ( pos S-curLen-1) printf (位置pos无效!); exit (1); return S-chpos; char *Trans ( HString *S ) /

10、指针转换：求串S中存储堆的首地址 return S-ch; ,int StrCompare ( HString *S, HString *T ) /比较字符串S与T: 若S = T, 返回值 = 0; 若S / T, 返回值= 1; 若S ch, T-ch ) ); ,void StrAssign ( HString *S, char *cs ) /从字符数组cs创建字符串S int n = strlen(cs) +1; /新串的长度 free ( S-ch ); /释放老串的堆空间 S-ch = (char *) malloc ( n * sizeof (char) ); if ( S-ch

11、 = NULL ) printf (overflow); exit(1); strcpy( S-ch, cs ); /复制老数组到新串中 S-curLen = n-1; /新串的长度 ,void StrConcat ( HString *S, HString *S1, HString *S2 ) /字符串S2连接于S1后面, 结果存于S中 int n = S1-curLen + S2-curLen + 1; free( S-ch); /重新分配串空间 S-ch = (char *) malloc (n * sizeof (char) ); if ( S-ch = NULL) printf (o

12、verflow); exit (1); strcpy ( S-ch, S1-ch ); /串S1复制到S中 strcat ( S-ch, S2-ch); /串S2连接到S后部 S-curLen = n-1; /串长度 ,提取子串的算法示例,pos+count -1 pos+count-1 curLen-1 curLen-1 修改 count = curLen-pos,i n f i n i t y,i n f i n i t y,pos = 2, count = 3,pos = 5, count = 4,f i n,i t y,超出,void SubString( HString *T, HS

13、tring *S, int pos, int count) /从串S中第pos字符起连续取count个字符，由 /串T返回 int i, charsleft; char *p, *q; if ( pos S-curLen-1) printf ( 位置pos无效!n); exit(1); if ( count curLen - pos; if ( count charsleft ) count = charsleft;,free ( T-ch ); T-ch = (char *) malloc ( (count+1) * sizeof (char); if ( T-ch = NULL ) /重新

14、分配子串空间 printf (overflow); exit(1); p = T-ch; q = S-ch + pos; for ( i = 1; i curLen = count; /子串长度 ,void StrInsert ( HString *S, char *cs, int pos ) /插入字符数组cs到串S的第pos位置 int n, i, charsleft; char *temp, *p, *q; if ( pos S-curLen ) printf ( 位置pos无效!n ); exit (1); n = S-curLen+1; temp = (char *) malloc

15、( n*sizeof (char) ); if ( temp = NULL ) /创建临时串 printf ( overflow ); exit (1); strcpy( temp, S-ch ); /复制串S到临时串 free( S-ch); /释放串S原来的空间 n = strlen(temp)+strlen(cs)+1; /新串长度,S-ch = (char *) malloc( n*sizeof (char) ); if ( S-ch = NULL ) /按新长度分配串空间 printf (overflow); exit (1); strcpy( S-ch, temp ); /复制回原

16、串S的内容 /原串从pos位置起后移，空出cs个字符位置 p = S-ch+strlen(temp); /原串末尾 q = S-ch+n-1; /新串末尾 charsleft = strlen(temp)-pos+1; /移动字符数 for ( i = 1; i ch+pos; q = cs; while ( *q != 0 ) *p+ = *q+; /插入cs串,S-curLen = n-1; free (temp); ,S,pos,cs,B E I S H I 0,pos,B E I S H I 0,pos,B E I J I N G S H I 0,void StrDelete( HSt

17、ring *S, int pos, int count) /从pos位置起在串S中连续删除count个字符 int i, n, charsleft; char *temp, *p, *q; if ( pos S-curLen-1 ) printf ( “删除位置pos无效!n); exit(1); if ( count curLen+1; temp = (char *) malloc (n*sizeof (char) ); if ( temp = NULL) /创建临时串 printf(overflow); exit(1); ,strcpy( temp, S-ch ); /原串复制到临时串 i

18、f ( count = strlen(temp)-pos ) /count太大 temppos = 0; /从pos到串尾全删 else /否则,从pos+count起连续前移 p = temp+pos; q = temp+pos+count; while ( *q != 0 ) *p+ = *q+; *p = 0; /串收尾 free( S-ch ); n = strlen(temp)+1; S-ch = (char *) malloc ( n*sizeof (char) ); /重新分配字符串S的空间,if ( S-ch = NULL ) printf (overflow); exit(1

19、); strcpy( S-ch, temp ); /结果串赋值 S-curLen = n-1; /结果串长度 free(temp); void FreeString( HString *S ) /释放串S的空间 free( S-ch ); ,void ClearString( HString *S ) /清空字符串 free( S-ch ); S-ch = (char *) malloc ( maxLen*sizeof (char) ); if ( S-ch = NULL ) printf( overflow); exit(1); *(S-ch) = 0; S-curLen = 0; ,串的模

20、式匹配,定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 3,第1趟 T a b b a b a 穷举的模式 P a b a 匹配过程 第2趟 T a b b a b a P a b a 第3趟 T a b b a b a P a b a 第4趟 T a b b a b a P a b a ,int Find ( HString *T, Hstring *P ) /穷举的模式匹配 char *p = P-ch, *s = T-ch; int i = 1; if ( *p

21、 != 0 ,第1趟匹配 Ta b a b c a b c a c b a b Pa b c a c 第2趟匹配 T a b a b c a b c a c b a b P a b c a c 第3趟匹配 T a b a b c a b c a c b a b P (a)b c a c,改进的模式匹配,i,j,i,j,i,j,T t1 ts-1 ts ts+1 ts+j-2 ts+j-1 ts+j tn P p1 p2 pj-1 pj 则有 ts ts+1 ts+2 ts+j-2 = p1 p2 p3 pj-1 (1) 为使模式 P 与目标 T 匹配，必须满足 p1 p2 pj-1 pm =

22、ts+1 ts+2 ts+3 ts+j ts+m 如果 p2 p3 pj-1 p1 p2 pj-2 (2) 则立刻可以断定 p1 p2 pj-2 ts+1 ts+2 ts+j 下一趟必不匹配,同样，若 p1 p2 pj-3 p3 p4 pj-1 则再下一趟也不匹配，因为有 p1 p2 pj-3 ts+1 ts+2 ts+j-2 直到对于某一个“k”值，使得 p1 p2 pk pj-k pj-k+1 pj-1 且 p1 p2 pk-1 = pj-k+1 pj-k+2 pj-1 则 p1 p2 pk-1 = ts+1 ts+2 ts+j-2 pj-k+1 pj-k+2 pj -1 下次只需将pk与T失配位置对齐就可继续比较 T t1 ts ts+1 ts+2 ts+j-2 ts+j-1 ts+j tn P ( p1 p2 pk-1 ) pk pk+1 ,k 的确定方法 当比较到模式第 j 个字符失配时， k 的值与模式的前 j 个字符有关，与目标无关。 利用失效函数 next j可描述。 利用失效函数 next j 的匹配处理 如果 j = 0，则目标指针加 1，模式指针回到 p1。 如果 j 0，则目标指针不变，模式指针回到 pnext j。,若设模式 P = p1 p2 pm-1 pm,示例 ：确定失效函