第四章串.

算法与数据结构[e-mail]1第四章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例算法与数据结构算法与数据结构[e-mail]24.1串类型的定义一、串的基本概念二、串的基本操作算法与数据结构[e-mail]3一、串的基本概念串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串(String)是零个或多个字符组成的有限序列。算法与数据结构[e-mail]4子串与主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。子串的位置：通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。算法与数据结构[e-mail]5例如，设A和B分别为A=Thisisastring,B=is则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3特别地，空串是任意串的子串，任意串是其自身的子串。串的相等算法与数据结构[e-mail]6二、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算。定义下列几个变量：chars1[20]=dirtreeformat,chars2[20]=file.mem;chars3[30],*p;intresult;算法与数据结构[e-mail]7(1)求串长strlen(s);(2)串赋值或串拷贝(copy)strcpy(&to,from);(3)联接(concatenation)strcat(&to,from1,from2)(4)串比较（compare)strcmp(s1,s2);(5)求子串SubString(&Sub,S,pos,len)算法与数据结构[e-mail]84.2串的表示和实现一、顺序表示和实现二、链式表示和实现算法与数据结构[e-mail]9一、顺序表示和实现两种实现方式：1、定长顺序存储表示和实现直接使用定长的字符数组来定义#definemaxstrlen256typedefunsignedcharsstring[maxstrlen];sstrings;/*s是一个可容纳255个字符的顺序串*/算法与数据结构[e-mail]102、堆分配存储表示和实现其特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数malloc()和free()，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式：算法与数据结构[e-mail]11（1）typedefchar*string;/*c中的串库相当于此类型定义*/（2）typedefstruct{char*ch;/*若是非空串，则按串长分配存储区，否则ch为NULL*/intlength;//串长度}hstring;算法与数据结构[e-mail]12基本运算的实现：(1)求串的长度(2)串的清空(3)串的赋值(4)串的插入(5)串联接(6)求子串算法与数据结构[e-mail]13（4）串的插入为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制。statussubinsert(hstring&s,intpos,hstringt)//1≤pos≤StrLength(S)+1.在串S的第pos个字符之前插入串T.{if(pos1||poss.length+1)returnerror;//pos不合法if(t.length){//T非空，则重新分配空间，插入Tif(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)))算法与数据结构[e-mail]14returnerror;for(i=s.length-1;i=pos-1;--i)s.ch[i+t.length]=s.ch[i];//为插入T而腾出位置s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];//插入Ts.length+=t.length;}returnok;}算法与数据结构[e-mail]15（5）串的比较intstrcmp(hstrings,hstringt){for(i=0;is.length&&it.length;++i)if(s.ch[i]!=t.ch[i]return(s.ch[i]-t.ch[i]);return（s.length-t.length）;}（6）串联接算法与数据结构[e-mail]16statusstrcat(hstring&t,hstrings1,hstrings2){if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))exit(overflow);//将串s1存入t中t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;//求串长度t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];//将串s1存入t中returnok;}算法与数据结构[e-mail]17（7）求子串Statussubstr(hstring&sub,hstrings,intpos,intlen){if(pos1||poss.length||len0||lens.length-pos+1)//判断pos和len的合理性returnerror;if(sub.ch)free(sub.ch);//释放原空间if(!len){//子串为空串sub.ch=NULL;sub.length=0;}算法与数据结构[e-mail]18else{sub.ch=(char*)malloc(len*sizeof(char));if(!sub.ch)returnerror;sub.ch[0..len-1]=s[pos-1..pos+len-2];s.length=len;}}算法与数据结构[e-mail]19二、串的链式表示和实现链式存储结构简称为链串。最直接的链式存储结构是每个结点的数据域存放一个字符。strg^…stypedefstructnode{chardata;structnode*next;}Lstring;算法与数据结构[e-mail]20为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。算法与数据结构[e-mail]21#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}node;typedefstruct{node*head,*tail;intcurlen;}Lstring;算法与数据结构[e-mail]224.3串的模式匹配算法子串定位运算又称为模式匹配(PatternMatching)或串匹配(StringMatching)在串匹配中，一般将主串称为目标串,子串称之为模式串。位置i称为位移,当s[i..i+m-1]==t[0..m-1]时,i称为有效位移;当s[i..i+m-1]≠t[0..m-1]时，i称为无效位移。算法与数据结构[e-mail]231、简单算法模式匹配的最简单的做法是：用模式串T中的字符依次与主串S的字符比较：t1t2t3…tmS1S2S3…SmSn如果t1=s1，t2=s2,…，tm=sm则匹配成功。否则必有某个i(1im)，使得tj不等于si，这时可从主串s中与t1比较的字符的下一个字符起（将串t右移一个字符）再重新与模式串t中字符依次比较：S1S2S3…SmSm+1…Snt1t2t3…tm算法与数据结构[e-mail]24设S=“abbaba”，T=“aba”，用上述做法进行模式匹配的过程见下图：S：abbabaS:abbaba(a)T3S3S：abbabaT：aba(b)T1S2（c）T1S3(d)找到模式串T：abaS:abbabaT:abaT:aba算法与数据结构[e-mail]25(1)下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。intindex(sstrings,sstringt,intpos){//返回子串t在主串S中第pos个字符之后的位置。若不存在，则函数值为0。//其中，T非空，0≤pos≤strlen(S)。intn=s.length;//目标串的长度intm=t.length;//模式串的长度for(i=pos;i=n-m;i++){j=0;k=i;while(jm&&s.ch[k]==t.ch[j]{k++;j++;}if(j==m)returni;}return–1;}算法与数据结构[e-mail]26(2)链串上的子串定位算法用结点大小为1的单链表做串的存储结构时，实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。具体算法如下：Lstring*lindex(Lstrings,Lstringt){Lstring*shift,*q,*p;shift=S;//初始位移q=shift;p=t;while(q&&p){if(q-data==p-data){算法与数据结构[e-mail]27q=q-next;p=p-next;}else{shift=shift-next;q=shift;p=t;}}if(p==NULL)returnshift;elsereturnNULL;}例：p80算法与数据结构[e-mail]28下面分析它的时间复杂度，设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：例如：s=”aaaaaaaaaabc”，t=”bc”设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：即最好情况下的时间复杂度是O(n+m)。算法与数据结构[e-mail]29在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符：例如：s=”aaaaaaaaaaab”，t=”aaab”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。算法与数据结构[e-mail]302、模式匹配的改进算法改进算法是D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的