数据结构课件(c语言).ppt

1,第4章串,本章知识点串的概念和基本术语串的基本运算和操作串的存储方式：顺序存储和链式存储串的模式匹配本章学习要求（1）了解串的概念（2）掌握串的逻辑结构、存储结构、及各种基本操作和实现（3）了解串的模式匹配算法的基本思想,4.1串的基本概念及其基本运算,4.1.1串的基本概念串（字符串）：是由零个或多个字符组成的有限序列。一般标记为：s=“(n0)注意：空串不等同于空格串串中任意的一个连续的字符构成的序列称为这个串的子串，相应的，我们称包含该子串的串为主串。串是可以进行比较的。从逻辑上看，串和线性表非常类似，区别仅在于串的数据对象是字符的集合。但是由于字符串往往将整个串作为操作的对象，而不是像线性表那样，以单个元素作为操作对象，所以在基本操作上，串与线性表有较大的区别。,4.1.1串的基本概念,串在实际应用中经常出现。如程序设计语言中的源程序和目标程序都是字符串数据，事物处理中的顾客的姓名、地址等都用字符串来描述。【例4.1】如有下列四个字符串，求出各串的长度，判断其中是否有子串，如果有，求出其在主串中的位置。S1=“ILOVEFUJIAN”;S2=“ILOVE”;S3=“FUJIAN”;S4=“FUJIAN”;以上字符串的长度为：S1长度13；S2长度6；S3长度6；S4长度7；其中，S2和S3均为S1的子串，它们在主串S1的位置分别为1和8；但是S4并不是S1的子串，且这个四个串均不相等。,4.1.2串的基本操作,1、求串的长度StrLen(s)2、串比较StrCmp（s1,s2)3、串连接Concat（s1，s2）4、求子串SubStr（s，start，len）5、串复制StrCopy(s1,s2)6、插入子串StrInsert(s1,pos,s2)7、删除子串：StrDelete(s,pos,len)8、串置换StrReplace(s1,pos,s2)9、串赋值StrAssign(s1,s2)10、串定位Index（s1,s2）,4.2串的存储结构,串实际是一种特殊的线性表，它的结点仅由一个字符组成，存储结构和线性表也类似。一般来说，常见的有两种存储方法：顺序存储、链式存储和堆存储。4.2.1串的顺序存储结构和线性表的顺序存储一样，串的顺序存储结构也称为静态存储结构，就是采用与逻辑结构相对应的存储结构，即将串的各个字符按顺序存入地址连续的存储单元中，因此逻辑上相邻的字符在内存中的存储的位置也是相邻的，这样的串称为顺序串。由于一个字符只占一个字节，因此采用顺序存储结构的串有非压缩格式（一个字存储单元中存放一个字符）和压缩格式（根据机器字的长度，尽可能将多个字符存放在一个内存单元内，如一个字节存放一个字符）两种形式。,4.2.1串的顺序存储结构,例如，串S=“CHINAFUJIAN”的顺序存储结构如图4.1（a）所示：串的顺序结构类型可定义如下：Constmaxlen=100typedefstructcharstrmaxlen;intlen;SeqString;提示：C语言中，数组以0开始作为下标，每个字符占内存一个字节，且具体存储时每个字符串最后都会使用字符串结束标志“0”，遇到“0”即认为字符串结束。,串的顺序存储结构的部分基本操作,1、求串长StrLen算法实现：2、串复制StrCopy算法实现：SeqString*StrCopy(SeqString*s1,SeqString*s2)inti;for(i=0;ilen;i+)s1-stri=s2-stri;s1-len=s2-len;/*设置s1的长度*/return(s1);,3、求子串SubStr的算法实现：从串s中的第pos个字符开始取长度为len的子串，并返回给sub。SeqString*SubStr（SeqStrings,intpos,intlen,SeqString*sub）inti;if(pos=s.len|lens.len-pos+1)/*判断pos和len是否合法*/printf(“posorlenerror!”);returnNULL;for(i=0;istri=s.strpos+i-1;/*将子串复制给sub*/sub-len=len;return(sub);,4、删除子串StrDelete算法实现：从串s中的pos位置开始，删除len个字符，并返回串s。SeqString*StrDelete(SeqString*s,intpos,intlen)inti;if(pos=s-len|lens-len-pos+1)printf(“posorlenerror!”)retrunNULL;for(i=pos+len-1;ilen;i+)s-stri-len=s-stri;s-len=s-lenlen;return(s);思考：串的插入操作如何实现？,4.2.2串的链式存储结构,由于串的特殊性结构中的每个数据元素是一个字符，则使用链表存储串值时，每个结点可以存放一个字符，也可以存放多个字符，结点中存放字符的个数称为“结点大小”。图4.2（a）是结点大小为3的链表,串的链式结构类型可定义如下：constnodesize=80Typedefstructnodechardatanodesize;/*一个结点存多个字符*/structnode*next;/*链指针*/linkstring;或Typedefstructnodechardata;/*一个结点存一个字符*/structnode*next;LinkString;,链式存储结构的插入串操作StrInsert的算法,将串s2插入到串s1中的第i个字符开始的位置上(第i个结点之后）*/linkstring*StrInsert（linkstring*s1，linkstring*s2，inti）intk;linkstring*p,*q;p=s1;k=1;while(knext;k+；if(p=NULL)printf(“overflow!n”);elseq=s2;while(q!=NULL)q=q-next;q-next=p-next;p-next=s2;return(s1);,4.3串的模式匹配运算,4.3.1基本的模式匹配算法子串定位操作又称为串的模式匹配（patternmatching），就是判断一个串是否是另一个已知串的子串,如果是其子串，则给出该子串的起始点（即是从已知串的哪个字符开始），则称匹配成功，否则则匹配失败。该操作是各种串处理系统的重要操作之一。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本出现的位置。显然，高效的模式匹配算法能大大地提高文本编辑程序效率。本章只讨论简单的模式匹配算法。假设存在主串S（又称目标）和子串T（又称模式）,模式匹配算法基本思想:从主串的第一个字符起与子串T的第一个字符进行比较，若相等则继续比较它们的后续字符，否则从主串S的下个字符起重新与子串T的第一个字符进行比较。以此类推，直到子串T中的每一个字符依次与主串S中的每一个连续的字符序列相等，则匹配成功，否则匹配失败。,设有两个串S和T,其中：目标S=”abbaba”,模式T=”aba”,匹配过程如图所示：,第一次匹配：S=abbabai=3T=abaj=3失败第二次匹配：S=abbabai=2T=abaj=1失败第三次匹配：S=abbabai=3T=abaj=1失败第四次匹配：S=abbabai=6T=abaj=3成功,简单模式匹配算法,intStrIndex(SeqString*S,SeqString*T)inti,j;i=;j=;/注从字符数组的第个字符开始比while(ilen/*匹配失败*/,简单模式匹配算法分析,在某趟匹配过程中，若出现字符比较不相等，则指向主串的指针需要回溯，需要从模式串的第一个字符重新开始比较。没有利用已经比较成功的工作。设主串和模式串的长度分别为n、m，在最坏的情况下（即第i趟匹配成功，前面的i-1趟不成功），每趟比较了m次，第i趟也比较了m次，那么上述算法所执行的字符比较总数为m*(n-m+1)。如果用比较次数来衡量算法的时间复杂度，则上诉算法的时间复杂度为O(m*(n-m),若nm，则时间复杂度为O(m*n).,4.3.2模式匹配的改进算法KMP算法,该算法相较于StrIndex的改进之处在于：每当一趟匹配过程出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。该算法可以在O(m+n)的数量级上完成串的模式匹配。如在匹配过程中：第一次回，当S0=T0,S1=T1,S2T2时，算法中取i=1，j=0，比较S1和T0因为T0T1,一定有S1T0,所以可直接在第二次匹配时取i=2，j=0去比较S2和T0。这样，模式匹配过程主串指针i就不用回溯。,希望在Si和Tj某次匹配失败后指针i不回溯，模式T向后移动至某个位置上，似的Tk对准Si匹配失败后，指针i不动，模式T向后移动，使Tk和Si对准继续向右进行比较，要满足这一假设，即有如下关系成立：“TOT1.Tk-1”“Si-kSi-k+1.Si-1”而本趟匹配失败是在Si和Tj之处，已得部分匹配结果是：“TOT1.T-1”“Si-jSi-j+1.Si-1”而j故：“Tj-kTj-k+1.Tj-1”“Si-kSi-k+1.Si-1”，由此可得：“T0T1.Tk-1”“Tj-kTj-k+1.Tj-1”,故某趟在Si和Tj匹配失败后，如果模式串中有满足上述关系的子串存在，即模式串中的前k个字符与模式中Tj字符前面的k个字符相等时，模式T就可以向后移动到使Tk和Si对准，继续向右进行比较即可。ababcabcacbababcacababcabcacbababcacababcabcacbababcac模式中的每一个Tj都对应一个k值