4.1.1 串的定义#

串(string)是由零个或多个字符组成的有限序列，通常记为

其中，S 是串名，单引号括起的字符序列是串的值；每个 $a_i$ 可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。当 n=0 时，该串称为空串(用 $\varnothing$ 表示)。

串中任意多个连续字符组成的子序列称为该串的子串，而包含该子串的串称为主串。某个字符在串中的序号称为该字符在串中的位置；子串在主串中的位置以其第1个字符在主串中的位置来标识。当两个串长度相等，且对应位置上的字符完全相同时，称这两个串相等。

例如，设串 $A='$China Beijing’，$B='$Beijing’，$C='$China’，则它们的长度分别为13、7和5。其中，B和C都是A的子串，B在A中的位置为7，C在A中的位置为1。

需注意，由一个或多个空格(空格是一种特殊字符)组成的串称为空格串，空格串不是空串，其长度等于其中空格字符的个数。

串的逻辑结构与线性表极为相似，区别仅在于串的数据对象被限定为字符集。但在基本操作上，二者有显著差异：线性表的基本操作通常以单个元素为单位，如查找、插入或删除某个元素；而串的基本操作一般以子串为单位，如查找、插入或删除一个子串等。

4.1.2 串的基本操作#

• StrAssign(&T,chars): 赋值操作。将串 T 赋值为 chars。
• StrCopy(&T,S): 复制操作。将串 S 复制给串 T。
• StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
• StrCompare(S,T)：比较操作。若 S>T，返回值>0；若 S=T，返回值=0；若 S<T，返回值<0。
• StrLength(S)：求串长操作。返回串 S 中字符的个数。
• SubString(&Sub,S,pos,len): 求子串操作。用 Sub 返回串 S 中从第 pos 个字符起、长度为 len 的子串。
• Concat(&T, S1, S2)：串联接操作。用 T 返回由 S1 和 S2 联接而成的新串。
• Index (S,T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回其在 S 中首次出现的位置；否则返回 0。
• ClearString(&S): 清空操作。将串 S 置为空串。
• DestroyString(&S): 销毁操作。将串 S 销毁。

不同的高级语言对串的基本操作集可能有不同的定义方式。在上述操作中，StrAssign(赋值)、StrCompare(比较)、StrLength(求长)、Concat(联接)和SubString(求子串)这五种操作构成了串类型的最小操作子集：它们无法通过其他串操作实现；而其余串操作(除ClearString和DestroyString外)均可基于该最小操作子集实现。

4.1.3 串的存储结构#

1
#define MAXLEN 255      //预定义最大串长为255
2
typedef struct{
3
    char ch[MAXLEN];    //每个分量存储一个字符
4
    int length;         //串的实际长度
5
} SString;

1
typedef struct{
2
    char *ch;       //按串长分配存储区，ch指向串的基地址
3
    int length;     //串的长度
4
}HString;