算法与数据结构：7、8-串.pdf

在IT行业中，数据结构与算法是构建任何软件系统的基础，其中串（String）是一种特殊的数据结构，用于表示零个或多个字符组成的有限序列。这一讲主要讨论串的逻辑结构、存储结构以及模式匹配算法。 串的逻辑结构是指由字符构成的线性表。在串中，字符的位置从1开始编号，直到串的长度n。例如，串S=‘a1a2a3…an’，其中a1到an代表序列中的字符，n为串的长度。引号用于区分串和其他变量或常量，空串用‘’或Φ表示，其长度n=0。空格串是指只包含空格字符的特殊串，而子串是主串中任意连续字符组成的序列。例如，对于主串‘abcdef’，‘abc’是子串。在串中，字符位置指的是字符在序列中的序号，而子串在主串中的位置指的是子串首次出现时其首字符在主串中的位置。 串与线性表的关系非常密切，但又有所不同。串的数据对象是字符集，而数据操作是以子串为操作对象，如查找子串、插入子串、删除子串等。串可以看作是一种扩展的线性表，串的操作也包含了线性表的操作，但其操作单元是子串而非单个元素。 接下来，串的存储结构通常分为顺序存储和链式存储。顺序存储是指用一段地址连续的存储单元来存储串中的字符，可以通过数组实现。例如，SString[MAXSIZE+1]可以用来存储一个最大长度为MAXSIZE的串，其中MAXSIZE+1是为了存储结束标志或长度信息。这里需要注意的是，顺序存储方式可能会导致溢出，尤其是当实际串长度超出预定长度时。 动态分配的堆存储是一种更加灵活的串存储方法。在这种方法中，使用malloc/free动态分配内存来存储串中的字符。例如，可以定义一个结构体HString，其中包含一个指向动态分配内存的指针p和记录串长的整型变量length。这种方法可以避免固定大小的限制，但需要程序员手动管理内存。 串的基本操作在抽象数据类型中定义。包括串的生成、销毁、清空、判断空串、获取长度、复制串、串比较、连接串、获取子串、定位子串、替换子串、插入子串和删除子串等。这些操作构成了串类型的行为规范，为串的处理提供了基本手段。 模式匹配算法是串操作中一个重要的部分。常见的模式匹配算法有朴素匹配算法和KMP算法。朴素匹配算法简单直观，它按照模式串的每一个位置逐一尝试与主串匹配，直到找到一个匹配或遍历完主串。KMP算法是一种改进的算法，它可以在不匹配的情况下跳过尽可能多的字符，从而提高效率。 串是一种基本但又非常重要的数据结构，在编程语言中广泛使用，了解和掌握串的逻辑结构、存储结构以及模式匹配算法对于提高程序的性能和编写高效的代码有着重要意义。