串、数组和广义表
串的定义
串（string）： 是由零个或多个字符组成的有限序列，又称 字符串 。
其中的序列表示串的元素也是具有一对一的关系，又因为其是有限的，所以串也是线性表。
一般记为 s=“a1a2a3……an”，(n>=0)。
空串（null string）： 零个字符的串。用两双引号表示 "" ，也可以用希腊字母“Φ” 。
串中任意个数的连续字符组成的子序列称为该串的 子串 ；相应地，包含子串的串被称为 主串 。
子串在主串中的位置就是子串的第一个字符在主串中的序号。
串的比较
在 C 语言中，当两个串的 长度和对应位置的字符相等 ，才能说两个串是相等的。
给定两个串： s="a1a2a3……an" 和 t="b1b2b3……bn" ，当两个串不相等时，当满足以下条件之一时， s<t ：
- n<m ，且 ai = bi (i=1,2,3……,n) 。
- 存在某个 k<=min(m, n) ，使得 ai = bi (i=1,2,3……,k-1)，ak < bk 。
串的抽象数据类型、存储结构及其运算
串的抽象数据类型
ADT 串 (string)
Data
串中元素仅有一个字符组成，相邻元素具有直接前驱和直接后继关系。
Operation
StrAssign(T, *chars)：生成一个其值等于字符串常量 chars 的串 T 。
StrCopy(T, S)：串 S 存在，有串 S 复制得串 T 。
ClearString(S)：串 S 存在，将串清空。
StringEmpty(S)：若串 S 为空，返回 true ，否则返回 false。
StrLength(S)：返回串的长度，也就是串的元素个数。
StrCompare(S, T)：若 S>T ，返回值>0，若 S=T ，返回0，若 S<T ，返回值<0。
Concat(T, S1, S2)：用 T 返回由 S1 和 S2 联结而成的新串。
SubString(sub, S, pos, len)：串 S 存在，1<=pos<=StrLength(S)，且 0<=len<=StrLength(S)-pos+1，用 Sub 返回串的 S 的第 pos 个字符起长度为 len 的子串。
Index(S, T, pos)：若串 S 和 T 存在， T 是非空串，1<=pos<=StrLength(S)。若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中第 pos 个字符后第一次出现的位置，否则返回0。
Replace(S, T, V)：串 S 、 T 和 V 存在， T 是非空串。用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串。
StrInsert(S, pos, T)：串 S 和 T 存在，1<=pos<=StrLength(S)+1。在串 S 的第 pos 个字符之前插入串 T 。
StrDelete(S, pos, T)：串 S 存在，1<=pos<=StrLength(S)+1。从串 S 中删除第 pos 个字符起长度为 len 的子串。
DestroyString(S)：销毁串 S 。
endADT
