第4章串(String) 4.1串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法
1 第4章 串（String） 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法
4.1串类型的定义 串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。 记为： S=‘a1a2.an (n≥0 串名串值（用”括起来） 隐含结束符八0'， 即ASCII码NUL 为何要单独讨论“串”类型？ 1)字符串操作比其他数据类型更复杂（如拷贝、 连接操作) 2)程序设计中，处理对象很多都是串类型
2 记为： s =‘ a1 a2 . an’ (n≥0 ) 串名 串值（用‘’ 括起来） 串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。 4.1 串类型的定义 隐含结束符‘\0’ ， 即ASCII码NUL 为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型
若干术语： 串长：串中字符的个数(n≥0).n=0时称为空串⑦ 空白串：由一个或多个空格符组成的串。 问：空串和空白串有无区别？ 答： 有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串. 3
3 若干术语： 串长：串中字符的个数（n≥0）. n=0 时称为空串 。 空白串：由一个或多个空格符组成的串。 问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符 ‘ ’(空格键)的字符串
子串：串S中任意个连续的字符序列叫S的子串；S叫主串。 子串位置：子串的第一个字符在主串中的序号。 字符位置：字符在串中的序号。 串相等：串长度相等，且对应位置上字符相等。 例1：现有以下4个字符串： a =BEP b=JING'c=BEIJING' d=BEI JING' 问：①他们各自的长度？ a=3,b=4,c卡7，d=8 ②a是哪个串的子串？在主串中的位置是多少？ a是c和d的子串，在c和d中的位置都是1 ③空串是哪个串的子串？a是不是自己的子串？ “空串是任意串的子串；任意串S都是S本身的子串，除S本身 外，S的其他子串称为S的真子串。 《数据结构与算法》中山大学出版社
4 子串： 子串位置： 字符位置： 串相等： 例1：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ a是c和d的子串，在c和d中的位置都是1 串S中任意个连续的字符序列叫S的子串; S叫主串。 子串的第一个字符在主串中的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 “空串是任意串的子串；任意串S都是S本身的子串，除S本身 外，S的其他子串称为S的真子串。 ” ——《数据结构与算法》中山大学出版社 ③ 空串是哪个串的子串？a是不是自己的子串？
串的抽象数据类型定义（参见教材P71) ADT String{ Objects: D=fai aiE CharacterSet,i=1,2,.,n,n20} Relations:R1={<ai-1ai>ai-1,ai ED,i=2,., n, functions: /至少有13种基本操作 StrAssign(&T,chars) /串赋值，生成值为chars的串T StrCompare(S,T) /串比较，若5>工，返回值大于0. 最 StrLength(S) /求串长，即返回串S中的元素个数 操 Concat(&T,S1,S2) /串连接，用T返回S1+S2的新串 SubString(&Sub,S,pos,len)/求S中pos起长度为len的子串 子集 Index(S,T,pos) 仔串定位函数（模式匹配），返回位置 Replace(&S,T,V) 用孓串V替换子串T }ADT String C语言中已有类似串运算函数！
5 C语言中已有类似串运算函数！ ADT String{ Objects: D={ai | ai∈CharacterSet, i=1, 2,.，n, n≥0} Relations: R1={<ai-1,ai> | ai-1,ai ∈D, i=2, .，n} functions: //至少有13种基本操作 StrAssign(&T, chars) // 串赋值，生成值为chars的串T StrCompare(S,T) // 串比较，若S>T，返回值大于0. StrLength(S) // 求串长，即返回串S中的元素个数 Concat(&T, S1, S2) // 串连接，用T返回S1＋S2的新串 SubString(&Sub, S, pos, len) // 求S中pos起长度为len的子串 . Index(S, T, pos) //子串定位函数（模式匹配），返回位置 Replace(&S, T,V) // 用子串V替换子串T }ADT String 串的抽象数据类型定义（参见教材P71） 最 小 操 作 子 集