2017/06/21
1.串（String）
㈠'逻辑结构':
串是由零个或多个字符组成的有限序列，又名字符串
s = "a1a2...an"; (n>=0)
注意：串中字符的位置是从1开始的，
空串：零个字符的串，即值为：null， 其长度为 0
空格串：是只包含空格的串，是有内容长度的。这与空串不同，值为：""(长度为0), " "(长度为1), " "(长度为3)，等
(1)串的比较
通过组成串的字符之间的编码（即字符在对应字符集中的序号）来进行的。
计算机常用的字符集：
ASCII：早前用7位二进制数表示，总共表示128个字符, 后来扩展为8位二进制表示，总共表示256个字符（英语语言基本满足，其他语言可能不够）
Unicode：采用16位二进制表示，总共可以表示 2^16 个字符，65536个字符。
注意:为了兼容ASCII，其前256个字符和ASCII完全相同。
(2)串的抽象数据类型
串的逻辑结构和线性表很像，只是串的元素针对的是字符集，它们是一个个字符而已。
况且串更多的是看成一个整体的，如："123"，这是整体
线性表则更关注的是对单个元素的操作，比如查找一个元素，插入一个元素等
串中更多的是针对子串，比如查找 子串的位置，得到某个位置的子串等
基本操作：
① 串复制：将某个串复制给当前串
② 判空：若当前串为空，则返回true，否则返回false
③ 串比较：
④ 求串长：返回当前串的字符个数
⑤ 串连接：将s1和s2连接成一个新串，赋值给串T（即生成新的串）
⑥ 求子串：返回当前串中的第i个字符开始的长度为k的子串
⑦ 子串定位：返回子串在主串中首次出现的位置
⑧ 串替换：用子串x替换当前串中的子串y
⑨ 插入子串：将子串插入到当前串中的某个位置
⑩ 删除子串：从当前串中删除指定的子串
⑾ 大写转小写：
⑿ 小写转大写：
⒀ 串压缩：删除串中首尾处的空格
㈡'物理存储结构'
(1)串的顺序存储
与线性表一样，串的顺序存储结构是采用一组地址连续的存储单元来存储串中的字符序列，一般用数组来实现的
注意：这里采用的数组来实现串的顺序存储时，要注意可能是采用定长数组。这会在进行串连接、新串插入、替换等造成上溢截断，从而使数据不完整。因此，为了解决这个问题，使数组的长度在程序执行过程中被动态分配。
典型的例子,如计算机中的"堆",是自由存储区，可由C语言的动态分配函数malloc(), free() 来管理。
表示串的长度有三种常见的方式：
- 用一个变量来表示串的长度
- 在串尾存储一个不会在串中出现的特殊字符作为串的终结符。例如'\0'
- 用数组的0号单元存放串的长度，串值从1号单元开始存放
'代码实现'
public class MyString {
private int maxSize = 10; //串中字符数组的初始长度
private char[] chars; //存储字符的数组
private int lenght; //记录串的长度的变量，即上面讲的第一种方式
//1.初始化串: 采用默认长度
public MyString() {
this.chars = new String[maxSize];
this.length = 0;
}
public MyString(int n) {
this.maxSize = n;
this.chars = new String[maxSize];
this.length = 0;
}
//2.将串t复制给当前串，即调用该方法的字符串
public void copy(MyString t) {
}
//3.判空
public boolean isEmpty() {
return length == 0;
}
//4.串的比较
public int compare(MyString t) {
}
//5.求串的长度
public int getLength() {
return length;
}
//6. 清空当前串
public boolean clear() {}
//7.将指定串t连接到当前串的尾部
public void concat(MyString t) {}
//8.获得当前串的子串
public MyString subString(int pos, int len) {}
//
public MyString subString(int pos) {}
//9.返回子串t在当前串中首次出现的位置
public int index(Mystring t) {}
//10.返回子串t在当前串中最后一次出现的位置
public int lastIndext(MyString t) {}
//11.替换,用v代替所有与t相同的子串
public int replace(MyString t, MyString v) {}
//12.插入子串
public boolean insert(MyString s, int pos) {}
//13.删除子串
public boolean delete(int pos, int len) {}
//删除
public int remove(MyString s) {}
//14.转换为大写
public void toUpperCase() {}
//15.转换为小写
public void toLowerCase() {}
}
(2)串的链式存储结构
与线性表的链式结构表示相似，但由于串结构的每个元素数据是一个字符，如果此时采用在链表的每个结点处存储一个串的元素，就会造成大量的浪费(因为，每个结点的数据域对多个存储单元)
┌──┬──┬──┬──┬─┐ ┌──┬──┬──┬──┬─┐ ┌──┬──┬──┬──┬─┐
——> │ A│ B│ C│ D│-│——> │ E│ F│ G│ H│-│——> │I │J │ #│ #│^│
└──┴──┴──┴──┴─┘ └──┴──┴──┴──┴─┘ └──┴──┴──┴──┴─┘
因此，可以考虑在一个结点处存放多个字符(如上图)，最后一个结点若是未被占满，就用#，^等非串值字符补全
注意：串的链式存储结构在连接串与串的操作中有一定方便外，其他的一些操作灵活性不如顺序存储结构
㈢ '模式匹配'
在当前串中寻找某个子串的过程称为模式匹配，其中该子串称为模式串。如果成功，则返回子串在当前串中的首次出现的存储位置(或序号)，否则匹配失败。
模式匹配的算法：
1)朴素的模式匹配算法(简单的意思)
基本思想：
第 1 趟：首先将子串的第1个字符和主串的第1个字符比较，若相等，再比
较子串的第2个字符和主串的第2个字符的，
若相等再比较下一个, ....
若不相等，则进行下一趟的比较。
第 2 趟：将子串的第1个字符和主串的第2个字符比较....
...
第 i 趟：将子串的第1个字符和主串的第 i 个字符比较...
直到匹配成功或失败。
给该类算法取个名称：Brute(野蛮,粗鲁) Force, BF
此类算法低效，最坏情况：O((n-m+1)*m)
平均情况：O(n+m)
'代码实现'
/**
* @param s 主串
* @param t 子串
* @param pos 起始位置
* @return 返回子串在主串中首次出现的位置
* 注意：实际上字符的位置是从1开始，这里为了使用toCharArray()方便，将字符串转换为
* 字符数组，所以，字符的位置便从0开始的
*/
public static int index(String s, String t, int pos) {
//数据验证
if(pos < 0) {
System.out.println("输入的pos参数不合理，应该是大于等于0的数");
return -1;
} else if(pos >= (s.length() - t.length() + 1)){
System.out.println("输入的pos参数不合理");
return -1;
}
char[] chs = s.toCharArray();
char[] cht = t.toCharArray();
//完成正常的匹配任务
int i = pos; //控制大循环，即针对主串的
int j = 0; //针对子串的
while (i < (s.length() - t.length() + 1) && j < t.length()) {
if (chs[i] == cht[j]) {
//部分匹配成功
i ++;
j ++;
}else {
//匹配不成功,切换到主串的的下一个地方
//核心部分，仔细体会
i = i - j + 1; //返回到主串的这次起始位置的下一个位置
j = 0; //返回子串的起始位置（即开头处）
}
}
if (j == t.length()) {
return i-t.length() + 1; //返回子串的位置
}else {
return -1;
}
}
为了避免重复遍历，研究除了下面的算法：KMP算法，克努特-莫里斯-普拉特算法
2) KMP算法
核心思想：就是避免不必要的回溯（即重复遍历）,那么什么是不必要的回溯，主要是由模式串来决定的
next数组：
前缀是固定的，后缀是相对的
'代码描述':
/**
* KMP算法:核心是求取next数组，其大体框架同朴素算法
* 如果将数组的第一个存储单元拿来存储数组长度，则其变成就会简单一些，不过本质
* 都是一样的
* 注意：KMP的优化部分
* @author Administrator
*/
public class KMP {
/**
* 返回子串t在主串s中从pos之后首次出现的位置
*
* @param s
* @param t
* @param pos
* @return
*/
public int kmpIndex(String s, String t, int pos) {
// 数据验证
if (pos < 0) {
System.out.println("输入的pos参数不合理，应该是大于等于0的数");
return -1;
} else if (pos >= (s.length() - t.length() + 1)) {
System.out.println("输入的pos参数不合理");
return -1;
}
char[] chrs = s.toCharArray();
char[] chrt = t.toCharArray();
int i = pos; //控制主串,从 pos 之后开始检索
int j = 0; //控制子串，从子串的头部开始检索
//获取next数组
int[] next = getNext(t);
while(i < chrs.length && j < chrt.length) {
//注意：相对于朴素算法，这里要注意j的调整，有可能j变为-1，说明j指
// 到子串的外面去了。所以，当 j = -1 时需要修正
if(-1 == j || chrs[i] == chrt[j]) {
i++;
j++;
} else {
//i = i - j + 1; //在这里i就不用回溯了
j = next[j] - 1;
}
}
if(j == chrt.length) {
return i - chrt.length + 1;
}else {
return -1;
}
}
/**
* 计算next数组
* 字符的前后缀，如果有1个字符相等，则next数组对应的是2,有2个字符相等，就对应是3，即如果有k个字符相等，则对应的数组是(k+1)，
* @param t 为模式字符串
*/
private int[] getNext(String t) {
int[] next = new int[t.length()];
char[] chrs = t.toCharArray(); // 转换为数组，方便进一步操作
next[0] = 0;
// next[1] = 1;
int i = 0; // 控制后缀，只前进，不后退
int j = -1; // 控制前缀，自动调节后退的位置,等于-1时，是个特殊位置，要注意
while (i < t.length() - 1) {
if (j == -1 || chrs[i] == chrs[j]) {
i++;
j++;
/**
* 对next数组的优化部分:
* 这里出现了缺陷，如：aaaaax,还是会造成一些不必要的匹配操作，
* 因此。要对next数组的进行调整
*/
if(chrs[i] == chrs[j]) {
next[i] = next[j];
}else {
next[i] = j + 1;
}
} else {
// 不相等时,j得退回到上一次相等的地方
j = next[j] - 1;
}
}
return next;
}
// 打印数组
public void getPrint(int[] next) {
System.out.print("[");
for (int i = 0; i < next.length; i++) {
if (i == next.length - 1) {
System.out.println(next[i] + "]");
} else {
System.out.print(next[i] + ", ");
}
}
}
}
