1
算法与数据结构  C语言版
1.6.2.1 4.2.1 串的顺序存储结构——顺序串
4.2.1 串的顺序存储结构——顺序串

和线性表的顺序存储结构类似,可用一个字符类型的数组存放串值。用数组存储串时,若定义了一个串变量,这个串在内存中的开始地址就确定了。由于串的长度是不确定的,因此需要有某种方法确定一个串的长度。

串是不定长的,在串的顺序存储结构中,表示串的长度一般有两种方法:一种是设置一个串的长度参数,此种方法的优点是便于在算法中用长度参数控制循环过程;另一种方法是在串值的末尾添加结束标记,此种方法的优点是便于系统自动实现。比如,C语言定义串为字符类型的数组(即顺序存储结构),串值是双引号中的字符序列,系统将自动在串值的末尾添加结束标记'\0'字符(字符'\0'为ASCII代码0,即空操作字符)。这样,字符数组名给出了串在内存中的开始地址,串值末尾的结束标记'\0'标记了串在内存中的结束位置。当自己定义串的顺序存储结构时,设置串的长度参数确定串的长度的方法更为常用。为了算法实现方便,或为了兼容两种串的长度表示方法,也可同时使用两种方法来表示串的长度。

串的顺序存储结构就是用数组存放串的所有字符,数组有静态数组和动态数组两种,因此,串的顺序存储结构也有静态数组结构和动态数组结构两种。

1.静态数组结构

串的静态数组结构又称为定长数组结构,此时数组的长度是编译时确定的,在运行时是不可改变的。串的静态数组结构体可定义如下:

其中,MaxSize表示数组的最大存储空间,str表示存储串值的数组名,length表示串的长度(必须满足length<MaxSize),String是为结构体定义的名字。

2.动态数组结构

动态数组即用来表示数组的元素个数在用户使用时来确定。通常情况下,系统从一个称为堆的区域为用户定义的动态数组分配存储单元。串的动态数组结构体可定义如下:

其中,str表示动态数组的首地址(即数组名),maxLength表示动态数组的最大数组元素个数,length表示当前串的长度(必须满足length≤maxLength),DString是为结构体定义的名字。