数据结构——第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 串的抽象数据类型,ADT String 数据对象： D=ai | 1in,n0,ai为char类型 数据关系： R=r r= | ai,ai+1D, i=1,n-1 基本运算： void StrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。 void StrCopy(t)：串复制，由串t复制产生一个串。 int StrLength()：求串长，返回当前串中字符个数。 String Concat(t)：串连接，返回一个当前串和串t连接后的结果。 String SubStr(i,j)：求子串，返回当前串中从第i个字符开始的j个连续字符组成的子串。 String InsStr(i,s)：串插入，返回串s插入到当前串的第i个位置后的子串。 String DelStr(i,j)：串删除，返回当前串中删去从第i个字符开始的j个字符后的结果。 String RepStr(i,j,s)：串替换，返回用串s替换当前串中第i个字符开始的j个字符后的结果。 DispStr()：串输出，输出当前串的所有元素值。 ,4.2 串的存储结构,4.2.1 串的顺序存储结构顺序串,和顺序表一样，用一个data数组（大小为MaxSize）和一个整型变量length来表示一个顺序串，length表示data数组中实际字符的个数。 定义顺序串类SqStringClass如下：,class SqStringClass const int MaxSize=100; public char data; /存放串中字符 public int length; /存放串长 public SqStringClass() /构造函数,用于顺序串的初始化 data=new charMaxSize; length=0; /顺序串的基本运算 ,下面讨论在顺序串上实现串基本运算的算法。,（1）建立串StrAssign(cstr) 由一个字符串常量cstr建立一个串，即生成一个其值等于cstr的串。对应的算法如下：,public void StrAssign(string cstr) int i; for (i=0;icstr.Length;i+) datai=cstri; length=i; ,例如，cstr=“abcdef”，执行StrAssign(cstr)方法的结果如下图所示。,（2）串复制StrCopy(t) 将串t复制给当前串对象。对应的算法如下：,public void StrCopy(SqStringClass t) int i; for (i=0;it.length;i+) datai=t.datai; length=t.length; ,（3）求串长度StrLength() 返回当前串中的字符个数。对应的算法如下：,public int StrLength() return length; ,（4）串连接Concat(t) 将当前串和串t的所有字符连接在一起形成的新串，并返回这个新串。对应的算法如下：,public SqStringClass Concat(SqStringClass t) SqStringClass nstr=new SqStringClass(); /新建一个空串 int i; nstr.length=length+t.length; for (i=0;ilength;i+)/将当前串data0str.length-1到nstr nstr.datai=datai; for (i=0;it.length;i+)/将t.data0t.length-1nstr nstr.datalength+i=t.datai; return nstr; /返回新串nstr ,例如，串对象s和t连接产生新串对象s1的过程如下图所示。,（5）求子串SubStr(i,j) 产生由当前串中第i个字符开始的、连续j个字符组成的子串，并返回这个子串。当参数i、j不正确时返回一个空串。对应的算法如下：,public SqStringClass SubStr(int i,int j) SqStringClass nstr=new SqStringClass(); /新建一个空串 int k; if (ilength | jlength) return nstr; /参数不正确时返回空串 for (k=i-1;ki+j-1;k+) /将str.dataii+j-1nstr nstr.datak-i+1=datak; nstr.length=j; return nstr; /返回新建的顺序串 ,（6）串插入InsStr(i,s) 将串s插入到当前串的第i个位置中产生一个新串，并返回这个新串。当参数不正确时返回一个空串。对应的算法如下：,public SqStringClass InsStr(int i,SqStringClass s) int j; SqStringClass nstr=new SqStringClass(); /新建一个空串 if (ilength+1) /参数不正确时返回空串 return nstr; for (j=0;ji-1;j+) /将当前串data0i-2nstr nstr.dataj=dataj; for (j=0;js.length;j+) /将s.data0s.length-1nstr nstr.datai+j-1=s.dataj; for (j=i-1;jlength;j+) /将当前串datai-1length-1nstr nstr.datas.length+j=dataj; nstr.length=length+s.length; return nstr; /返回新建的顺序串 ,（7）串删除DelStr(i,j) 从当前串中删去第i个字符开始的连续j个字符产生一个子串，并返回这个子串。当参数不正确时返回一个空串。对应的算法如下：,public SqStringClass DelStr(int i,int j) int k; SqStringClass nstr=new SqStringClass(); /新建一个空串 if (ilength | i+j-1length) /参数不正确时返回空串 return nstr; for (k=0;ki-1;k+) /将当前串data0i-2nstr nstr.datak=datak; for (k=i+j-1;klength;k+) /将当前串datai+j-1length-1nstr nstr.datak-j=datak; nstr.length=length-j; return nstr; /返回新建的顺序串 ,（8）串替换RepStr(i,j,s) 将当前串中第i个字符开始的连续j个字符用串s替换而产生一个新串，并返回这个新串。当参数不正确时返回一个空串。对应的算法如下：,public SqStringClass RepStr(int i,int j,SqStringClass s) int k; SqStringClass nstr=new SqStringClass(); /新建一个空串 if (ilength | i+j-1length) /参数不正确时返回空串 return nstr; for (k=0;ki-1;k+) /将当前串data0i-2nstr nstr.datak=datak; for (k=0;ks.length;k+) /将s.data0s.length-1nstr nstr.datai+k-1=s.datak; for (k=i+j-1;klength;k+) /将当前串datai+j-1length-1nstr nstr.datas.length+k-j=datak; nstr.length=length-j+s.length; return nstr; /返回新建的顺序串 ,（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算法如下：,public string DispStr() int i; string mystr=“; if (length=0) mystr = “空串“; else for (i=0;ilength;i+) mystr+=datai.ToString(); return mystr; ,【例4.2】 设计一个算法StrEqueal(s,t)比较两个顺序串s、t是否相等。,解：两个顺序串对象s、t相等的条件是它们的长度相等且所有对应位置上的字符均相同。对应的算法如下：,public bool StrEqueal(SqStringClass s, SqStringClass t) int i; if (s.length!=t.length) return false; for (i=0; is.length;i+) if (s.datai!=t.datai) return false; return true; ,4.2.2 串的链式存储结构链串,通常将链串中每个结点所存储的字符个数称为结点大小 。,结点大小为4的链串 ：,结点大小为1的链串 ：,为简便起见，这里规定链串结点大小均为1。,链串的结点类LinkNode定义如下：,class LinkNode public char data; /存放一个字符 public LinkNode next; /指向下一个结点 ;,一个链串用一个头结点head来唯一标识。链串类LinkStringClass的定义如下：,class LinkStringClass public LinkNode head=new LinkNode(); /链串头结点 public LinkStringClass() /构造函数,用于链串初始化 head.next=null; /链串的基本运算算法 ,下面讨论在链串上实现串基本运算的算法。,（1）建立链串StrAssign(cstr) 由一个字符串常量cstr建立一个链串，其头结点为head。以下采用尾插法建立链串。对应的算法如下：,public void StrAssign(string cstr) int i; LinkNode r=head,p; /r始终指向尾结点 for (i=0;icstr.Length;i+) /循环建立字符结点 p=new LinkNode(); p.data=cstri; r.next=p; r=p; /将p结点插入到尾部 r.next=null; /尾结点的next置为null ,例如，cstr=“abcdef”，执行StrAssign(cstr)方法的结果如下图所示。,（2）串复制StrCopy(t) 将串t的每个结点复制并链接到当前串尾。以下采用尾插法建立当前链串。对应的算法如下：,public void StrCopy(LinkStringClass t) LinkNode p=t.head.next,q,r; r=head; /r始终指向尾结点 while (p!=null) /将t的结点p复制产生结点q q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null ,（3）求串长StrLength() 返回当前串中的字符个数。对应的算法如下：,public int StrLength() int i=0; LinkNode p=head.next; /p指向第一个字符结点 while (p!=null) i+; p=p.next; /p移到下一个字符结点 return i; ,（4）串连接Concat(t) 返回由当前串s和串t所有字符连接在一起形成的新串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,public LinkStringClass Concat(LinkStringClass t) LinkStringClass nstr=new LinkStringClass();/新建一个空串 LinkNode p=head.next,q,r; r = nstr.head; while (p!=null) /将当前链串的所有结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; p=t.head.next; while (p!=null) /将链串t的所有结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null return nstr; /返回新建的链串 ,（5）求子串SubStr(i,j) 返回当前串中从第i个字符开始的连续j个字符组成的子串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,public LinkStringClass SubStr(int i,int j) LinkStringClass nstr=new LinkStringClass();/新建一个空串 int k; LinkNode p=head.next,q,r; r=nstr.head; /r指向新建链表的尾结点 if (iStrLength() | jStrLength() return nstr; /参数不正确时返回空串 for (k=0;ki-1;k+) p=p.next; for (k=1;k=j;k+) /将s的第i个结点开始的j个结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null return nstr; /返回新建的链串 ,（6）串插入InsStr(i,t) 将串t插入到当前串中的第i个位置产生一个新串，并返回这个新串。当 参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,public LinkStringClass InsStr(int i,LinkStringClass t) LinkStringClass nstr=new LinkStringClass();/新建一个空串 int k; LinkNode p=head.next,p1=t.head.next,q,r; r=nstr.head; /r指向新建链表的尾结点 if (iStrLength()+1) /参数不正确时返回空串 return nstr; for (k=1; ki; k+) /将当前链串的前i个结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; ,while (p1!=null) /将t的所有结点nstr q=new LinkNode(); q.data=p1.data; r.next=q; r=q; /将q结点插入到尾部 p1=p1.next; while (p!=null) /将p及其后的结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null return nstr; /返回新建的链串 ,（7）子串删除DelStr(i,j) 从当前串中删除从第i个字符开始连续j个字符而产生一个新，并返回这个新串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,public LinkStringClass DelStr(int i,int j) LinkStringClass nstr=new LinkStringClass();/新建一个空串 int k; LinkNode p=head.next,q,r; r = nstr.head; /r指向新建链表的尾结点 if (iStrLength() | jStrLength() return nstr; /参数不正确时返回空串 for (k=0; ki-1;k+) /将s的前i-1个结点nstr q=new LinkNode(); 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及其后的结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null return nstr; /返回新建的链串 ,（8）串替换RepStr(i,j,t) 将当前串中第i个字符开始的连续j个字符用串t替换而产生一个新串，并返回这个新串。当参数不正确时返回一个空串。以下采用尾插法建立链串nstr并返回。对应的算法如下：,public LinkStringClass RepStr(int i,int j,LinkStringClass t) LinkStringClass nstr=new LinkStringClass();/新建一个空串 int k; LinkNode p=head.next,p1=t.head.next,q,r; r=nstr.head; /r指向新建链表的尾结点 if (iStrLength() | jStrLength() return nstr; /参数不正确时返回空串 for (k=0; ki-1; k+) /将s的前i-1个结点nstr q=new LinkNode(); 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的所有结点nstr q=new LinkNode(); q.data=p1.data; r.next=q; r=q; /将q结点插入到尾部 p1=p1.next; while (p != null) /将p及其后的结点nstr q=new LinkNode(); q.data=p.data; r.next=q; r=q; /将q结点插入到尾部 p=p.next; r.next=null; /尾结点的next置为null return nstr; /返回新建的链串 ,（9）DispStr() 将当前链的所有结点值构成一个字符串并返回。对应的算法如下：,public string DispStr() string mystr=“; LinkNode p=head.next; /p指向链串的头结点 if (p=null) mystr=“空串“; /返回一个表示空串的信息 else while (p!=null) mystr+=p.data.ToString(); p=p.next; /p指向下一个结点 return mystr; /返回字符串mystr ,【例4.3】 以链串为存储结构，重做例4.2。 解：用p、q分别遍历链串s和t的数据结点，当两者都没有遍历完时，比较它们的data字段，若不相等时返回false。当循环结束后若两个链串都遍历完则返回true，否则返回false。对应的算法如下：,public bool StrEqueal(LinkStringClass s, LinkStringClass t) LinkNode p = s.head.next; LinkNode q = t.head.next; while (p!=null ,4.3 串的模式匹配,4.4.1 Brute-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算法如下：,public int Index() int i=0, j=0; while (i=t.length) return (i-t.length); /返回匹配的第一个字符的下标 else return (-1); /模式匹配不成功 ,BF算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯（即i=i-j+1）。 BF算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(nm)。,【例4.4】 设主串s=“ababcabcacbab“，模式串t=“abcac“。给出BF进行模式匹配的过程。,解：采用BF算法进行模式匹配的过程如下：,4.3.2 KMP算法,例如，目标串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数组的公式如下：,public void GetNext() /由模式串t求出next值 int j,k; j=0; k=-1; next0=-1; while (jt.length-1) if (k=-1 | t.dataj=t.datak) /k为-1或比较的字符相等时 j+;k+; nextj=k; else k=nextk; ,求模式串t的next数