04 第04章 串.pptx

第1页：第四章串封面

本页为第四章串封面。本章讲解串（字符串）这一数据元素受限的线性表，以及 C# 中的 String、StringBuilder 类型和 BF、KMP 两种模式匹配算法。

第2页：串的引入

串又称为字符串，是一种特殊的线性表。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象为字符集。

串的基本操作和线性表有很大区别：在线性表操作中，大多以“单个元素”作为操作对象；而在串的基本操作中，通常以“串的整体”作为操作对象。

第3页：串的定义

串又称为字符串，它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符。

人们经常又这样定义串：串是由零个或多个字符组成的有限序列。串一般记作 s=“a1a2···an”（n≥0），其中 s 是串的名称，用一对双引号括起来的字符序列是串的值。

第4页：串的基本术语

空串

不含任何字符的串称为空串

空格串

由一个或多个空格组成的串，称为空格串

串相等

两个串的长度相等且对应的字符相等

模式匹配

确定子串在主串中首次出现位置的运算

子串

串中任意个连续的字符组成的子序列称为该串的子串

主串

包含子串的串称为该子串的主串

第5页：String 类型

C# 中使用 System.String 类型表示字符串。String 类型是 .NET 中使用最频繁、应用最广泛的基本类型，因此 CLR 有针对性地对其性能采取了特殊的解决办法，这使得 String 成为一个很特殊的类型。

第6页：String 的不可变性

String 对象最重要的一个特点是：它是不可变的（immutable）。也就是说，字符串在创建之后就再也不能改变。

任何对 String 的修改操作都会在托管堆中创建新的 String 对象。

第7页：不可变性的优点

String 对象不可变性的优点：

• 保证对 String 对象的任意操作不会改变原字符串
• 在操作或访问一个字符串时不会发生线程同步问题
• 对于相同字符串，可以不为它们分配内存块，而使它们共享一块内存，这样能减少系统中字符串的数量，从而节省内存

第8页：不可变性的缺点

String 对象不可变性的缺点：会在堆上创建大量的 String 对象，造成频繁的垃圾收集，从而妨碍应用程序的性能。

第9页：StringBuilder 可变字符串

与 String 不同，System.Text.StringBuilder 代表的是一个可变的字符串。也就是说 StringBuilder 中的大多数操作在更改字符数组内容的同时不会造成在托管堆上分配新的对象。

例 4-1 Demo4-1.cs 给出了 String 和 StringBuilder 的性能对比。

第10页：Brute-Force 算法

Brute-Force 算法简称 BF 算法，也称为简单匹配算法。它用主串指针 i 和模式串指针 j 逐位比较：相等则同时后移，不等则 i 回溯到本次起始位置的后一位、j 回到模式串起点重新开始比较。

第11页：BF 算法的效率

BF 算法简单，易于理解，但算法效率不高。原因在于匹配失败时主串指针 i 需要回溯，模式串指针 j 也要退回起点，已经比较过的字符被反复比较。

第12页：KMP 算法的提出

KMP 算法是由 D.E.Knuth 与 J.H.Morris、V.R.Pratt 共同提出的，所以称为 Knuth-Morris-Pratt 算法，简称 KMP 算法。

它通过预先求解模式串每个字符的 k 值，使匹配失败时模式串指针按 k 值滑动，主串指针不再回溯。

第13页：模式串abcabca的k值

模式串 abcabca 的 k 值表：下标、子串与 k 值对应如下。

模式串 k 值的约定：① k=-1，只有模式串的第 1 个字符的 k 值为 -1；② k>0，表示指定字符前面 k 个字符和模式串的头 k 个字符相等；③ k=0，其他情况。模式串的第 2 个字符的 k 值必为 0。

第14页：模式串abcababcaacb的k值

模式串 abcababcaacb 的 k 值表：下标、子串与 k 值对应如下。

模式串 k 值的约定：① k=-1，只有模式串的第 1 个字符的 k 值为 -1；② k>0，表示指定字符前面 k 个字符和模式串的头 k 个字符相等；③ k=0，其他情况。模式串的第 2 个字符的 k 值必为 0。

第15页：模式串ababac的k值

模式串 ababac 的 k 值表：下标、子串与 k 值对应如下。

模式串 k 值的约定：① k=-1，只有模式串的第 1 个字符的 k 值为 -1；② k>0，表示指定字符前面 k 个字符和模式串的头 k 个字符相等；③ k=0，其他情况。模式串的第 2 个字符的 k 值必为 0。

第16页：模式串aaaaaaac的k值

模式串 aaaaaaac 的 k 值表：下标、子串与 k 值对应如下。

模式串 k 值的约定：① k=-1，只有模式串的第 1 个字符的 k 值为 -1；② k>0，表示指定字符前面 k 个字符和模式串的头 k 个字符相等；③ k=0，其他情况。模式串的第 2 个字符的 k 值必为 0。

第17页：KMP 串的匹配过程

本页演示模式串 ababc 在主串 abadababc 上的 KMP 匹配过程。模式串各字符的 k 值为：a 为 -1，b 为 0，a 为 0，b 为 1，c 为 2。

匹配中主串指针 i 始终不回溯，一旦某位失配，模式串指针 j 退到该字符 k 值所对应的位置继续比较，从而跳过必然不可能匹配的位置。

第18页：KMP 匹配过程（续）

本页继续演示 KMP 匹配过程：失配后模式串指针连续按 k 值滑动，主串指针 i 保持不变，直到模式串末位与主串对应位置相等，即在主串中定位到子串首次出现的位置。

第19页：KMP 算法的缺陷

KMP 算法仍有缺陷：当失配字符与其 k 值所指向的字符相同时，按 k 值滑动后的这次比较必然也失配，属于一次无意义的比较。

要消除这种多余比较，需要在求解 k 值时增加一层判断，这就是改进后的 KMP 算法。

第20页：改进后的 KMP 算法

改进后的 KMP 算法对 k 值做进一步修正：若某字符与其 k 值所指字符相同，则把该字符的 k 值改为所指字符的 k 值，使失配后一次性滑过所有必然失配的位置。

以模式串 abcab 为例，修正后的 k 值依次为 -1、0、0、-1、0，避免了原 KMP 算法中的多余比较。

第21页：改进后 KMP 的匹配过程

本页演示使用修正后 k 值的匹配过程：模式串各字符的 k 值取到 -1 时会带动主串指针前移，因此失配后模式串可以一次滑动到正确位置，比较次数进一步减少。

第22页：串的小结

串是一种数据类型受限的特殊线性表，它规定表中的每一个元素只能为字符。一般情况下，线性表是基于单个元素进行操作的，而字符串则是针对多个元素组成的子串进行操作的。

C# 中的字符串类有 String 和 StringBuilder 类。String 是不可变字符串，所以当程序中有大量连接字符串的操作时，要尽量避免使用 String 类，而应该使用 StringBuilder 类代替。

串的匹配运算是一个比较复杂的串操作，它就是判断某串是否是另一已知串的子串，使用该问题的有效算法能大大提高程序的响应性能。