厦门理工算法第四章.ppt

第4章 串 课前导学 4.1 串类型的定义 4.2 串的表示和实现 4.3** 串的模式匹配算法 4.4 串操作应用举例 4.4.1 文本编辑 4.4.2** 建立词索引表 学习目标 了解串的相关概念。 掌握串的3种机内表示方法和实现，即定长顺序存储、堆分配存储和块链存储。 熟悉串的操作应用。 4.1 串类型的定义 串（string，或称字符串）：是由零个或多个字符组成的有限序列。通常记作　　　 s = ′a1a2a3…an′ (n≥0)  其中，S是串的名，用单引号括起来的字符序列是串的值。串中字符的数目n称为串的长度。含零个字符的串称为空串(null string)，它的长度为零。 串的相关概念 在各种应用中，空格通常是串的字符集合中的一个元素，可以出现在其他字符之间。由一个或多个空格组成的串称为空格串(blank string)，例如: ′ ′和′ ′, 它的长度为串中空格字符的个数。 注意：空串和空格串的不同，例如′ ′和′′分别表示长度为1的空格串和长度为0的空串。 串的相关概念 子串：指串中任意个连续的字符组成的子序列。相应的包含子串的串称为主串。 位置：对字符而言是指字符在串中的序号；对子串而言是指子串第一个字符在主串中的序号。 相等：当且仅当两个串的值相等。即串长相等，且对应位置的字符相等。 下面来看看对于串的抽象数据类型定义: 串的抽象数据类型 ADT String { 数据对象：D＝{ai|ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1,ai | ai-1 ,ai ∈D, i=2,...,n } 基本操作： StrAssign (T, chars) 初始条件：chars 是串常量。 操作结果：赋于串T的值为 chars。　 StrCopy (T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。 　 串的抽象数据类型 DestroyString (S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty (S) 初始条件：串 S 存在。 操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。 StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回 值0。 串值大小是按词典次序进行比较的，如：　　　　StrCompare(data,stru)0　　　　StrCompare(cat,case)0 显然，只有在两个串的长度相等且每个字符一一对等的情况下称两 个串相等。 串的抽象数据类型 StrLength (S) 初始条件：串 S 存在。 操作结果：返回串 S 序列中的字符个数，即串的长度。ClearString (S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。 Concat (T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 “串联接”操作的结果是生成一个新的串，其值是“将第二的串的第一 个字符紧接在第一个串的最后一个字符之后“得到的字符序列。如操作 Concat(T, man,kind)得到的结果是：T =mankind。 串的抽象数据类型 SubString (Sub, S, pos, len) 初始条件：串S存在,1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。  “子串”指串中任意个连续的字符组成的子序列。如：操作 SubString(Sub,“commander”,4,3)得到的结果是Sub=“man”。显然必须在满 足初始条件中规定的“起始位置”和“长度”之间的约束关系时才能求得一 个合法的子串。允许len的下限为0是由于空串也是合法串，但实际上求 长度为0的子串是没有意义的。 串的抽象数据类型 Index (S, T, pos) 初始条件:串S和T存在,T 是非空串，1≤pos≤StrLength(S)。 操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos 个字符之后第一次出现的位置；否则函数值为0。 包含子串的串相应地称为主串。“子串在主串中的位置”指的是子串 中的第1个字符在主串中的位序。如子串‘man’在主串‘commander’中的位 置为4。In