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

4.4.5 KMP算法：求公共前后缀 next数组 -- 推导

• 当我们准备求公共前后缀时，主串和模式串具有相同的内容，所以只需要看模式串。
  
• 实例1：模式串："abcabc"
  
• 提前将模式进行处理（预判）：将每一个字符假设不匹配时，公共前后缀提前记录下来，形成一个表格。
  
• 第一个位置：-1
  
• 第二个位置：0
  
• 使用next数组，记录统计好的表格。
  

4.4.6 KMP算法：求公共前后缀 next数组 -- 算法演示

• 实例1：模式串："abcabc"
  

4.4.7 KMP算法：求公共前后缀 next数组 -- 算法

/** 获得next数组* @param T 模式串* return 返回next数组*/publicint[] getNext(IStringT) {
//1. 创建数组，与模式串字符个数一致int[] next=newint[T.length()];       
intj=1;                              // 串的指针intk=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++;
        } elseif (k==0) {
next[j+1] =0;
j++;
        } else {        //k不是零k=next[k];                //p119 数学推导        }
    }
// 4 处理完成，返回数组returnnext;
}

4.4.8 KMP算法：next数组使用

• 主串：ababababaaa
  
• 模式串：ababaaa

• next数组
  

4.4.9 KMP算法

/** this 当前串，也就是主串 (this.length() 主串长度)* @param T 模式串 (T.length() 模式串长度)* @param start 从主串中开始位置，例如："abaababaaa".index_KMP("ababaaa",0);*/publicintindex_KMP(IStringT, intstart) {
//1 准备工作：next数组、指针int[] next=getNext(T);            //1.1 获得模式的next数组inti=start;                      //1.2 主串指针intj=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 {
returni-T.length();          //3.2 匹配，目前在串后面，需要移动首字符    }
}

4.5 数组

4.5.1 概述

• 数组：一组具有相同数据类型的数据元素的集合。数组元素按某种次序存储在一个地址连续的内存单元空间中。
  
• 一维数组：一个顺序存储结构的线性表。[a0,a1,a2, ....]
  
• 二维数组：数组元素是一维数组的数组。[ [] , [] , [] ] 。二维数组又称为矩阵。

4.5.2 数组的顺序存储（一维）

• 多维数组中，存在两种存储方式：

• 以行序为主序列的存储方式（行优先存储）。大部分程序都是按照行序进行存储的。
  
• 以列序为主序列的存储方式（列优先存储）
  

• 一维数组内存地址
• Loc(0) ：数组的首地址
  
• i ： 第i个元素
  
• L ：每一个数据元素占用字节数
  

4.5.3 数组的顺序存储（二维）

1）行序

• 行序：使用内存中一维空间（一片连续的存储空间），以行的方式存放二维数组。先存放第一行，在存放第二行，依次类推存放所有行。
  

二维数组（n×m）内存地址（以==行序==为主序列）

• Loc(0,0) ：二维数组的首地址
  
• i ： 第i个元素
  
• L ： 每一个数据元素占用字节数
  
• m：矩阵中的列数

注意：

• 如果索引号不是从0开始，不能使用此公式。
  
• 如果索引号不是从0开始的，需要先将索引号归零，再使用公式。
  

2）列序

• 列序：使用内存中一维空间（一片连续的存储空间），以列的方式存放二维数组。先存放第一列，再存放第二列，依次类推，存放所有列。
  

二维数组（n×m）内存地址（以==列序==为主序列）

3）练习

• 实例1：

有一个二维数组A[1..6,0..7]，每一个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ ==D== ）个字节。

A. 48

B. 96

C. 252

D. 288

实例2：

设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以==列序==为主顺序存放，则数组元素A[5,8]的存储首地址为（ ）。

A. BA + 141

B. BA + 180

C. BA + 222

D. BA + 225

• 例如3：
  

设有数组A[0..8,1..10]，数组的每个元素占5字节，数组从内存首地址BA开始以==列序==为主顺序存放，则数组元素A[7,8]的存储首地址为（ BA + 350 ）。