第4章 串
内容提要：
本章首先介绍串的定义，包括串的基本术语和基本运算。接着介绍串的三种存储结构：定长顺序存储、对分配存储和块链存储。最后介绍了串的基本操作的实现。
学习目标与重点：
◆理解串的定义；
◆理解串的顺序存储结构和链式存储结构；
◆掌握串的定长顺序存储的基本算法。
关键术语：串；定长顺序存储；堆分配存储
4.1 串的定义
串(String)是零个或多个字符组成的有限序列。一般记作a=”a1a2a3…an’’，其中：a是串名，双引号括起来的字符序列是串值：ai(1≦i≦n)可以是字母、数字或其它字符，称为串的元素，是构成串的基本单位。
4.1.1 基本术语
（1）串的长度。串中所包含的字符个数称为该串的长度。
（2）空串。长度为零的串称为空串(Empty String)，它不包含任何字符，记作∮。
（3）空白串。通常将仅由一个或多个空格组成的串称为空白串(Blank String)。
注意：空串和空白串的不同，例如‘‘ ’’和‘‘’’分别表示长度为1的空白串和长度为0的空串。
（4）子串。串中任意个连续字符组成的子序列称为该串的子串。
（5）主串。包含子串的串相应地称为主串。
（6）子串的位置。通常将子串在主串中首次出现时，该子串的首字符在主串中的序号，称为子串在主串中的位置。
例：设字符串A和B分别为 A=“This is a string”，B=“is”。则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。
（7）串相等。称两个串是相等的，是指两个串的长度相等且对应位置的字符都相等。
4.1.2 基本运算
对于串的基本运算，许多高级语言均提供了相应的运算或标准库函数来实现。
4.2 串的存储结构
因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符，串在存储时还有一些与一般线性表不同的地方。串有三种机内表示方法，下面分别介绍。
4.2.1 定长顺序存储
串的顺序存储表示，也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。其优点是涉及到串长操作时速度快。
4.2.2 堆分配存储
在顺序串上的插入、删除操作并不方便，必须移动大量的字符，而且当操作中出现串值序列的长度超过上界MAXLEN时，只能用截尾法处理。要克服这个弊病只有不限定串的最大长度，动态分配串值的存储空间。
堆分配存储的特点是：仍以一组地址连续的存储单元存放串值字符序列，但其存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用malloc() 和free() 动态存储管理函数，根据实际需要动态分配和释放字符数组空间。
4.2.3 块链存储
顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，可用单链表方式来存储串值，具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。
这种结构便于进行插入和删除运算，但存储空间利用率太低。由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较少。
