数据结构c语言西安交大.pptx

串的概念串的概念 串是由零个或多个字符组成的有序序列。串是由零个或多个字符组成的有序序列。值为空格的字符串不同于空串。值为空格的字符串不同于空串。值为单个字符的字符串不同于单个字符。值为单个字符的字符串不同于单个字符。一个串中任意多个连续的字符组成的子序一个串中任意多个连续的字符组成的子序 列称为该串的子串。包含该子串的串称列称为该串的子串。包含该子串的串称 为主串。为主串。一、串及其串操作一、串及其串操作第1页/共33页 子串在主串中的位置指的是该子串的第一个子串在主串中的位置指的是该子串的第一个 字符在主串中的位置。字符在主串中的位置。两个串相等指两个串中的字符序列一一对应。两个串相等指两个串中的字符序列一一对应。一个串的长度指的是串中所包含的字符个数。一个串的长度指的是串中所包含的字符个数。在在C C语言中，串是由双引号括起来的，双引号语言中，串是由双引号括起来的，双引号 本身不是串的组成部分。本身不是串的组成部分。第2页/共33页举例举例S1=“I am a student”S2=“child”S3=“a”S4=“student”S5=“student”S1S1是是S3S3和和S4S4的主串，子串的主串，子串S3S3在在S1S1中的位中的位置为置为2 2，子串，子串S4S4在在S1S1中的位置为中的位置为7 7。S4S4的长度的长度是是7 7，S5S5的长度是的长度是8 8，S4S4和和S5S5不相等，不相等，S5S5不是不是S1S1的子串。的子串。第3页/共33页串的基本操作串的基本操作1 1、赋值、赋值2 2、联接、联接3 3、求串长、求串长4 4、求子串、求子串5 5、比较串的大小、比较串的大小6 6、插入、插入7 7、删除、删除8 8、子串定位、子串定位9 9、置换、置换第4页/共33页二、串的存储结构二、串的存储结构1 1、顺序存储、顺序存储 串的顺序存储结构简称为顺序串。顺序串的顺序存储结构简称为顺序串。顺序串中的字符被顺序地存放在内存的一片相邻串中的字符被顺序地存放在内存的一片相邻的单元中。的单元中。在在C C语言中，用一个特定的、不会出现在语言中，用一个特定的、不会出现在串中的字符作为串的终结符，这就是串中的字符作为串的终结符，这就是/0/0This is a string00Maxsize-1第5页/共33页串的顺序存储形式串的顺序存储形式#define maxsize 32typedef struct char chmaxsize;int curlen;seqstring;第6页/共33页链串的定义与单链表类似，串的链接存储形式为链串的定义与单链表类似，串的链接存储形式为typedef struct linknode char data;struct linknode*next;linkstring;2、链接存储、链接存储第7页/共33页abcdefga b c de f g 0a b c xf g 0 0y z d e结点大小为结点大小为1 1的链串的链串结点大小为结点大小为4 4的链串的链串结点大小为结点大小为4 4的链串在第三个字符后插入的链串在第三个字符后插入“xyzxyz”第8页/共33页3 3、索引存储、索引存储 该方法是用串变量的名字作为关键字组该方法是用串变量的名字作为关键字组织名字表，该表中存储的是串名和串值之间织名字表，该表中存储的是串名和串值之间的对应关系。名字表一般是顺序存放的。的对应关系。名字表一般是顺序存放的。s17s23.a b c d e fg b c d.带长度的名字表带长度的名字表name length stadrname length stadr第9页/共33页串的索引存储形式带长度的名字表串的索引存储形式带长度的名字表typedef struct char namemaxsize;int length;char*stadr;lnode第10页/共33页s1s2.a b c d e fg b c d.带末指针的名字表带末指针的名字表name enadr stadrname enadr stadr第11页/共33页串的索引存储形式带末指针的名字表串的索引存储形式带末指针的名字表typedef struct char namemaxsize;char*stadr,*enadr;enode;第12页/共33页s10s21bcd0.a b c d e fg 0带特征位的名字表带特征位的名字表 name tag stadr/value name tag stadr/value.第13页/共33页串的索引存储形式带特征位的名字表串的索引存储形式带特征位的名字表typedef struct char namemaxsize;union char*stadr;char value4;uval;tagnode第14页/共33页s100s2-31.a b c d e fg.带位移量的名字表带位移量的名字表 name enadr offset2 stadr offset1 name enadr offset2 stadr offset1第15页/共33页串的索引存储形式带位移量的名字表串的索引存储形式带位移量的名字表typedef struct char namemaxsize;char*stadr,enadr;int offset1,offset2;onode第16页/共33页s1130s21614.procedure.var i:integer在索引存储表示下，串值空间的动态分配示意在索引存储表示下，串值空间的动态分配示意name length stadrname length stadr0 14 free0 14 free第17页/共33页3、串基本操作的实现 这里只讨论子串的定位（模式匹配）操这里只讨论子串的定位（模式匹配）操作，是串处理中最重要的一种。作，是串处理中最重要的一种。对主串对主串S S的子串的子串T T，子串，子串T T定位就是要在定位就是要在S S中找到一个与子串中找到一个与子串T T相等的子串。通常把主相等的子串。通常把主串串S S称为目标串，把子串称为目标串，把子串T T称为模式串，因此称为模式串，因此定位被称为模式匹配。模式匹配成功是指在定位被称为模式匹配。模式匹配成功是指在目标串目标串S S中找到一个模式串中找到一个模式串T T。朴素的模式匹配的基本朴素的模式匹配的基本思想是：用子串思想是：用子串中的字符依次与主串中的字符进行比较。中的字符依次与主串中的字符进行比较。第18页/共33页第一次匹配 s=c d d c d e s=c d d c d e 失败 t=c d ct=c d c第二次匹配 s=c d d c d e s=c d d c d e 失败 t=c d ct=c d c第三次匹配 s=c d d c d e s=c d d c d e 失败 t=c d ct=c d c第四次匹配 s=c d d c d e s=c d d c d e 成功 t=c d ct=c d c第19页/共33页简单匹配算法简单匹配算法int INDEX(seqstring*S,seqstring*T)int i=0,j=0;while(icurlen)&(jcurlen)if(S-chi=T-chj)i+;j+;else i=i-j+1;j=0;if(j=T-curlen)return(i-T-curlen);else return(-1);第20页/共33页链串上的子串定位运算链串上的子串定位运算linkstring*INDEXL(linkstring*S,linkstring*T)linkstring*first,*sptr,*tptr;first=S;sptr=first;tptr=T;while(sptr&tptr)if(sptr-data=tptr-data)sptr=sptr-next;tptr=tptr-next;else first=first-next;sptr=first;tptr=T;if(tptr=NULL)return(first);else return(NULL)第21页/共33页算法分析算法分析 在最坏情况下，第在最坏情况下，第i i趟匹配成功，前面趟匹配成功，前面i-1i-1趟的不成功的匹配中，每趟比较了趟的不成功的匹配中，每趟比较了m m次，次，第第i i趟成功时也比较了趟成功时也比较了m m次，所以共比较了次，所以共比较了i i m m次。因此在最坏情况下，平均比较次次。因此在最坏情况下，平均比较次数是：数是：由于由于nmnm，故上述的时间复杂度为，故上述的时间复杂度为O(mn)O(mn)第22页/共33页KMP算法算法 分析简单匹配算法可以发现，算法中出分析简单匹配算法可以发现，算法中出现的主串指针回朔并非一定必要。现的主串指针回朔并非一定必要。第一次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第二次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第三次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第四次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第23页/共33页可见，一旦可见，一旦s si i和和t tj j比较不相等，主串比较不相等，主串s s的指的指针不一定要回朔，主串针不一定要回朔，主串s si i（或（或s si+1i+1）可直接）可直接与与t tk k（0=k0=kj j）比较，）比较，k k的决定与主串的决定与主串s s并并无关系，而只与模式串无关系，而只与模式串t t本身的构成有关，本身的构成有关，即从模式串即从模式串t t本身就可求出本身就可求出k k值。值。讨论一般情况，设讨论一般情况，设s=s=“s s0 0s s1 1.s.sn-1n-1”，t=t=“t t0 0t t1 1.t.tm-1m-1”。假定：。假定：第24页/共33页若模式串中存在可互相重叠的真子串若模式串中存在可互相重叠的真子串,使得：使得：（1 1）说明模式串的子串说明模式串的子串“t t0 0t t1 1.t.tk-1k-1”已和已和主串主串 “s si-ki-ks si-k+1i-k+1.s.si-1i-1”匹配，下一次可直匹配，下一次可直接比较接比较s si i和和t tk k；（2 2）说明在说明在“t t0 0t t1 1.t.tk-1k-1”中不存在任何以中不存在任何以t t0 0为首字符子串与为首字符子串与“s si-ki-ks si-i-k+1k+1.s.si-1i-1”中以中以s si-1i-1为末字符的匹配子串，下为末字符的匹配子串，下一次可直接比较一次可直接比较s si i和和t t0 0。（1 1）（2 2）第25页/共33页定义定义nextjnextj如下：如下：其它情况当j=0时由此定义可推出由此定义可推出nextnext的函数值：的函数值：j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 模式串模式串nextjnextj a b a a b c a c a b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1第26页/共33页int Nextmaxsize;int KMPIndex(seqstring*S,seqstring*T)int i,j,v;i=0;j=0;while(i curlen&j curlen)if (i=-1|S-chj=T-curlen)i+;j+;else j=Nextj;if (j=T-curlen)v=i T-curlen;else v=-1;return(v);第27页/共33页可以用递推的方法推出可以用递推的方法推出nextnext的值。当的值。当j j时，时，nextj=-1;nextj=-1;设设nextj=knextj=k，即，即t t中存在中存在其中其中k k为满足等式的最大值。以下求为满足等式的最大值。以下求nextj+1nextj+1，分两种情况讨论：，分两种情况讨论：1 1、若、若t tk k=t=tj j，则表明模式串，则表明模式串t t中有：中有：且不可能存在某个且不可能存在某个k k k k满足上式，因此满足上式，因此nextj+1=nextj+1=k+1;nextj+1=nextj+1=k+1;第28页/共33页2 2、若、若t tk kttj j，此时可把求，此时可把求nextj+1nextj+1值的问值的问题看作是一个模式匹配问题，即把模式串题看作是一个模式匹配问题，即把模式串t t向右滑动至向右滑动至k k=nextk=nextk（0k0kkjkj），），若若t tk k=t=tj j，则说明在主串，则说明在主串t t中第中第j+1j+1个字符之个字符之前存在一个长度为前存在一个长度为k k的子串满足：的子串满足：也就是说，也就是说，nextj+1=knextj+1=k+1=+1=nextk+1;nextk+1;此时若此时若t tk kttj j，则将模式串，则将模式串t t继续右滑至继续右滑至k k”=nextk=nextk。以次类推，直到某次匹配成。以次类推，直到某次匹配成功或匹配失败。设功或匹配失败。设k kl l次右滑匹配失败，则有次右滑匹配失败，则有nextnextkkl-1l-1=-1=-1，则有：，则有：nextj+1=nextknextj+1=nextkl-1l-1+1=-1+1=0+1=-1+1=0第29页/共33页举例：现有如图所示的字符串。举例：现有如图所示的字符串。j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7模式串模式串nextjnextj a b a a b c a c a b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1已求得前已求得前6 6个字符的个字符的nextnext函数值，现求函数值，现求next6next6。因为因为next5=2next5=2，又，又t t5 5tt2 2，则需比较，则需比较t t5 5和和t t0 0（因（因为为next2=0next2=0），这相当于将子串向右滑动。由），这相当于将子串向右滑动。由于于next0=-1next0=-1，所以，所以next6=0next6=0，而因为，而因为t t6 6=t=t0 0，则则next7=1next7=1。第30页/共33页int Nextmaxsize;int GetNext(seqstring *T)int j,k;k=-1;j=0;Next0=-1;while(j curlen-1)if (k=-1|T-chj=T-chk)i+;j+;Nextj=k;else k=Nextk;第31页/共33页例如，当：例如，当：S=“0000000000000000000000000000001”T=“000001”时，时，KMP算法比简单算法效率要高地多。算法比简单算法效率要高地多。第32页/共33页感谢您的观看！第33页/共33页