串（string，或称字符串）是 n 个字符的有限序列。通常记作
　　　s = " … " (n≥0)

　　其中，S是串的名，用双引号括起来的字符序列是串的值。串中字符的数目 n 称为串的长度。含零个字符的串称为空串(null string)，它的长度为零。在各种应用中，空格通常是串的字符集合中的一个元素，可以出现在其他字符之间。由一个或多个空格组成的串称为空格串(blank string)，例如
　　　" "，" 　　" 和 "　　　　"

　　是三个空格串，它们的长度为串中空格字符的个数，分别为1，5和8。为了清楚起见，以下将用符号"Φ"表示"空格符"。
　		  
　　串值必须用一对双引号括起来，但双引号本身不属于串，它的作用只是为了避免与变量或数的常量混淆而已。如 x="123";表明x是一个串变量名，赋予它的值是字符序列123，而 x=123;则表明x是一个整型变量，赋予它的值为整数123。同样在
　　aString = "aString";中，左边的 aString 是一个串变量名，而右边的字符序列"aString"是赋给它的值。
　		  
  　串的抽象数据类型定义如下：
ADT String {
　数据对象：D＝{ | ∈CharacterSet, i=1,2,...,n, n≥0 }

　数据关系：R1＝{ < , > | , ∈D, i=2,...,n }

　基本操作：
　　StrAssign (&T, chars)
　　　初始条件：chars 是串常量。
　　　操作结果：赋于串T的值为 chars。

　　StrCopy (&T, S)
　　　初始条件：串 S 存在。
　　　操作结果：由串 S 复制得串 T。

　　DestroyString (&S)
　　　初始条件：串 S 存在。
　　　操作结果：串 S 被销毁。

　　StrEmpty (S)
　　　初始条件：串 S 存在。
　　　操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。
　
  
　　回顾线性表的数据对象和数据关系的定义可见，作为数据结构，串和线性表的差别仅在于串中的数据元素限定为"字符"。

　　和线性表类似，通常称字符在序列中的序号为该字符在串中的位序。
  
  　　StrCompare (S, T)
　　　初始条件：串 S 和 T 存在。
　　　操作结果：若S>T，则返回值=0；若S=T，则返回值<0；若S<T，则返回值<0。

　　StrLength (S)
　　　初始条件：串 S 存在。
　　　操作结果：返回串 S 序列中的字符个数，即串的长度。

　　ClearString (&S)
　　　初始条件：串 S 存在。
　　　操作结果：将 S 清为空串。
　
   　　"串值大小"是按"词典次序"进行比较的，如：
　　　　StrCompare("data","Stru")<0
　　　　StrCompare("cat"," case")>0
　　显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。		  
  　　Concat (&T, S1, S2)
　　　初始条件：串 S1 和 S2 存在。
　　　操作结果：用 T 返回由 S1 和 S2 联接而成的新串。
　
   　　"串联接"操作的结果是生成一个新的串，其值是"将第二的串的第一个字符紧接在第一个串的最后一个字符之后"得到的字符序列。如操作
　　Concat(T," man","kind")得到的结果是：
　　T ="mankind"。
　		  
  　　SubString (&Sub, S, pos, len)
　　　初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。
　　　操作结果：用 Sub 返回串S的第 pos 个字符起长度为 len 的子串。
　		   　　"子串"指串中任意个连续的字符组成的子序列。如：操作SubString(Sub,"commander",4,3)得到的结果是Sub="man"。显然必须在满足初始条件中规定的"起始位置"和"长度"之间的约束关系时才能求得一个合法的子串。允许 len 的下限为0是由于空串也是合法串，但实际上求长度为0的子串是没有意义的。
　		  
  　　Index (S, T, pos)
　　　初始条件：串S和T存在，T 是非空串，1≤pos≤StrLength(S)。
　　　操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。
　		   　　包含子串的串相应地称为主串。"子串在主串中的位置"指的是子串中的第1个字符在主串中的位序。如子串"man"在主串"commander"中的位置为4。Index 操作类似于线性表的Locate操作，在S中查询和T值相同的子串，pos为查询的起始位置。如：
　　Index("This is a pen","is",pos)，若pos=1，则查询得结果为3，若 pos=4，则得结果为6，若pos=6，则得查询结果为0。
　		  
  　　Replace (&S, T, V)
　　　初始条件：串 S，T 和 V 存在，T 是非空串。
　　　操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。
　
   　　假设S="abcacabcaca"，T="abca"和V="x"，则置换之后的S="xcxca"。注意定义中"不重叠"三个字，若上例中的V="ab"时，则置换后的结果应该是
　　S=" abcabca"，而不是"abbca"。
　		  
  　　StrInsert (&S, pos, T)
　　　初始条件：串 S 和 T 存在，1≤pos≤StrLength(S)＋1。
　　　操作结果：在串 S 的第 pos 个字符之前插入串 T。

　　StrDelete (&S, pos, len)
　　　初始条件：串 S 存在，1≤pos≤StrLength(S)-len+1。
　　　操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串。

} ADT String
   　　例如：S="chater"，T="rac"，pos=4，则插入后的结果为S="character"。

  思考题 串的基本操作和线性表一样，无非也就是查找、插入和删除等，那么它们能否用线性表的操作来替代呢？