数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第五章 串
★ 串的基本概念
★ 串的基本操作
★ 串的存储结构
North China Electric Power University
★ 关于串的几个算法
★ 串的基本概念
North China Electric Power University
华电 计算机系例如,
S1= ′ abc ′
S2= ′ FORTRAN_77 ′
S3= ′′=? (空串 )
S4= ′ ′ 由 4个空格组成的空格串串是由 n?0个字符组成的有限序列,通常记为
S = ′ a1 a2 a3 … a n-1 an ′
其中,S表示串名 (也称串变量 ),一对引号括起来的字符序列称为串值,ai可以是字母、数字或其他允许的字符。 n 为串的长度,长度为 0的串称为空串。
一,串的定义
North China Electric Power University
华电计算机系
1,串值须用一对引号括起来，但引号不属于串值。
说明
2,要区分空串与由空格字符组成的串的不同。
String = ′ String ′
North China Electric Power University
华电 计算机系
1,子串,串中若干个连续的字符组成的子序列 。
例如,S= ′ Beijing&Shanghai ′
T= ′ jing ′
2,主串,包含子串的串 。
3,位置：
(2).子串在主串中的位置 被定义为该 字符在串中的序号。
例如,S= ′ Beijing&Nanjing&Shanghai ′
T= ′ jing ′
位置为 4
二,几个名词概念
(1),单个字符在主串中的位置 被定义为主串中首次出现的该子串的第一个字符在主串中的位置。
North China Electric Power University
华电 计算机系的充分必要条件为两个字符串的长度相等，并且对应位置上的字符相同。
4,两个字符串相等
′ abcd ′? ′ bacd ′
′ abcd ′ = ′ abcd ′
North China Electric Power University
华电 计算机系
6.2 串的基本操作
1.给串变量赋值 ASSIGN(S1,S2) strcpy(S2,S1)
2.判断两个串是否相等 EQUAL(S1,S2) strcmp(S1,S2)
3.两个字符串连接 CONCAT(S1,S2) strcat(S1,S2)
4.求字符串的长度 LEN(S) strlen(S)
5.求子串 SUBSTR(S,i,k)
6.求子串在主串中的位置 INDEX(S1,S2) strstr(S1,S2)
7.串的替换 REPLACE(S,S1,S2)
8.串的复制 COPY(S1,S2) strcpy(S2,S1)
9.串的插入 INSERTS(S1,i,S2)
C函数
North China Electric Power University
华电 计算机系
1,非紧缩格式 (设每个字有 4个字节 )
例如,S = ′ DATA STRUCTURE ′
D
A
S
T
R
U
C
T
A
T
U
R
E
@
D A T A
S T R
U C T U
R E@
2,紧缩格式
3,单字节方式
6.3 串的存储结构一,串的顺序存储结构
A T SA T R U UTCD R E @
North China Electric Power University
S
D A T E ^… …
说 明：
所谓链结点大小是指每个链结点的数据域中存放的字符的个数。
DATA STRU RE@@… …
S
^
二,串的链式存储结构结点大小为 4的链表结点大小为 1的链表
North China Electric Power University
6.4 串的几个算法一,串的定义
Type string=record
curlen:integer;
ch:array[1..maxlen] of char;
end;
二,串的连接假设 r,s,t都是上面定义的 string型变量，且 r是 s与 t连接后得到的串，则连接运算 concat(r,s,t)是将 s与 t的串值分别传送到 r相应的位置上。
North China Electric Power University
华电 计算机系
1) s.curlen+t.curlen≤ maxlen,这时得到的串 r是连接所要求的正确结果；
2) s.curlen+t.curlen>maxlen,需要将 t的一部分截断，得到的串 r只包含 s和 t的一个子串；
3) s.curlen>maxlen,这时需要对 s进行截断，得到的串 r仅是
s的一个子串；
Procedure concat(var r,s,t:string; var p:boolean);
Begin
case s.curlen+t.curlen<=maxlen:
[ p:=false;movch(r,s,1,1,s.curlen);
movch(r,t,s.curlen+1,1,t.curlen);
r.curlen:=s.curlen+t.curlen;]
s.curlen+t.curlen>maxlen and s.curlen<maxlen:
[ p:=true;movch(r,s,1,1,s.curlen);
movch(r,t,s.curlen+1,1,maxlen-s.curlen);
r.curlen:=maxlen;]
North China Electric Power University
s.curlen>=maxlen:
[ p:=true; movch(r,s,1,1,maxlen);
r.curlen:=maxlen;]
end case
End;
Procedure movch(t,s,i,j,num);
Begin
for k:=0 to num –1 do
t[i+k]:=s[j+k];
End;
三,求子串的运算求子串的过程 sub(r,s,fir,length)也是移动字符序列的过程，
它将串 s中从第 fir位置开始的长度为 length的子串赋给 r。
Procedure sub(r,s,fir,lenth);
Begin
if(fir+length-1>s.curlen) or (fir<1) or(length<0) then
[ write(‘inproperly specified substring in sub proc’); exit;]
else [movch(r,s,1,fir,length);r.curlen:=length;]
End;
North China Electric Power University
四,求子串在串中的序号的运算
Procedure index_bf(s,t,ind);
Begin
i:=1;j:=1;
repeat
if s.ch[i]=t.ch[j] then [i:=i+1;j:=j+1;]
else [i:=i+j-2;j:=1;]
until (i>s.curlen) or (j>t.curlen);
if j>t.curlen then ind:=i-t.curlen
else ind:=0;
End;
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第五章 串
★ 串的基本概念
★ 串的基本操作
★ 串的存储结构
North China Electric Power University
★ 关于串的几个算法
★ 串的基本概念
North China Electric Power University
华电 计算机系例如,
S1= ′ abc ′
S2= ′ FORTRAN_77 ′
S3= ′′=? (空串 )
S4= ′ ′ 由 4个空格组成的空格串串是由 n?0个字符组成的有限序列,通常记为
S = ′ a1 a2 a3 … a n-1 an ′
其中,S表示串名 (也称串变量 ),一对引号括起来的字符序列称为串值,ai可以是字母、数字或其他允许的字符。 n 为串的长度,长度为 0的串称为空串。
一,串的定义
North China Electric Power University
华电计算机系
1,串值须用一对引号括起来，但引号不属于串值。
说明
2,要区分空串与由空格字符组成的串的不同。
String = ′ String ′
North China Electric Power University
华电 计算机系
1,子串,串中若干个连续的字符组成的子序列 。
例如,S= ′ Beijing&Shanghai ′
T= ′ jing ′
2,主串,包含子串的串 。
3,位置：
(2).子串在主串中的位置 被定义为该 字符在串中的序号。
例如,S= ′ Beijing&Nanjing&Shanghai ′
T= ′ jing ′
位置为 4
二,几个名词概念
(1),单个字符在主串中的位置 被定义为主串中首次出现的该子串的第一个字符在主串中的位置。
North China Electric Power University
华电 计算机系的充分必要条件为两个字符串的长度相等，并且对应位置上的字符相同。
4,两个字符串相等
′ abcd ′? ′ bacd ′
′ abcd ′ = ′ abcd ′
North China Electric Power University
华电 计算机系
6.2 串的基本操作
1.给串变量赋值 ASSIGN(S1,S2) strcpy(S2,S1)
2.判断两个串是否相等 EQUAL(S1,S2) strcmp(S1,S2)
3.两个字符串连接 CONCAT(S1,S2) strcat(S1,S2)
4.求字符串的长度 LEN(S) strlen(S)
5.求子串 SUBSTR(S,i,k)
6.求子串在主串中的位置 INDEX(S1,S2) strstr(S1,S2)
7.串的替换 REPLACE(S,S1,S2)
8.串的复制 COPY(S1,S2) strcpy(S2,S1)
9.串的插入 INSERTS(S1,i,S2)
C函数
North China Electric Power University
华电 计算机系
1,非紧缩格式 (设每个字有 4个字节 )
例如,S = ′ DATA STRUCTURE ′
D
A
S
T
R
U
C
T
A
T
U
R
E
@
D A T A
S T R
U C T U
R E@
2,紧缩格式
3,单字节方式
6.3 串的存储结构一,串的顺序存储结构
A T SA T R U UTCD R E @
North China Electric Power University
S
D A T E ^… …
说 明：
所谓链结点大小是指每个链结点的数据域中存放的字符的个数。
DATA STRU RE@@… …
S
^
二,串的链式存储结构结点大小为 4的链表结点大小为 1的链表
North China Electric Power University
6.4 串的几个算法一,串的定义
Type string=record
curlen:integer;
ch:array[1..maxlen] of char;
end;
二,串的连接假设 r,s,t都是上面定义的 string型变量，且 r是 s与 t连接后得到的串，则连接运算 concat(r,s,t)是将 s与 t的串值分别传送到 r相应的位置上。
North China Electric Power University
华电 计算机系
1) s.curlen+t.curlen≤ maxlen,这时得到的串 r是连接所要求的正确结果；
2) s.curlen+t.curlen>maxlen,需要将 t的一部分截断，得到的串 r只包含 s和 t的一个子串；
3) s.curlen>maxlen,这时需要对 s进行截断，得到的串 r仅是
s的一个子串；
Procedure concat(var r,s,t:string; var p:boolean);
Begin
case s.curlen+t.curlen<=maxlen:
[ p:=false;movch(r,s,1,1,s.curlen);
movch(r,t,s.curlen+1,1,t.curlen);
r.curlen:=s.curlen+t.curlen;]
s.curlen+t.curlen>maxlen and s.curlen<maxlen:
[ p:=true;movch(r,s,1,1,s.curlen);
movch(r,t,s.curlen+1,1,maxlen-s.curlen);
r.curlen:=maxlen;]
North China Electric Power University
s.curlen>=maxlen:
[ p:=true; movch(r,s,1,1,maxlen);
r.curlen:=maxlen;]
end case
End;
Procedure movch(t,s,i,j,num);
Begin
for k:=0 to num –1 do
t[i+k]:=s[j+k];
End;
三,求子串的运算求子串的过程 sub(r,s,fir,length)也是移动字符序列的过程，
它将串 s中从第 fir位置开始的长度为 length的子串赋给 r。
Procedure sub(r,s,fir,lenth);
Begin
if(fir+length-1>s.curlen) or (fir<1) or(length<0) then
[ write(‘inproperly specified substring in sub proc’); exit;]
else [movch(r,s,1,fir,length);r.curlen:=length;]
End;
North China Electric Power University
四,求子串在串中的序号的运算
Procedure index_bf(s,t,ind);
Begin
i:=1;j:=1;
repeat
if s.ch[i]=t.ch[j] then [i:=i+1;j:=j+1;]
else [i:=i+j-2;j:=1;]
until (i>s.curlen) or (j>t.curlen);
if j>t.curlen then ind:=i-t.curlen
else ind:=0;
End;
North China Electric Power University
