Java版数据结构与算法：串的基本概念

计算机已被大量用来处理非数值计算问题，如文本编辑、自然语言理解、关键词搜索等，在这些问题中所涉及的处理对象多数是字符串数据。在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。随着计算机应用的发展，字符串作为一种变量类型出现，并产生了一系列字符串的操作。字符串一般简称为串（String），是由零个或多个字符组成的有限序列。一般记为

式中，S是串名，用双引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符。

串是一种特殊的线性表，其特殊性在于：串中的每个数据元素仅由一个字符组成。串中字符的数目n称为串的长度，长度为0的串称为空串。

【例4.1】设A、B、C为以下串：A="data"，B="structure"，C=""，求它们的长度。

串的长度为串中字符的数目，所以串A、B、C的长度分别是4、9、0。

注意：在Java语言中，单引号括起来的是Unicode字符常量，数据类型是char，占用2个字节，如'a'、'汉'等都是char类型，字符长度为1；由双引号括起来的是字符串常量，数据类型是String，如"a"、"汉字是方块字"等，长度根据具体内容而定。

子串和主串：串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常把字符在序列中的序号称为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。空串是任意串的子串，任意串是其自身的子串。

【例4.2】有3个字符串：A="data"，B="structure"，C="data structure"，求子串A和子串B在主串C中的位置。

子串在主串中的位置是子串的第一个字符在主串中的位置，因此，子串A在主串C中的位置是0，而子串B在主串C中的位置是5。(www.xing528.com)

串的比较：通过组成串的字符之间的比较来进行。给定两个串：X="x0x1…xn-1"和Y="y0y1…ym-1"，则：

（1）当n=m且x0=y0，x1=y1，…，xn-1=ym-1时，称X=Y。

（2）当下列条件之一成立时，称X＜Y：

① n＜m且xi=yi（0≤i＜n）。

② 存在k＜min(m,n)，使得xi=yi（0≤i＜k-1）且xk＜yk。

【例4.3】现有3个字符串S1="ab12cd"，S2="ab12"，S3="ab13"，比较其大小。

根据串的比较规则，通过组成串的字符之间的比较，得到S2＜S1、S2＜S3。