数据结构教学课件：第5讲串

1、字符串串类型的定义串的表示和实现模式匹配算法串操作应用举例 串类型的定义1、名词术语 串（String)(或字符串），是由零个或多个字符组成的有限序列。一般记做s=a1a2an(n=0)串的长度，串中字符的数目n。空串（Null string),零个字符的串，它的长度为零。子串，串中任意个连续的字符组成的子序列称为该串的子串。 你可以委婉地问你的GG：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”主串，包含子串的串。位置,字符在序列中的序号为该字符在串中的位置.例:4个串a=BEI,b=JING, c=BEIJING,d=BEI JING两个串相等,当且仅当这两个串的值相等

2、.空格串 (blank string,请注意此处不是空串），由一个或多个空格组成的串.空串,用” ”表示. 串的表示和实现 顺序存储表示 链存储表示顺序存储表示思想:用一组地址连续的存储单元存储串值的字符序列C语言表示:用一个字符数组存储一个串，c 语言中以0作为串的结束标志。串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称为“截断”。基本运算实现 1.串联接Concat（&T，S1，S2）S10S20S1S2TT0MAXSTRLEN( a ) S10+S20MAXSTRLENS10S20T0MAXSTRLEN( b ) S10MAXSTRLENT0MAXSTRLEN

3、( c ) S10=MAXSTRLENS2中被截去的部分S10S20S2串全部被截去S1S1S2S2TT算法实现Concat(SString &T,SString S1,SString S2) if (S10+S20=MAXSTRLEN) / 未截断 T1.S10=S11.S10; TS10+1.S10+S20=S21.S20; T0=S10+S20; uncut =TRUE;else if(S10MAXSTRLEN) / 截断 T1.S10=S11.S10; TS10+1.MAXSTRLEN=S21.MAXSTRLEN-S10; T0= MAXSTRLEN; uncut =FALSE;els

4、e / 截断(仅取S1) T0 .MAXSTRLEN= S10 .MAXSTRLEN; uncut =FALSE;return uncut;2.求子串SubString(&Sub,S,pos,len)初始条件：串S存在，1posStrLength(S)且 0lenStrLength(S)-pos+1 。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。算法思想： 求子串的过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。算法实现SubString(SString &Sub,SString S,int pos,int len)if(po

5、sS0 | lenS0-pos+1) return ERROR;Sub1.len=Spos.pos+len-1;Sub0=len;return OK; 链存储表示思想:链串的存储形式与一般的链表类似，是将存储区分成许多结点，每个结点有一个存放字符的域和一个存放指向下一个结点的指针域。链串中的一个存储结点可以存储1个或多个字符，通常将链串中每个存储结点所存储的字符个数称为结点大小。 w v u x y z # # head 结点大小为1的串的链表存储结构结点大小为4的串的链表存储结构串的链表存储方式w vu x y z headC语言表示： #define CHUNKSIZE 80 /可由用户定

6、义的块(结点)大小typedef struct Chuck char chCHUNKSIZE;struct Chuck *next;Chuck;typedef struct Chuck *head,*tail; /串的头和尾指针 int curlen; /串的当前长度LString; 串的模式匹配算法 求子串位置的定位函数Index(S,T,pos)子串定位操作通常称做串的模式匹配(其中T称为模式串),是各种串处理系统中最重要的操作之一.初始条件:串S和T存在,T非空,1=pos=StrLength(S)操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现

7、的位置;否则返回值0.算法演示:Index(S,T,1)a b a b c a b c a c b a b a b c a cSTi=1j=1第一趟匹配i=2j=2i=3j=3a b a b c a b c a c b a b a b c a cST第二趟匹配i=2j=1a b a b c a b c a c b a b a b c a cST第三趟匹配i=3j=1i=4j=2i=5j=3i=6j=4i=7j=5a b a b c a b c a c b a b a b c a cST第四趟匹配i=4j=1a b a b c a b c a c b a b a b c a cST第五趟匹配i=

8、5j=1a b a b c a b c a c b a b a b c a cST第六趟匹配i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos个字符之后的位置。/若不存在，返回值为0。/ 其中，T非空，1posStrLength(S) i=pos; j=1;while (i=s0&jT0) return i-T0;else return 0;)/Index 算法实现最难的一个算法KMP算法dsfdskjgldkjgjgrglsiggls“s”不匹配时，下一次比较应

9、该从哪里开始？有人提出“kj”根本与“模式”没关系看都不用看只需要从“g”开头的字符开始比较。可是，不比较你怎么知道没关系？反正要想个办法不要挨个比较，比如：0000000000000000000000000000000000001000001能不能把5个连续的0看做一个字符？经过研究，KMP算法提出一个与目标串无关的预处理算法！这样：模式=abcabcd序号=1234567假如“d”失配，意味着什么？意味着，“1”号字符a可以和“4”号字符对齐的那个字符比较！手工算一遍，感受一下：设模式串Pattern = a b c c a b c c a b c a Pattern 数组编号：0 1 2

10、 3 4 5 6 7 8 9 10 11假如失配该和谁比较？000001234567放在一个一位数组next中Next0=0Next7=3Next8=4假设next里面的值已经知道了，那么新的匹配过程：目标串中某处T.模式串中某处M.假如“T”=“M”,那么上下字符串指示比较的“指针”i+,j+假如失配：此时nextj=k那么，由于“M”之前有k个字符和模式串前k个字符相同而且也与目标串中字符“T”之前的k个字符相同，所以，此时要与“T”继续比较的应该是：?!这样的算法有什么意义呢？答：原来挨个比较时，i已经+了好远了，但是一旦失配i的值需要调整小。而kmp算法中，i永远向后走，速度当然快很多

11、。整个KMP算法就是依赖这个next数组的，这个next怎么求？假设已经知道了next1next4怎样推导出next5,next6 1 2 3 4 5 6 B = a b a b a c next = 0 0 1 2 ? ?因为next4=2，说明B1B2= B3B4，又因为B5=B3=Bnext4+1所以next5=next4+1=3可是B6!=Bnext5+1,所以B6不能简单地等于4既然B5=B3,而B6!=B4,那么会不会和BnextB3+1相等呢？结果是不相等，那就只能是0了。有个人解释是这样的（和教材不一样）一般教材上的说法是这样的：（很多人吐槽说根本看不懂）(1)nextj =

12、-1（j=0）；(2)nextj = Maxk|1kj且pj-kpj-k+1.pj-1=p0p1.pk-1（j!=0且集合有解）；(3)nextj = 0（j!=0且集合无解）；现在假设已知nextj=k，那么： “p0p1.pk-1” = “pj-kpj-k+1.pj-1”假如如果pj=pk 显然nextj+1=k+1=nextj+1由于next0=-1;所以似乎胜利在望了。译文：比如：已知next9=3p0p1p2 = p6p7p8假如如果p3 = p9那么next10=4 问题是p3 ！= p9，next10=?如果pj!=pk，将模式串向右滑动至k(k=nextkkj)位置，使得主串的

13、pj字符与模式串的pk字符比较。如果此时pj=pk(kk)，则有pj-kpj-k+1.pj-1pj=p0p1.pk-1pk，由next函数的定义该式等价于：nextj+1=k+1=nextk+1如果此时pj!=pk，则将模式串继续向右滑动，直至pj和模式串的某个字符pk_lucky匹配成功和的讨论说明，无论经过多少次滑动，只要主串的pj最终与模式串pk_lucky字符匹配成功，则主串字符指针(j+1)位置处的nextj+1一定可以由nextt(其中t=j)加1求得。尽管向右滑动，一直到j=nextt=-1，很不幸找不到k使得pj=pk，这相当于匹配过程中无解，此时由定义知nextj+1=0第一

14、次判断时k=-1,导致j=1,k=0,next1=0第二次判断时如果k!=-1,data1!=data0执行else,k=-1假如模式串=0000000001执行结果：初值：k=-1,j=0,next0=-1If成立导致：k=0,j=1,next1=0If成立导致：k=1,j=2,next2=1If成立导致：k=2,j=3,next3=2If成立导致：k=3,j=4,next4=3. k=7,j=8,next8=7 k=8,j=9,next9=8J=9结束假设模式串=000000000101，j=9还要执行将导致:由于k!=-1,data8!=data9执行else k=nextk=7.5,4,3,2,1,0,-1当k再次=-1时，执行if语句，导致k=0,j=10,next10=00123456789至此，我们终于明白，K和J是从头开始k为尾子串和j为尾的比较 01234567假设模式串=abcdabct程序执行