第四章串 学习要点 掌握串的基本操作以及串操 作在存储结构下的实现。 理解串的模式匹配算法
第四章 串 学习要点 ▪掌握串的基本操作以及串操 作在存储结构下的实现。 ▪理解串的模式匹配算法
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>ai-1,ai ED. i=2,…,n}
串的抽象数据类型的定义： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ < ai-1 , ai > | ai-1 , ai ∈D, i=2,...,n }