1.2.4　串

串是字符串的简称，是由零到多个字符组成的连续有限序列，一般记为：

s="a1a2a3…an"

其中，s为串名，引号中为串值（双引号本身不是串值）。ai（1≤i≤n）为串元素，由字母或其他符号组成。n（n≥0）是串的长度，当串长度为0（即n=0）时称为空串，记为s=" "。空格也可作为串字符。由于各个串的串值是不等长的，大多数高级语言在实现串操作时都要进行专门处理以确定串的长度，为此应特别注意不要将串值为空格字符的空格串等同空串。为了明确起见，一般用“□”表示一个空格的串。

一个串中任意多个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。一个字符在串中的序号称为该字符在串中的位置。当一个字符在串中多次出现时，该字符在串中的位置指的是该字符在串中第一次出现的位置。子串在主串中的位置指的是该子串的第一个字符在主串中的位置。称两个串是相等的是指两个串中的字符序列一一对应相等。如有如下串：

在这5个串中，可以说S1是S3的主串，子串S3在主串S1中的位置是3，S4是S5的主串，S4的长度为8，S5的长度为1。

由串的定义可知，串是一种其数据元素固定为字符的线性表。因此，仅就数据结构而言，串归属于线性表这种数据结构。但是，串的基本操作和线性表上的基本操作相比却大有不同。线性表上的操作主要针对线性表中的某个数据元素进行，而串上的操作主要是针对串的整体或串的某部分子串进行。

与线性表存储结构类似，字符串的两种基本存储结构是顺序结构和链式存储结构。

顺序存储结构是用地址连续的一块存储单元存储串的字符序列。由于大多数计算机的存储器地址采用的是以字编址，一个字占多个字节，而一个字符只占一个字节，所以为了节省存储空间，顺序存储结构存储串值时允许采用紧缩格式，即一个字节存放一个字符，而把一个存储单元中放一个字符称为非紧缩格式。显然，非紧缩格式浪费存储空间，但操作方便；紧缩格式节省存储空间，但若要分离某部分字符时，操作比较麻烦。图1-35（a）是串的非紧缩格式存储示例；图1-35（b）是串的紧缩格式存储示例。通常系统在存储串时，自动在串的末尾处添加一个特殊符号作为当前串的结束标志。在C语言中串结束标志采用转义符'\0'。

图1-35　串的两种存储格式

串的顺序存储结构有两个缺点：一是需要预先定义一个串允许的最大字符个数，当该值估计过大时存储效率就降低，浪费存储空间；二是当需要在字符串中插入或删除字符时，要花许多时间移动字符。解决这个问题可以使用链表存储结构来存储串。串的链式存储结构定义如下：

例如，对于字符串s="data"，其链式存储结构如图1-36所示。

图1-36　串的链式存储结构

串的链式存储结构具有链式存储结构的共同特点，即存储一个串的字符数据结点，存储空间可以动态申请，不需要预先定义，对串进行字符数据结点的插入和删除时都不需要进行大量的字符移动。