五、串

5.1串的定义

串string)是由零个或多个字符组成的有限序列，又名叫字符串。

一般记为s = “a1a2a3a4…an”(n>0)，其中，s是串的名称，用双引号括起来的字符序列是串的值，单引号不属于串的内容

串中的字符数目n称为串的长度，零个字符的串称为空串，可以用“”表示也可以用空集表示

5.2串的比较

两个数字其实很好比较，但是字符串之间是如何进行比较的呢？

比如：“silly” 和“stupid”它俩谁大？

第一个字母都是s，我们认为大小不存在差异，而第二个字母，i比t更靠前，所以我们说：“silly” > “stupid”

事实上串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集的序号

计算机中常用字符是使用标准ASCII编码，更准确一点，由7位二进制数表示一个字符，共可以表示128个字符，后来不够用了扩展ASCII码由8位二进制数表示一个字符，共可以表示256个字符，已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。

显然这256个字符是不够的，因此后来就有了Unicode 编码，比较常用的是由16位的二进制数表示-一个字符，这样总共就可以表示216个字符，约是65万多个字符，足够表示世界上所有语言的所有字符了。当然，为了和ASCII码兼容Unicode的前256个字符与ASCII码完全相同。

5.3串的抽象数据类型

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

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) :返回串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,len) :串S存在，1≤pos≤StrLength (s) -len+1。
          从串S中删除第pos个字符起长度为len的子串。
endADT

对于不同的高级语言，其实对串的基本操作会有不同的定义方法

在C#中，字符串操作有ToLower转小写、ToUpper转大写、IndexOf从左查找子串位置

/*T为非空串。若主串S中第pos个字符之后存在与T相等的子串，*/
/*则返回第一个这样的子串在S中的位置，否则返回0 */
int a Index (String S, String T, int pos )
{
    int n,m,i;
    String sub;
    if (pos > 0)
    {
    n=StrLength (s) ; /*得到主串S的长度*/
            m = StrLength (T) ; /*得到子串T的长度*/
            i = pos;
    while (i <= n-m+1 )
            {
    SubString (sub,S,i,m) ;/*取主串第i个位置*/
          /*长度与T相等子串给sub */
    if (StrCompare (sub,T)!= 0) /★ 如果两串不相等*/
      ++i;
    else  /*如果两串相等*/
      return i;  /*则返回i值*/
            }
    }
    return 0;  /*若无子串与T相等，返回0 */ 
}

5.4串的存储结构

5.4.1串的顺序存储结构

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

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\0” 来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才 知道了，其实这还是需要占用一个空间，何必呢。

于是对于串的顺序存储，有一些变化， 串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在-一个自由存储区，叫做“堆”。 这个堆可由C语言的动态分配函数malloc ()和free ()来管理。

5.4.2串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符， 也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全

当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

5.5朴素的模式匹配算法

在文章（相当于一个大串）中找到单词的定位，这种子串的定位操作通常称做串的模式匹配

这是串中很重要的操作之一

实例

我们要找到主串S=“wyjbat”中，找到T = “bat”这个子串的位置。通常要进行下面的步骤。

1.主串S第一位开始，S与T字母进行匹配

2.多次比较从4位开始，S与T，3个字母全匹配，匹配成功

简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。