4.2　串的表示和实现

视频二维码（扫码观看）

串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作。串在计算机中有3种表示方式：

定长顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。

堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。

块链存储方式：是一种链式存储结构表示。

一、串的定长顺序存储表示

定长顺序存储结构：直接使用定长且存储单元地址连续的字符数组来定义，数组的上界预先确定。

定长顺序存储结构定义为：

串的实际长度可在预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。

串长表示方法：

①以下标为0的数组分量存放串的实际长度；

②在串值后面加一个不计入串长的结束标记字符，如C语言中以“\0”表示串值的终结。

顺序存储结构的弊病：

①实现串操作的时间复杂度取决于参与操作的字符序列的长度。

②如果在操作中出现串值序列的长度超过上界时，用约定的截尾法处理，输出结果错误。

二、堆分配存储表示

系统在程序执行过程中动态分配地址连续的存储空间供串使用。C语言中，这个存储空间称为“堆”，通过动态存储分配函数malloc（）和free（）来管理。

特点是：仍然以一组地址连续的存储空间来存储字符串值，但其所需的存储空间是在程序执行过程中动态分配，故是动态的，变长的。

串的堆式存储结构的类型定义：

堆分配存储结构特点：

①顺序存储处理方便

②操作中对串长又没有任何限制

③应用程序处理串时常使用。

三、串的块链存储表示

串的链式存储结构和线性表的串的链式存储结构类似，采用单链表来存储串，结点的构成是：

data域：存放字符，data域可存放的字符个数称为结点的大小；

next域：存放指向下一结点的指针。

若每个结点仅存放一个字符，则结点的指针域就非常多，造成系统空间浪费，为节省存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为块链结构。如图4-1是块大小为3的串的块链式存储结构示意图。

图4-1　串的块链存储结构示意图

串的块链式存储的类型定义：

#define BLOCK_SIZE 4//可由用户定义的大小
typedef struct Chunk
{
    char ch[BLOCK_SIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head,*tail;/*头、尾指针*/
    int Strlen;/*当前长度*/
}LString;

块链式存储特点：

①对串进行操作时，只需要从头向尾顺序扫描即可，则对串值不必建立双向链表。设尾指针的目的是为了便于进行联结操作，但应注意联结时需处理第一个串尾的无效字符。

②结点大小的选择直接影响着串处理的效率。

③不如前两种存储结构灵活，它占用存储量大且操作复杂。