的 华中科技大学 计算机学院(5) 2001-3-26
2001-3-26 华中科技大学 数据结构 计算机学院(5)
第四章,字符串/串( str ing) 4.1串的定义与操作 1.术语 (1)串一由零个或多个字符组成的有限序列 n个字符C1,C2,,Cn组成的串记作: s=C1C2...C n>=0 其中:s为串名,C1C2.Cn为串值n为串长 例 PASCA语言 sl- datal234 s2=123*abc C语 s1=data1234″ s2="123*abc A为字符 "A"为字符串 %c为字符格式%s为字符串格式 (2)空串一不含字符的串/长度为零的串。 PASCA语言:s=2 C语言:
第四章，字符串/串(string) 4.1 串的定义与操作 1.术语 (1)串----由零个或多个字符组成的有限序列。 n个字符C1,C2,...,Cn组成的串记作： s='C1C2...Cn' n>=0 其中:s为串名， C1C2...Cn为串值 n为串长 例 PASCA语言: s1='data1234' s2='123*abc' C语言: s1="data1234" s2="123*abc" ’A’为字符 "A"为字符串 %c为字符格式 %s为字符串格式 (2)空串----不含字符的串/长度为零的串。 PASCA语言: s='' C语言: s=
(3)空格串-仅含空格字符’’的串。 例sl=Φ 2=Φd (4)子串一串s中任意个连续的字符组成的子序列称为串s的子串 主串一包含某个子串的串。 例st="ABC123A123CD" 1=ABC S3=123A S4=ABCA s2="ABC12 S5=ABCE S6=321CBA 2.串变量、字符变量的定义与使用 例1串变量 char st[=abc\*123 gets(st); scanf(%s", st) strcpy(st, data puts(st); printf( st=%s\n", st) 例2字符变量 char ch=a ch='B,; ch=getchar o scanf(%c,&ch); printf( ch=%c\n",ch
(3)空格串-----仅含空格字符’ ’的串。 例 s1='' s2='' s1=' ' s2=' ' (4)子串---串s中任意个连续的字符组成的子序列称为串s的子串。 主串---包含某个子串的串。 例 st="ABC123A123CD" s1="ABC" s3="123A" s4="ABCA" s2="ABC12" s5="ABCE" s6="321CBA" 2.串变量、字符变量的定义与使用 例1 串变量 char st[]="abc\'*123"； gets(st)； scanf("%s",st)； strcpy(st,"data")； puts(st)； printf("st=%s\n",st)； 例2 字符变量 char ch='A'； ch=’B’ ； ch=getchar()； scanf("%c",&ch)； printf("ch=%c\n",ch)；
3.串的基本操作与串函数 (1) strcpy(t,s)--s的串值复制到t中。 执行: strcpy(t,"data");有:t="data" (2) strlen(s)-求s的长度 strlen( data*123)=8 strlen()=0 (3) strcat(s1,s2)-s2的值接到sl1的后面。 设执有 s1="data",s2="123′ 行: strcat(s1,s2); s1="data123″,s2="123 (4) strcmp(s1,s2)-比较s1和s2的大小 若s1s2,返回正整数如:"ABCD">"ABC
3.串的基本操作与串函数 (1)strcpy(t,s)---s的串值复制到t中。 执行：strcpy(t,"data")； 有：t="data" (2)strlen(s)----求s的长度 strlen("data*123")=8 strlen("")=0 (3)strcat(s1,s2)----s2的值接到s1的后面。 设 s1="data" ， s2="123" 执行：strcat(s1,s2)； 有： s1="data123" ， s2="123“ (4)strcmp(s1,s2)---比较s1和s2的大小 若s1s2,返回正整数 如："ABCD">"ABC
(5) strstr(s1,s2)—若s2是s1的子串,则指向s2在s1中第1 次出现时的第1个字符的位置,即序号值;否则返回NULL。 i s1="ABE123*DE123bcd s2="E123″ 有 strstr(s1,s2)=3 s1="ABE123DE123″ (6) Replace(s,t,v)-置换 用v代替主串s中出现的所有与t相等的不重叠的子串 i s=abc123abc*abC, t=abc", v=OK 执行: Replace(s,t,V); 有:s="0K1230K*ABC",t=”abC?,v="O爪" ix a="abcaaaaaabC, b="aa, c=aaOK 执行: Replace(A,B,C); A: A=abcaaOKaaOKaABC b="aa",c=aaOK
(5) strstr(s1,s2)----若s2是s1的子串，则指向s2在s1中第1 次出现时的第1个字符的位置,即序号值；否则返回NULL。 设 s1="ABE123*DE123bcd" s2="E123" 有 strstr(s1,s2)=3 s1="ABE123*DE123" ↑ (6)Replace(s,t,v)----置换 用v代替主串s中出现的所有与t相等的不重叠的子串 设 s="abc123abc*ABC", t="abc", v="OK" 执行：Replace(s,t,v)； 有： s="OK123OK*ABC", t=”abc”, v="OK" 设 A="abcaaaaaABC", B="aa", C="aaOK" 执行：Replace(A,B,C)； 有： A="abcaaOKaaOKaABC", B="aa", C="aaOK
(7) Strlnsert(s,pot,t)-将t插入s中第pot个字符之前 设s=ABC123″ 执行: Strinsert(s,4,"*") 有:S="ABC*123 (8)用 Replace(s,t,v)实现删除 设s="ABC//123″ 执行: Strlnsert(s,"/",") 有:s="ABC123″ (9)用 Replace(s,t,v)实现插入 设s="ABC123 执行: Strlnsert(s,"123","*123") 有:S="ABC*123
(7) StrInsert(s,pot,t)----将t插入s中第pot个字符之前。 设 s="ABC123" 执行: StrInsert(s,4,"**")； 有: s="ABC**123" (8)用Replace(s,t,v)实现删除 设 s="ABC//123" 执行：StrInsert(s,"//","") 有： s="ABC123" (9)用Replace(s,t,v)实现插入 设 s="ABC123" 执行：StrInsert(s,"123","**123") 有： s="ABC**123
4.2串的存储表示和实现 4.2.1串的定长顺序存储表示 给每个定义的串分配一个固定长度的存储区 # define MaXstrlen255/用户可在255以内定义最大长度 typedef unsigned char Sstring[ MAXSTRLEN1];//0号单元存放 //串的长度 PASCAL:下标为0的分量存放串的实际长度 6ABc|123 /.. 012 255 在串值后加串结束标记“\0°,串长为隐含值 AB c 1230//1../
4.2 串的存储表示和实现 4.2.1 串的定长顺序存储表示 给每个定义的串分配一个固定长度的存储区 #define MAXSTRLEN 255 //用户可在255以内定义最大长度 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放 //串的长度 PASCAL: 下标为0的分量存放串的实际长度 0 1 2 255 C: 在串值后加串结束标记‘\0’ ,串长为隐含值 0 1 2 255 A B C 1 2 3 \0 // ... // 6 A B C 1 2 3 // ... //
1.顺序存储一用一维字符数组表示一个串的值。 例1 char stl[80]=ABC123”; ABc123/4.: 例2 char st2[=”ABC123”; ABC123\ 0123456 例3 char st[20] 0123456..19
1.顺序存储----用一维字符数组表示一个串的值。 例1 char st1[80]=”ABC123” ； A B C 1 2 3 \0 // ... // 0 1 2 3 4 5 6 ... 79 A B C 1 2 3 \0 0 1 2 3 4 5 6 例2 char st2[]=”ABC123” ； 0 1 2 3 4 5 6 ... 19 例3 char st[20]；
2.串运算实现举例 例联接运算:给定串s1,s2,将s1,s2联接为串t,记作: Concat(t, s1, s2) 设s1=123,s2=” ABCDE” 执行: Concat(t,sl,s2); 有 t=”123 ABCDE 实现 Concat(t,sl,s2)的方法: (1)s1的长度+s2的长度≤t的最大长度: S B CDE\ 2345 T3 A BCDE 0 01234567891011
A B C D E \0 0 1 2 3 1 2 3 \0 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 1 2 3 A B C D E \0 s1 s2 t 2.串运算实现举例 例 联接运算: 给定串s1,s2,将s1,s2联接为串t,记作： Concat(t,s1,s2) 设 s1=”123”, s2=”ABCDE” 执行： Concat(t,s1,s2)； 有： t=”123ABCDE” 实现Concat(t,s1,s2)的方法： (1)s1的长度+s2的长度≤t的最大长度：
(2)s1的长度≤t的最大长度≤s1的长度+s2的长度: sI[[ 0 s2A Bc D E o 0121345 截去 I2 BCO (3)t的最大长度<s1的长度: S1A BC D EI\O 21230 截去 t A B CDO
(3) t的最大长度<s1的长度： A B C D E \0 0 1 2 3 4 5 0 1 2 3 4 A B C D \0 s1 t 截去 0 1 2 3 s2 1 2 3 \0 (2)s1的长度≤t的最大长度≤s1的长度+s2的长度： A B C D E \0 0 1 2 3 1 2 3 \0 0 1 2 3 4 5 0 1 2 3 4 5 6 1 2 3 A B C \0 s1 s2 t 截去