[工学]数据结构——第4章 串C.ppt

　　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 q!=null) 　　{ if (p.data!=q.data) return false; p=p.next; q=q.next; 　　} 　　if (p==null q==null) return true; 　　else return false; } 4.3 串的模式匹配 4.4.1 Brute-Force算法 　　Brute-Force简称为BF算法，亦称简单匹配算法，其基本思路是： 　　从目标串s=“s0s1…sn-1”的第一个字符开始和模式串t=“t0t1…tm-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 (is.length jt.length) 　　{ if (s.data[i]==t.data[j]) //继续匹配下一个字符 {　 i++; //主串和子串依次匹配下一个字符 　　j++; } else //主串、子串指针回溯重新开始下一次匹配 {　 i=i-j+1; //主串从下一个位置开始匹配 　　j=0; //子串从头开始匹配 } 　　} 　　if (j=t.length) return (i-t.length); //返回匹配的第一个字符的下标 　　else return (-1); //模式匹配不成功 } 　　BF算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯（即i=i-j+1）。 　　BF算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(n×m)。 　　【例4.4】 设主串s=ababcabcacbab，模式串t=abcac。给出BF进行模式匹配的过程。 解：采用BF算法进行模式匹配的过程如下： 4.3.2 KMP算法 　　例如，目标串s=“aaaaab”，模式串t=“aaab”。当进行第1趟匹