5.4　串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符，哪怕串中的字符是“123”这样的数字组成，或者“2010-10-10”这样的日期组成，它们都只能理解为长度为3和长度为10的字符串，每个元素都是字符而已。

因此，对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作。

  1. ADT 串(string)
  2. Data
  3.     串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
  4. Operation
  5.     StrAssign(T, *chars):        生成一个其值等于字符串常量chars的串T。
  6.     StrCopy(T, S):               串S存在，由串S复制得串T。
  7.     ClearString(S):              串S存在，将串清空。
  8.     StringEmpty(S):              若串S为空，返回true，否则返回false。
  9.     StrLength(S):                返回串S的元素个数，即串的长度。
  10.     StrCompare(S, T):            若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0。
  11.     Concat(T, S1, S2):           用T返回由S1和S2联接而成的新串。
  12.     SubString(Sub, S, pos, len): 串S存在，1≤pos≤StrLength(S)，
  13.                                  且0≤len≤StrLength(S)-pos+1，用Sub返
  14.                                  回串S的第pos个字符起长度为len的子串。
  15.     Index(S, T, pos):            串S和T存在，T是非空串，1≤pos≤StrLength(S)。
  16.                                  若主串S中存在和串T值相同的子串，则返回它在主串S中
  17.                                  第pos个字符之后第一次出现的位置，否则返回0。
  18.     Replace(S, T, V):            串S、T和V存在，T是非空串。用V替换主串S中出现的所有
  19.                                  与T相等的不重叠的子串。
  20.     StrInsert(S, pos, T):        串S和T存在，1≤pos≤StrLength(S)+1。
  21.                                  在串S的第pos个字符之前插入串T。
  22.     StrDelete(S, pos, len):      串S存在，1≤pos≤StrLength(S)-len+1。
  23.                                  从串S中删除第pos个字符起长度为len的子串。
  24. endADT

对于不同的高级语言，其实对串的基本操作会有不同的定义方法，所以同学们在用某个语言操作字符串时，需要先查看它的参考手册关于字符串的基本操作有哪些。不过还好，不同语言除方法名称外，操作实质都是相类似的。比如C#中，字符串操作就还有ToLower转小写、ToUpper转大写、In-dexOf从左查找子串位置（操作名有修改）、LastIndexOf从右查找子串位置、Trim去除两边空格等比较方便的操作，它们其实就是前面这些基本操作的扩展函数。

我们来看一个操作Index的实现算法。

  1. /* T为非空串。若主串S中第pos个字符之后存在与T
  2. 相等的子串， */
  3. /* 则返回第一个这样的子串在S中的位置，否则返
  4. 回0 */
  5. int Index(String S, String T, int pos)
  6. {
  7.     int n, m, i;
  8.     String sub;
  9.     if (pos > 0)
  10.     {
  11.         /* 得到主串S的长度 */
  12.         n = StrLength(S);                   
  13.         /* 得到子串T的长度 */
  14.         m = StrLength(T);                   
  15.         i = pos;
  16.         while (i <= n - m + 1)
  17.         {
  18.             /* 取主串第i个位置 */
  19.             /* 长度与T相等子串给sub */
  20.             SubString(sub, S, i, m);        
  21.             /* 如果两串不相等 */
  22.             if (StrCompare(sub, T) != 0)    
  23.                 ++i;
  24.             /* 如果两串相等 */
  25.             else                            
  26.                 /* 则返回i值 */
  27.                 return i;                   
  28.         }
  29.     }
  30.     /* 若无子串与T相等，返回0 */
  31.     return 0;                               
  32. }

当中用到了StrLength、SubString、StrCom-pare等基本操作来实现。