数据结构课件(c语言)(3)

第4章串1第4章串•本章知识点串的概念和基本术语串的基本运算和操作串的存储方式：顺序存储和链式存储串的模式匹配•本章学习要求（1）了解串的概念（2）掌握串的逻辑结构、存储结构、及各种基本操作和实现（3）了解串的模式匹配算法的基本思想第4章串4.1串的基本概念及其基本运算•4.1.1串的基本概念串（字符串）：是由零个或多个字符组成的有限序列。一般标记为：s=““(n≥0)注意：空串不等同于空格串•串中任意的一个连续的字符构成的序列称为这个串的子串，相应的，我们称包含该子串的串为主串。•串是可以进行比较的。–从逻辑上看，串和线性表非常类似，区别仅在于串的数据对象是字符的集合。但是由于字符串往往将整个串作为操作的对象，而不是像线性表那样，以单个元素作为操作对象，所以在基本操作上，串与线性表有较大的区别。naaa21aaaa•第4章串4.1.1串的基本概念•串在实际应用中经常出现。如程序设计语言中的源程序和目标程序都是字符串数据，事物处理中的顾客的姓名、地址等都用字符串来描述。•【例4.1】如有下列四个字符串，求出各串的长度，判断其中是否有子串，如果有，求出其在主串中的位置。S1=“I□LOVE□FUJIAN”;S2=“I□LOVE”;S3=“FUJIAN”;S4=“FU□JIAN”;–以上字符串的长度为：S1长度13；S2长度6；S3长度6；S4长度7；–其中，S2和S3均为S1的子串，它们在主串S1的位置分别为1和8；但是S4并不是S1的子串，且这个四个串均不相等。第4章串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章串4.2串的存储结构串实际是一种特殊的线性表，它的结点仅由一个字符组成，存储结构和线性表也类似。一般来说，常见的有两种存储方法：顺序存储、链式存储和堆存储。4.2.1串的顺序存储结构和线性表的顺序存储一样，串的顺序存储结构也称为静态存储结构，就是采用与逻辑结构相对应的存储结构，即将串的各个字符按顺序存入地址连续的存储单元中，因此逻辑上相邻的字符在内存中的存储的位置也是相邻的，这样的串称为顺序串。由于一个字符只占一个字节，因此采用顺序存储结构的串有非压缩格式（一个字存储单元中存放一个字符）和压缩格式（根据机器字的长度，尽可能将多个字符存放在一个内存单元内，如一个字节存放一个字符）两种形式。第4章串4.2.1串的顺序存储结构•例如，串S=“CHINA□FUJIAN”的顺序存储结构如图4.1（a）所示：•串的顺序结构类型可定义如下：Constmaxlen=100typedefstruct{charstr[maxlen];intlen;}SeqString;•提示：C语言中，数组以0开始作为下标，每个字符占内存一个字节，且具体存储时每个字符串最后都会使用字符串结束标志“\0”，遇到“\0”即认为字符串结束。第4章串串的顺序存储结构的部分基本操作•1、求串长StrLen算法实现：•2、串复制StrCopy算法实现：•SeqString*StrCopy(SeqString*s1,SeqString*s2)•{•inti;•for(i=0;is2-len;i++)•s1-str[i]=s2-str[i];•s1-len=s2-len;/*设置s1的长度*/•return(s1);•}第4章串•3、求子串SubStr的算法实现：从串s中的第pos个字符开始取长度为len的子串，并返回给sub。SeqString*SubStr（SeqStrings,intpos,intlen,SeqString*sub）{inti;if(pos1||pos=s.len||len0||lens.len-pos+1)/*判断pos和len是否合法*/{printf(“posorlenerror!”);returnNULL;}for(i=0;ilen;i++)sub-str[i]=s.str[pos+i-1];/*将子串复制给sub*/sub-len=len;return(sub);}第4章串•4、删除子串StrDelete算法实现：从串s中的pos位置开始，删除len个字符，并返回串s。SeqString*StrDelete(SeqString*s,intpos,intlen){inti;if(pos1||pos=s-len||len0||lens-len-pos+1){printf(“posorlenerror!”)retrunNULL;}for(i=pos+len-1;is-len;i++)s-str[i-len]=s-str[i];s-len=s-len–len;return(s);}•思考：串的插入操作如何实现？第4章串4.2.2串的链式存储结构•由于串的特殊性——结构中的每个数据元素是一个字符，则使用链表存储串值时，每个结点可以存放一个字符，也可以存放多个字符，结点中存放字符的个数称为“结点大小”。•图4.2（a）是结点大小为3的链表headabcefghij^headaeh^headabcefghij^headabcefghij^第4章串•串的链式结构类型可定义如下：constnodesize=80Typedefstructnode{chardata[nodesize];/*一个结点存多个字符*/structnode*next;/*链指针*/}linkstring;或Typedefstructnode{chardata;/*一个结点存一个字符*/structnode*next;}LinkString;第4章串链式存储结构的插入串操作StrInsert的算法•将串s2插入到串s1中的第i个字符开始的位置上(第i个结点之后）*/•linkstring*StrInsert（linkstring*s1，linkstring*s2，inti）{intk;linkstring*p,*q;p=s1;k=1;while(ki&&p!=NULL){p==p-next;k++；}if(p==NULL)printf(“overflow!＼n”);else{q=s2;while(q!=NULL)q=q-next;q-next=p-next;p-next=s2;}return(s1);}第4章串4.3串的模式匹配运算•4.3.1基本的模式匹配算法•子串定位操作又称为串的模式匹配（patternmatching），就是判断一个串是否是另一个已知串的子串,如果是其子串，则给出该子串的起始点（即是从已知串的哪个字符开始），则称匹配成功，否则则匹配失败。该操作是各种串处理系统的重要操作之一。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本出现的位置。显然，高效的模式匹配算法能大大地提高文本编辑程序效率。本章只讨论简单的模式匹配算法。•假设存在主串S（又称目标）和子串T（又称模式）,模式匹配算法基本思想:从主串的第一个字符起与子串T的第一个字符进行比较，若相等则继续比较它们的后续字符，否则从主串S的下个字符起重新与子串T的第一个字符进行比较。以此类推，直到子串T中的每一个字符依次与主串S中的每一个连续的字符序列相等，则匹配成功，否则匹配失败。第4章串设有两个串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成功第4章串简单模式匹配算法•intStrIndex(SeqString*S,SeqString*T){inti,j;i=０;j=０;/注从字符数组的第０个字符开始比while(iS-len&&jT-len)/*字符比较成功，继续比较后续字符*/if(S-str[i]==T-str[j]){i++；j++;}/*字符比较不成功，i指针回溯，并充T的第一个字符起重新比较*/else{i=i-j+１;j=０};if(jT-len)return(i-T-len+1);/*匹配成功*/elsereturn（0）;/*匹配失败*/}第4章串简单模式匹配算法分析•在某趟匹配过程中，若出现字符比较不相等，则指向主串的指针需要回溯，需要从模式串的第一个字符重新开始比较。没有利用已经比较成功的工作。设主串和模式串的长度分别为n、m，在最坏的情况下（即第i趟匹配成功，前面的i-1趟不成功），每趟比较了m次，第i趟也比较了m次，那么上述算法所执行的字符比较总数为m*(n-m+1)。如果用比较次数来衡量算法的时间复杂度，则上诉算法的时间复杂度为O(m*(n-m)),若nm，则时间复杂度为O(m*n).第4章串4.3.2模式匹配的改进算法——KMP算法•该算法相较于StrIndex的改进之处在于：每当一趟匹配过程出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。该算法可以在O(m+n)的数量级上完成串的模式匹配。•如在匹配过程中：第一次回，当S0=T0,S1=T1,S2≠T2时，算法中取i=1，j=0，比较S1和T0因为T0≠T1,一定有S1≠T0,所以可直接在第二次匹配时取i=2，j=0去比较S2和T0。这样，模式匹配过程主串指针i就不用回溯。第4章串•希望在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”第4章串•故某趟在Si和Tj匹配失败后，如果模式串中有满足上述关系的子串存在，即模式串中的前k个字符与模式中Tj字符前面的k个字符相等时，模式T就可以向后移动到使Tk和Si对准，继续向右进行比较即可。ababcabcacbababcacababcabcacbababcacababcabcacbababcac•模式中的每一个Tj都对应一个k值，该值仅依赖于模式T本身字符序列的构成，而与主串S无关，可以用next［ｊ］表示Ｔｊ对应的ｋ值，根据以上分析，可引出模式串的next函数的定义：第4章串定义：模式串的next函数其它情况且时当1}'pp''ppp'jk1|Max{k1j0[j]1-j1k-j1-k21next第4章串•改进的匹配算法——KMP算法intIndex_kmp(SeqStrings,SeqStringt){/*在目标串S中找模式串T首次出现的位置，若不存在则返回0*/inti=1,j=1;while(i=s.len&&j=t.len)if(j==0||s.str[i-1]==t.str[j-1]){++i;++j;}elsej=next[j];if(jt.len)return(i-t.len)elsereturn(0);}