程序猿必修课之数据结构（九）串

2017-05-10 本文已影响93人 Xiao_Mai

原文：http://www.jianshu.com/p/d0ad73bd638f

上一章：程序猿必修课之数据结构（八）队列

串的定义

串（String）是由零个或多个字符组成的有限序列，又名字符串。

从定义中可以看出:、

串的字符数目是“有限”的，零个字符的串叫“空串（null string）”。
它是一个序列，相邻字符之间具有前驱和后继关系。

空格串

只包含空格的串叫“空格串”，它和空串的区别是：空格串是有内容有长度的，而且可以不止一个空格。

子串与主串

串中任意个数的连续字符组成的子序列称为该串的子串，相应的，包含子串的串称为主串。

子串在主串中的位置就是子串的第一个字符在主串中的序号。

串的比较

数字可以比较大小，串同样可以比较大小，只不过串的比较是通过比较组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。

比较两个串是否相等，必须满足两个条件：

两个串的长度相等
两个串的各个对应位置的字符都相等。

编码知识

计算机中的常用字符是使用标准的 ASCII 编码，它由 7 位二进制数表示一个字符，总共可以表示 128 个字符。后来发现缺少一些特殊符号，于是扩展 ASCII 码产生，它由 8 位二进制数表示，总共可以表示 256 个字符，这足够以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。但是对于以汉字为代表的象形文字来说，显然 256 个字符是不够的，因此后来就有了 Unicode 编码。

串的抽象数据类型

ADT 串（string)

Data 串中相邻元素具有前驱和后继关系

Operation
    
    copy(t, s): 由串 s 复制得到 t。
    clear(s): 串 s 存在，将串清空。
    isEmpty(s): 若串 s 为空，返回 true，否则返回 false
    length(s): 返回串 s 的无数个数，即串的长度
    compare(s, t): 若 s > t，返回值为正数；若 s == t，返回 0；若 s < t，返回负数。
    contat(t, s1, s2): 将 s1 和 s2 拼接成 t 返回。
    subString(sub, s, pos, len): 若串存在， 1 <= pos <= length(s)，且 0 <= len <= length(s) - pos + 1，用 sub 返回串 s 的第 pos 个字符起长度为 len 的子串。 
    index(s, t, pos): 串 s 和 t 存在， t 是非空串， 1 <= pos <= length(s)。若主串 s 中存在和串 t 值相同的子串，则返回它在主串 s 中第 pos 个字符之后第一次出现的位置，否则返回 -1。
    replace(s, t, v): 串 s、t 和 v 存在，t 是非空串。用 v 替换主串 s 中出现的所有与 t 相等的子串。
    insert(s, pos, t): 串 s 和 t 存在， 1 <= pos < length(s) + 1。在串 s 的第 pos 个字符之前插入串 t。
    delete(s, pos, len): 串 s 存在，1 <= pos <= length(s) - len + 1。从串 s 中删除第 pos 个字符起长度为 len 的子串。

endADT

串的顺序存储结构

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

但是串的顺序存储方式存在一些问题，对于字符串的操作，比如拼接、插入、替换等，都有可能使得串的升序超过数组的长度。

串的链式存储结构

串的链式存储结构与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果一个结点对应一个字符，就会造成很大的空间浪费，因此，一个结点可以存储一到多个字符，最后一个结点若未被占满，可以用其他非串值字符补全。一个结点存多少个字符会直接影响着串处理的效率，需要根据实际情况做出选择。

串的链式存储结构除了在串的拼接等操作时方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

~~KMP模式匹配算法~~