数据结构-合肥工业大学 5

NorthChinaElectricPowerUniversity第五章串第五章串5.1串的基本概念5.2串的基本操作5.3

串的存储结构NorthChinaElectricPowerUniversity5.4关于串的几个算法NorthChinaElectricPowerUniversity例如:

S1=〝abc

〞S2=〝FORTRAN_77〞

S3=〝

〞

=

(空串)S4=

〝

〞

由4个空格组成的空格串

串是由n0个字符组成的有限序列,通常记为

S=〝a1a2a3…an-1an〞

其中,S表示串名(也称串变量),一对引号括起来的字符序列称为串值,ai为串的元素，可以是字母、数字或其他允许的字符。n为串的长度（即串中字符的个数）,长度为0的串称为空串。一.串的定义

5.1

串的基本概念华电计算机系NorthChinaElectricPowerUniversity

1.串值须用一对引号括起来，但引号不属于串值。说明2.要区分空串与由空格字符组成的串的不同。例如：a=〝

beijing〞

其值为字符串序列beijing

。华电计算机系1.子串：串中若干个连续的字符组成的子序列。例如:S=〝Beijing&Shanghai〞

T=〝jing

〞2.主串:

包含子串的串。3.序号：(1).单个字符在主串中的位置

(2).子串在主串中的序号。定义为主串中首次出现的该子串的第一个字符在主串中的位置。被定义为该字符在串中的序号。例如:S=〝Beijing&Nanjing&Shanghai〞

T=〝jing

〞

位置为4二.几个名词概念华电计算机系

的充分必要条件为两个字符串的长度相等，4.两个字符串相等〝abcd

〞

〝

bacd

〞〝

abcd

〞=〝

abcd

〞并且对应位置上的字符相同。5.空格串:

仅由空格组成的串，串中空格字符的个数即为其长度，为了清楚起见，经常用符号Ф

来表示空格。空串：空串中无任何字符，记作s=〝〞，其长度为0。5.空格串:

仅由空格组成的串，串中空格字符的个数即为其长度，为了清楚起见，经常用符号Ф

来表示空格。华电计算机系NorthChinaElectricPowerUniversity

5.2

串的基本操作1.将串t的值赋给串s:String

Strassign(Strings,Stringt)2.判断两个串是否相等EQUAL(S1,S2).相等值为真，否则为假3.两个字符串连接CONCAT(S1,S2)把S2的值放到S1的后边如：a=〝bei

〞,b=〝jing

〞

Concat(a,b)=〝beijing

〞,Concat(b,a)=〝jingbei

〞4.求字符串的长度LEN(S)。5.求子串SUBSTR(S,i,k)表示从S串的第i个字符开始起数k个字符的子串。6.求子串在主串中的序号

INDEX(S1,S2)，求子串S2在主串S1中的位置。7.串的替换REPLACE(S,S1,S2)，把S中的子串S1用S2替换，如果S1不是S的子串，则S不变。例：a=〝Monday

〞,b=〝Mon

〞,c=〝Thurs

〞REPLACE(a,b,c)=〝Thursday

〞华电计算机系NorthChinaElectricPowerUniversity

1、求子串在主串中的序号运算（index(a,b,k)）思想：在a串从第k个字符起进行搜索看是否有和b相同的子串，若有则子串的第一个字符在a中的位置便是index(a,b)的结果，若无则结果为0。voidindex(a,b,k)//求b在a中的序号ind，从第k个字符开始，第一次k等于1{n=LEN(a);m=LEN(b);ind=0;if(n-k+1<m)return；//子串>主串时返回i=k;do{if(SUBSTR

(a,i,m)==b){ind=i;exit}elsei=i+1;}while(i>n-m+1)；}华电计算机系NorthChinaElectricPowerUniversity

2、置换运算（REPLACE(a,b,c)）思想：在a串中搜索和b串相同的子串，若有则以C串代替这个子串，在继续往下搜索，直到在a串中找不到和b相同的子串为止。VoidREPLACE(a,b,c)\\将a中的所有子串b置换为串c{n=LEN(a);m=LEN(b);s=LEN(c);if(n<m)return；p=1;Do{

index(a,b,p);

switch(ind){case0:break;case1:ifn==m{a=c;break}elsea=concat(c,Substr(a,m+1,n-m));华电计算机系NorthChinaElectricPowerUniversitycasen-m+1:{a=concat(sub(a,1,n-m),c);break}default:a=concat(sub(a,1,ind-1),c,sub(a,ind+m,n-ind-m+1));}//casen=n-m+s;p=ind+s;while(p>n-m+1)}华电计算机系NorthChinaElectricPowerUniversity1.非紧缩格式(设每个字有4个字节)例如:S=〝DATASTRUCTURE〞DASTRUCTATURE@DATASTRUCTURE@2.紧缩格式(按字编址）3.单字节方式(按字节编址）

5.3

串的存储结构一.串的顺序存储结构ATSATRUUTCDRE@华电计算机系(按字编址）顺序存储中三种方式比较显然紧缩格式节省空间，但在进行串运算时，需要花费较多的时间去分离同一个字中的字符，而非紧缩格式正相反。通常一个字节恰好存储一个字符的ASCII码，这就自然形成了一个字节存放一个字符的单字节存储格式，既节省空间，又处理方便。他们的共性就是空间利用率高，访问方便，但插入删除不方便，链表存储恰好弥补了这一不足。华电计算机系NorthChinaElectricPowerUniversity说明：所谓链结点大小是指每个链结点的数据域中存放的字符的个数。二.串的链式存储结构DATASTRRE

……S^结点大小为4的链表SDATE^……结点大小为1的链表华电计算机系当结点大小大于1时，一个串中最后结点不一定全部占满，我们一般补上空格符填满。我们用

来表示NorthChinaElectricPowerUniversity符号表包括:(1)串值的起始地址。(2)串值的末尾地址。确定末尾地址的方式有三种：

a、用串长来代替末尾地址。

b、串值末尾设结束符。

c、直接写末尾地址。(3)若字数不多可直接写串值本身。

我们用变量作各种运算，是通过对变量名的访问，而找到它的内容的，我们对串变量进行运算，也需要通过变量来找到它的内容，因此在内存中除了存储串值本身，另外在内存中需要设一个符号表。这种方式我们叫做串变量的存储映像。三、串变量的存储映像华电计算机系NorthChinaElectricPowerUniversity５.4

串的几个算法一.串的定义typedef

structstring{int

curlen;charch[1:maxlen];}二.串的连接华电计算机系假设r,s,t都是上面定义的string型变量，且r是s与t连接后得到的串，则连接运算concat(r,s,t)是将s与t的串值分别传送到r相应的位置上。NorthChinaElectricPowerUniversity1)s.curlen+t.curlen≤maxlen，这时得到的串r是连接所要求的正确结果；2)s.curlen+t.curlen>maxlen，需要将t的一部分截断，得到的串r只包含s和t的一个子串；3)s.curlen>maxlen，这时需要对s进行截断，得到的串r仅是

s的一个子串；voidconcat(string&r,&s,&t;bool&p);{if(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;}if((s.curlen+t.curlen>maxlen)&&(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;}华电计算机系NorthChinaElectricPowerUniversity

if(s.curlen>=maxlen){p=true;movch(r,s,1,1,maxlen);

r.curlen=maxlen;}

}voidmovch(int

t,s,i,j,num)//movch表示将位于s[j]起始的num个字符依次送到t[i]位置上

{for(k=0;k<=num-1;k++)

t[i+k]=s[j+k];}三.求子串的运算求子串的过程sub(r,s,fir,length)也是移动字符序列的过程，它将串s中从第fir位置开始的长度为length的子串赋给r。voidsub(r,s,fir,lenth);{if((fir+length-1>s.curlen)||(fir<1)||(length<0)){printf(“inproperlyspecifiedsubstringinsubproc”);exit;}else{movch(r,s,1,fir,length);r.curlen=length;}}华电计算机系NorthChinaElectricPowerUniversity四.求子串在串中的序号的运算（模式匹配）voidindex_bf(s,t,ind);{i=