串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。

• 但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\o”来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了，其实这还是需要占用一个空间。

刚才讲的串的顺序存储方式其实是有问题的，因为字符串的操作，比如两串的连接Concat、新串的插入Strlnsert、以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度MaxSize。

• 也就是说，串的顺序存储结构的缺点是字符串的截断，截断就是超过预定义长度的串值被舍去。

于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

接下来我们试着按照串ADT定义的操作，来实现串这个数据结构。

延伸阅读

此文章所在专题列表如下：

1. 数据结构里的串是什么东西？
2. 如何比较串的大小
3. 串的抽象数据类型ADT
4. 串的顺序存储结构
5. 串最基本的5个操作的C实现
6. 寻找子串在主串中的位置
7. 如何在串中插入串
8. 如何在串中删除特定长度的子串
9. 字符串中的子串替换
10. 题外话：谈谈malloc()和free()

本文地址：http://www.nowamagic.net/librarys/veda/detail/2405，欢迎访问原出处。