4.1.1　基本概念

1. 串的定义及其基本术语

(1) 串的定义。串(string)是由零个或多个字符组成的有限序列，表示形式为

s=‘a₁a₂…a_n’ (n≥0)

其中：s是串的名，用单引号括起来的字符序列是串的值；a_i(0≤i≤n) 可以是字母、数字或其他字符。

(2) 串的长度。串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。

(3) 主串和子串。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。

(4) 串的相等。当且仅当两个串的值相等时，称两个串是相等的。

2. 串的存储结构

(1) 定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。

(2) 堆分配存储表示

以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得到的。

(3) 串的块链存储表示

由于串结构的特殊性——结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

3. 串的匹配

设有两个字符串T和pat，若我们打算在串T中查是否有与串pat相等的子串，则称串T为目标，把pat称为模式。并称查找模式在目标中的匹配位置的运算为模式匹配。

4. 数组的定义和顺序表示

一维数组是一个向量，它的每个元素是这个结构中不可分割的最小单位。n(n＞1)维数组是一个向量，它的每个元素是n-1维数组，且具有相同的上限和下限。由于存储单元是一维的结构，而数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有两种存储方式：一种以行序为主序的存储方式；一种以列序为主序的存储方式。

5. 稀疏矩阵的压缩存储

(1) 在特殊矩阵中，非零元的分布都有明显的规律，我们可将其压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。

(2) 对于非零元较零元少得多，且分布没有一定规律的稀疏矩阵，可采用三元组法和十字链表来存储。

6. 广义表的定义及其存储结构

广义表一般记作：

LS=(d₁，d₂，…，d_n)

其中：LS是广义表(d₁，d₂，…，d_n)的名称，n是它的长度。d_i可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。当广义表LS非空时，称第一个元素d₁为LS的表头(Head)，称其余元素组成的表(d₂，…，d_n)是LS的表尾 (Tail)。通常采用链式存储结构，每个数据元素可用一个结点表示。

7. 广义表的递归算法

(1) 求广义表的深度。

(2) 复制广义表。

(3) 建立广义表的存储结构。