第4章串( String 4.1串 4.2串的存储结构 4.3串基本操作的实现算法 4.4串的模式匹配算法
1 第4章 串（String） 4.1 串 4.2 串的存储结构 4.3 串基本操作的实现算法 4.4 串的模式匹配算法
4.1串 般是字母、数学、标点符 号等可屏幕显示的字符 串的基本概念 串(又称字符串)是由n(n≥0)个字符组成的有限序列 (它是数据元素为单个字符的特殊线性表。) 记为:s=“s0,s1, ······ 隐含结束符“0’, 串名串值(用“”括起来)即Asc码NU 为何要单独讨论“串”类型 1)字符串操作比其他数据类型更复杂(如拷贝、连接操作) 2)程序设计中,处理对象很多都是串类型
2 记为： s =“s0,s1, ……,sn-1” (n≥0 ) 串名 串值（用“”括起来） 一、串的基本概念 １、串（又称字符串）是由n(n ≥0)个字符组成的有限序列。 （它是数据元素为单个字符的特殊线性表。） 4.1 串 隐含结束符‘\0’ ， 即ASCII码NUL 为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型。 一般是字母、数学、标点符 号等可屏幕显示的字符
2、串长串中字符的个数(n≥0)。 3、空串串中字符的个数为0时称为空串。 4、空白串由一个或多个空格符组成的串 5、子串串S中任意个连续的字符序列叫S的子串;S叫主串。 6、子串位置子串的第一个字符在主串中的序号。 7、字符位置字符在串中的序号。 8、串相等串长度相等,且对应位置上字符相等。(即两个 串中的字符序列一一对应相等。) 问:空串和空白串有无区别? 答:有区别。 空串(Nu! String)是指长度为零的串 而空白串 Blank String)是指包含一个或多个空白字 符′′(空格键)的字符串
3 ２、串长 串中字符的个数（n≥0）。 ３、空串 串中字符的个数为0 时称为空串 。 ４、空白串 由一个或多个空格符组成的串。 ５、子串 串S中任意个连续的字符序列叫S的子串; S叫主串。 ６、子串位置 子串的第一个字符在主串中的序号。 ７、字符位置 字符在串中的序号。 ８、串相等 串长度相等，且对应位置上字符相等。（即两个 串中的字符序列一一对应相等。） 问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字 符‘ ’(空格键)的字符串
例1:现有以下4个字符串: a=“BEIb=“JING”c=“ BEJJING”d=“ BEI JING” 问:①他们各自的长度?a=3,b=4,c=7,d-8 ②a是哪个串的子串?在主串中的位置是多少? a是c和d的子串,在c和d中的位置都是1 ③空串是哪个串的子串?a是不是自己的子串? 空串是任意串的子串;任意串S都是S本身的子 串,除S本身外,S的其他子串称为S的真子串。 注:串与字符的区别 串,长度为1的串。(它不仅要存储字符 还要存储该串的长度数据1) a字符a。(只存储字符a”)
4 例1：现有以下4个字符串： a =“BEI” b =“JING” c = “BEIJING” d = “BEI JING” 问：① 他们各自的长度？ a是c和d的子串，在c和d中的位置都是1 ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 ③ 空串是哪个串的子串？a是不是自己的子串？ 空串是任意串的子串；任意串S都是S本身的子 串，除S本身外，S的其他子串称为S的真子串。 注：串与字符的区别 “a” 串，长度为１的串。（它不仅要存储字符‘a’， 还要存储该串的长度数据１） ‘a’ 字符a。(只存储字符‘a’)
串的抽象数据类型 数据集合:串的数据集合可以表示为字符序列s0,1 n-1,每 个数据元素的数据类型为字符类型。 操作集合: (1)初始化串 Initiate(S) (2)赋值 assign(S,T) (3)求串长度 Length(S) (4)比较 Compare(S,T (5)插入 Insert(S,pos,T) (6)删除 Delete(S, pos,len) (7)取子串 Substring(Spos,len (8)查找子串 Search(S, start,T (9)替换子串 Replace(S, start,T,v)
5 数据集合：串的数据集合可以表示为字符序列s0,s1, ……,sn-1，每 个数据元素的数据类型为字符类型。 操作集合： (1)初始化串 Initiate(S) (2)赋值 Assign(S,T) (3)求串长度 Length(S) (4)比较 Compare(S,T) (5)插入 Insert(S,pos,T) (6)删除 Delete(S,pos,len) (7)取子串 SubString(S pos, len) (8)查找子串 Search(S,start,T) (9)替换子串 Replace(S,start,T,V) 二、串的抽象数据类型