数据结构（java版）第4章串与数组课件

数数 据据 结结 构构(Java(Java语言描述语言描述)第四章第四章 串与数组串与数组第四章 串与数组数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第四章第四章 串与数组串与数组章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映教学内容教学内容4.1 串的基本概念串的基本概念 4.2 串的存储结构串的存储结构 4.3 顺序串的实现顺序串的实现 4.4 串的模式匹配操作串的模式匹配操作 4.5 串的应用举例串的应用举例 4.6 数组的概念及顺序存储结构数组的概念及顺序存储结构 4.7 特殊矩阵的压缩存储特殊矩阵的压缩存储 4.8 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 教学内容4.1 串的基本概念 4.2 串的存储结构 4.数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第四章第四章 串与数组串与数组章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映教学重点与难点教学重点与难点重点：重点：掌握串类型定义中各基掌握串类型定义中各基本操作的定义以本操作的定义以及串中基本操作的应用。及串中基本操作的应用。掌握数组的定义、操作和存储结构掌握数组的定义、操作和存储结构难点：难点：串的基本操作的应用，即如何运用串串的基本操作的应用，即如何运用串的基本操作来实现其它串的复杂操作。的基本操作来实现其它串的复杂操作。矩阵的压缩存储。矩阵的压缩存储。教学重点与难点重点：掌握串类型定义中各基本操作的定义以及串中数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1 1、串：串：是由是由零个零个或或多个多个字符组成的有限序列。字符组成的有限序列。一般记为一般记为s=s=a a0 0a a1 1a an-1 n-1,其中其中s s为为串名串名，双引号括起来的字符序列是，双引号括起来的字符序列是串值串值。2 2、串的长度：串的长度：串中串中字符的个数字符的个数。3 3、空串：空串：长度为长度为0 0的串，即不包含任何字符的的串，即不包含任何字符的串，表示为串，表示为。4 4、空白串：空白串：由一个或多个空白字符组成的串，由一个或多个空白字符组成的串，如：如：。注意：注意：空串与空白串的区别空串与空白串的区别串也是一种特殊的线性表。串也是一种特殊的线性表。4.1.1 4.1.1 串的基本概念串的基本概念1、串：是由零个或多个字符组成的有限序列。一般记为数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录5 5、子串：子串：主串：主串：串中任意个串中任意个连续字符连续字符组成的组成的子子序列序列称为该串的子串。称为该串的子串。包含子串的串相应地称为包含子串的串相应地称为主主串。串。6 6、字符在串中的位置：字符在串中的位置：子串在主串中的位置：子串在主串中的位置：如：如：s1=s1=cdababefcdababef,s2=,s2=abab字符在串中的序号值。字符在串中的序号值。子串在主串中第一次子串在主串中第一次出现时的第一个字符在主串中的序号值。出现时的第一个字符在主串中的序号值。注意：注意：空串是任意串的子串空串是任意串的子串,任意串是其自任意串是其自 身的子串。身的子串。4.1.1 4.1.1 串的基本概念串的基本概念5、子串：串中任意个连续字符组成的子序列称为该串的子串。包含数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录7 7、两个串相等：两个串相等：长度相等长度相等各个字符对应相等各个字符对应相等串值相等串值相等4.1.1 4.1.1 串的基本概念串的基本概念7、两个串相等：长度相等各个字符对应相等串值相等4.1.1 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 clear()1 1）串的置空操作：）串的置空操作：isEmpty()2 2）串的判空操作：）串的判空操作：length()3 3）求串的长度操作：）求串的长度操作：4 4）取字符元素操作：）取字符元素操作：5 5）截取子串操作：）截取子串操作：charAT(index)substring(bengin,end)6 6）插入操作：）插入操作：insert(offset,str)1.1.基本操作基本操作4.1.2 串的抽象数据类型描述 clear()1）数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 delete(begin,end )7 7）删除操作：）删除操作：concat(str)8 8）串的连接操作：）串的连接操作：compareTo(str )9 9）串的比较操作：）串的比较操作：1010）子串定位操作：）子串定位操作：indexOf(str,begin)1.1.基本操作基本操作4.1.2 串的抽象数据类型描述 delete(begi数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述charAT(index)读取并返回串中的第读取并返回串中的第indexindex个字符值个字符值,其中其中:0:0indexindexlength()-1length()-1 例如例如:当前串为当前串为abcdefg charAT(0)=?acharAT(3)=?dcharAT(6)=?g4.1.2 串的抽象数据类型描述charAT(index)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述substring(bengin,end)截取当前串中从序号截取当前串中从序号beginbegin开始开始,到序号到序号end-1end-1为止的子串并返回其值为止的子串并返回其值,其中其中:0beginlength()-1,1 1endendlength()length()例如例如:当前串为当前串为commander substring(3,6)=?man substring(0,9)=?commander substring(8,9)=?r substring(3,10)=?substring(9,1)=?4.1.2 串的抽象数据类型描述substring(be数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 将串将串strstr插入到当前串中的第插入到当前串中的第offsetoffset个字个字符的前面符的前面,并返回操作结果。其中并返回操作结果。其中:0offsetlength()例如例如:当前串为当前串为chater,则则insert(3,rac）=?character insert(offset,str)insert(0,rac)=?racchater insert(6,rac)=?chaterrac 4.1.2 串的抽象数据类型描述 将串str插入到当前数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述delete(bengin,end)删除当前串中从序号删除当前串中从序号beginbegin开始开始,到序号到序号end-1end-1为止的子串为止的子串,并返回操作结果。其中并返回操作结果。其中:0beginlength()-1,1 1endendlength()length()例如例如:当前串为当前串为commanderdelete(3,6)=?comder delete(0,9)=?delete(8,9)=?commande delete(3,10)=?delete(9,1)=?4.1.2 串的抽象数据类型描述delete(bengi数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 concat(str)将串将串strstr连接在当前串的后面，连接在当前串的后面，并返回其值。并返回其值。例如例如:当前串为当前串为man,则则concat(kind)=?mankind 4.1.2 串的抽象数据类型描述 concat(str)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 compareTo(str)将当前串与目标串将当前串与目标串strstr进行比较进行比较,若若:当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 strstr，则返回值，则返回值 0 0。例如例如:当前串为当前串为 cat compareTo(case)?0 compareTo(cate)?0compareTo(cht )?0 4.1.2 串的抽象数据类型描述 compareTo(s数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述indexOf(str,begin)在当前串中从在当前串中从beginbegin位置开始去找与位置开始去找与非空串非空串strstr相等的子串相等的子串,若查找成功则返回在当前串中的位置若查找成功则返回在当前串中的位置,否则返回否则返回-1,-1,其中其中:0beginlength()-1 例如例如:当前串为当前串为 bcaabcaaabc,str=,str=bca indexOf(str,0)=?0indexOf(str,2)=?4indexOf(str,6)=?-14.1.2 串的抽象数据类型描述indexOf(str,be数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录public interface IString public void clear();public boolean isEmpty();public int length();public char charAt(int index);public IString substring(int begin,int end);public IString insert(int offset,IString str);4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 2.2.串的抽象数据类型的串的抽象数据类型的JavaJava接口描述接口描述public interface IString 4.1.数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）4.1串的基本概念串的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 串串的逻辑结构和的逻辑结构和线性表线性表极为相似，极为相似，区区别别仅在于仅在于串的数据对象约束为字符集串的数据对象约束为字符集。但串的基本操作和线性表有很大差别但串的基本操作和线性表有很大差别:在线性表的基本操作中，大多以大多以“单个元素单个元素”作为操作对象作为操作对象；在串的基本操作中，通常以通常以“串的串的整体整体”作为操作对象作为操作对象。串的逻辑结构和线性表极为相似，区别仅在于串的数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.2串的存储结构串的存储结构4.2.1 4.2.1 串的顺序存储结构串的顺序存储结构 串的顺序存储结构与线性表的顺序存储结串的顺序存储结构与线性表的顺序存储结构类似，可以采用一组地址连续的存储单元构类似，可以采用一组地址连续的存储单元来存储串字符序列。顺序存储的串称为来存储串字符序列。顺序存储的串称为顺序顺序串，顺序串的类型描述如下串，顺序串的类型描述如下:public class SeqString implements IString private char strvalue;/存放串值存放串值 private int curlen;/存放串的长度存放串的长度 4.2.1 串的顺序存储结构 串的顺序存储结构与线性表的数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.2串的存储结构串的存储结构 其中：其中：strvaluestrvalue是一个字符数组，数组是一个字符数组，数组容量是容量是1111，该数组中存放字符串，该数组中存放字符串“I am a I am a dogdog，串的实际长度，串的实际长度curlencurlen的值是的值是1010。4.2.1 4.2.1 串的顺序存储结构串的顺序存储结构 其中：strvalue是一个字符数组，数组容量是11，该数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.2串的存储结构串的存储结构4.2.2 4.2.2 串的链式存储结构串的链式存储结构 串的链式存储结构和线性表的链式存储结串的链式存储结构和线性表的链式存储结构类似，可以构类似，可以采用单链表来存储串值采用单链表来存储串值，串的，串的这种链式存储结构称为链串。如下图这种链式存储结构称为链串。如下图:4.2.2 串的链式存储结构 串的链式存储结构和线性表的链数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring private char strValue;private int curLen;public SqStack()/构造一个空串构造一个空串 /以字符串常量构造串对象以字符串常量构造串对象 public SqStack(String str)stingValue=new char0;curLen=0;char tempchararray=str.toCharArray();strValue=tempchararray;curLen=tempchararray.length;4.3.1 顺序串的类定义（见教材P113-115）pub数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring public SqStack(char value)/以字符数组构造串对象以字符数组构造串对象 this.strValue=new charvalue.length;for(int i=0;i value.length;i+)/复制数组复制数组 this.strValuei=valuei;curLen=value.length;public void clear()/顺序串的置空函数顺序串的置空函数 curLen=0;4.3.1 顺序串的类定义（见教材P113-115）pub数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring return curLen;/判判空函数空函数public boolean isEmpty()/求顺序串长度函数求顺序串长度函数 public int length()/返回顺序串中第返回顺序串中第indexindex个字符个字符 public char charAt(int index)return curLen=0;if(index=curLen)throw new StringIndexOutofBoundsException(index);return strValuei;4.3.1 顺序串的类定义（见教材P113-115）pub数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring /扩充字符串的存储容量，参数指定容量扩充字符串的存储容量，参数指定容量 public void allocate(int newCapacity)char temp=srtValue;strValue=new charnewCapacity;for(int i=0;itemp.length;i+)strValuei=tempi;/截子串操作截子串操作public IString subString(int begin,int end)4.3.1 顺序串的类定义（见教材P113-115）pub数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring /串的插入操作串的插入操作public IString insert(int offset,IString str)/串的删除操作串的删除操作public IString delete(int begin,int end)/串的比较操作串的比较操作public int compareTo(IString str)/子串的定位操作子串的定位操作 public int indexOf(IString str,int begin)4.3.1 顺序串的类定义（见教材P113-115）pub数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现1.截子串操作截子串操作 subString(begin,end)的实现（的实现（P115/算法算法 4.1)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：a.a.检测参数检测参数beginbegin和和end end 是否合法是否合法 if(if(begin0begincurLenendcurLen|beginbegin=endend)抛出异常抛出异常1 1）操作要求：）操作要求：）操作要求：）操作要求：返回当前串中序号从返回当前串中序号从beginbegin至至end-1end-1的子的子串。起始下标串。起始下标beginbegin的范围是：的范围是：0beginlength()-10beginlength()-1；结束下标；结束下标endend的范围的范围是：是：1endlength()1endlength()。4.3.2 串的基本操作实现截子串操作 2）算法步骤：数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现char buffer=new charend-begin;for(int i=0;i buffer.length;i+)/复制子串复制子串 bufferi=this.strvaluei+begin;return new SeqString(buffer);if(begin=0&end=curLen)return this;else b.b.若要截取整个串，则返回原串；若要截取整个串，则返回原串；否则返回截取从否则返回截取从beginbegin到到end-1end-1之间的子串之间的子串 1.截子串操作截子串操作 subString(begin,end)的实现（的实现（P115/算法算法 4.1)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：char buffer=new charend-数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现char buffer=new charend-begin;for(int i=0;i 0|endend)throw new StringIndexOutOfBoundsException(参数不合法);char buffer=new charend-数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)1 1）操作要求：）操作要求：）操作要求：）操作要求：在当前串中第在当前串中第offsetoffset个字符之前插入串个字符之前插入串strstr，并返回结果串对象并返回结果串对象。其中：参数。其中：参数offsetoffset的有效范围是：的有效范围是：0offsetlength()0offsetlength()。当当offset=0offset=0，表示在当前串的，表示在当前串的开始处开始处插入插入串串strstr；当；当offset=length()offset=length()，表示在当前串，表示在当前串的的结尾处结尾处插入串插入串strstr。4.3.2 串的基本操作实现2.串的插入操作 1）操作要求数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现a.a.检测参数的合法性检测参数的合法性 2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：if(if(offset0offsetcurLenoffsetcurLen)抛出异常抛出异常b.b.判断空间是足够判断空间是足够:如果不足如果不足,则扩充空间则扩充空间,否则否则转转c cint len=str.length();/str串的长度串的长度int newcount=this.curLen+len;/插入后串的长度插入后串的长度if(newcountstrValue.length)allocate(newcount);c.c.后移：后移：将将strvaluestrvalue中从中从offsetoffset开始的所有字符开始的所有字符向后移动向后移动lenlen个位置个位置 （注意：要从后往前移动）（注意：要从后往前移动）for(int i=this.curLen-1;i=offset;i-)strValuei+len=strValuei;a.检测参数的合法性 2.串的插入操作 insert(off数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现d.d.插入：插入：将串将串strstr插入到指定的位置插入到指定的位置（用字符（用字符复制的方法）复制的方法）2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：for(int i=0;i len;i+)strValue offset+i=str.charAt(i);e.e.修正串长修正串长this.curLen=newcount;d.插入：将串str插入到指定的位置（用字符复制的方法）2数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现3 3）算法：）算法：）算法：）算法：public Istring insert(int offset,ISting str)/算法4.2结束if(offset this.curlen)throw new StringIndexOutOfBoundsException(“插入位置不合法);2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)int int len=str.length();/str串的长度串的长度int newcount=this.curLen+len;/插入后串的长度插入后串的长度if(newcountstrValue.length)allocate(newcount);for(int i=this.curLen-1;i=offset;i-)/后移后移 strValuelen+i=strvaluei;for(int i=0;i len;i+)/插入插入 strValue offset+i=str.charAt(i);this.curLen=newcount;/修正串长修正串长return this;3）算法：public Istring insert数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现3.串的删除操作串的删除操作 delete(begin,end)的实现（的实现（P117/算法算法 4.3)1 1）操作要求：）操作要求：）操作要求：）操作要求：在当前串中删除从在当前串中删除从beginbegin到到end-1end-1之间的子之间的子串，并返回当前串对象。串，并返回当前串对象。参数参数beginbegin和和endend的取值范围分别是：的取值范围分别是：0beginlength()-1 0beginlength()-1 1endlength()1endlength()。4.3.2 串的基本操作实现3.串的删除操作 1）操作要求数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现a.a.检测参数的合法性检测参数的合法性 3.串的删除操作串的删除操作 delete(begin,end)的实现（的实现（P117/算法算法 4.3)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：b.b.前移：前移：将将strvaluestrvalue中从中从endend开始到串尾的子串开始到串尾的子串 向前移动到从向前移动到从beginbegin开始的位置开始的位置for(int i=0;i curlen-end;i+)strValue begin+i =strValue end+i;if(if(begin0begincurLenendcurLen|beginbegin=endend)抛出异常抛出异常c.c.修正串长修正串长this.curLen=curLen-(end-begin);a.检测参数的合法性 3.串的删除操作 delete(beg数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现3 3）算法：）算法：）算法：）算法：public Istring delete(int begin,int end)/算法4.3结束if(begincurLen|beginend)throw new StringIndexOutOfBoundsException(“参数位置不合法);for(int i=0;i curlen-end;i+)strValue begin+i =strValue end+i;this.curLen=curLen-(end-begin);return this;3.串的删除操作串的删除操作 delete(begin,end)的实现（的实现（P117/算法算法 4.3)3）算法：public Istring delete数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现4.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)1 1）操作要求：）操作要求：）操作要求：）操作要求：将当前串与目标串将当前串与目标串strstr进行比较进行比较,若若:当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 strstr，则返回值，则返回值 0 0。4.3.2 串的基本操作实现4.串的比较操作 1）操作要求数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现a.a.求当前串长度和求当前串长度和strstr串长度的最小值并赋给串长度的最小值并赋给n n 3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：b.b.从下标从下标0 0到到n-1n-1依次取出两个串中对应的字符进依次取出两个串中对应的字符进 行比较，若不等，则返回第一个不相等的字符行比较，若不等，则返回第一个不相等的字符 的数值差。的数值差。for(int i=0;i n;i+)if(strValuei!=str.strValusei)return strValuei-str.strValusei;int len1=this.curlen;int len2=str.curlen;int n=Math.min(len1,len2);a.求当前串长度和str串长度的最小值并赋给n 3.串的比较数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)2 2）算法步骤：）算法步骤：）算法步骤：）算法步骤：c.c.若下标从若下标从0 0到到n-1n-1对应的字符均相等，则返对应的字符均相等，则返 回两个串长度的差。回两个串长度的差。return len1-len2;3.串的比较操作 compareTo(str)的实现（P11数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现3 3）算法：）算法：）算法：）算法：public int comparTo(IString str)/算法4.4结束3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)int len1=curlen;int len2=str.curlen;int n=Math.min(len1,len2);for(int i=0;i n;i+)if(strValuei!=str.strValusei)return strValuei-str.strValusei;return len1-len2;3）算法：public int comparTo(数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,beging)的实现（补充）的实现（补充）1）操作要求：）操作要求：在当前串中从在当前串中从beginbegin位置开始去找位置开始去找与与非空串非空串strstr相等的子串相等的子串,若查找成功则若查找成功则返回在当前串中的位置返回在当前串中的位置,否则返回否则返回-1,-1,其其中中:0beginlength()-1补充：补充：串的基本操作的应用串的基本操作的应用1.子串的定位操作 indexOf(str,beging)的数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,begin)的实现（补充）的实现（补充）可利用可利用串比较串比较、求串长和截子串等操、求串长和截子串等操作实现子串的定位操作作实现子串的定位操作indexOf(str,begin)。compareTo(substring(begin,begin+str.length()?0 this串 str 串串 str串串ibeginthis.legth()-str.length()+12 2）算法的基本思想：）算法的基本思想：）算法的基本思想：）算法的基本思想：1.子串的定位操作 indexOf(str,begin)的实数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,begin)的实现（补充）的实现（补充）3 3）算法）算法）算法）算法public int indexOf(IString Str,int bgein)while(i=0)return-1;/S中不存在与T相等的子串1.子串的定位操作 indexOf(str,begin)的实数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现2.串的置换操作串的置换操作 replace(begin,s1,s2)的实现（补充）的实现（补充）1）操作要求：）操作要求：在当前对象串在当前对象串this中，从下标中，从下标begin开始，将所有的开始，将所有的s1非空子串替换为非空子串替换为s2非非空空串。串。例如：例如：假设假设 this=abcaabcaaabca ，s1=bca 若若 s2=x ，则经置换后得到则经置换后得到 this=若若 s2=bc ，则经置换后得到则经置换后得到 S=axaxaax abcabcaabc 2.串的置换操作 replace(begin,s1,s2)的数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现2 2）算法的基本思想：）算法的基本思想：）算法的基本思想：）算法的基本思想：2.串的置换操作串的置换操作 replace(begin,s1,s2)的实现（补充）的实现（补充）source串 s1 串 s2 串 s2 串begin=index+s1.length()sub1indexss串串(初始是一个空串）初始是一个空串）sub2beginsource串串（初始为（初始为this串）串）2）算法的基本思想：2.串的置换操作 replace数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.3顺序串的实现顺序串的实现3）算法）算法2.串的置换操作串的置换操作 replace(begin,s1,s2)的实现（补充）的实现（补充）P148/习题三中的第习题三中的第2题，题，作为学生课后作业完成。作为学生课后作业完成。3）算法2.串的置换操作 replace(begin,s1,数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.4串的模式匹配操作串的模式匹配操作 这是串的一种重要操作，很多 软件，若有“编辑编辑”菜单项的话，则其中必有“查找查找”子菜单项。4.4 串的模式匹配操作串的模式匹配操作 这是串的一种重要操作，很多4.4 串的模数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.4串的模式匹配操作串的模式匹配操作操作条件：当前串操作条件：当前串this和和t串存在，串存在，t是非空是非空 串，串，0 start S.Length()-1。操作结果：操作结果：若串若串this中存在和串中存在和串t值相值相 同的子串返回它在同的子串返回它在this中中 第第start个字符之后第一次出个字符之后第一次出 现现的位置；否则函数的位置；否则函数 值为值为0。首先，回忆一下首先，回忆一下串匹配串匹配(查找查找)的定义的定义:index(t,start)4.4 串的模式匹配操作串的模式匹配操作操作条件：当前串this和t串存在，t是非空 首先，回忆一数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.4串的模式匹配操作串的模式匹配操作一、模式匹配的概念一、模式匹配的概念1 1、什么叫、什么叫模式匹配模式匹配 设设s,t s,t 是两个串，是两个串，s=s=s s0 0s s1 1s sn-1n-1,t=,t=t t0 0t t1 1t tm-1m-1(0mn)(0m=S.length()i=S.length()或或j=T.length(),j=T.length(),若若j=T.length()j=T.length()则匹配成功，则匹配成功，函数返回函数返回T T串在串在S S串串startstart位置之后首次出现的位位置之后首次出现的位序号值序号值,否则匹配失败否则匹配失败,函数返回函数返回-1-1。4.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）1）算法思想：用T串字符依次与S串字符比较，分别引进变量i和数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4.4串的模式匹配操作串的模式匹配操作int IndexOf(IString t,int start)/返回子串返回子串t在主串（当前串在主串（当前串this）中第）中第start个字符之个字符之后的位置。若不存在，后的位置。若不存在，则函数值为则函数值为-1。其中，。其中，t非空，非空，0startS.Length()-1。/算法4.5 结束2 2）算法：算法：int i=start,j=0,slen=this.length(),tlen=t.length();while (islen&j=tlen)return i-tlen;else return-1;时间复杂度：时间复杂度：O(slen*tlen)O(slen*tlen)4.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）int IndexOf(IString t,int st数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）作业布置作业布置作