定长顺序存储表示

扫码获取更多资源

如果在程序设计语言中，串只是作为输入输出的常量岀现，则只需要存储这个串常量值，也就是字符序列即可。但在大多数非数值处理的程序中，串也以变量的形式出现，因此需要根据串操作的特点，合理地选择和设计串值的存储结构和维护方式。

类似于线性表的顺序存储表示方法，可以使用一组地址连续的存储单元存储串值的字符序列。

在程序执行之前，按照预先定义的大小，为串分配一个固定长度的存储区，把串中的字符按照其逻辑次序依次存放在这组地址连续的存储单元里的方式称为串的定长顺序存储表示，釆用这种存储结构的串称为定长顺序串（Fixed Length Sequential String） o

在定长顺序串中，一般用下面两种方法来表示串的长度。

在串值后面添加一个不计串长的结束标记符，就像C/C++语言中以*0,来表示串的结束一样。这种存储方法不能直接得到串的长度，而是通过判断当前字符是否为，\0,来确定串是否结束，从而求得串的长度，显然不便于进行某些串操作

以下标为0的数组分量存放串的实际长度，串值（字符序列）从下标为1的数组分量开始存放。这种存储方法能够直接得到串的长度，方便进行串的操作。本书采用这种方法来表75串的长度

由于串的存储空间是在程序执行之前分配的，因此其大小在编译时就已经确定。在进行串操作时，如果串的实际长度超过STRING_SIZE,则超过的串值将被舍去，称之为“截断”。因此，定长顺序串难以适应诸如插入、连接、替换等操作。

①计算存放在字符数组chars中的串常量长度chars_len；

②判断串常量长度：如果chars_len = O,则置串S为空串；如果chars.len〈定长顺序串空间，则将chars中的字符赋值给串S;如果chars_len＞定长顺序串空间，则将chars部分字符赋值给串S,发生截断。

①问题规模：串常量chars的长度（设值为n）;

②基本操作：求chars的长度、字符复制；

③时间分析：算法4-2的时间复杂度为O（n）。