第四章串 学习要点 掌握串的基本操作以及串操 作在存储结构下的实现。 理解串的模式匹配算法
第四章 串 学习要点 ▪掌握串的基本操作以及串操 作在存储结构下的实现。 ▪理解串的模式匹配算法
4. 1串类型的定义 4.2串的表示和实现 4.3串的模式匹配算法
4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法
4.1串类型的定义 一、 串和基本概念 1.串的定义 串(string)是由零个或多个字符组成的有 限序列，一般记作S=‘a1a2a3.an’(n>=0) a(1≤i≤n)可以是字母、数字或其它字符。 串中字符的个数n称为串的长度。 2.空串 长度为零的串称为空串。由一个或多个 空格组成的串称为空白串
4.1 串类型的定义 一、串和基本概念 1.串的定义 串( string) 是由零个或多个字符组成的有 限序列，一般记作S=‘a1 a2 a3…an ’ (n>=0) 。 ai (1≤i≤n)可以是字母、数字或其它字符。 串中字符的个数n称为串的长度。 2.空串 长度为零的串称为空串。由一个或多个 空格组成的串称为空白串
3.子串、主串 串中任意连续字符组成的子序列称为 该串的子串。而包含子串的串相应地称 为主串。通常将子串的第一个字符在主 串的位置称为子串在主串中的位置。 如，串s1=“is”,s2=This is a string’ 则s1为s2的子串，s2相对于s1为主串 s1在s2中出现了两次，其中首次出现所对 应的主串位置是3。因此，称s1在s2中的 位置为3
3.子串、主串 串中任意连续字符组成的子序列称为 该串的子串。而包含子串的串相应地称 为主串。通常将子串的第一个字符在主 串的位置称为子串在主串中的位置。 如,串s1 =“is”，s2 =“This is a string”， 则s1为s2的子串， s2相对于s1为主串。 s1在s2中出现了两次，其中首次出现所对 应的主串位置是3。因此，称s1在s2中的 位置为3
串的抽象数据类型的定义： ADT String 数据对象： D={a aE CharacterSet, i=1,2,…,n, n≥0} 数据关系： Ri=ai-1,ai ED. i=2,…,n}
串的抽象数据类型的定义： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ | ai-1 , ai ∈D, i=2,...,n }
串的基本操作： 串赋值 串复制 串判空 串比较 求串长 串联接 求子串 串定位 串替换 串插入 串删除 串销毁
串赋值 串的基本操作： 串复制 串判空 串比较 求串长 串联接 求子串 串定位 串替换 串插入 串删除 串销毁
基本操作 StrAssign (&T,chars) 初始条件：chars是字符串常量。 操作结果：把chars赋为T的值。 例如：StrAssign(T,'datastru) 得T='datastru
StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 基本操作： 例如： StrAssign ( T, datastru) 得 T = datastru
StrCopy (&T,S) 初始条件：串S存在。 操作结果：由串S复制得串T。 例如：S='datastru',StrCopy(T,S) 得T='datastru
StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。 例如：S= datastru , StrCopy ( T, S) 得 T = datastru
StrEmpty (S) 初始条件：串$存在。 操作结果：若S为空串，则返回TRUE 否则返回FALSE。 表示空串，空串的长度为零
StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。 表示空串，空串的长度为零
StrCompare (S,T) 初始条件：串S和T存在。 操作结果：若$>T,则返回值>0： 若$=T,则返回值=0， 若S0
StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0； 若S = T，则返回值 = 0； 若S T，则返回值 0。 例如：StrCompare(data , state) 0
