2001-3-26
华中科技大学计算机学院 (5)数据结构第四章，字符串 /串 (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)空格串 -----仅含空格字符 ’ ’ 的串。
例 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的值接到 s1的后面。
设 s1="data",s2="123"
执行,strcat(s1,s2)；
有,s1="data123",s2="123“
(4)strcmp(s1,s2)---比较 s1和 s2的大小若 s1<s2,返回负整数 如,"ABC"<"abc"
若 s1=s2,返回 0如,如,"abc"=="abc"
若 s1>s2,返回正整数 如,"ABCD">"ABC"
(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) 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 MAXSTRLEN 255 //用户可在 255以内定义最大长度
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放
//串的 长度
PASCAL,下标为 0的分量存放 串的实际 长度
0 1 2 255
C,在串值后加串结束标记 ‘ \0’,串长为隐含值
0 1 2 255
//...//\0321CBA
//...//321CBA6
1.顺序存储 ----用一维字符数组表示一个串的值。
例 1 char st1[80]=”ABC123”；
//...//\0321CBA
0 1 2 3 4 5 6,.,79
\0321CBA
0 1 2 3 4 5 6
例 2 char st2[]=”ABC123”；
0 1 2 3 4 5 6,.,19
例 3 char st[20]；
\0EDCBA
0 1 2 3
\0321
0 1 2 3 4 5
0 1 2 3 4 5 6 7 8 9 10 11
\0EDCBA321
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的最大长度：
(3) t的最大长度 <s1的长度：
\0EDCBA
0 1 2 3 4 5
0 1 2 3 4
\0DCBA
s1
t
截去
0 1 2 3
\0321s2
(2)s1的长度 ≤ t的最大长度 ≤ s1的长度 +s2的长度：
\0EDCBA
0 1 2 3
\0321
0 1 2 3 4 5
0 1 2 3 4 5 6
\0CBA321
s1 s2
t
截去
4.2.2 串的 堆分配存储表示例
{ char *ps1,*ps2； int len；
scanf(”%d”,&len)； //输入长度值
ps1=(char *)malloc(len)； //ps1指向分配的存储空间
gets(ps1)； puts(ps1)； //输入一个串，再输出
ps2=(char *)malloc(80)； //ps2指向分配的存储空间
strcpy(ps2;”abc123ok”) ； puts(ps2)； //赋值，再输出
free(ps1)； free(ps2)； //释放存储空间
}
0 1 2,......,len-1
ps1
k3 o \021cba
0 1 2,......,79
ps2
将串长作为存储结构的一部分：
typedef struct {
char *ch; //若是非空串，则按串长
//分配存储区，否则 ch为 NULL
int length; //串长度
} HString;
HString str;
ch
k3 o21cbalength 8
4.2.3串的单链表表示例 1 一个结点只放 1个字符
struct node1
{ char data； //为一个字符
struct node *next； //为指针
}*ps1；
A B C ^Dps1,ABCD”
存储密度 =串值所占存储位 /实际分配存储位存储密度为 0.33
例 2 一个结点放 4个字符
struct node4
{ char data[4]； //为 4个字符的串
struct node *next； //为指针
}*ps2；
^5\0ps2 BCD4123A,123ABCD45”
存储密度为 0.67
家庭作业：
1.试问空串和空格串有何区别？它们在程序设计中各有什么用途？分别举例说明之。
2.在 C语言中,字符和字符串的表示有何区别？分别举例说明之。
3.试问用单链表表示字符串时，一个结点放一个字符和一个结点放多个字符，各有什么优点和缺点？
上机作业：
1.输入一个字符串，再按与输入相反的次序输出。
2.输入两个字符串 s1,s2,联接为字符串 s3，分别输出
s1,s2,s3。要求不使用标准函数 strcat(s1,s2)。
华中科技大学计算机学院 (5)数据结构第四章，字符串 /串 (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)空格串 -----仅含空格字符 ’ ’ 的串。
例 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的值接到 s1的后面。
设 s1="data",s2="123"
执行,strcat(s1,s2)；
有,s1="data123",s2="123“
(4)strcmp(s1,s2)---比较 s1和 s2的大小若 s1<s2,返回负整数 如,"ABC"<"abc"
若 s1=s2,返回 0如,如,"abc"=="abc"
若 s1>s2,返回正整数 如,"ABCD">"ABC"
(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) 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 MAXSTRLEN 255 //用户可在 255以内定义最大长度
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放
//串的 长度
PASCAL,下标为 0的分量存放 串的实际 长度
0 1 2 255
C,在串值后加串结束标记 ‘ \0’,串长为隐含值
0 1 2 255
//...//\0321CBA
//...//321CBA6
1.顺序存储 ----用一维字符数组表示一个串的值。
例 1 char st1[80]=”ABC123”；
//...//\0321CBA
0 1 2 3 4 5 6,.,79
\0321CBA
0 1 2 3 4 5 6
例 2 char st2[]=”ABC123”；
0 1 2 3 4 5 6,.,19
例 3 char st[20]；
\0EDCBA
0 1 2 3
\0321
0 1 2 3 4 5
0 1 2 3 4 5 6 7 8 9 10 11
\0EDCBA321
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的最大长度：
(3) t的最大长度 <s1的长度：
\0EDCBA
0 1 2 3 4 5
0 1 2 3 4
\0DCBA
s1
t
截去
0 1 2 3
\0321s2
(2)s1的长度 ≤ t的最大长度 ≤ s1的长度 +s2的长度：
\0EDCBA
0 1 2 3
\0321
0 1 2 3 4 5
0 1 2 3 4 5 6
\0CBA321
s1 s2
t
截去
4.2.2 串的 堆分配存储表示例
{ char *ps1,*ps2； int len；
scanf(”%d”,&len)； //输入长度值
ps1=(char *)malloc(len)； //ps1指向分配的存储空间
gets(ps1)； puts(ps1)； //输入一个串，再输出
ps2=(char *)malloc(80)； //ps2指向分配的存储空间
strcpy(ps2;”abc123ok”) ； puts(ps2)； //赋值，再输出
free(ps1)； free(ps2)； //释放存储空间
}
0 1 2,......,len-1
ps1
k3 o \021cba
0 1 2,......,79
ps2
将串长作为存储结构的一部分：
typedef struct {
char *ch; //若是非空串，则按串长
//分配存储区，否则 ch为 NULL
int length; //串长度
} HString;
HString str;
ch
k3 o21cbalength 8
4.2.3串的单链表表示例 1 一个结点只放 1个字符
struct node1
{ char data； //为一个字符
struct node *next； //为指针
}*ps1；
A B C ^Dps1,ABCD”
存储密度 =串值所占存储位 /实际分配存储位存储密度为 0.33
例 2 一个结点放 4个字符
struct node4
{ char data[4]； //为 4个字符的串
struct node *next； //为指针
}*ps2；
^5\0ps2 BCD4123A,123ABCD45”
存储密度为 0.67
家庭作业：
1.试问空串和空格串有何区别？它们在程序设计中各有什么用途？分别举例说明之。
2.在 C语言中,字符和字符串的表示有何区别？分别举例说明之。
3.试问用单链表表示字符串时，一个结点放一个字符和一个结点放多个字符，各有什么优点和缺点？
上机作业：
1.输入一个字符串，再按与输入相反的次序输出。
2.输入两个字符串 s1,s2,联接为字符串 s3，分别输出
s1,s2,s3。要求不使用标准函数 strcat(s1,s2)。
