Tim的资源站

一、串的基本概念

（一）串的定义

串是由0个或多个任意字符组成的字符序列，一般记作：

s = “s₁s₂s₃…s_n”

其中，s是串名，双引号为串的定界符，引号中间的字符序列为串值，引号本身不属于串的内容。

s_i（1≤i≤n）是一个任意字符，成为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。当n=0时，称为空串。

以下是一些串的示例：

a = "Welcome to Beijing"
b = "Welcome"
c = "Bei"
d = "   "

（二）几个术语

1. 子串与主串

   串中任意连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。上例中，b是a的子串，a是主串。

2. 子串的位置

   子串的第一个字符在主串中的序号称为子串的位置。

3. 串相等

   两个串的长度相等且对应字符都相等，则称为串相等。

4. 空格串

   串中的字符全是空格。上例中，d是空格串。

二、串的基本运算

（一）求串长

操作条件：串s存在

操作结果：求出串s中的字符的个数

设串s₁ = “abc123”，s₂=“bhjkl433”，则StrLength(s₁) = 6，StrLength(S₂) = 8。

（二）串赋值

操作条件：s₁是一个串变量，s₂是一个串常量或串变量（通常，为串常量时称为串赋值，为串变量时称为串复制）。

操作结果：将s₂的串值赋值给s₁，s₁原来的值被覆盖。

设串s₁ = “abc123”，s₂ = “bhjk433”，则StrAssign(s₁, s₂)，s₁、s₂的值都是"bhjk433"。

（三）串连接

操作条件：s₁，s₂存在。

操作结果：两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。对于StrConcat(s₁, s₂, s)来说，产生新串s，s₁、s₂不改变；对于StrConcat(s1, s2)来说，在s₁的后面连接s₂的串值，s₁改变，s₂不改变。

例如，s₁ = “abc”，s₂ = “123”，前者操作结果是s = “abc123”，后者操作结果是s₁ = “abc123”。

（四）求子串

操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。

操作结果：SubStr(s, i, len)返回从串s的第i个字符开始的长度为len的子串，len为0时得到的是空串。

例如：SubStr(“abcdefghi”, 3, 4) = “cdef”。

（五）串比较

操作条件：s₁、s₂存在。

操作结果：若s₁ = s₂，则StrCmp(s₁, s₂)返回值为0；若s₁ < s₂，则返回负值；若s₁ > s₂，则返回正值。

（六）子串定位

操作条件：串s、t存在。

操作结果：若 t∈s，则返回 t 在 s 中首次出现的位置，否则返回值为-1。

例如：StrIndex(“abcdebda”, “bc”) = 2，StrIndex(“abcdebda”, “ba”) = -1

（七）串插入

操作条件：串s、t存在，1≤i≤StrLength(s)+1。

操作结果：StrInsert(s, i, t)将串t插入串s的第i个位置上，s的串值发生改变。

（八）串删除

操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。

操作结果：StrDelete(s, i, len) 删除串s中从第i个字符开始的长度为len的子串，s的串值改变。

（九）串替换

操作条件：串s、t、r存在，t不为空。

操作结果：StrRep(s, t, r)用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。

以上是串的几个基本操作。其中前5个操作是最为基本的，不能用其他的操作来合成；因此，通常将这5个基本操作成为最小操作集。