算法与数据结构 C语言版 第二版 陈守孔 第4章.ppt

1、第 4 章 串,本章目录,4.1串类型的定义 4.2串的表示和实现 4.2.1 串的顺序存储结构 4.2.2 串的链式存储结构 4.3 串的模式匹配 4.3.1 朴素的模式匹配算法 4.3.2 首尾匹配算法 4.3.3 KMP算法 4.4 串的应用举例 4.5 算法设计举例,知识点和难点重点,知识点 基本概念 串操作 模式匹配 难点重点 根据给定操作，编写其它操作的算法 (如，根据前5个基本操作，编写index,replace KMP算法 模式串的next和nextval函数值 手工模拟KMP算法的执行过程 串的其它算法。,定义和概念,串（String）:由零个或多个字符组成的有限序列。记为：

2、s=a1a2an（n0） 概念： s为串名 a1a2an为串值 n为串的长度 ai，字符 n=0，空串（Null String），记为： 若ai = ，则称为空格串(blank string) 子串：串中任意连续个字符组成的子序列被称为该串的子串 ，包含子串的串又被称为该子串的主串 子串在主串中的位置： 串的相等：两个串的串值相等（两个串的长度相等，并且各个对应的字符也都相同 ）,串的操作,串赋值：StringAssign(S,T) 求串长：StringLenth(S) 串判等：StringEqual(S,T) 串联接：StringConcat(S,T) 求子串：SubString(S,sta

3、rt,length) 子串定位：Index(S,T) 置换：Replace(S,T,V) 插入子串：StringInsert(S,start,T) 删除子串：StringDelete(S,start,length) （其中，前5个操作为基本操作。）,串运算举例,串运算的例子：,长度分别为18、7、3、3；且b、c、d都是a的子串；b在a中的位置是1，c在a中的位置是12；c和d两串相等,例： a= Welcome to Beijing b= Welcome c= Bei d= Bei,子串定位（index）的实现,int Index(String S, String T) 若主串S第i个字符之

4、后存在与T相等的子串，则返回T串在S中的位置，否则返回0 n=StringLength(S); m=StringLength(T); i=1; while(i=n-m+1)当i加上T的长度超过串S的长度结束 StringAssign(sub,SubString(S,i,m); if(StringEqual(sub,T)0) return i; else +i; while return 0; S中不存在与T相等的子串 Index,利用已给操作，求其它操作，是本章的一个重点。下面是利用求串长、取子串和串的判等操作，求子串定位操作。,串的表示和实现,串的顺序存储结构 :用一组连续的存储单元依次存储

5、串中的字符序列。 字符数组表示法 事先定义字符串的最大长度 在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符（0）作为字符串的结束标志 链式表示 每个结点一个字符的单链表表示法 每个结点多个字符的块链存储表示,串的表示和实现,字符数组表示法 #define MAXlen 256 typedef struct char datamaxlen; int len; strtp; 事先定义字符串的最大长度 #define MAX_STRING 256 0号单元存放串的长度，字符从1号单元开始存放 typedef unsigned char S

6、tringMAX_STRING;,串的堆表示法,在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符（0）作为字符串的结束标志。,typedef struct char *str; int length; STRING;,基本操作:串的赋值,int StringAssign(STRING *S, *T) 将串T的值赋给串S if(S-str) free(S-str); 若s已经存在，将它占据的空间释放掉 len= T-length; T串的长度 S-length=len; 赋予字符串长度 if(!len) 空串 S-str=(char*)

7、malloc(sizeof(char); S-str0=0; else 非空串 S-str=(char*)malloc(len+1)*sizeof(char);分配空间 if(!S-str) return ERROR; for(i=0;istri=T-stri; if return OK; StringAssign,基本操作:串联接,int StringConcat(STRING *S,*T) 将串T联接到串S后 STRING temp; StringAssign(temp,S); 将S原来的内容保留在temp中 S-length=S-length+T-length; 计算S和T的长度之和为S

8、的新长度 free(S-str); 释放S原来占据的空间 S-str=(char*)malloc(S-length+1)*sizeof(char); 重新为S分配空间 if(!S-str) return ERROR; else 连接两个串的内容 for(i=0;istri=temp.stri; for(j=0;jlength;j+,i+) 将T的值赋在S现有值之后 S-stri=T-strj; free(temp.str); 释放为临时串temp分配的空间 return OK; if StringConcat,int Index(STRING *S,*T) 返回子串T在主串S中的位置，若T非S

9、的子串则返回0 i=0; j=0; 设置两个扫描指针 while(ilength 子串不在主串中 Index,基本操作的算法:子串定位,定长顺序表示中的C表示方法,在C中，字符串的概念是：以0为结尾的字符数组。 初始化： String s; S0 = 0;,串的链式存储结构,串作为一种特殊的线性表（数据元素为字符），使用顺序表示时，做插入和删除运算，运算量很大，不方便。 链式存储结构：,串的块链存储结构,直接使用线性链表来存储字符串：效率太低,块链式结构的定义,#define CHUNKSIZE 80 可由用户定义的块大小 typedef struct Chunk 结点结构 char chCH

10、UNKSIZE; struct Chunk *next; Chunk; typedef struct 串的链表结构 Chunk *head, *tail; 串的头和尾指针 int curlen; 串的当前长度 LString;,块链运算：插入,H,e,s,i,s,d,e,n,u,t,a,#,#,.,t,He is a student.,He is a bright student.,块链运算：插入,串的模式匹配,子串定位算法Index 基本思想：先以主串S中第一个字符为S子串的头一个字符，模式串T的长度作为S子串的长度，得到一个子串去与模式串T中的字符逐个比较，若子串与模式串相同，即返回S中子

11、串的第一个字符位置作为模式串在主串S中的位置；否则，取S中第二个字符为子串头，将其往后的字符再依次和模式串T比较判断是否相等，以此类推直到找到子串位置或没有一个子串与模式串相同为止 ，前者模式匹配成功，后者模式匹配失败。,朴素的模式匹配,主串S=ababcabcacbab，模式串T= abcac,i=2 第一趟匹配： a b a b c a b c a c b a b a b c j=2 i=1 第二趟匹配： a b a b c a b c a c b a b a j=0 i=6 第三趟匹配： a b a b c a b c a c b a b a b c a c j=4 i=3 第四趟匹配：

12、 a b a b c a b c a c b a b a j=0 i=4 第五趟匹配： a b a b c a b c a c b a b a j=0 i=10 第六趟匹配： a b a b c a b c a c b a b a b c a c（成功） j=5,上面的模式匹配只需三趟,主串S=ababcabcacbab，模式串T= abcac,i=3 第一趟匹配： a b a b c a b c a c b a b a b c j=3 (next3=1) i=3 第二趟匹配： a b a b c a b c a c b a b a b c a c j=5 (next5=2 i=7 第三趟匹配

13、： a b a b c a b c a c b a b (a) b c a c j=5 i=7 怎么得来的呢？这就是KMP算法。,首尾匹配,基本思想：先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n1个字符。,主串: a b a b c a b c a a a b c b a a b c 模式串: a a (2次) a (1次) a a (2次) a (1次) a (1次) a b c b a (5 次) a (1 次) a (1 次) a a (2 次) a a (2次) a b c b a (5 次),例如主串S=ababcabcaaabcbaabc，模

14、式串T=abcba,首尾模式匹配,int IndexFL(STRING *S,*T) 返回子串T在主串S中的位置。若不存在，则函数值为0。其中，T非空。 sLength=S-length; tLength=T-length; i=0; StartChar=T-str0; 模式串第一个字符 EndChar=T-strT-length-1; 模式串最后一个字符 while(istri!=StartChar) +i; 重新查找匹配起始点 else if(S-stri+tLength-1!=EndChar) +i; 模式串的“尾字符”不匹配，重新查找匹配起始点 else 检查中间字符的匹配情况 k=1

15、; j=1; while(jstri+k=Tj) +k; +j; if(j=tLength-1) return i+1; else +i; 重新开始下一次的匹配检测 return 0; IndexFL,KMP算法,KMPKnuth, Morris, Pratt三人发明 特点 无需回溯 在O（nm）的时间量级上完成串的模式匹配操作,KMP算法,假设主串S为s1s2s3sn，模式串T为p1p2tm，若si与tj发生失配，则有： si-j+1si-1=p1pj-1 (1),由（1），若kj,则有： si-k+1si-1= pj-k+1pj-1 (3),若主串不回溯，设此时将模式串中第k（kj）个字符

16、继续比较，则有： si-k+1si-1= p1pk-1 (2),由（2）和（3），则下式成立： p1pk-1 =pj-k+1pj-1 （4） 该等式只与模式串有关，与主串无关。,若模式串P为 abaabc，由定义可得next函数值,KMP算法,next函数的定义,i=2 第一趟匹配： 主串 a c a b a a b a a b c a c a a b c 模式串 a b j=2 next2=1 i=2 第二趟匹配： 主串 a c a b a a b a a b c a c a a b c 模式串 a j=1 next1=0 i=3 i=8 第三趟匹配： 主串 a c a b a a b a

17、a b c a c a a b c 模式串 a b a a b c j=1 j=6 next6=3 i=8 i=12 第四趟匹配： 主串 a c a b a a b a a b c a c a a b c 模式串 (a b) a a b c j=3 j=7,KMP算法手工模拟,主串 S=a c a b a a b a a b c a c a a b c 模式串 P=a b a a b c,0 1 2 3 1 1 2 3 1,0 1 1 1 2 3 4 5 1,求模式串的next函数值举例,如何求next函数,已知next1 = 0，假设nextj = k且 tj = tk，则有nextj+1

18、= k+1= nextj+1； 若nextj = k且 tj tk，则需往前回溯，检查 tj = t?。这实际上也是一个匹配的过程，不同在于主串和模式串是同一个串。 若k=nextk且tj = tk，则nextj=nextk+1，若tj tk 则继续往前回溯，直到存在k使tj = tk或k=0,0 1 1 2 2 3 4 3,利用KMP算法的子串定位函数,int IndexKMP(STRING *S,*T) 利用模式串T的next函数求T在主串S中的位置的KMP算法。其中，T非空 i=0; j=1; while(ilength IndexKMP,对S=aabcbabcaabcaaba，T=bc

19、a，画出以T为模式串，S为目标串的匹配过程。,a a b c b a b c a a b c a a b a,b b b c a b c b b c a,bca的next值数为: 011,利用KMP算法举例,如何求next函数,已知next1=0，假设nextj=k且 pj=pk，则有nextj+1=k+1=nextj+1；若nextj=k且 pjpk，则需往前回溯，检查 pj=p?。这实际上也是一个匹配的过程，不同在于主串和模式串是同一个串。若k=nextk且pj=pk，则nextj=nextk+1，若pjpk 则继续往前回溯，直到存在k使pj=pk或k=0。next函数算法描述如下：,vo

20、id GetNext(STRING *P,int next) 求模式串P的next函数值并存入数组next。 i=1; next1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; nexti=j; else j=nextj; while GetNext,next函数的改进,问题的提出 模式串P=aaaab，其next函数值为01234，若主串为aaabaaabaaaab，当i4，j4时sipj，由nextj的指示还需进行i4、j3，i4、j2，i4、j1等三次比较。实际上，由于模式中第1、2、3个字符和第4个字符都相等，因此这种

21、比较是不必要的，可以将模式串一次向右滑动4个字符直接进行i5、j1的比较。也就是说，若nextj=k，当si与pj失配且pjpk，则下一步不需将主串中的si与pk比较，而是直接与nextk进行比较。由以上思想对next函数进行改进，得到nextval函数如下,nextval函数,void GetNextVal(STRING *P,int nextval) 求模式串P的next函数修正值存入数组nextval。 i=1; nextval1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; if(P-stri-1!=P-strj-1) nextvali=j; else nextvali=n