华北水利学院数据结构课件第四章陈波.pptx

数据结构第四章串问题 数据结构是计算机科学中的一门重要基础学科，它研究的是数据的组织、存储和管理。数据结构第四章讨论的是串问题，串是一种特殊的线性表，它由零个或多个任意字符组成的有限序列。串的逻辑结构是指串的长度和串的逻辑关系，串的存储结构可以是顺序串或链接串，顺序串用数组来存储串中的字符序列，链接串用链接存储结构来存储串。 串的基本操作包括串的链接、串的比较、串的复制等，串的应用包括模式匹配、BF 模式匹配算法等。在模式匹配中，给定主串 S 和模式 T，需要在 S 中寻找 T 的过程称为模式匹配。如果匹配成功，返回 T 在 S 中的位置，如果匹配失败，返回 0。BF 模式匹配算法是一种基本的模式匹配算法，它的思想是从主串 S 的第一个字符开始和模式 T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串 S 的第二个字符开始和模式 T 的第一个字符进行比较，重复上述过程，直到 T 中的字符全部比较完毕，则说明本趟匹配成功；或 S 中字符全部比较完，则说明匹配失败。 在本章中，我们还讨论了串的存储结构，包括顺序串和链接串，顺序串用数组来存储串中的字符序列，链接串用链接存储结构来存储串。在顺序串中，可以用一个变量来表示串的长度，也可以在串尾存储一个不会在串中出现的特殊字符作为串的终结符。链接串可以用来存储大型串，且可以快速地进行串的操作。 在模式匹配中，BF 模式匹配算法是一种基本的模式匹配算法，它的思想是从主串 S 的第一个字符开始和模式 T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串 S 的第二个字符开始和模式 T 的第一个字符进行比较，重复上述过程，直到 T 中的字符全部比较完毕，则说明本趟匹配成功；或 S 中字符全部比较完，则说明匹配失败。 在串的应用中，我们还讨论了删除特定字符和颠倒单词在字符串里的出现顺序这两个问题，删除特定字符是指删除字符串里的给定字符，颠倒单词在字符串里的出现顺序是指颠倒单词在字符串里的出现顺序。这些问题都需要使用串的基本操作来解决。 数据结构第四章讨论的是串问题，包括串的逻辑结构、串的存储结构、串的基本操作和串的应用等。串是一个重要的数据结构，它广泛应用于计算机科学和信息技术等领域。