数据结构课件数据结构课件串

第四章

串串类型的定义串的表示和实现串的模式匹配算法串操作应用举例14.1.1串的逻辑结构定义串——是由零个或多个字符组成的有限序列。一般记为：S=‘a1a2…an’长度——串中字符的(n数>=目0)。空串——零个字符的串，用符号φ来表示空串。子串——串中任意个连续的字符组成的子序列。主串——包含子串的串。位置——字符在序列中的序号为该字符在串中的位置例：a=‘bei’

b=‘jing’c=‘beijing’d=‘bei

jing’则：a,b,c,d的长度分别为：3、4、7、8。a、b是c和d的子串。a在c和d中的位置都是1。b在c中的位置是4，在d中的位置是52相等——当两个串的长度相等，并且各个对应位置的字符都相等，则称两个串是相等的。空格串——由一个或多个空格组成的串称为空格串。注意：串值必须用一对单引号括起来，但单引号本身不属于串。例：

x=‘123’;

x=123;

tsing=‘tsing’3串的抽象数据类型的定义：

ADT

String{数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>数据关系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：StrAssign(&T,chars)chars是字符常量。生成一个其值等于chars的串T。StrCopy(&T,S)串S存在则由串S复制得串TStrEmpty(S)串S存在则若S为空串,返回真否则返回假StrCompare(S,T)串S和T存在,若S>T,则返回值>0,若S=T,则返回值=0,若S<T,则返回值<04StrLength(S)串S存在返回S的元素个数称为串的长度.ClearString(&S)串S存在将S清为空串Concat(&T,S1,S2)串S1和S2存在用T返回由S1和S2联接而成的新串SubString(&Sub,S,pos,len)串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1用Sub返回串S的第pos个字符起长度为len的子串Index(S,T,pos)串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0Replace(&S,T,V)串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串5StrInsert(&S,pos,T)串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos字符起长度为len的子串DestroyString(&S)串S存在,则串S被销毁}ADT

String6例子：设：s,t,v,a,b,c,d都为串名。a=‘bei’

b=‘jing’c=‘

’(1)dS=t‘rabsesijgin(g&’s,ss)和strcopy(&s,t)赋值操作。例：

strassign(s,‘abcd’)

S=‘

abcd’例：strcopy(s,d)S=‘beijing’返回值<0返回值=0(2)strcompare(s,t)

判等函数。例：strcompare(a,b)strcompare(φ,φ)(3)strlength(s)

求长函数7(4)concat(&t,s1,s2)联接函数。例

S1=‘S1S2…Sm’则:

concat(t,s1,s2)concat(t,s2,s1)s2=‘t1t2…tn’t=‘S1S2…Smt1t2…tn’t=‘t1t2…tnS1S2…Sm’(5)substring(&sub,s,pos,len)

求子串函数。if

1≦pos≦length(s)且0≦len≦length(s)-pos+1用sub返回从串s中第pos个字符起，长度为len的字符序列else

返回error例：substring(sub,d,1,3S)ub=‘bei’Substring(sub,d,4,0)sub=φ8(6)index(s,t,pos)

定位函数。if

在主串S中的第pos个位置之后存在和t相等的子串返回S中第一个这样的子串在主串S中的位置。例：设

s=‘bbabbabba’

t=‘ab’v=‘c’则

replace(s,t,v)

s=‘bbcbcba’else

返回零例：index(d,b,1)=4index(d,c,1)=0index(d,b,5)=(7)replace(&s,t,v)

置换函数。以串v替换所有出现的和非空串t相等的不重叠的子串例：

replace(d,b,c)

d=‘bei

’9(8)strsert(&s,pos,t)

插入操作。elseif

1≦pos≦length(s)+1在串S的第pos个字符之前插入串t。返回error例：

strinsert(a,4,b)

a=‘beijing’(9)strdelete(&s,pos,len)

删除操作。if

1≦pos≦length(s)-len+1从串S中删除第pos个字符起长度为len的子串。else

返回error例：

strdelete(a,4,4)

a=‘bei’基本操作：strassign、strcompare、strlength、concat、substring10定位函数

index(s,t,pos)的算法实现：算法分析：S=‘abdgjgutabcdhhuac’

t=‘abc’Int

index

(string

s,string

t,int

pos)

{if

(pos>0)

{n=strlength(s);

m=strlength(t);

i=pos;while

(i<=n)

{substrimg(sub,S,i,m);if

(strcompare(sub,t)!=0)

++i;else

return

i;

}}return

0;}11作业：1.用5种串的基本操作（strassignsstrcomparesstrlengthssubstring）来逻辑实现strinsert(&s,pos,t)操作.Status

strinsert(string

s,int

pos

,string

t){

if

………..

Return

error;}(1)Substring(sub1,s,(2)substring(sub2,s,,,););concat(

s1,

,

);concat(s,

,

);return

ok;124.2串的表示和实现4.2.1定长顺序存储表示类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.用定长数组表示：

#define

MAXSTRLEN

255typedef

unsigned

char

SString[MAXSTRLEN+1]//0号单元存放串长13串长可用下标为0的数组元素存储,也可在串值后设特殊标记a[0]

a[1]a[2]a[3]a[4]a[5]

...a[n]pascalcba3c\0cba141.串联接的实现Concat(&T,S1,S2)假设S1,S2和T都是SString型的串变量,且串T是由串

S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的"

串值复制"操作即可,对超长部分实施"截断"操作串可能有三种情况：（1）S1,S2串长和<=最大值S1S2T426adabebccddef15S1S2T668agabhbcicdjdekeflfgh(2)S1串长<最大串长;

S1,S2串长和>最大串长;(3)S1串长已=最大串长;TS2S1828aiabjbccddeeffgghh16算法描述如下:Status

Concat(SString

&T,SString

S1,SString

S2){if

(S1[0]+S2[0]<=MAXSTRLEN){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0

]；uncut=TRUE;}else

if

(S1[0]<MAXSTRSIZE){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;

uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}172.求子串substring(&sub,S,pos,len)if

1≦pos≦length(s)且0≦len≦length(s)-pos+1用sub返回从串s中第pos个字符起，长度为len的字符序列else

返回errorStatus

substring(sstring

&sub,sstring

s,int

pos,if (pos<1||

pos>s[0]

||

len<0||

len>s[0]-pos+1)return

error;sub[1..len]=s[pos..pos+len-1];sub[0]=len;}18※4.2.2堆分配存储表示这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得。在C语言中,存在一个称之为堆的自存储区,并由C语言的动态分配函数malloc()和free()来利用函数malloc()为每个新产生的串分配一块实际串长需存储空间,为处理方便,约定串长也作为存储结构的一部分堆分配的存储表示：typedef

struct{char

*ch;int

length;}HString；19ADT

string的堆分配存储的表示和实现：堆分配存储的表示；基本操作的函数原型说明；基本操作的算法描述；P76～77204.2.3串的块链存储表示例:

s=‘abcdefghi’i

#

#

#

^heada

b

c

de

f

g

hheadabc…

i

^为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表的最后一个结点并给出当前串的长度，称如此定义的串存储结构为块链结构。21块链结构串的C表示：#define

CHUKSIZE

80Typedef

struct

chunk

{char

ch[CHUKSIZE];*next;struct

chunk}chunk;Typedef

struct

{chunk

*head,*tail;Int

curlen;}Lstring;a

bc

d例：

Lstring

S;s.heads.tails.curlen

5e

#

^22串块链结构结点大小的选择依据：存储密度=串值所占的存储位实际分配的存储位heada

b

c

de

f

g

hheadabc…i

#

#

#

^i

^例：存储密度=915=35存储密度=918=12234.3串的模式匹配算法定位函数

index(s,t,pos)的算法实现：算法分析：S=‘abdgjgutabcdhhuac’

t=‘abc’Int

index

(string

s,string

t,int

pos)

{if

(pos>0)

{n=strlength(s);

m=strlength(t);

i=pos;while

(i<=n-m+1)

{substrimg(sub,S,i,m);if

(strcompare(sub,t)!=0)

++i;else

return

i;

}}return

0;}要求：采用SString结构，24算法分析:

S=‘abdgagutabcdhhuac’

t=‘abc’用i和j分别指示主串s和模式t中当前正待比较的字位置,从主串s的第pos字符起和模式t的第一个字符比较若相等,则继续逐个比较后续字符,否则从主串的下一个符起再重新和模式的字符比较之。依次类推,直至模式匹配成功或匹配不成功.一级算法:i=pos;

j=1;while

(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

继续比较后继字符;else

重新开始匹配；25二级算法：{i=i-j+1+1;;j=1;}i=pos;whilej=1;(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

继续比较后继字符;else

重新开始匹配；{++i;

++j;

}i=pos;

j=1;while

(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

{++i; ++j;

}else

{i=i-j+2;

j=1;}26if

j>t[0]else返回t在s的位置值

return(0);return(

i-t[0]);三级算法：i=pos;

j=1;while

(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

{++i; ++j;

}else

{i=i-j+2;j=1;}返回t在s的位置值或零；27Index(s,t,pos)的算法实现演：示Int

index

(sstring

s,sstring

t,int

pos)

{i=pos;

j=1;while

(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

{++i; ++j;

}else

{i=i-j+2;

j=1;}if

j>t[0]

return(

i-t[0]);else

return(0);}28i=3第二趟匹配：abtabcdhhuaci=2第三趟匹配：abtabcdhhuaci=3第四趟匹配：abtabcdhhuacabcj=3abcj=1abcj=1abc例：S=‘abtabcdhhuac’

t=‘abc’index(s,t,1)的匹配过程i：=1,j=1第一趟匹配：abtabcdhhuaci=4

i=7j=1

j=429串操作应用举例文本编辑文本编辑——修改字符数据的形式或格式，包括串的查找、插入、删除等基本操作。文本编辑可以用于源程序的输入和修改（如图一）:图一30用于报刊和书籍的编辑排版以及办公室的公文书信的起和润色（如图二）：图二31在进行文本编辑时，我们把整个文本看成是一个字符串，称为文串，页则是文本串的子串，行又是页的子串。例如有下列一段源