1、串类型的定义

串(或字符串)是由零个或多个字符组成的有限序列,一般记为 s='ab...c'。其中s为串名,用单引号括起来的字符序列是串的值。

 

串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。然而,串的基本操作和线性表有很大差别。

在线性表中,大多以“单个元素”作为操作对象;而在串的基本操作中,通常以“串的整体”作为操作对象。

 

串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString。此5种操作构成串类型的最小操作子集。

例如,可利用StrCompare、StrLength、SubString等操作来实现Indes(S,T,pos)。

2、串的表示和实现

串有3中机内表示方法。

一、定长顺序存储表示(因其有自身的缺点,因此舍弃)

二、堆分配存储表示

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

在C语言中,存在一个称之为“堆”的自由存储区,并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需的存储空间,若分配成功,则返回一个指向起始地址的指针,作为串的基址,同意,为了以后处理方便,约定串长也作为存储结构的一部分。

 

三、串的块链存储表示

说明如下:

 

;