数据结构（Java语言版）课件 第六章 串

数据结构（Java语言版）06串【知识目标】

理解串的基本概念；

掌握串的顺序存储的结构、链式存储的结构特点；

掌握Java中串的基本操作及实现；

掌握串的模式匹配算法。【能力目标】

具备利用顺序串进行查找、替换的能力；

具备利用链串处理文字的能力。实例引入如图所示为一个常见的打字游戏针对单词练习的界面，当用户正确输入字符串表示的单词时，青蛙就可跳到相应位置处，青蛙可通过某一系列位置跳到河岸对面。串，又被称作字符串，它是一种特殊的线性表，其包含的每个结点都是由单一字符组成的。一个串是由零个或多个字符组成的有限字符序列，通常一个串被记作：str="a1a2....an"（n≥0）其中，str是串对象名，双引号是串的标志，括起来的字符序列就是串值。串的概述串中的元素ai（0≤i≤n）可以是字母，数字或其它有效字符，被称作串的元素，是构成串的基本单元，i是每个串元素在串中的索引位置。在Java语言中，串的索引位置下界为0，上界是串中的字符个数减去1（即n-1）。n是串的长度，即串中包含有效字符的个数。串的概述当n=0时，串不包含任何字符，被称作为空串；一个或多个空格字符的串，其长度n≥1，称作为空格串。串的概述stringstr1=“”stringstr2=“”stringstr3=null;【例】比较串"tong"和"too"。“to”“to”串比较时，其索引值从0开始，即第一个字符索引位置为0，后面依次为1，2，...，n。其比较过程如图所示：

串的比较

在串中，任意一个连续字符组成的子序列称为该串的子串。包含子串的串相应地被称为主串。

通常将子串在主串中首次出现时，对应主串第一个元素的索引位置，称为该子串在主串中的索引位置，其索引值是子串的第一个字符在主串中的索引位置。

【例】设有S1和S2两个串，分别为S1="Thisisastring"S2="is"通过判断可知，S2是S1的子串，且S2在S1中出现了两次。其中首次出现对应的主串位置索引是2，因此，称S2在S1中的索引或位置是2。根据定义，有如下规定：

空串是任意串的子串，空串在主串的第一次出现时索引值为0。 任意串是其自身的子串，在主串的第一次出现时索引值为0。

串的顺序存储结构

串的存储结构分为顺序存储和链式存储。

Java语言中对于字符串的处理是通过String类或者StringBuffer类来完成的，这两个类对串的存储实际是通过字符数组顺序存储实现的。串的链式存储结构采用单向链表表示，每个结点的值可以是一个字符，也可以是多个字符。

串的顺序存储结构串的顺序存储结构，就是在内存中用一段连续的存储单元存储字符序列，如图所示，因此可通过数组实现，而在Java语言中常用的串存储结构就是顺序存储结构。

根据串的操作，可将串分为静态字符串和动态字符串两种。静态字符串是指对串的操作不能进行插入、删除等改变串结构的操作，只能进行查询、求其长度等不改变串结构的操作。动态字符串是指对串进行操作时，可以对数据元素进行插入、删除等改变串结构的操作。在Java语言中，串是通过JavaAPI中的两个类来实现的，这两个类分别包含在默认包中的java.lang.String类和java.lang.StringBuffer类；这两个类对串的存储方式本质是相同的，都采用了字符数组方式进行存储，即按照顺序结构来存储字符串。但这两个类在功能上略有不同，java.lang.String类对应的是静态字符串，java.lang.StringBuffer类中对应的是动态字符串，具有同步安全机制。通过string类处理串 在Java语言中，java.lang.String类是JavaAPI提供的一个最为常用的基本字符串处理类，该类提供了非常丰富的串处理方法。1．构造字符串（1）直接赋值方式： Stringstr="HelloJava";//直接赋值方式 Stringstr1=newString("HelloJava");//通过常量字符串构造

Stringstr2=newString();//构建一个空串，不是null

通过string类处理串（2）利用字符串数组或字符数组构造字符串方式。按照字节数组以及字符数组构造一个字符串对象分别如下： 利用字符串数组构造一个新的字符串对象： byte[]b="HelloJava".getBytes(); Stringstrb=newString(b);利用字符数组构造一个字符串对象： char[]c=newchar[]{'H','e','l','l','o','','J','a','v','a'}; Stringstrch=newString(c);2．获取指定索引位置处的字符方法：publiccharcharAt(intindex)功能：返回索引index处的字符，当指定参数不在字符串索引值范围内时显示IndexOutOfBoundsException异常。【例】获取字符串"HelloJava"索引位置为6的字符。Strings="HelloJava";intiLocation=s.charAt(6);程序运行后iLocation值为'J'。3．比较两个字符串的大小方法：publicintcompareTo(stringanotherString)功能：比较两个字符串的大小，当前面字符串string比后面字符串anotherString小时，返回负数值，其中，数值为第一个不相同字符的ASCII值的差；当前面字符串string与后面字符串anotherString相同时返回0；当前面字符串string比后面字符串anotherString大时，返回正数值，其中，数值为第一个不相同字符的ASCII值的差。【例】比较字符串"too"和字符串"two"。Strings1="too";Strings2="two";inticomp=pareTo(s2);程序运行结果：icomp=-8，因为：'o'-'w'=-8。4．连接两个字符串方法：publicStringconcat(Stringstr)功能：连接两个字符串，组合成一个新的串，参数str串被连接到当前字符串后面，返回值为当前字符串和参数字符串连接后的结果。5．获取字符串的长度length()：返回字符串中包含字符的个数。【例】获取字符串"ThisisJava"的长度。Strings="ThisisJava";intiLen=s.length();程序运行结果：iLen=12字符串模式匹配,也称子串的定位操作主串：zhuanlanzhihu子串：zhihu主串中包含子串"zhihu"，说明匹配成功，且返回的索引为：8

串的匹配简单算法朴素模式匹配也称为BF(Brute-Force)算法，其基本思想是：从主串的第一个字符起与子串的第一个字符进行比较，若相等，则继续逐对字符进行后续的比较；若不相等，则从主串第二个字符起与子串的第一个字符重新比较，以此类推，直到子串中每个字符依次和主串中的一个连续的字符序列相等为止，此时称为匹配成功。如果不能在主串中找到与子串相同的字符序列，则匹配失败。BF算法是最原始、最暴力的求解过程，但也是其他匹配算法的基础。下面通过具体Demo演示该算法的基本思想。简单算法简单算法假设，S=“asascasabcs”，T=“asabc”S=“asascasabcs”T=“asabc”s简单算法publicclassBruteForce{intindex(StringS,StringT,intindex){

i=0;j=0;intindex=0;while(i<=S.length&&j<=T.length){if(S.charAt(i)==T.charAt(j)){++i;++j;}else{i=i-j+1;j=0;}

}if(j>T.length)returnindex=i-T.l