【数据结构】串与数组（一）

2022-09-22 162

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】串与数组

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”，没有最大公共前后缀。模式串从头开始