第四章 串
4.1 串的基本概念
4.2 串的存储结构
4.2.1 串的顺序存储结构
4.2.2 串的链式存储结构
** 4.3 串的模式匹配启迪管理课程2
串 (String),是由 n个字符组成的有限序列。
记为,S=“a1a2a3…a n”（ n>=0)
4.1 串的基本概念
s是 串名,用双引号括起来的字符序列是串的值；
串中字符个数 n称为串的 长度；
长度为 0的串称为 空串,用 ф 表示；
串中任意个 连续 的字符组成的子序列称为该串的 子串； 如若 s1=“a2a3”就是 s的一个子串,s称为 s1的 主串 。
启迪管理课程3
判断题,如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）
S1=“I have a sweet dream!”
S1的串长 =
a在 S1中的位置为
21
4
注意区分,,,和,”
前者是长度为 1的空白串；后者是空串，长度为 0。
4.1 串的基本概念启迪管理课程4
(1)StrAssign(s,cstr),将一个字符串常量赋给串 s,即生成一个其值等于 cstr的串 s。如 StrAssign(s,“abc”),则
s=“abc”。
(2)StrCopy(s,t),串复制,将串 t 赋给串 s。
(3)StrEqual(s,t),判串相等,若两个串 s与 t相等则返回真；否则返回假。
串的基本运算如下,
相等的条件？
(4)StrLength(s),求串长,返回串 s中字符个数。
4.1 串的基本概念启迪管理课程5
(5)Concat(s,t); //串连接返回由两个串 s和 t连接在一起形成的新串。如 s=“xyz”
t=“abc”,则 Concat(s,t)=“xyzabc” 注意,Concat(s,t)!=
Concat(t,s)
(6)SubStr(s,i,j); //求子串返回串 s中从第 i (1≤i≤StrLength(s)) 个字符开始的、连续 j(0≤j≤StrLength(s)-i+1)个字符组成的子串。如
s=“abcde”,i=2,则 j的取值在 0～ 4。
4.1 串的基本概念启迪管理课程6
(7)InsStr(s1,i,s2); //将串 s2插入到串 s1的第
i(1≤i≤StrLength(s)+1)个字符中,即将 s2最为一个整体插入到 s1的第 i个字符中,并返回产生的新串。
(8)DelStr(s,i,j):从串 s中删去从第 i(1≤i≤StrLength(s))
个字符开始的长度为 j的子串,并返回产生的新串。
4.1 串的基本概念启迪管理课程7
(9)RepStr(s,i,j,t); //替换在串 s中,将第 i(1≤i≤StrLength(s))个字符开始的
j个字符构成的子串用串 t替换,并返回产生的新串。如 s=“bbabbabba”,i=7,j=3,t=“c”,结果为：
s=“bbabbac”
(10)DispStr(s); //串输出输出串 s的所有元素值。
4.1 串的基本概念启迪管理课程8
4.2 串的存储结构－－顺序串
4.2.1 串的顺序存储结构 ——顺序串
1001 A
1002 B
1003 C
1004 D
1005 E
1006 F
1007 G
1008 H
1009 I
100a J
1001 A B C D
1002 E F G H
1003 I J
紧缩格式 非紧缩格式顺序串,串中的字符被依次存放在一组连续的存储单元里。
根据每个存储单元中存放字符数的不同，串的顺序存储份紧缩格式和非紧缩格式两类顺序串。
启迪管理课程9
4.2 串的存储结构－－顺序串
o 非紧缩各式的顺序存储结构
typedef struct
{ char data[MaxSize]; //存放串的字符
int len; //当前串的长度
} SqString;
例,s=“I have a sweat dream!”
……!maerdtaewsaevahI
0 1 maxsize-1
len-1
启迪管理课程10
4.2 串的存储结构－－顺序串顺序串中实现串的基本运算如下,
1,StrAssign(s,cstr)
void StrAssign(SqString &s,char cstr[])
{ //将一个字符串常量 cstr赋给串 s.
int i;
for (i=0;cstr[i]!='\0';i++)
s.ch[i]=cstr[i];
s.len=i;
}
串常量怎样存放？
\0e……ca
启迪管理课程11
4.2 串的存储结构－－顺序串
2.StrCopy(s,t) 将串 t复制给串 s。
void StrCopy(SqString &s,SqString t)
e……cat
s
for (i=0;i<t.len;i++)
s.ch[i]=t.ch[i];
s.len=t.len;
启迪管理课程12
4.2 串的存储结构－－顺序串
3,StrEqual(s,t)
int StrEqual(SqString s,SqString t)
{
int same=1,i;
if (s.len!=t.len) same=0; /*长度不相等时返回 0*/
else
for (i=0;i<s.len;i++)
if (s.ch[i]!=t.ch[i]) //有一个对应字符不相同时返回 0
{ same=0;
break;
}
return same;
} 其他运算略启迪管理课程13
4.2 串的存储结构－－顺序串
例 (p125)：文本加密（字母映射法）。设映射关系为：
a b c d e f g h i j k l m n o p q r s t u v w x y z
n g z q t c o b m u h e l k p d a w x f y i v r s j
则字符串,encrypt”被加密为” tkzwsdf”。试编写一算法将输入的字符串进行加密。
设输入的字符串存放在串 S中，加密的结果存在串 R
中用串 A存放映射关系中的第一个串，用串 B存放第二个串启迪管理课程14
uomtaetacS
zy…q……….hgfedcbaA
js…a………bo ctqzgnB
fplxntxnzR
4.2 串的存储结构－－顺序串启迪管理课程15
Encode_String(SqString S,SqString A,SqString B,
SqString &R)
{ int i=0,j;
while(i<S.len)
{for(j=0;j<A.len,S.ch[i]!=A.ch[j];j++); //在 A中查找
if(j>=A.len) R.ch[i]=S.ch[i]; //不在 A中
else R.ch[i]=B.ch[j];
i++;
}
R.len=S.len;
}
4.2 串的存储结构－－顺序串启迪管理课程16
串的链式存储结构称为链串，其结构定义为：
typedef struct snode
{char data;
struct snode *next;
}LiString;
LiString *S;
例,(*S)=“dream”
d r e a ^mS
4.2 串的存储结构－－链串
4.2.2 串的链式存储结构 ——链串启迪管理课程17
改进存储结构：
typedef struct snode
{char data[4];
struct snode *next;
}LiString;
LiString *S;
例,s=“I have a dream!”
ahI aev
^###m
ae rdS
4.2 串的存储结构－－链串启迪管理课程18
小 结
串的定义及相关的概念
串的基本运算
串的存储结构
4.1 串的基本概念
4.2 串的存储结构
4.2.1 串的顺序存储结构
4.2.2 串的链式存储结构
** 4.3 串的模式匹配启迪管理课程2
串 (String),是由 n个字符组成的有限序列。
记为,S=“a1a2a3…a n”（ n>=0)
4.1 串的基本概念
s是 串名,用双引号括起来的字符序列是串的值；
串中字符个数 n称为串的 长度；
长度为 0的串称为 空串,用 ф 表示；
串中任意个 连续 的字符组成的子序列称为该串的 子串； 如若 s1=“a2a3”就是 s的一个子串,s称为 s1的 主串 。
启迪管理课程3
判断题,如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）
S1=“I have a sweet dream!”
S1的串长 =
a在 S1中的位置为
21
4
注意区分,,,和,”
前者是长度为 1的空白串；后者是空串，长度为 0。
4.1 串的基本概念启迪管理课程4
(1)StrAssign(s,cstr),将一个字符串常量赋给串 s,即生成一个其值等于 cstr的串 s。如 StrAssign(s,“abc”),则
s=“abc”。
(2)StrCopy(s,t),串复制,将串 t 赋给串 s。
(3)StrEqual(s,t),判串相等,若两个串 s与 t相等则返回真；否则返回假。
串的基本运算如下,
相等的条件？
(4)StrLength(s),求串长,返回串 s中字符个数。
4.1 串的基本概念启迪管理课程5
(5)Concat(s,t); //串连接返回由两个串 s和 t连接在一起形成的新串。如 s=“xyz”
t=“abc”,则 Concat(s,t)=“xyzabc” 注意,Concat(s,t)!=
Concat(t,s)
(6)SubStr(s,i,j); //求子串返回串 s中从第 i (1≤i≤StrLength(s)) 个字符开始的、连续 j(0≤j≤StrLength(s)-i+1)个字符组成的子串。如
s=“abcde”,i=2,则 j的取值在 0～ 4。
4.1 串的基本概念启迪管理课程6
(7)InsStr(s1,i,s2); //将串 s2插入到串 s1的第
i(1≤i≤StrLength(s)+1)个字符中,即将 s2最为一个整体插入到 s1的第 i个字符中,并返回产生的新串。
(8)DelStr(s,i,j):从串 s中删去从第 i(1≤i≤StrLength(s))
个字符开始的长度为 j的子串,并返回产生的新串。
4.1 串的基本概念启迪管理课程7
(9)RepStr(s,i,j,t); //替换在串 s中,将第 i(1≤i≤StrLength(s))个字符开始的
j个字符构成的子串用串 t替换,并返回产生的新串。如 s=“bbabbabba”,i=7,j=3,t=“c”,结果为：
s=“bbabbac”
(10)DispStr(s); //串输出输出串 s的所有元素值。
4.1 串的基本概念启迪管理课程8
4.2 串的存储结构－－顺序串
4.2.1 串的顺序存储结构 ——顺序串
1001 A
1002 B
1003 C
1004 D
1005 E
1006 F
1007 G
1008 H
1009 I
100a J
1001 A B C D
1002 E F G H
1003 I J
紧缩格式 非紧缩格式顺序串,串中的字符被依次存放在一组连续的存储单元里。
根据每个存储单元中存放字符数的不同，串的顺序存储份紧缩格式和非紧缩格式两类顺序串。
启迪管理课程9
4.2 串的存储结构－－顺序串
o 非紧缩各式的顺序存储结构
typedef struct
{ char data[MaxSize]; //存放串的字符
int len; //当前串的长度
} SqString;
例,s=“I have a sweat dream!”
……!maerdtaewsaevahI
0 1 maxsize-1
len-1
启迪管理课程10
4.2 串的存储结构－－顺序串顺序串中实现串的基本运算如下,
1,StrAssign(s,cstr)
void StrAssign(SqString &s,char cstr[])
{ //将一个字符串常量 cstr赋给串 s.
int i;
for (i=0;cstr[i]!='\0';i++)
s.ch[i]=cstr[i];
s.len=i;
}
串常量怎样存放？
\0e……ca
启迪管理课程11
4.2 串的存储结构－－顺序串
2.StrCopy(s,t) 将串 t复制给串 s。
void StrCopy(SqString &s,SqString t)
e……cat
s
for (i=0;i<t.len;i++)
s.ch[i]=t.ch[i];
s.len=t.len;
启迪管理课程12
4.2 串的存储结构－－顺序串
3,StrEqual(s,t)
int StrEqual(SqString s,SqString t)
{
int same=1,i;
if (s.len!=t.len) same=0; /*长度不相等时返回 0*/
else
for (i=0;i<s.len;i++)
if (s.ch[i]!=t.ch[i]) //有一个对应字符不相同时返回 0
{ same=0;
break;
}
return same;
} 其他运算略启迪管理课程13
4.2 串的存储结构－－顺序串
例 (p125)：文本加密（字母映射法）。设映射关系为：
a b c d e f g h i j k l m n o p q r s t u v w x y z
n g z q t c o b m u h e l k p d a w x f y i v r s j
则字符串,encrypt”被加密为” tkzwsdf”。试编写一算法将输入的字符串进行加密。
设输入的字符串存放在串 S中，加密的结果存在串 R
中用串 A存放映射关系中的第一个串，用串 B存放第二个串启迪管理课程14
uomtaetacS
zy…q……….hgfedcbaA
js…a………bo ctqzgnB
fplxntxnzR
4.2 串的存储结构－－顺序串启迪管理课程15
Encode_String(SqString S,SqString A,SqString B,
SqString &R)
{ int i=0,j;
while(i<S.len)
{for(j=0;j<A.len,S.ch[i]!=A.ch[j];j++); //在 A中查找
if(j>=A.len) R.ch[i]=S.ch[i]; //不在 A中
else R.ch[i]=B.ch[j];
i++;
}
R.len=S.len;
}
4.2 串的存储结构－－顺序串启迪管理课程16
串的链式存储结构称为链串，其结构定义为：
typedef struct snode
{char data;
struct snode *next;
}LiString;
LiString *S;
例,(*S)=“dream”
d r e a ^mS
4.2 串的存储结构－－链串
4.2.2 串的链式存储结构 ——链串启迪管理课程17
改进存储结构：
typedef struct snode
{char data[4];
struct snode *next;
}LiString;
LiString *S;
例,s=“I have a dream!”
ahI aev
^###m
ae rdS
4.2 串的存储结构－－链串启迪管理课程18
小 结
串的定义及相关的概念
串的基本运算
串的存储结构
