第五章、串、数组和广义表
5.1、串（也叫字符串）
5.5.1、串的定义—几个术语
1、定义
2、子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串
3、真子串：是指不包含自身的所有子串
4、主串：包含子串的串
5、字符位置：字符在序列中的序号为该字符在串中的位置
6、子串位置：子串第一个字符在主串中的位置
7、空格串：由一个或多个空格组成的串，与空串不同
8、例子
9、串相等：长度相等，各个对应位置上的字符都相同。
10、所有的空串都是相等的
5.2、案例引入
1、非数值处理。例如：文字编写，符号处理，信息处理系统
2、字符串查找
5.3、串的类型定义、存储结构及运算
5.3.1、字符串的类型定义
1、compareTo()：按字典顺序比较两个字符串大小
（1）例子：
String a = "Hello Word";
String b = "hello word";
System.out.println(a.compareTo(b));2、compareToIgnoreCase()：和上面一样，忽略大小写
3、length()：求字符串的长度
（1）例子：
String a = "Hello Word!";
System.out.println(a.length);4、concat() ：连接两个字符串
（1）例子：
String a = "Hello Word";
String b = "你好";
System.out.println(b.concat(a));5、subString()：截取字符串
（1）例子：
String a = "Hello Word";
System.out.println(a.substring(0, 2));6、copyValueOf() :复制字符串
（1）例子：
char[] Str1 = {'h','b'};
String Str2 = "";
Str2 = Str2.copyValueOf( Str1 );
System.out.println("返回结果：" + Str2);7、isEmpty()：判断字符串是否为空
（1）例子：
String myStr2 = "";
System.out.println("myStr2 是否为空：" + myStr2.isEmpty());8、indexOf(String str, int fromIndex)：
返回指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始。
（1）例子：
String string = "aaa456ac";
System.out.println(string.indexOf("b")); // indexOf(String str); 返回结果：-1，"b"不存在 9、replace() ：替换
String a = "Hello Word";
String b = "你好";
System.out.println(a.replace(a, b));10、insert()：任意位置添加
（1）例子：
StringBuffer stringBuilder1=new StringBuffer("20180918");
stringBuilder1.insert(6,"-");
stringBuilder1.insert(4,"-");5.3.2、串的存储结构
1、顺序存储结构
1、使用数组作为容器
2、定义长度，设置变量
3、java代码实现
public class SeqString {
/* 存放字符元素的数组 */
char[] data = new char[10];
/* 实际串长 */
int curlen = 0;
}2、链式存储结构
1、串存储密度较低，字符存储一个字节，下一个地址存储4个字节
2、解决方法啊，存储区块（多个字符一起存储）
3、示意图
4、java代码实现
public class LinkString {
// 头结点
Node head = new Node();
// 实际表长
int curlen;
// 结点内部类，也阔以设置单独类
private class Node {
public char c;
public Node next;
public Node() {
c = null;
next = null;
}
}
}5.3.3、串的模式匹配算法（BF)
1、算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）
2、算法应用
（1）搜索引擎、拼写检查、语言翻译、数据压缩
（2）算法种类
BF算法（暴力破解法、经典的、古典、穷举的）
KMP算法（特点：速度快）
1、BF算法
1、Brute-Force：简称BF算法，简单匹配算法，采用穷举的思想。
2、算法思路：从S的每一个字符开始依次与T的字符进行匹配。
3、示意图
4、匹配失败
（1） i=i-j+2=2(回溯)
（2） j=1(从头开始)
（3）其中i是目标串的位置，j是主串的位置
5、匹配成功
（1）返回：i-t.length=3
（2）例子
6、总结：Index（S,T,pos)
（1）将主串的第pos个字符和模式串的第一字符比较
（2）若相等，继续逐个比较后续字符
（3）若不等，从主串的下一个字符起，出现与模式串的第一个字符比较。
7、结果
2、BF算法实现
1、java代码实现
public class BF01 {
/**
* str主串
* sub子串
* pos要找的位置
*/
public static int BF01(String str ,String sub,int pos){
int strlen = str.length();
int sublen = sub.length();
// 对pos合法判断
if(pos<1 || pos>strlen){
return -1;
}
int i = pos;//遍历主串
int j = 0;//遍历子串
while ( i<strlen && j< sublen){
if(str.charAt(i)==sub.charAt(j)){//比较i和j是否相等
i++;
j++;
}else {//不相等则重置，j。并设置i
i = i-j +1;
j=0;
}
}
if(j>=sublen){//如果匹配成功，返回i的起始位置
return i-j;
}else {//没找到
return -1;
}
}
}3、时间复杂度、空间复杂度
1、时间复杂度
（1）定义n为主串长度，m为子串长度
（2）公式
（3）理解，主串-子串的长度，都要和子串m进行比较，并且最后一次也比较，+1
5.3.4、KMP算法
1、算法设计思路
2、理解
（1）next[j] = 比较最大公约数+1
（2）图示
2、java代码实现
public class KMP02 {
/**
* O(m+n)
*
* @param str 目标串
* @param sub 模式串
* @return 如果匹配成功，返回下标，否则返回-1
*/
static int kmpSearch(String str, String sub) {
int strLen = str.length();
int subLen = sub.length();
if (strLen < subLen) {//判断模式串是否大于目标串
return -1;
}
int[] next = getNext(sub);
// matching: O(n)
int i = 0, j = 0;
while (i < strLen && j < subLen) {
//①如果j = -1，或者当前字符匹配成功（即str[i] == sub[j]），都令i++，j++
if (j == -1 || str.charAt(i) == sub.charAt(j)) {
i++;
j++;
} else {
//②如果j != -1，且当前字符匹配失败（即str[i] != sub[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == subLen) {
return i - j;
} else {
return -1;
}
}
/**
* Table building: O(m)
*
* @param sub 匹配串
* @return
*/
private static int[] getNext(String sub) {
int len = sub.length();
int[] next = new int[len];
next[0] = -1;
int i = 0, k = -1;
while (i < len - 1) {
// p[k]表示前缀，p[i]表示后缀
if (k == -1 || sub.charAt(i) == sub.charAt(k)) {
++k;
++i;
next[i] = k;
} else {
k = next[k];
}
}
return next;
}
}5.4、数组
5.4.1、一维数组概念
5.4.2、二维数组概念
1、声明格式：数据类型 变量名称 【行数】 【列数】;
2、理解：二维数组就是一维数组中的元素是一个一维数组
3、数组的特点：结构固定—定义后，维数和维界不再改变。
4、数组的基本操作：结构初始化、和销毁、取元素、修改元素
5.4.3、数组的抽象数据类型定义
1、基本操作
1、构造数组
2、销毁数组
3、取出数组元素
4、给数组元素赋值
5、一般不做插入和删除操作
6、java代码实现（不是重点）
package Array_;
public class Array01 {
private int [] data;//存放数据
private int size;//计数器
// 数组初始化,构造器
public Array01( int capacity){
data = new int[capacity];//定义初始化
size = 0;
}
// 获取尺寸
public int getSize(){
return size;
}
// 获取数组的容量
public int getCapacity(){
return data.length;//
}
// 判断当前数组是否为空
public boolean isEmpty(){
if (size==0){
return true;
}
return false;
}
}5.4.4、数组的顺序存储
1、两种顺序存储方式
1、以行序为主序（图解）
2、以列序为主序（图解）
2、二维数组的行序优先表示
1、以行序为主序，计算a[i][j]存储位置
5.4.4、三维数组
1、理解
2、n维数组
5.4.5、特殊矩阵的压缩存储
1、介绍和特点
2、压缩存储
（1）多个数据元素的值相同，则只分配一个元素值的存储空间，且0元素不占存储空间
3、什么样的矩形能够压缩？
（1）对称矩阵、对角矩阵、三角矩阵、稀疏矩阵
2、对称矩形
1、特点和存储方法（n为行）
2、判断
（1）设置i为行，j为列
（2）当i>=j时（行大于列）：i*(i-1)/2+j-1
（3）当j>=i时（行大于列）： j*(j-1)/2+i-1
3、例子
package Array_;
public class SMA02 {
public static void main(String[] args) {
SMA02 matrix = new SMA02();
matrix.init();
matrix.printMatrix();
matrix.printSA();
int result = matrix.find(0, 0);
System.out.println();
System.out.println(result);
}
private static final int N = 3;//这个是阶层
int[][] a = new int[N][N];//数组元素的具体位置
int[] SA = new int[N * (N + 1) / 2];//用于存储数组元素
public void init(){//根据初始化数组SA
for(int i=0; i<N; i++){
for(int j=0;j<=i;j++){
a[i][j] = a[j][i] = i+j;//三者相等
}
}
int count = 0;
for(int i=0;i<N; i++){
for(int j=0;j<=i;j++){
SA[count] = a[i][j];
count++;
}
}
}
public void printMatrix(){//public printMatrix 打印对称矩阵
for(int i=0; i<N; i++){
for(int j=0;j<N;j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}
}
public int find(int i,int j){//public find(int i, int j) 查找矩阵中第i行第j列的元素，查找对象SA
return SA[i*(i+1)/2+j];
}
public void printSA(){
for (int i : SA) {
System.out.print(i+" ");
}
}
}3、三角矩阵
5.5、广义表
1、广义表又称为（List）是n>=0的元素a1~an的有限序列，其中每一个ai或者是原子，或者是一个广义表
2、拓宽的线性表就是广义表
5.5.1、广义表概念
1、概念
2、性质
1、广义表的中的数据元素是相对次序；有一个直接前驱和一个直接后继。
2、广义表的长度定义为最外层所包含的元素个数。
3、广义表的深度定义为该广义表展开后所含括号的重数。
4、广义表可以为其他广义表所共享。
5、广义表可以是一个递归的表。
6、递归表的深度是无穷值，长度是有限的。
7、广义表是多层次结构，广义表的元素可以是单元素，多元素，或者是一个广义表。
5.5.2、广义表与线性表的区别
1、广义表可以看成是线性表的推广、线性表是广义表的特例。
（1）广义表相当灵活，兼容线性表、数组、树、和有向图等。
2、二维数组的每行（或每列）作为字表处理时，二维数组即为一个广义表。
3、数和有向图也可以用广义表表示。
5.5.3、广义表的基本运算
1、求表头
1、非空广义表的第一个元素，可以是个元素，也可以是一个字表。
2、求表尾
1、非空广义表除去表头元素以外元素所构成的表，表尾一定是一个表。
3、例子
5.5.4、广义表的链式存储
5.5.5、案例分析与实现
1、案例：病毒感染检测
2、分析
1、因为是由一些字符串组成的序列，相当于匹配字符串模式。
2、可以利用BF算法，或者KMP算法。
3、本次病毒的DNA是环状的。
4、需要对传统的KMP和BF算法改进。
3、解析
