串的定义

AI 摘要

|

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统 （如搜索引擎）、文本编辑程序（如 Word）、问答系统、自然语言翻译系统等，都是以字符串数据作为处理对象的。本章详细介绍字符串的存储结构及相应的操作。

串（string）是由零个或多个字符组成的有限序列。一般记为 $S={}^{\prime }{a}_1{a}_2\cdots a_n^{\prime }(n⩾0)$

其中，$S$ 是串名，单引号括起来的字符序列是串的值；$a_i$ 可以是字母、数字或其他字符；串中字符的个数 $n$ 称为串的长度。 $n=0$ 时的串称为空串（用 $\varnothing$ 表示）。

串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第 1 个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

例如，有串 A = 'China Beijing'，B = 'Beijing'，C = 'China'，则它们的长度分别为 13、7 和 5。B 和 C 是 A 的子串，B 在 A 中的位置是 7，C 在 A 中的位置是 1。

注意，由一个或多个空格（空格是特殊字符）组成的串称为空格串（空格串不是空串），其长度为串中空格字符的个数。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。