《数据结构c语言2.pptx》由会员分享，可在线阅读，更多相关《数据结构c语言2.pptx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.1串的基本概念及其基本运算4.1.1 串的基本概念串（字符串）：是由零个或多个字符组成的有限序列。一般标记为：s=“(n0)注意：空串不等同于空格串 串中任意的一个连续的字符构成的序列称为这个串的子串，相应的，我们称包含该子串的串为主串。串是可以进行比较的。从逻辑上看，串和线性表非常类似，区别仅在于串的数据对象是字符的集合。但是由于字符串往往将整个串作为操作的对象，而不是像线性表那样，以单个元素作为操作对象，所以在基本操作上，串与线性表有较大的区别。第1页/共21页4.1.1 串的基本概念串在实际应用中经常出现。如程序设计语言中的源程序和目标程序都是字符串数据，事物处理中的顾客的姓名、地址
2、等都用字符串来描述。【例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的子串，且这个四个串均不相等。第2页/共21页4.1.2 串的基本操作 1、求串的长度 StrLen(s)2、串比较 StrCmp（s1,s2)3、串连接 Concat（s1，s2）4、求子串 SubStr（s，start，
3、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）第3页/共21页4.2 串的存储结构串实际是一种特殊的线性表，它的结点仅由一个字符组成，存储结构和线性表也类似。一般来说，常见的有两种存储方法：顺序存储、链式存储和堆存储。4.2.1 串的顺序存储结构和线性表的顺序存储一样，串的顺序存储结构也称为静态存储结构，就是采用与逻辑结构相对应的存储结构，即将串的各个
4、字符按顺序存入地址连续的存储单元中，因此逻辑上相邻的字符在内存中的存储的位置也是相邻的，这样的串称为顺序串。由于一个字符只占一个字节，因此采用顺序存储结构的串有非压缩格式（一个字存储单元中存放一个字符）和压缩格式（根据机器字的长度，尽可能将多个字符存放在一个内存单元内，如一个字节存放一个字符）两种形式。第4页/共21页4.2.1 串的顺序存储结构例如，串S=“CHINAFUJIAN”的顺序存储结构如图4.1（a）所示：串的顺序结构类型可定义如下：Const maxlen=100 typedef struct char str maxlen ;int len;SeqString;提示：C语言中，
5、数组以0开始作为下标，每个字符占内存一个字节，且具体存储时每个字符串最后都会使用字符串结束标志“0”，遇到“0”即认为字符串结束。第5页/共21页串的顺序存储结构的部分基本操作1、求串长StrLen算法实现：2、串复制StrCopy算法实现：SeqString *StrCopy(SeqString *s1,SeqString *s2)int i;for(i=0;ilen;i+)s1-stri=s2-stri;s1-len=s2-len;/*设置s1的长度*/return(s1);第6页/共21页3、求子串SubStr的算法实现：从串s中的第pos个字符开始取长度为len的子串，并返回给sub。
6、SeqString *SubStr（SeqString s,int pos,int len,SeqString *sub）int i;if(pos=s.len|lens.len-pos+1)/*判断pos和len是否合法*/printf(“pos or len error!”);return NULL;for(i=0;istri=s.strpos+i-1;/*将子串复制给sub*/sub-len=len;return(sub);第7页/共21页4、删除子串StrDelete算法实现：从串s 中的pos位置开始，删除len个字符，并返回串s。SeqString *StrDelete(SeqStr
7、ing *s,int pos,int len)int i;if(pos=s-len|len s-len-pos+1)printf(“pos o r len error!”)retrun NULL;for(i=pos+len-1;ilen;i+)s-stri-len=s-stri;s-len=s-len len;return(s);思考：串的插入操作如何实现？第8页/共21页4.2.2 串的链式存储结构由于串的特殊性结构中的每个数据元素是一个字符，则使用链表存储串值时，每个结点可以存放一个字符，也可以存放多个字符，结点中存放字符的个数称为“结点大小”。图4.2（a）是结点大小为3的链表 head
8、abcefghijheadaehheadabcefghijheadabcefghij第9页/共21页 串的链式结构类型可定义如下：const nodesize=80 Typedef struct node char datanodesize;/*一个结点存多个字符*/struct node *next ;/*链指针*/linkstring;或Typedef struct node char data;/*一个结点存一个字符*/struct node *next ;LinkString;第10页/共21页链式存储结构的插入串操作StrInsert的算法 将串s2插入到串s1中的第i个字符开始的位
9、置上(第i个结点之后）*/linkstring *StrInsert（linkstring*s1，linkstring*s2，int i）int k;linkstring *p,*q;p=s1;k=1;while(knext;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);第11页/共21页4.3 串的模式匹配运算 4.3.1 基本的模式匹配算法 子串定位操作又称为串的模式匹配（pattern matching），就是判断一个串是否是另一个
10、已知串的子串,如果是其子串，则给出该子串的起始点（即是从已知串的哪个字符开始），则称匹配成功，否则则匹配失败。该操作是各种串处理系统的重要操作之一。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本出现的位置。显然，高效的模式匹配算法能大大地提高文本编辑程序效率。本章只讨论简单的模式匹配算法。假设存在主串S（又称目标）和子串T（又称模式）,模式匹配算法基本思想:从主串的第一个字符起与子串T 的第一个字符进行比较，若相等则继续比较它们的后续字符，否则从主串S 的下个字符起重新与子串T的第一个字符进行比较。以此类推，直到子串T中的每一个字符依次与主串S中的每一个连续的字符序列相等，则匹配成功
11、，否则匹配失败。第12页/共21页设有两个串S 和 T,其中：目标S=”abbaba”,模式T=”aba”,匹配过程如图所示：第一次匹配：S=a b b a b a i=3 T=a b a j=3 失败第二次匹配：S=a b b a b a i=2 T=a b a j=1 失败第三次匹配：S=a b b a b a i=3 T=a b a j=1 失败第四次匹配：S=a b b a b a i=6 T=a b a j=3 成功第13页/共21页简单模式匹配算法 int StrIndex(SeqString *S,SeqString *T)int i,j;i=;j=;/注从字符数组的第个字符开始
12、比 while(ilen&jlen)/*字符比较成功，继续比较后续字符*/if(S-str i =T-str j)i+；j+;/*字符比较不成功，i指针回溯，并充T的第一个字符起重新比较*/else i=i-j+;j=;if (jT-len)return (i-T-len+1);/*匹配成功*/else return （0）;/*匹配失败*/第14页/共21页简单模式匹配算法分析在某趟匹配过程中，若出现字符比较不相等，则指向主串的指针需要回溯，需要从模式串的第一个字符重新开始比较。没有利用已经比较成功的工作。设主串和模式串的长度分别为n、m，在最坏的情况下（即第i趟匹配成功，前面的i-1趟不成
13、功），每趟比较了m次，第i趟也比较了m次，那么上述算法所执行的字符比较总数为m*(n-m+1)。如果用比较次数来衡量算法的时间复杂度，则上诉算法的时间复杂度为O(m*(n-m),若nm，则时间复杂度为O(m*n).第15页/共21页4.3.2 模式匹配的改进算法KMP算法该算法相较于StrIndex的改进之处在于：每当一趟匹配过程出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。该算法可以在O(m+n)的数量级上完成串的模式匹配。如在匹配过程中：第一次回，当S0=T0,S1=T1,S2T2时，算法中取i=1，j=0，比较S1
14、和T0 因为T0T1,一定有S1T0,所以可直接在第二次匹配时取i=2，j=0去比较S2和T0。这样，模式匹配过程主串指针i就不用回溯。第16页/共21页希望在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”，由此可
15、得：“T0T1.Tk-1”“Tj-kTj-k+1.Tj-1”第17页/共21页 故某趟在Si和Tj匹配失败后，如果模式串中有满足上述关系的子串存在，即模式串中的前k个字符与模式中Tj字符前面的k个字符相等时，模式T就可以向后移动到使Tk和Si对准，继续向右进行比较即可。a b a b c a b c a c b a ba b c a c a b a b c a b c a c b a b a b c a c a b a b c a b c a c b a b a b c a c模式中的每一个Tj都对应一个k值，该值仅依赖于模式T本身字符序列的构成，而与主串S无关，可以用next表示对应的值，根据以上分析，可引出模式串的next函数的定义：第18页/共21页定义：模式串的next函数第19页/共21页改进的匹配算法KMP算法 int Index_kmp(SeqString s,SeqString t)/*在目标串S中找模式串T首次出现的位置，若不存在则返回0*/int i=1,j=1;while(i=s.len&jt.len)return(i-t.len)else return(0);第20页/共21页感谢您的观看。第21页/共21页