大学数据结构课件-第4章串

1

4.1串类型的定义

4.2串的表示和实现

4.3串的模式匹配算法第4章串2串（字符串）是由零个或多个字符组成的有限序列，记为：S=

‘a1a2……an-1an’

（n≥0）串的长度：串中字符的个数；零个字符的串称为空串，记为串名串值（单引号内的部分，但‘’不属于串）串的相关术语空格串：由一个或多个空格组成的串，其长度为串中空格字符的个数子串：串s中任意个连续的字符组成的子序列称为该串的子串，包含子串的串s相应地称为主串。子串位置：字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置以第一个字符在主串中的位置来表示。串相等：两个串相等，当且仅当这两个串的值相等。即，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。4.1

串类型的定义3例：现有以下4个字符串‘’

a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEI□JING’问：①4个字符串的的长度分别是多少？

②

b是哪个串的子串？其在主串的位置是多少？

③串c是不是串d的子串，为什么？4.1串类型的定义4StrAssign(&T,chars);//串赋值，生成一个值等于chars的串TStrCompare(S,T);//串比较，若S>T，返回值>0……StrLength(S);//求串长Concat(&T,S1,S2);//串连接，用T返回S1+S2的新串SubString(&Sub,S,pos,len);//求S中pos位置起长度为len的子串……Index(S,T,pos);//返回子串T在主串S中pos字符之后首次出现的位置Replace(&S,T,V);//用子串V代替串S中所有的子串TADTstring{}string数据对象:数据关系:数据操作:串的抽象数据类型定义4.1串类型的定义5例：s=‘I□AM□A□STUDENT’,t=‘GOOD’,q=‘WORKER’求：StrLength(s)=StrLength(t)=SubString(s,8,7)=SubString(t,2,1)=Index(s,’A’)=Index(s,t)=Replace(s,’STUDENT’,q)=Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))=4.1串类型的定义6定长顺序存储表示堆分配存储表示串的块链存储表示顺序存储链式存储4.2串的表示和实现7用一组地址连续的存储单元存储串值的字符序列。一、定长顺序存储表示#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];按照予定义的大小，为每个定义的串变量分配一个固定长度的存储区，可用定长数组描述。注意：①用SString[0]来存放串长信息；

②串值后面加一个不计入串长度的标识符‘\0’；

③串的实际长度可在予定义长度的范围内随意,超过予定义长度的串值则被舍去，称为“截断”。4.2串的表示和实现8例：用顺序存储方式实现求子串函数SubString(&Sub,s,pos,len)将串S中从第pos个字符开始长度为len的字符序列复制到Sub中（注：串Sub的预留长度与S一样）StatusSubString(SString&Sub,SStrings,intpos,intlen)S=‘a1a2……an-1an’poslenS[pos…pos+len-1]=Sub[1…len]Sub[0]=len;{}RetrunOK:If(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)Returnerror;想存放超长字符串怎么办？改用动态分配的一维数组4.2串的表示和实现9仍以一组地址连续的存储单元存放串值字符序列，但存储空间是在程序执行过程中动态分配而得二、堆分配存储表示malloc()合理预设串长空间；若串长改变，使用realloc()按新串长度增加空间Typedefstruct{char*ch;intlength;}HString;//若非空串，按串长分配空间；否则ch=NULL//串长度4.2串的表示和实现10例：用堆分配存储方式实现串插入操作(参见教材P75)

StatusStrInsert(HString&S,intpos,HStringT){//在串S的第pos个字符之前（包括尾部）插入串T}//StrInsertif(pos<1||pos>S.length+1)ReturnERROR;//pos不合法则警告if(T.length){//只要串T不空，就需要重新分配S空间，以便插入T

}returnOK;if(!(S.ch=(char)*realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);//若开不了新空间，则退出for(i=S.length-1;i>=pos-1;--i)//为插入T而腾出pos之后的位置，即从S的pos位置起全部字符均后移

S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入TS.length+=T.length;//刷新S串长度4.2串的表示和实现11三、串的块链存储表示headABI^C…例：S=‘ABCDEFGHI’①

链表结点大小为1②

链表结点大小为4^headABCDEFGHI###法1存储密度为1/2；法2存储密度为9/15=3/5存储密度=串值所占的存储位实际分配的存储位4.2串的表示和实现12模式匹配：即子串定位运算（Index函数）算法目的：确定主串中所含子串第一次出现的位置（定位）

——即如何实现Index(S,T,pos)函数初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(s)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0注：串S称为被匹配的串，T称为模式串。若S包含T，则称

“匹配成功”，否则称“匹配不成功”。4.3串的模式匹配算法13①基本设计思想：

将主串的第pos个字符和模式的第1个字符比较，(pos=1)

若相等，继续比较后续字符;

若不等，从主串的下一字符（pos+1）起，重新与第1个字符比较直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第1个字符的序号，即匹配成功，否则匹配失败，返回值04.3串的模式匹配算法14主串S=‘ababcabcacbab’，模式串T=‘abcac’第1趟匹配：ababcabcacbab

abc

第2趟匹配：ababcabcacbab

a

第3趟匹配：ababcabcacbab

abcac第4趟匹配：ababcabcacbab

a第5趟匹配：ababcabcacbab

a第6趟匹配：ababcabcacbab

abcac能否利用已部分匹配过的信息而加快模式串的滑动速度？KMP算法4.3串的模式匹配算法15当主串S中第i个字符与模式串P中第j个字符“失配”时(Si≠Pj)，主串中第i个字母应与模式中哪个字符再比较呢？假设此时与模式串中第k个字符继续比较，则模式串P中前k-1个字符的子串必满足下列的关系（1<K<j）

‘P1P2…Pk-1’=‘Si-k+1Si-k+2…Si-1’而得到的部分匹配的结果是（Si和Pj失配时的结果）

‘P1P2…Pj-1’=‘Si-j+1Si-j+2…Si-1’两式联立可得：‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’结论：K的选择与主串无关，只与模式串的结构有关。同理可得：‘Pj-k+1Pj-k+2…Pj-1’=‘Si-k+1Si-k+2…Si-1’已知：主串S1S2…Si…Sm

子串P1P2…Pk…Pj…Pn4.3串的模式匹配算法16

j12345tabcacnext[j]根据‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’，求next[j]第1趟匹配：ababcabcacbab

abc第2趟匹配：ababcabcacbab

abcac第3趟匹配：ababcabcacbab

abcac改进的主串S=‘ababcabcacbab’和子串T=‘abcac’的匹配过程01112令next[j]=k=0j=1Max{k|1<k<j且‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’

}1其它4.3串的模式匹配算法17令next[j]=k，根据‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’，求j12345678910111213141516模式串abcdabcdabcdaabcnext[j]01111234567891023Nextval[j]

011101110111010114.3串的模式匹配算法18Nextval[j]0000006第1趟匹配：aaaaabaaaaaaab

aaaaaa第2趟匹配：aaaaabaaaaaaab

aaaa

a第3趟匹配：aaaaabaaaaaaab

aaa

a

j1234567模式串

aaaaaabnext[j]0123456第4趟匹配：aaaaabaaaaaaab

aa

a

第5趟匹配：aaaaabaaaaaaab

a

a

第6趟匹配：aaaaabaaaaaaab

a

第7趟匹配：aaaaabaaaaaaab

aaaaaa

b

第1趟匹配：aaaaabaaaaaaab

aaaaaa第2趟匹配：aaaaabaaaaaaab

aaaaaab第3趟匹配：aaaaabaaaaaaab

aaaaaab4.3串的模式匹配算法19设主串S=‘S1S2……Sm’

子串P=‘P1P2……Pn’当Si和Pj不相等（失配）时，求出next[j]=K，表示下一次比较时让Si和Pk相比较。如果Pk和Pj相等，Si和Pk肯定不相等，所以，必然需要再继续比较下去，即next[j]的值需要修正。如果Pk和Pj不相等，则Si和Pk有可能相等，有比较的必要，即next[j]的值不需要修正。再下一次比较的时候，是判断Pk所对应的next[j]所代表的字符是否与Pk相等，即Pk是否等于Pnext[k]，如果相等则继续比较，否则即可得到next[j]的修正值。4.3串的模式匹配算法201、试问执行以下函数会产生怎样的输出结果？voiddemonstrate(){StrAssign(s,‘THISISABOOK’);Replace(s,SubString(s,3,7),‘ESEARE’);StrAssign(t,Conca