java数据结构第四章串.ppt

第4章 串,4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法,本章主要知识点： 串的基本概念 串的存储结构 串类的设计方法，主要是拷贝、插入子串和删除子串的设计方法 串的模式匹配算法，包括Brute-Force算法和KMP算法,4.1 串的基本概念及其抽象数据类型,4.1.1 串的基本概念 串（也称作字符串）是由n（n0）个字符组成的有限序列。 一个串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串称为该子串的主串。 一个字符在一个串中的位置序号（为大于等于0的正整数）称为该字符在串中的位置。当且仅当这两个串的值完全相等时，称这两个串相等。,4.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(str)：把串str连接到当前对象串的末尾。 （6）插入子串insert(str, pos)：在当前对象串的第pos个字符前插入子串str。 （7）删除子串delete(beginIndex, endIndex)：删除当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串 。 （8）输出串值myPrint()：输出当前对象的串值。 （9）查找子串index(subStr, start)：在当前对象串的start下标开始，查找是否存在子串subStr。,4.2 串的存储结构,1 串的顺序存储结构 串的顺序存储结构就是用字符类型数组存放串的所有字符。 表示串的长度通常有两种方法： （1）设置一个串的长度参数。 （2）在串值的末尾添加结束标记。,串值长度的第一种表示方法下，串的成员变量应包括如下两项： char value; int count; 其中，value为存储串值的字符类型数组名，count表示串值的长度。,2 串的链式存储结构 串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据元素域上。 有单字符结点链和块链两种。 单字符结点链就是每个结点的数据元素域只包括一个字符。 块链就是每个结点的数据元素域包括若干个字符。,4.3 串类,4.3.1 MyString类 4.3.2 MyString类的测试 4.3.3 MyStringBuffer类 4.3.4 MyStringBuffer类的测试,4.4 串的模式匹配算法,4.4.1 Brute-Force算法 （1）从主串s的第一个字符开始和模式串t的第一个字符比较,若相等则继续比较后续字符； （2）若主串s的第一个字符和模式串t的第一个字符比较不相等，则从主串s的第二个字符开始重新与模式串t的第一个字符比较，若相等则继续比较后续字符,（3）若主串s的第二个字符与模式串t的第一个字符比较不相等，则从主串s的第三个字符开始重新与模式串t的第一个字符比较； （4）如此不断继续。若存在模式串t中的每个字符依次和主串s中的一个连续字符序列相等，则模式匹配成功，函数返回模式串t的第一个字符在主串s中的下标；若比较完主串s的所有字符序列，不存在一个和模式串t相等的子串，则模式匹配失败，函数返回-1。 设主串s=“cddcdc”,模式串t=“cdc”,模式匹配过程如图：,Brute-Force算法模式匹配的一般性过程如图 ：,4.4.2 KMP算法 Brute-Force算法的缺点以及解决方法分析 KMP算法是在Brute-Force算法基础上的改进算法。KMP算法的特点主要是，消除了Brute-Force算法的主串比较位置在相当多个字符比较相等后，只要有一个字符比较不相等，主串位置便需要回退的缺点。 Brute-Force算法的匹配过程可以发现，算法中的主串比较位置的回退并非一定必要。这可分两种情况:,（1）第一种情况。主串s=“cddcdc”、模式串t=“cdc”的模式匹配过程为：当s0=t0，s1=t1，s2t2时，算法中下一次的比较位置为i=1,j=0，即下来比较s1和t0。但是因t0t1，而s1=t1，所以一定有s1t0。所以此时比较s1和t0无意义，实际上随后可直接比较s2和t0。 （2）第二种情况。主串s=“abacabab”、模式串t=“abab”的第一次匹配过程如图4-5所示。此时有s0t0a，s1t1b，s2t2a，s3t3。因有t0t1，s1=t1，所以必有s1t0。又因有t0=t2，s2=t2，所以必有s2=t0，因此下来可直接比较s3和t1。,KMP算法的改进 模式串中是否存在可相互重叠的真子串，只与模式串自身有关，与主串无关。因此，对于主串s=“s0s1sn-1”，子串t=“t0t1tm-1”，可以首先计算出模式串t中每个字符的最大真子串的字符个数k。当模式匹配比较到sitj（0in,0jm）时，随后要比较的主串的下标值不变，模式串的下标值即为k。,3 模式串中最大真子串的求法 模式串中每个字符的最大真子串构成一个数组，定义为模式串的nextj函数。模式串的nextj函数定义如下：,4 KMP函数设计 KMP算法的模式匹配过程如图所示,KMP函数可按如下方法设计： 设s为主串，t为模式串，i为主串当前比较字符的下标，j为模式串当前比较字符的下标。令i的初值为start，j的初值为0。当si=tj时，i和j分别增1再继续比较；否则i不变，j改变为nextj值再继续比较。 比较过程有两种情况： 一是j增加到某个值或j退回到某个j=nextj值时有si=tj，则此时i和j分别增1再继续比较； 二是j退回到j=-1时，令主串和子串的下标各增1，随后比较si+1和t0。这样的循环过程直到变量i大于等于主串s的长度或变量j大于等于子串t的长度终止。,5 计算nextj值的函数设计方法 设有nextj=k，即在模式串t中存在“t0t1tk-1” = “tj- ktj-k+1tj-1”（0k满足上式， 因此有： nextj+1 = nextj + 1 = k + 1 （2）若tktj，则可把计算nextj+1值