数据结构-第4章串(C#).ppt

第4章串,4.1串的基本概念,4.1.1什么是串,串（或字符串）是由零个或多个字符组成的有限序列。记作str=a1a2an（n0），其中str是串名，用双引号括起来的字符序列为串值，引号是界限符，ai（1in）是一个任意字符（字母、数字或其他字符），它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。,一个串中任意连续的字符组成的子序列称为该串的子串，例如，a、ab、abc和abcd等都是abcde的子串。包含子串的串相应地称为主串。,若两个串的长度相等且对应字符都相等，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。,【例4.1】设str是一个长度为n的串，其中的字符各不相同，则str中的所有子串个数是多少？,解：对于这样的串str，有：空串是其子串，计1个每个字符构成的串是其子串，计n个每2个连续的字符构成的串是其子串，计n-1个每3个连续的字符构成的串是其子串，计n-2个每n-1个连续的字符构成的串是其子串，计2个str是其自身的子串，计1个所有子串个数=1+n+(n-1)+2+1=n(n+1)/2+1。例如，str=software的子串个数=(89)/2+1=37。,4.1.2串的抽象数据类型,ADTString数据对象：D=ai|1in,n0,ai为char类型数据关系：R=rr=|ai,ai+1D,i=1,n-1基本运算：voidStrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。voidStrCopy(t)：串复制，由串t复制产生一个串。intStrLength()：求串长，返回当前串中字符个数。StringConcat(t)：串连接，返回一个当前串和串t连接后的结果。StringSubStr(i,j)：求子串，返回当前串中从第i个字符开始的j个连续字符组成的子串。StringInsStr(i,s)：串插入，返回串s插入到当前串的第i个位置后的子串。StringDelStr(i,j)：串删除，返回当前串中删去从第i个字符开始的j个字符后的结果。StringRepStr(i,j,s)：串替换，返回用串s替换当前串中第i个字符开始的j个字符后的结果。DispStr()：串输出，输出当前串的所有元素值。,4.2串的存储结构,4.2.1串的顺序存储结构顺序串,和顺序表一样，用一个data数组（大小为MaxSize）和一个整型变量length来表示一个顺序串，length表示data数组中实际字符的个数。定义顺序串类SqStringClass如下：,classSqStringClassconstintMaxSize=100;publicchardata;/存放串中字符publicintlength;/存放串长publicSqStringClass()/构造函数,用于顺序串的初始化data=newcharMaxSize;length=0;/顺序串的基本运算,下面讨论在顺序串上实现串基本运算的算法。,（1）建立串StrAssign(cstr)由一个字符串常量cstr建立一个串，即生成一个其值等于cstr的串。对应的算法如下：,publicvoidStrAssign(stringcstr)inti;for(i=0;icstr.Length;i+)datai=cstri;length=i;,例如，cstr=“abcdef”，执行StrAssign(cstr)方法的结果如下图所示。,（2）串复制StrCopy(t)将串t复制给当前串对象。对应的算法如下：,publicvoidStrCopy(SqStringClasst)inti;for(i=0;it.length;i+)datai=t.datai;length=t.length;,（3）求串长度StrLength()返回当前串中的字符个数。对应的算法如下：,publicintStrLength()returnlength;,（4）串连接Concat(t)将当前串和串t的所有字符连接在一起形成的新串，并返回这个新串。对应的算法如下：,publicSqStringClassConcat(SqStringClasst)SqStringClassnstr=newSqStringClass();/新建一个空串inti;nstr.length=length+t.length;for(i=0;ilength;i+)/将当前串data0.str.length-1到nstrnstr.datai=datai;for(i=0;it.length;i+)/将t.data0.t.length-1nstrnstr.datalength+i=t.datai;returnnstr;/返回新串nstr,例如，串对象s和t连接产生新串对象s1的过程如下图所示。,（5）求子串SubStr(i,j)产生由当前串中第i个字符开始的、连续j个字符组成的子串，并返回这个子串。当参数i、j不正确时返回一个空串。对应的算法如下：,publicSqStringClassSubStr(inti,intj)SqStringClassnstr=newSqStringClass();/新建一个空串intk;if(ilength|jlength)returnnstr;/参数不正确时返回空串for(k=i-1;ki+j-1;k+)/将str.datai.i+j-1nstrnstr.datak-i+1=datak;nstr.length=j;returnnstr;/返回新建的顺序串,（6）串插入InsStr(i,s)将串s插入到当前串的第i个位置中产生一个新串，并返回这个新串。当参数不正确时返回一个空串。对应的算法如下：,publicSqStringClassInsStr(inti,SqStringClasss)intj;SqStringClassnstr=newSqStringClass();/新建一个空串if(ilength+1)/参数不正确时返回空串returnnstr;for(j=0;ji-1;j+)/将当前串data0.i-2nstrnstr.dataj=dataj;for(j=0;js.length;j+)/将s.data0.s.length-1nstrnstr.datai+j-1=s.dataj;for(j=i-1;jlength)/参数不正确时返回空串returnnstr;for(k=0;ki-1;k+)/将当前串data0.i-2nstrnstr.datak=datak;for(k=i+j-1;klength)/参数不正确时返回空串returnnstr;for(k=0;ki-1;k+)/将当前串data0.i-2nstrnstr.datak=datak;for(k=0;ks.length;k+)/将s.data0.s.length-1nstrnstr.datai+k-1=s.datak;for(k=i+j-1;klength;k+)/将当前串datai+j-1.length-1nstrnstr.datas.length+k-j=datak;nstr.length=length-j+s.length;returnnstr;/返回新建的顺序串,（9）串输出DispStr()将当前串s的所有字符构成一个字符串并输出。对应的算法如下：,publicstringDispStr()inti;stringmystr=;if(length=0)mystr=空串;elsefor(i=0;ilength;i+)mystr+=datai.ToString();returnmystr;,【例4.2】设计一个算法StrEqueal(s,t)比较两个顺序串s、t是否相等。,解：两个顺序串对象s、t相等的条件是它们的长度相等且所有对应位置上的字符均相同。对应的算法如下：,publicboolStrEqueal(SqStringClasss,SqStringClasst)inti;if(s.length!=t.length)returnfalse;for(i=0;is.length;i+)if(s.datai!=t.datai)returnfalse;returntrue;,4.2.2串的链式存储结构链串,通常将链串中每个结点所存储的字符个数称为结点大小。,结点大小为4的链串：,结点大小为1的链串：,为简便起见，这里规定链串结点大小均为1。,链串的结点类LinkNode定义如下：,classLinkNodepublicchardata;/存放一个字符publicLinkNodenext;/指向下一个结点;,一个链串用一个头结点head来唯一标识。链串类LinkStringClass的定义如下：,classLinkStringClasspublicLinkNodehead=newLinkNode();/链串头结点publicLinkStringClass()/构造函数,用于链串初始化head.next=null;/链串的基本运算算法,下面讨论在链串上实现串基本运算的算法。,（1）建立链串StrAssign(cstr)由一个字符串常量cstr建立一个链串，其头结点为head。以下采用尾插法建立链串。对应的算法如下：,publicvoidStrAssign(stringcstr)inti;LinkNoder=head,p;/r始终指向尾结点for(i=0;icstr.Length;i+)/循环建立字符结点p=newLinkNode();p.data=cstri;r.next=p;r=p;/将p结点插入到尾部r.next=null;/尾结点的next置为null,例如，cstr=“abcdef”，执行StrAssign(cstr)方法的结果如下图所示。,（2）串复制StrCopy(t)将串t的每个结点复制并链接到当前串尾。以下采用尾插法建立当前链串。对应的算法如下：,publicvoidStrCopy(LinkStringClasst)LinkNodep=t.head.next,q,r;r=head;/r始终指向尾结点while(p!=null)/将t的结点p复制产生结点qq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为null,（3）求串长StrLength()返回当前串中的字符个数。对应的算法如下：,publicintStrLength()inti=0;LinkNodep=head.next;/p指向第一个字符结点while(p!=null)i+;p=p.next;/p移到下一个字符结点returni;,（4）串连接Concat(t)返回由当前串s和串t所有字符连接在一起形成的新串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,publicLinkStringClassConcat(LinkStringClasst)LinkStringClassnstr=newLinkStringClass();/新建一个空串LinkNodep=head.next,q,r;r=nstr.head;while(p!=null)/将当前链串的所有结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;p=t.head.next;while(p!=null)/将链串t的所有结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为nullreturnnstr;/返回新建的链串,（5）求子串SubStr(i,j)返回当前串中从第i个字符开始的连续j个字符组成的子串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,publicLinkStringClassSubStr(inti,intj)LinkStringClassnstr=newLinkStringClass();/新建一个空串intk;LinkNodep=head.next,q,r;r=nstr.head;/r指向新建链表的尾结点if(iStrLength()|jStrLength()returnnstr;/参数不正确时返回空串for(k=0;ki-1;k+)p=p.next;for(k=1;k=j;k+)/将s的第i个结点开始的j个结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为nullreturnnstr;/返回新建的链串,（6）串插入InsStr(i,t)将串t插入到当前串中的第i个位置产生一个新串，并返回这个新串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,publicLinkStringClassInsStr(inti,LinkStringClasst)LinkStringClassnstr=newLinkStringClass();/新建一个空串intk;LinkNodep=head.next,p1=t.head.next,q,r;r=nstr.head;/r指向新建链表的尾结点if(iStrLength()+1)/参数不正确时返回空串returnnstr;for(k=1;ki;k+)/将当前链串的前i个结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;,while(p1!=null)/将t的所有结点nstrq=newLinkNode();q.data=p1.data;r.next=q;r=q;/将q结点插入到尾部p1=p1.next;while(p!=null)/将p及其后的结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为nullreturnnstr;/返回新建的链串,（7）子串删除DelStr(i,j)从当前串中删除从第i个字符开始连续j个字符而产生一个新，并返回这个新串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,publicLinkStringClassDelStr(inti,intj)LinkStringClassnstr=newLinkStringClass();/新建一个空串intk;LinkNodep=head.next,q,r;r=nstr.head;/r指向新建链表的尾结点if(iStrLength()|jStrLength()returnnstr;/参数不正确时返回空串for(k=0;ki-1;k+)/将s的前i-1个结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;,for(k=0;kj;k+)/让p沿next跳j个结点p=p.next;while(p!=null)/将p及其后的结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为nullreturnnstr;/返回新建的链串,（8）串替换RepStr(i,j,t)将当前串中第i个字符开始的连续j个字符用串t替换而产生一个新串，并返回这个新串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,publicLinkStringClassRepStr(inti,intj,LinkStringClasst)LinkStringClassnstr=newLinkStringClass();/新建一个空串intk;LinkNodep=head.next,p1=t.head.next,q,r;r=nstr.head;/r指向新建链表的尾结点if(iStrLength()|jStrLength()returnnstr;/参数不正确时返回空串for(k=0;ki-1;k+)/将s的前i-1个结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;,for(k=0;kj;k+)/让p沿next跳j个结点p=p.next;while(p1!=null)/将t的所有结点nstrq=newLinkNode();q.data=p1.data;r.next=q;r=q;/将q结点插入到尾部p1=p1.next;while(p!=null)/将p及其后的结点nstrq=newLinkNode();q.data=p.data;r.next=q;r=q;/将q结点插入到尾部p=p.next;r.next=null;/尾结点的next置为nullreturnnstr;/返回新建的链串,（9）DispStr()将当前链的所有结点值构成一个字符串并返回。对应的算法如下：,publicstringDispStr()stringmystr=;LinkNodep=head.next;/p指向链串的头结点if(p=null)mystr=空串;/返回一个表示空串的信息elsewhile(p!=null)mystr+=p.data.ToString();p=p.next;/p指向下一个结点returnmystr;/返回字符串mystr,【例4.3】以链串为存储结构，重做例4.2。解：用p、q分别遍历链串s和t的数据结点，当两者都没有遍历完时，比较它们的data字段，若不相等时返回false。当循环结束后若两个链串都遍历完则返回true，否则返回false。对应的算法如下：,publicboolStrEqueal(LinkStringClasss,LinkStringClasst)LinkNodep=s.head.next;LinkNodeq=t.head.next;while(p!=null,4.3串的模式匹配,4.4.1Brute-Force算法Brute-Force简称为BF算法，亦称简单匹配算法，其基本思路是：从目标串s=“s0s1sn-1”的第一个字符开始和模式串t=“t0t1tm-1”中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推，若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回-1。,例如，设目标串s=“aaaaab”，模式串t=“aaab”。s的长度为n（n=6），t的长度为m（m=4）。用指针i指示目标串s的当前比较字符位置，用指针j指示模式串t的当前比较字符位置。模式匹配过程如下所示。,对应的BF算法如下：,publicintIndex()inti=0,j=0;while(i=t.length)return(i-t.length);/返回匹配的第一个字符的下标elsereturn(-1);/模式匹配不成功,BF算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯（即i=i-j+1）。BF算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(nm)。,【例4.4】设主串s=ababcabcacbab，模式串t=abcac。给出BF进行模式匹配的过程。,解：采用BF算法进行模式匹配的过程如下：,4.3.2KMP算法,例如，目标串s=“aaaaab”，模式串t=“aaab”。当进行第1趟匹配时，匹配失败处为i=3，j=3。尽管本次匹配失败了，但得到这样的启发信息：s的前3个字符s0s1s2与t的前3个字符t0t1t2相同，另外从t中看到，t0t1与t1t2相同，所以有s1s2=t1t2=t0t1。下一趟匹配从s1开始，由于s1s2=t0t1，所以只需将s3与t2开始比较即可，如下图所示。,实际上，模式串中的“部分匹配”信息就是真子串。所谓真子串就是指模式串t存在某个k（0kj），使得t0t1tk-1=tj-ktj-k+1tj-1成立。例如t=abcac就是包含有真子串的模式串。归纳起来，求模式t的nextj数组的公式如下：,publicvoidGetNext()/由模式串t求出next值intj,k;j=0;k=-1;next0=-1;while(jt.length-1)if(k=-1|t.dataj=t.datak)/k为-1或比较的字符相等时j+;k+;nextj=k;elsek=nextk;,求模式串t的next数组的算法如下：,KMP算法如下：,publicintKMPIndex()/KMP算法inti=0,j=0;GetNext();/求出部分匹配信