串、数组和广义表

串

串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为

$$s="a_1{a}_2\dots a_n"(n⩾0)$$

其中，$s$ 是串的名，用双引号括起来的字符串序列是串的值；$a_i(1⩽i⩽n)$ 可以是字母、数字或其他字符串；串中字符的数目 $n$ 称为串的长度。零个字符的串称为空串（null string）。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。字符在序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置表示。

例如，假设 a、b、c、d 如下 4 个串：

$$\begin{gathered} a="BEI" \\ b="JING" \\ c="BEIJING" \\ d="BEIJING" \end{gathered}$$

它们的长度分别为 3、4、7 和 8；$a$ 和 $b$ 都是 $c$ 和 $d$ 的子串，$a$ 在 $c$ 和 $d$ 中的位置都是 1，$b$ 在 $c$ 中的位置是 4，在 $d$ 中的位置是 5。

当且仅当两个串的值相等时，称这两个串相等。换言之，只有当这两个串长度相等，各个对应位置的字符都相等时才相等。

数组

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受 $n(n⩾1)$ 个线性关系的约束，每个元素在 $n$ 个线性关系中的序号 $i_1,i_2,\dots ,i_n$ 称为该元素的下标，可以通过下标访问该元素。因为数组中每个元素处于 $n(n⩾1)$ 个关系中，故称该数组为 $n$ 维数组。数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。

广义表

广义表是线性表的推广，也称为列表。广泛地用于人工智能等领域的表处理语言 LISP 语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。

广义表一般记作

$$LS=(a_1,a_2,\dots ,a_n)$$

其中，$LS$ 是广义表 $(a_1,a_2,\dots ,a_n)$ 的名称，$n$ 是长度。在线性表的定义中，$a_i(1⩽i⩽n)$ 只限于单个元素。而在广义表的定义中，$a_i$ 可以是单个元素，也可以是广义表，分别称为广义表的原子和子表。习惯上，用大写字母表示广义表名称，用小写字母表示原子。