数据结构串的概述与算法（一）：求子串、比较、删除、插入、扩容、模式匹配详解
第三章 串与数组
一、什么是串？
1. 串概述
串，也称为字符串，是一个种特殊的线性表，由n（n>=0）个字符组成的有序序列。
2. 名词解释
长度：包含的字符个数n。
空串：n为0的串就是空串，不包含任何字符。
空白串：包含一个及以上（n>=1）空白字符的串，长度为空白字符的个数。
子串：串中任意连续的字符组成的子序列。
空串是任意串的子串。
任意串是其自身的子串。“ABC”
主串：包含子串的串。
序号值：在之前的学习过程中称为“索引值”，字符在串中的位置。
子串在主串中的位置：子串在主串中首次出现时的第一个字符在主串中的位置。
串相等：两个串的长度相同，且各个对应位置的字符相同。
3. 串的抽象类型（接口）
public interface IString{ public void clear(); //串的清空 public boolean isEmpty(); //是否为空 public int length(); //串的长度，串中字符的个数 public char charAt(index); //返回第index个字符值 public IString substring(begin,end); //*获得子串[begin,end) public IString insert(offset, str); //在第offset个字符之前插入str串 public IString delete(begin, end); //删除子串[begin,end) public IString concat(IString str); //*把str串连接到当前串的后面 public int compareTo(IString str); //串的比较，相同返回0，否则返回正/负 public int indexOf(str, begin); //从start开始，返回str在串中位置，不存在返回-1 }
二、串的存储方式有那些？
串的存储结构包括：顺序存储 和 链式存储。
顺序存储：使用数组存放字符。
public class SeqString implements IString{ private char[] strvalue; // 字符数组，用于存放字符串信息 private int curlen; // 串的长度 current length }
链式存储：使用链表存储。
字符链表：每个结点只有一个字符的链表。
块链表：每个结点可以有多个字符。
三、顺序串
3.1 算法：基本功能
public class SeqString implements IString{ private char[] strvalue; // 字符数组，用于存放字符串信息 private int curlen; // 串的长度 current length public void clear() { //清空 this.curlen = 0; } public boolean isEmpty() { //是否有空 return this.curlen == 0; } public int length() { //串的长度 return this.curlen; } public char charAt(int index) { if(index < 0 || index >= curlen) { throw new 字符串索引越界异常(); //String Index OutOfBounds Exception } return strvalue[index]; } }
3.2 算法：扩容
/** * @param newCapacity 新容器大小 */ public void allocate(int newCapacity) { char[] temp = strvalue; // 存放原来的数据 ab数组 strvalue = new char[newCapacity]; // 给strValue重新赋一个更大数组的值 for(int i = 0; i < temp.length; i++) { // 拷贝数据 strvalue[i] = temp[i]; } }
3.3 算法：求子串
需求："abcd".substring(1,3) --> "bc"
public IString substring(int begin , int end) { // 1 两个参数校验 if(begin < 0) { // 1.1 begin 不能小于0 throw new StringIndexOutOfBoundsException("begin不能小于0"); } if(end > curlen) { // 1.2 end 不能大于当前长度 throw new StringIndexOutOfBoundsException("end不能大于当前长度"); } if(begin > end) { // 1.3 throw new StringIndexOutOfBoundsException("begin不能大于end"); } // 2 优化：当前串直接返回 if(begin == 0 && end == curlen) { return this; } // 3 核心算法 char[] buffer = new char[end - begin]; // 构建新数组 for(int i = 0 ; i < buffer.length ; i ++) { // 依次循环遍历新数组，一个一个赋值 buffer[i] = strvalue[i + begin]; } return new SeqString(buffer); // 使用字符数组构建一个新字符串 }
3.4 算法：插入
/** "abcdef".insert(2,"123").insert(...) * @param offset 偏移量，插入的位置 * @param str 插入数据 */ public IString insert (int offset, IString str) { //1 校验 if(offset < 0 || offset > curlen) { throw new StringIndexOutOfBoundsException("插入位置不合法"); } //2 兼容：如果容器不够，需要扩容 当前长度 + 新字符串 > 容器长度 int newCount = curlen + str.length(); if( newCount > strvalue.length ) { allocate(newCount); //扩容结果就是刚刚好，没有额外空间 } // 3 核心 //3.1 核心1：从offset开始向后移动 str长度 个字符 for(int i = curlen-1 ; i >= offset ; i --) { strvalue[i + str.length() ] = strvalue[i]; } //3.2 核心2：依次插入 for(int i = 0; i < str.length() ; i ++) { strvalue[i + offset] = str.charAt(i); } //3.3 设置数组长度 this.curlen = newCount; return this; }
3.5 算法：删除
/** * @param begin 删除开始位置(含) * @param end 删除结果位置(不含) */ public IString delete(int begin , int end) { // 1 校验 // 1.1 begin 范围 if(begin < 0) { throw new StringIndexOutOfBoundsException("begin不能小于0"); } // 1.2 end 范围 if(end > curlen) { throw new StringIndexOutOfBoundsException("end不能大于串长"); } // 1.3 关系 if(begin > end) { throw new StringIndexOutOfBoundsException("begin不能大于end"); } // 2 核心：将后面内容移动到签名 // 2.1 移动 for(int i = 0 ; i < curlen - end ; i ++) { strvalue[i + begin] = strvalue[i + end]; } // 2.2 重新统计长度 (end-begin 需要删除串的长度) curlen = curlen - (end-begin) return this; }
3.6 算法：比较
/** * @param str 需要比较的串 * return * >0 : 前面串值的值大于后面串 * =0 : 前面串值的值等于后面串 * <0 : 前面串值的值小于后面串 */ public int compareTo(SeqString str) { int n = Math.min(curlen, str.curnlen) ; // 获得最短串的长度 int k = 0 ; // 循环遍历k char[] s1 = strvalue; char[] s2 = str.strvalue; while(k < n) { if(s1[k] != s2[k]) { // 处理前缀不一致 return s1[k] - s2[k]; } k++; } return curlen - str.curlen; // 两个串的前缀相等 }