《数据结构—Java语言描述》打卡第八天
- 💂 个人网站: 路遥叶子
- 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
- 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
- 💅 想寻找共同成长的小伙伴,请点击【Java全栈开发社区】
目录
第三章 串与数组
一、什么是串?
1. 串概述
2. 名词解释
3. 串的抽象类型(接口)
二、串的存储方式有那些?
三、顺序串
3.1 算法:基本功能
3.2 算法:扩容
3.3 算法:求子串
3.4 算法:插入
3.5 算法:删除
3.6 算法:比较
四、什么是模式匹配?
4.1 概述
4.2 Brute-Force算法:分析
4.3 Brute-Force算法:算法实现
4.4 KMP算法:动态演示
4.5 KMP算法:求公共前后缀
4.6KMP算法:求公共前后缀 next数组 -- 算法演示
4.7 KMP算法:求公共前后缀 next数组 -- 算法实现
4.8 KMP算法:算法实现
如果觉得文章对您有帮助,就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来,让我们一起加油学习。博主会不断推出更多优质文章哟
想要了解更多吗?没时间解释了,快来点一点!
第三章 串与数组
一、什么是串?
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 = 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 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 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 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;// 两个串的前缀相等}
------------------------------------------------------------------
四、什么是模式匹配?
4.1 概述
串的查找定位操作,也称为串的模式匹配操作。
主串:当前串,长度用n表示。
模式串:在主串中需要寻找的子串,长度用m表示。
模式匹配特点:
匹配成功,返回模式串的首字母在主串中的位序号(索引号)。
匹配失败,返回-1
模式匹配的常见算法:
Brute-Force算法:蛮力算法,依次比较每一个,比较次数多,时间复杂度O(n×m)
KMP算法:滑动算法,比较的次数较少,时间复杂度O(n+m)
4.2 Brute-Force算法:分析
第一趟:运行后的结果
第一趟 过渡 到第二趟
第二趟不匹配,直接 过渡 到第三趟
第三趟
第三趟过渡到第四趟
总结:核心算法(找主串的下一位)
4.3 Brute-Force算法:算法实现
/** this 主串* @param t 模式串* @param start 在主串中开始位置,例如:indexOf_BF("abcabc", 0)*/public int indexOf_BF(IString t, int start) { // 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; } int i = start , j = 0;// 1 声明变量 while( i<this.length() && j= t.length()) {//3.1 模式串已经循环完毕 return i - t.length();//3.2 匹配成功,第一个字母的索引号 } else { return -1;//3.3 匹配失败 }}
注解加强版
/** * this 主串 * @param t 模式串 * @param start 在主串中开始位置,例如:indexOf_BF("abcabc", 0) * @return */ //Brute-Force模式匹配算法 //返回模式串t在主串中从start开始的第一次匹配位置,匹配失败时返回-1 public int indexOf_BF ( IString t , int start) { //0.1非空校验:主串或模式串为空 if (this == null || t == null) { return -1; } //0.2范围校验 : 模式串长度=0 或 主串长度比模式串长度小 if (t.length() == 0 || this.length() < t.length()) { return -1; } //变量声明 //t是模式串,this表示当前主串 //当主串比模式串长时进行比较 int i = start; //i表示主串中某个子串的序号 int j = 0; // j 表示模式串当前字符的下标 int slen = this.length(); // slen 表示当前主串的长度 int tlen = t.length(); //tlen 表示当前模式串的长度 //循环条件:主串匹配的序号 < 主串的长度 ;或者 模式串当前字符下标j < 当前模式串的长度 //循环比较:主串和模式串都不能超过长度 while ((i < slen) && (j = 模式串的长度,即为匹配成功 if (j >= t.length()) { //匹配成功,返回子串序号 //返回模式串匹配成功的第一个字符在主串中的位置; // 即当前模式串最后一个字符在主串中的位置i - 模式串的长度 = 模式串匹配成功的第一个字符所在主串中的位置 return i - tlen; } else { return -1; } }
4.4 KMP算法:动态演示
核心思想:主串的指针 i 不会回退,通过滑动
模式串进行匹配。
滑动的原则:可以从最大公共前缀,直接跳 到最大公共后缀。
思考:ababa 最大公共前后缀是?
最大公共前缀:==aba==ba
最大公共后缀:ab==aba==
动态演示
第一趟:i 从 0 —> 2
遇到不匹配的数据时,需要移动模式串,当前公共部分是“ab”,没有最大公共前后缀。模式串从头开始
第二趟:i 从 2 —> 7
遇到不匹配的数据时,需要移动模式串,当前公共部分是“abcab”,有最大公共前后缀:
第三趟: i =7 位置数据不一致
遇到不匹配的数据时,需要移动模式串,当前公共部分是“ab”,没有最大公共前后缀。模式串从头开始
第四趟:数据不一致,i从 7—> 8
第五趟:i 从 8 —> 13,匹配成功
4.5 KMP算法:求公共前后缀
当我们准备求公共前后缀时,主串和模式串具有相同的内容,所以只需要看模式串。
实例1:模式串:"abcabc"
提前将模式进行处理(预判):将每一个字符假设不匹配时,公共前后缀提前记录下来,形成一个表格。
第一个位置:-1 (默认)
第二个位置:0 (默认)
使用next数组,记录统计好的表格。
实例2:"ababaaa"
4.6KMP算法:求公共前后缀 next数组 -- 算法演示
实例1:模式串:"abcabc" ; 前两个值默认为-1 和 0
第三位的数值 :
第四位的数值 :
第五位的数值 :
第六位的数值 :
处理完成 :
4.7 KMP算法:求公共前后缀 next数组 -- 算法实现
/** * 获得next数组 * @param T 模式串 * @return 返回next数组 */ public int[] getNext (IString T) { int[] next = new int[T.length()];//创建next[] 数组,与模式串字符个数一致 int j = 1 ; //主串指针 int k = 0 ; // 模式串指针(相同字符计数器) //2. 默认情况 next[0] = -1 ; next[1] = 0 ; //3. 准备比较 while (j < T.length() -1) { //比较倒数第二个字符 if (T.charAt(j) == T.charAt(k)) {//匹配,连续有字符相等 next[j+1] = k+1 ; j++ ; k++ ; }else if (k == 0 ) { //失配 next[j+1] = 0 ; j++ ; }else { // k不是0 k = next[k] ; } } //4 处理完成,返回数组 return next ; }
4.8 KMP算法:算法实现
//模式匹配的KMP算法 public int index_KMP (IString T , int start) { int[] next = getNext(T) ;//计算模式串的next[]的函数值 int i = start ; //主串指针 int j = 0 ;//模式串指针 //对两个串从左到右进行逐个比较字符 while ( i < this.length() && j < T.length()) { //若对应字符匹配 if (j == -1 || this.charAt(i) == T.charAt(j) ) { //j == -1 表示s[i] != T[0] i ++ ; j ++ ; }else { j = next[j] ;//模式串右移 } } if (j < T.length()) { return -1 ; //匹配失败 }else { return (i- T.length()) ; //匹配成功 } }
如果觉得文章对您有帮助,就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来,让我们一起加油学习。博主会不断推出更多优质文章哟
想要了解更多吗?没时间解释了,快来点一点!
《数据结构-Java语言描述》打卡第七天https://blog.csdn.net/zsy3757486/article/details/124001582?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第六天https://blog.csdn.net/zsy3757486/article/details/123894111?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第五天https://blog.csdn.net/zsy3757486/article/details/123862163?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第四天https://blog.csdn.net/zsy3757486/article/details/123846758?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第三天https://blog.csdn.net/zsy3757486/article/details/123810848?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第二天https://blog.csdn.net/zsy3757486/article/details/123786120?spm=1001.2014.3001.5502《数据结构-Java语言描述》打卡第一天https://blog.csdn.net/zsy3757486/article/details/123735691?spm=1001.2014.3001.5502