串的存储结构

AI 摘要

|

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元来存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

#define MAXLEN 255 //预定义最大串长为255
typedef struct{
    char ch [MAXLEN]; //每个分量存储一个字符
    int length; //串的实际长度
}SString;

串的实际长度只能小于或等于 MAXLEN，超过预定义长度的串值会被舍去，称为截断。

串长有两种表示方法：一是如上述定义描述的那样，用一个额外的变量 len 来存放串的长度；二是在串值后面加一个不计入串长的结束标记字符 \0，此时的串长为隐含值。

在一些串的操作（如插入、联接等）中，若串值序列的长度超过上界 MAXLEN，约定用＂截断＂法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

堆分配存储表示

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

typedef struct{
    char *ch; //按串长分配存储区, ch 指向串的基地址
    int length; //串的长度
}HString;

在 C 语言中，存在一个称为堆的自由存储区，并用 malloc() 和 free() 函数来完成动态存储管理。利用 malloc() 为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由 ch 指针来指示；若分配失败，则返回 NULL 。已分配的空间可用 free() 释放掉。

上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅做简单介绍。

块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点既可以存放一个字符，又可以存放多个字符。每个结点称为块，整个链表称为块链结构。

下图是结点大小为 4（每个结点存放4个字符）的链表，最后一个结点占不满时通常用 ＃ 补上；

下图是结点大小为 1 的链表。