java数据结构第四章串

《java数据结构第四章串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串4.1串的基本概念及其抽象数据4.2串的存储结构4.3串类4.4串的模式匹配算法本章主要知识点：串的基本概念串的存储结构串类的设计方法，主要是拷贝、插入子串和删除子串的设计方法串的模式匹配算法，包括Brute-Force算法和KMP算法4.1串的基本概念及其抽象数据类型4.1.1串的基本概念串（也称作字符串）是由n（n≥0）个字符组成的有限序列。一个串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。一个字符在一个串中的位置序号（为大于等于0的正整数）称为该字符在串中的位置。当且仅当这两个串的值完全相等时，称这两个串相等。4

2、.1.2串的抽象数据类型数据集合：串的数据集合可以表示为字符序列s0,s1,…,sn-1，每个数据元素的数据类型为字符类型。操作集合：（1）取字符charAt(index)：取index下标的字符返回。（2）求长度length()：返回串的长度。（3）比较compareTo(anotherString)：比较当前对象串和串anotherString的Unicode码值的大小。（4）取子串substring(beginIndex,endIndex)：取当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串（5）连接concat(s

3、tr)：把串str连接到当前对象串的末尾。（6）插入子串insert(str,pos)：在当前对象串的第pos个字符前插入子串str。（7）删除子串delete(beginIndex,endIndex)：删除当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串。（8）输出串值myPrint()：输出当前对象的串值。（9）查找子串index(subStr,start)：在当前对象串的start下标开始，查找是否存在子串subStr。4.2串的存储结构1串的顺序存储结构串的顺序存储结构就是用字符类型数组存放串的所有字符。表示串的长

4、度通常有两种方法：（1）设置一个串的长度参数。（2）在串值的末尾添加结束标记。串值长度的第一种表示方法下，串的成员变量应包括如下两项：char[]value;intcount;其中，value为存储串值的字符类型数组名，count表示串值的长度。2串的链式存储结构串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据元素域上。有单字符结点链和块链两种。单字符结点链就是每个结点的数据元素域只包括一个字符。块链就是每个结点的数据元素域包括若干个字符。4.3串类4.3.1MyString类4.3.2MyString类的测试4.3.3MyStringBuff

5、er类4.3.4MyStringBuffer类的测试4.4串的模式匹配算法4.4.1Brute-Force算法（1）从主串s的第一个字符开始和模式串t的第一个字符比较,若相等则继续比较后续字符；（2）若主串s的第一个字符和模式串t的第一个字符比较不相等，则从主串s的第二个字符开始重新与模式串t的第一个字符比较，若相等则继续比较后续字符（3）若主串s的第二个字符与模式串t的第一个字符比较不相等，则从主串s的第三个字符开始重新与模式串t的第一个字符比较；（4）如此不断继续。若存在模式串t中的每个字符依次和主串s中的一个连续字符序列相等，则模式匹配成功，函数返回模

6、式串t的第一个字符在主串s中的下标；若比较完主串s的所有字符序列，不存在一个和模式串t相等的子串，则模式匹配失败，函数返回-1。设主串s=“cddcdc”,模式串t=“cdc”,模式匹配过程如图：Brute-Force算法模式匹配的一般性过程如图：4.4.2KMP算法Brute-Force算法的缺点以及解决方法分析KMP算法是在Brute-Force算法基础上的改进算法。KMP算法的特点主要是，消除了Brute-Force算法的主串比较位置在相当多个字符比较相等后，只要有一个字符比较不相等，主串位置便需要回退的缺点。Brute-Force算法的匹配过程可以发

7、现，算法中的主串比较位置的回退并非一定必要。这可分两种情况:（1）第一种情况。主串s=“cddcdc”、模式串t=“cdc”的模式匹配过程为：当s0=t0，s1=t1，s2≠t2时，算法中下一次的比较位置为i=1,j=0，即下来比较s1和t0。但是因t0≠t1，而s1=t1，所以一定有s1≠t0。所以此时比较s1和t0无意义，实际上随后可直接比较s2和t0。（2）第二种情况。主串s=“abacabab”、模式串t=“abab”的第一次匹配过程如图4-5所示。此时有s0＝t0＝’a’，s1＝t1＝’b’，s2＝t2＝’a’，s3≠t3。因有t0≠t1，s1=t

8、1，所以必有s1≠t0。又因有t0=t2，s2=t2