【数据结构】串与数组

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];
    }
}

/**
* @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];
    }
}

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);                   // 使用字符数组构建一个新字符串
}

/**  "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;
}

/**
* @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;
}

/**
* @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;                 // 两个串的前缀相等
}

/** 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() ) {  // 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 模式串已经循环完毕
        return i - t.length();                  //3.2 匹配成功，第一个字母的索引号
    } else {
        return -1;                              //3.3 匹配失败
    }
}

/** 获得next数组
* @param T 模式串
* return 返回next数组
*/
public int[] getNext(IString T) {
    //1. 创建数组，与模式串字符个数一致
    int[] next = new int[T.length()];       
    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不是零
            k = next[k];                //p119 数学推导
        }
    }
    // 4 处理完成，返回数组
    return next;
}

/** this 当前串，也就是主串 (this.length() 主串长度)
* @param T 模式串 (T.length() 模式串长度)
* @param start 从主串中开始位置，例如："abaababaaa".index_KMP("ababaaa",0);
*/
public int index_KMP(IString T, int start) {
    //1 准备工作：next数组、指针
    int[] next = getNext(T);            //1.1 获得模式的next数组
    int i = start;                      //1.2 主串指针
    int j = 0;                          //1.3 模式串的指针
    //2 字符比较移动
    while(i<this.length() && j<T.length()) {    //2.1 串小于长度
        if(j == -1 ||                           //2.2.1 第一个字符不匹配，直接跳过
                this.charAt(i) == T.charAt(j)) {//2.2.2 字符匹配
            i++;
            j++;
        } else {
            j = next[j];                        //2.3 移动模式串
        }
    }
    //3 处理结果
    if(j < T.length()) {                //3.1 移动位置没有模式串长，不匹配
        return -1;
    } else {
        return i - T.length();          //3.2 匹配，目前在串后面，需要移动首字符
    }
}

A[1..8,1..10]  --> A[8×10]          //先行后列

A[0..8,1..10]   --> A[9×10]

a(8,5)  -->索引库1,1表示方式
需要将1,1转化成0,0方式，从而可以使用公式，i和j同时-1
a(7,4)  -->索引库0,0表示方式
因为：i >= j
k= i(i+1)/2 +j = 7 * 8 / 2 + 4 = 32
32为索引为0的一维数组的下标
数据b下标是从1开始，对应的下标 32+1=33

b[13] 下标从1开始，归零
b[12] 下标从0开始，k=12
i*(i+1)/2 , 如果i=4，结果为10
12-10 = j
下标0,0时，a(4,2)
下标1,1时，a(5,3)

/** this转置前的对象，每一个对象中都有一个data数据
*   tm 转置后的对象，每一个对象中都有一个data数据
* return 转置后的稀疏矩阵对象
*/
public SparseMatrix transpose() {       //转置
    // 1 根据元素个数，创建稀疏矩阵
    SparseMatrix tm = new SparseMatrix(nums);
    // 2 设置基本信息
    tm.cols = rows;                 //2.1 行列交换
    tm.rows = cols;                 //2.2 列行交换
    tm.nums = nums;                 //2.3 元素个数
    // 3 进行转置
    int q = 0;                                  //3.1 转置后数据的索引
    for(int col = 0 ; col < cols; col ++) {     //3.2 转置之前数据数组的每一个列号
        for(int p = 0; p < nums; p ++) {        //3.3 依次获得转置前数据数组的每一个数据
            if (data[p].column == col) {        //3.4 获得指定列的数据
                tm.data[q].row = data[p].column;    //3.5 行列交换，值不变
                tm.data[q].column = data[p].row;
                tm.data[q].value = data[p].value;
                q++;                                //3.6 转置后的指针后移
            }
        }
    }
    // 4 返回转置后的稀疏矩阵
    return tm;
}

public SparseMatrix fasttranspose() {
    // 1 根据元素个数，创建稀疏矩阵
    SparseMatrix tm = new SparseMatrix(nums);
    // 2 设置基本信息
    tm.cols = rows;                 //2.1 行列交换
    tm.rows = cols;                 //2.2 列行交换
    tm.nums = nums;                 //2.3 元素个数
    
    // 3 校验
    if(num <= 0) {
        return tm;
    }
    
    // 4 每一列的非零个数
    int num = new int[cols];            //4.1 根据列数创建num数组
    for(int i = 0; i<cols; i ++) {      //4.2 初始数据（可省略）
        num[i] = 0;
    }
    for(int i = 0; i< nums; i ++) {     //4.3 遍历转置的数据
        int j = data[i].column;
        num[j]++;
    }
    
    // 5 转置后每一列第一个元素的位置数组
    int cpot = new int[cols];           // 5.1 位置的数组
    cpot[0] = 0;                        // 5.2 第一列第一个元素为0
    for(int i = 1; i < cols ; i ++) {
        cpot[i] = cpot[i-1] + num[i-1]; // 5.3 当前列第一个元素位置 = 上一列位置+个数
    }
    
    // 6 转置处理
    for(int i = 0 ; i < nums ; i ++) {
        int j = data[i].column;             //6.1 转置前，每一个元素的列数
        int k = cpot[j];                    //6.2 转置后的位置
        tm.data[k].row = data[i].column;    //6.3 原数据 转置后 数据
        tm.data[k].column = data[i].row;
        tm.data[k].value = data[i].value;
        cpot[j]++;                          //6.4 下一个元素的位置
    }
    
}