4. 串与数组
4.1 串概述
- 串，也称为
字符串，是一个种特殊的线性表，由n（n>=0）个字符组成的有序序列。 - 名词解释
- 长度：包含的字符个数n。
- 空串：n为0的串就是空串，不包含任何字符。
- 空白串：包含一个及以上（n>=1）空白字符的串，长度为空白字符的个数。
- 子串：串中任意连续的字符组成的子序列。
- 空串是任意串的子串。
- 任意串是其自身的子串。“ABC”
- 主串：包含子串的串。
- 序号值：在之前的学习过程中称为“索引值”，字符在串中的位置。
- 子串在主串中的位置：子串在主串中首次出现时的第一个字符在主串中的位置。
- 串相等：两个串的长度相同，且各个对应位置的字符相同。
- 串的抽象类型（接口）
publicinterfaceIString{ publicvoidclear(); //串的清空publicbooleanisEmpty(); //是否为空publicintlength(); //串的长度，串中字符的个数publiccharcharAt(index); //返回第index个字符值publicIStringsubstring(begin,end); //*获得子串[begin,end)publicIStringinsert(offset, str); //在第offset个字符之前插入str串publicIStringdelete(begin, end); //删除子串[begin,end)publicIStringconcat(IStringstr); //*把str串连接到当前串的后面publicintcompareTo(IStringstr); //串的比较，相同返回0，否则返回正/负publicintindexOf(str, begin); //从start开始，返回str在串中位置，不存在返回-1}
4.2 串的存储
- 串的存储结构包括：顺序存储 和 链式存储。
- 顺序存储：使用数组存放字符。
publicclassSeqStringimplementsIString{ privatechar[] strvalue; // 字符数组，用于存放字符串信息privateintcurlen; // 串的长度 current length}
链式存储：使用链表存储。
- 字符链表：每个结点只有一个字符的链表。
- 块链表：每个结点可以有多个字符。
4.3 顺序串
4.3.1 算法：基本功能
publicclassSeqStringimplementsIString{ privatechar[] strvalue; // 字符数组，用于存放字符串信息privateintcurlen; // 串的长度 current lengthpublicvoidclear() { //清空this.curlen=0; } publicbooleanisEmpty() { //是否有空returnthis.curlen==0; } publicintlength() { //串的长度returnthis.curlen; } publiccharcharAt(intindex) { if(index<0||index>=curlen) { thrownew字符串索引越界异常(); //String Index OutOfBounds Exception } returnstrvalue[index]; } }
4.3.2 算法：扩容
/*** @param newCapacity 新容器大小*/publicvoidallocate(intnewCapacity) { char[] temp=strvalue; // 存放原来的数据 ab数组strvalue=newchar[newCapacity]; // 给strValue重新赋一个更大数组的值for(inti=0; i<temp.length; i++) { // 拷贝数据strvalue[i] =temp[i]; } }
4.3.3 算法：求子串
- 需求："abcd".substring(1,3) --> "bc"
publicIStringsubstring(intbegin , intend) { // 1 两个参数校验if(begin<0) { // 1.1 begin 不能小于0thrownewStringIndexOutOfBoundsException("begin不能小于0"); } if(end>curlen) { // 1.2 end 不能大于当前长度thrownewStringIndexOutOfBoundsException("end不能大于当前长度"); } if(begin>end) { // 1.3 thrownewStringIndexOutOfBoundsException("begin不能大于end"); } // 2 优化：当前串直接返回if(begin==0&&end==curlen) { returnthis; } // 3 核心算法char[] buffer=newchar[end-begin]; // 构建新数组for(inti=0 ; i<buffer.length ; i++) { // 依次循环遍历新数组，一个一个赋值buffer[i] =strvalue[i+begin]; } returnnewSeqString(buffer); // 使用字符数组构建一个新字符串}
4.3.4 算法：插入
/** "abcdef".insert(2,"123").insert(...)* @param offset 偏移量，插入的位置* @param str 插入数据*/publicIStringinsert (intoffset, IStringstr) { //1 校验if(offset<0||offset>curlen) { thrownewStringIndexOutOfBoundsException("插入位置不合法"); } //2 兼容：如果容器不够，需要扩容 当前长度 + 新字符串 > 容器长度intnewCount=curlen+str.length(); if( newCount>strvalue.length ) { allocate(newCount); //扩容结果就是刚刚好，没有额外空间 } // 3 核心//3.1 核心1：从offset开始向后移动 str长度 个字符for(inti=curlen-1 ; i>=offset ; i--) { strvalue[i+str.length() ] =strvalue[i]; } //3.2 核心2：依次插入for(inti=0; i<str.length() ; i++) { strvalue[i+offset] =str.charAt(i); } //3.3 设置数组长度this.curlen=newCount; returnthis; }
4.3.5 算法：删除
/*** @param begin 删除开始位置(含)* @param end 删除结果位置(不含)*/publicIStringdelete(intbegin , intend) { // 1 校验// 1.1 begin 范围if(begin<0) { thrownewStringIndexOutOfBoundsException("begin不能小于0"); } // 1.2 end 范围if(end>curlen) { thrownewStringIndexOutOfBoundsException("end不能大于串长"); } // 1.3 关系if(begin>end) { thrownewStringIndexOutOfBoundsException("begin不能大于end"); } // 2 核心：将后面内容移动到签名// 2.1 移动for(inti=0 ; i<curlen-end ; i++) { strvalue[i+begin] =strvalue[i+end]; } // 2.2 重新统计长度 (end-begin 需要删除串的长度)curlen=curlen- (end-begin) returnthis; }
4.3.6 算法：比较
/*** @param str 需要比较的串* return * >0 : 前面串值的值大于后面串* =0 : 前面串值的值等于后面串* <0 : 前面串值的值小于后面串*/publicintcompareTo(SeqStringstr) { intn=Math.min(curlen, str.curnlen) ; // 获得最短串的长度intk=0 ; // 循环遍历kchar[] s1=strvalue; char[] s2=str.strvalue; while(k<n) { if(s1[k] !=s2[k]) { // 处理前缀不一致returns1[k] -s2[k]; } k++; } returncurlen-str.curlen; // 两个串的前缀相等}
4.4 模式匹配【难点】
4.4.1 概述
- 串的查找定位操作，也称为串的模式匹配操作。
- 主串：当前串，长度用n表示。
- 模式串：在主串中需要寻找的子串，长度用m表示。
- 模式匹配特点：
- 匹配成功，返回模式串的首字母在主串中的位序号（索引号）。
- 匹配失败，返回-1
- 模式匹配的常见算法：
- Brute-Force算法：蛮力算法，依次比较每一个，比较次数多，时间复杂度O(n×m)
- KMP算法：滑动算法，比较的次数较少，时间复杂度O(n+m)
4.4.2 Brute-Force算法：分析
- 第一趟：运行后的结果
第一趟过渡到第二趟
4.4.3 Brute-Force算法：算法实现
/** this 主串* @param t 模式串* @param start 在主串中开始位置，例如：indexOf_BF("abcabc", 0)*/publicintindexOf_BF(IStringt, intstart) { // 0.1 非空校验if(this==null||t==null) { //0.1 主串或模式串为空return-1; } // 0.2 范围校验if(t.length() ==0||this.length() <t.length()) { //0.2模式串为空或比主串长return-1; } inti=start , j=0; // 1 声明变量while( i<this.length() &&j<t.length() ) { // 2 循环比较,主串和模式串都不能超过长度if(this.charAt(i) ==t.charAt(j)) { // 2.1 主串和模式串依次比较每一个字符i++; j++; } else { // 2.2 当前趟过渡到下一趟i=i-j+1; // 2.3 核心算法：主串中下一字符j=0; // 2.4 模式串归零 } } // 3 处理结果if(j>=t.length()) { //3.1 模式串已经循环完毕returni-t.length(); //3.2 匹配成功，第一个字母的索引号 } else { return-1; //3.3 匹配失败 } }
4.4.4 KMP算法：动态演示
- 核心思想：主串的指针i不会回退，通过
滑动模式串进行匹配。
- 滑动的原则：可以从最大公共前缀，直接跳到最大公共后缀。
- 思考：ababa 最大公共前后缀是？
- 最大公共前缀：==aba==ba
- 最大公共后缀：ab==aba==
- 第一趟：i 从 0-->2
遇到不匹配的数据时，需要移动模式串，当前公共部分是“ab”，没有最大公共前后缀。模式串从头开始
