串的抽象类型数据的设计

线性表：更关注单个元素的操作，如查找一个元素，插入或删除一个元素。串：更多是查找子串位置、得到指定位置子串、替换子串等操作。

定义：用节点保存串的数据。

若一个结点存放一个字符，会存在很大的空间浪费。

故串的链式可以一个结点放多个字符，最后一个结点若不满，可用#或其他非串值字符补全。（每个节点固定长度）

• str_assign(t, *cahrs); 生成一个其值等于字符串常量 chars 的串 t。
• str_copy(t, s); 串 s 存在，由串 s 复制得到串 t 中。
• str_clear(s);清空串str_empty(s); 判断串是否空。
• str_length(s); 串的长度。
• str_compare(s, t); 若 s>t，返回 >0 ， 若 s=t ，返回 0 ，若 s<t ，返回 <0。
• str_concat(t, s1, s2); 合并 s1 和 s2，通过 t 返回。
• str_get_sub(t, s, pos, len); 在串 s 中从 pos 点开始截取最大 len 的长度，通过 t 返回。
• str_index(s, t, pos); 在主串 s 的 pos 位置起查找子串 t 并返回起始子串起始位置，没有则返回 0。
• str_replace(s, t, v); 在主串 s 中查找子串 t，并用串 v 代替。

定义：用一组地址连续的存储单元来存储串中的字符序列。

按照预定义大小，为每个定义的串分配一个固定长度的存储区，一般用定长数组来定义。

一般可以将实际的串长值保存在数组的 0 下标位置，或者在数组的最后一个下标位置。

但有的语言规定在串值后面加一个不计入串长度的结束标记符号“\0”来表示串值的终结（但占用一个空间）。

由于过于不便，串的顺序存储操作有一些变化：串值的存储空间可在程序执行过程中动态分配而得

• 比如堆：可由 c 语言动态分配函数 malloc() 和 free()来管理。