狠狠撸

第 3 章串
? 3.1 串抽象数据类型
? 3.2 串的表示和实现
? 3.3 串的模式匹配

目的和要求
? 目的：串作为特殊线性表的实现与应用。
? 内容：字符串的基本概念，串抽象数据类型，
顺序和链式两种存储结构存储串的特点；采用
顺序存储结构实现串的各种操作算法；两种串
的模式匹配算法及应用： Brute-Force 算法和
KMP 算法。
? 要求：掌握顺序串类的基本操作实现方法，掌
握串的模式匹配算法及应用。
? 重点：串数据类型的各种操作实现，两种串的
模式匹配算法及应用。
? 难点： KMP 模式匹配算法， next 数组在 KMP
算法中的作用及产生过程。
? 实验：顺序串类的基本操作及串的模式匹配算

《数据结构（ Java 版）（第 3 版）》
3.1 串抽象数据类型
3.1.1 串的基本概念
1. 串定义。 s= " "
2. 子串。 "at" 是 "data" 的子串。
3. 串比较。
两个串可比较是否相等，也可比较大小。
110 ?nsss ?

public interface SString
{ int length(); // 返回串的长度
char charAt(int i) // 返回第 i （ i≥0 ）个字
符
SString concat(SString str); // 返回与 str 串连接生成
串
SString substring(int begin, int end);
// 返回串中字符序号从 begin 至 end-1 的
子串
void setCharAt(int i, char ch) // 设置第 i 个字符为
ch
SString insert(int i, SString str)// 在第 i 个字符处插入
str 串
3.1.2 串抽象数据类型

3.2 串的表示和实现
3.2.1 串的存储结构
3.2.2 字符串类 String
3.2.3 字符串类 StringBuffer

3.2.1 串的存储结构
1. 串的顺序存储结构
2. 串的链式存储结构

3.2.2 常量字符串类 String
1. String 类声明
public final class MyString implements
Comparable<MyString>,java.io.Serializable
{
private final char[] value;
// 字符数组，私有最终变量，只能赋值一
次
}

【例 3.1 】获得整数和实数字
符串表示的数值。

2. 连接串

3. 求子串

4. 比较串相等与大小

5. String 串的插入、删除操
作
（ 1 ）在 s1 串的 i 位置插入 s2 串

（ 2 ）删除串中序号从 begin
至 end-1 的子串
【例 3.2 】获得一个整数的二进制或十六
进制形式字符串。

3.2.3 变量字符串类
StringBuffer
public final class MyStringBuffer
implements java.io.Serializable
{
private char[] value; // 字符数
组
private int len; // 串长
度
}

1. 插入串

2. 删除子串

3.3 串的模式匹配
3.3.1 Brute-Force 算法
3.3.2 KMP 算法

3.3.1 Brute-Force 算法
1. Brute-Force 算法描述与实现

2. 模式匹配应用
（ 1 ）替换子串

（ 2 ）删除子串

3. Brute-Force 算法分析

3.3.2 KMP 算
法
1. 目标串不回溯

2. KMP 算法描述（ a ）
（ b ）

2. KMP 算法描述（ c ）

2. KMP 算法描述（ d ）

3. 求 next 数组
表 3-1 模式串 "abcabc" 的 next 数组
j 0 1 2 3 4 5
模式串 a b c a b c
" " 中最长相
同前后缀子串的长度
k
?1 0 0 0 1 2
0 1 1
1 0
[ ]
0?? ?? ????" ... " " ... "??×??ó ????k j k j
j
next j
k k j p p p p? ? ?
? =??
= ?
=??
4. KMP 算法实现
110 ?jppp ?

5. 计算 next 数组的递推算
法
表 3-2 模式串 "abcabdabcabcaa" 的 next
数组
"
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13
模式串 a b c a b d a b c a b c a a
"p0…pj?1" 中最长
相同的前后缀子串
长度 k
-1 0 0 0 1 2 0 1 2 3 4 5 3 4

6. 改进 next 数组

6. 改进 next 数组
表 3-3 模式串 "abcabc" 改进的 next 数组
j 0 1 2 3 4 5
模式串 a b c a b c
"p0
…pj?1
" 中最长相同的前
后缀子串长度 k
?1 0 0 0 1 2
pk
与 pj
比较 ≠ ≠ = = =
改进的 next[j] ?1 0 0 ?1 0 0

图 3-18 KMP 模式匹配过程（ a ～
b ）

图 3-18 KMP 模式匹配过程（ c
～ e ）

表 3-4 　模式
串 "abcabdabcabcaa" 改进的
next 数组
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13
模式
串
a b c a b d a b c a b c a a
串长 k -1 0 0 0 1 2 0 1 2 3 4 5 3 4
比较 ≠ ≠ = = ≠ = = = = = ≠ = ≠
改进
的
next[j]
-1 0 0 -1 0 2 -1 0 0 -1 0 5 -1 4

7.KMP 算法分析

狠狠撸

第03章串(java版)

More Related Content

第03章串(java版)

狠狠撸

第03章 串(java版)

More Related Content

第03章 串(java版)

第03章串(java版)

第03章串(java版)