3.1 串抽象数据类型 3.2 串的存储和实现 3.3 串的模式匹配 目的：串作为特殊线性表的实现与应用。 要求：掌握串的操作特点和实现方法， 掌握两种串的模式匹配算法。 重点：串的各种操作实现，两种串的模式 匹配算法。 难点：KMP模式匹配算法。
串的基本概念 串定义。s= " " 子串。"at"是"data"的子串。 串比较。比较相等，比较大小。
串的顺序存储结构
串的链式存储结构
（2）String类设计特点
最终类，不能被继承。
常量串，字符数组存储见图3.1（a），串尾没有' '。
最终变量，字符只读。当构造串对象时，对字符数组进行一次赋值，其后不能更改。只有charAt(i)取字符操作，不提供修改字符、插入串、删除子串操作。
构造串、求子串和连接串，深拷贝，重新申请字符数组，复制字符数组，不改变原串。
//trim()的实现 public MyString trim() //返回删除所有空格后的字符串 { char temp[]=new char[this.value.length]; int j=0; for (int i=0; i<this.value.length; i++) if (this.value[i]!=' ') temp[j++]=this.value[i]; return new MyString(temp,0,j); //以temp数组中从0开始的j个字符构造串对象 }
//反转字符串
public static String reverse2(String str) { char[] buffer = new char[str.length()]; //字符数组 for (int i=0; i<str.length(); i++) //复制str串一遍 buffer[str.length()-i-1] = str.charAt(i); return new String(buffer); //由buffer字符数组构造串，复制buffer一遍 }
Integer
//（3）将整数转换为radix进制字符串 //以下补码 public static String toHexString(int value) //返回整数value的十六进制补码字符串。采用位运算 { char[] buffer = new char[8]; //一个int有8个十六进制位 for (int i=buffer.length-1; i>=0; i--) //循环执行8次，高位补0 { int bit = value & 15; //获得十六进制的个位 buffer[i]=(char)(bit<=9 ? bit+'0' : bit+'a'-10); //将0～9、10～15转换为'0'～'9'、'a'～'f' value>>>=4; //右移4位，高位填充0，即value除以16 } return new String(buffer); //返回由字符数组构造的字符串 } //以下【思考题3-2】 MyInteger类声明以下静态成员方法。 public static String toBinaryString(int value) //返回整数value的二进制补码字符串。采用位运算 { char[] buffer = new char[32]; //一个int有32个二进制位 for (int i=buffer.length-1; i>=0; i--) //循环执行32次，高位补0 { buffer[i]=(char)((value & 1)+'0'); //获得个位字符存入数组。&运算符优先级低于+ value>>>=1; //value右移一位，高位以0填充，即value除以2 } return new String(buffer); //返回由字符数组构造的字符串 } public static String toOctalString(int value) //返回整数value的八进制补码字符串。采用位运算 { char[] buffer = new char[32/3+1]; //一个int有11个八进制位 for (int i=buffer.length-1; i>=0; i--) //循环执行11次，高位补0 { buffer[i] = (char)((value & 7)+'0'); //获得个位字符存入数组。&运算符优先级低于+ value>>>=3; //右移3位，高位以0填充，即value除以8 } return new String(buffer); //返回由字符数组构造的字符串 }
设有两个串：目标串target和模式串pattern，在目标串target中查找与模式串pattern相等的一个子串并确定该子串位置的操作称为串的模式匹配。 3.3.1 Brute-Force算法 3.3.2 模式匹配应用 3.3.3 KMP算法