第4章串 4.1串的定义 4.2串的表示和实现 4.3串的模式匹配算法 4.4串操作应用举例
第4章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例
第4章串 在非数值处理、事务处理等问题常涉及到一 系列的字符操作。比如汇编和语言编译、信息检 索系统、文字编辑系统、问答系统、自然语言翻 译系统等，都是以字符串作为处理对象的。 计算机的硬件结构主要是反映数值计算的要 求，因此，字符串的处理比具体数值处理复杂。 本章讨论串的存储结构及几种基本的处理
第4章 串 在非数值处理、事务处理等问题常涉及到一 系列的字符操作。比如汇编和语言编译、信息检 索系统、文字编辑系统、问答系统、自然语言翻 译系统等，都是以字符串作为处理对象的。 计算机的硬件结构主要是反映数值计算的要 求，因此，字符串的处理比具体数值处理复杂。 本章讨论串的存储结构及几种基本的处理
4.1 串类型的定义 4.1.1串的基本概念 串（字符串string),:由零个或多个字符组成的有限序列。 -记作S=‘a1a2…an’ (n≥0) 注意：串值一定要用单引号 ●串名：S; 括起来。单引号本身不属于 ●串值：用单引号括起来的字符序列。 串，只是为了避免混淆。 ●a:可以是字母、数字或其他字符。 长度：串中字符的数目n。 空串：含零个字符的串，表示。 注意：空串和空格串的区别。 - 空格串：由一个或多个空格组成的串。 例如：x=‘123’表明x是一个串变量名，赋予它的值是字符序列123， x=123 表明x是一个整型变量，赋予它的值为整数123
4.1 串类型的定义 4.1.1 串的基本概念 串(字符串string)：由零个或多个字符组成的有限序列。 – 记作 S=‘a1a2…an ’ （n≥0） ⚫ 串名：S； ⚫ 串值：用单引号括起来的字符序列。 ⚫ ai可以是字母、数字或其他字符。 – 长度：串中字符的数目n。 – 空串：含零个字符的串，表示。 – 空格串：由一个或多个空格组成的串。 例如： x=‘123’表明x是一个串变量名，赋予它的值是字符序列123， x=123 表明x是一个整型变量，赋予它的值为整数123。 注意：串值一定要用单引号 括起来。单引号本身不属于 串，只是为了避免混淆。 注意：空串和空格串的区别
-子串：串中任意个连续的字符组成的子序列。 -字符在串的位置：字符在序列中的序号。 -子串在串的位置：子串的第一个字符在串中的位置。 一相等：当且仅当两个串的值相等。长度相等且对应位置的 字符都相等。 例子： a= BEI' b=‘JING' c=‘BEIJING' d=‘BEI JING' 长度分别为3、4、7、8； a和b都是c和d的子串； a在c和d中的位置都是l; b在c和d中的位置是4和5； a、b、c、d彼此不相等
-子串：串中任意个连续的字符组成的子序列。 -字符在串的位置：字符在序列中的序号。 -子串在串的位置：子串的第一个字符在串中的位置。 -相等：当且仅当两个串的值相等。长度相等且对应位置的 字符都相等。 例子： a=‘BEI’ b=‘JING’ c=‘BEIJING’ d=‘BEI JING’ 长度分别为3、4、7、8； a和b都是c和d的子串； a在c和d中的位置都是1； b在c和d中的位置是4和5； a、b、c、d彼此不相等
串的比较： 串的比较：通过组成串的字符之间的比较来进行的。 给定两个串：X=‘x2xn’和Y=‘yy2ym’，则： 1.当=m且x1y1,…,xwym时，称X=Y; 2.当下列条件之一成立时，称X<Y: (1)n<m且xy:(1≤in); (2)存在k≤min(m,m),使得xy:(1≤达k-1)且xk<yk。 例：S1=‘ab12cd’,S2=‘ab12’,S3=‘ab13’
串的比较： 串的比较：通过组成串的字符之间的比较来进行的。 给定两个串：X= ‘x1 x2…xn ’和Y= ‘y1 y2…ym ’ ，则： 1. 当n=m且x1 =y1， … ，xn =ym时，称X=Y； 2. 当下列条件之一成立时，称X＜Y： ⑴ n＜m且xi =yi（1≤ i≤n）； ⑵存在k≤min(m,n)，使得xi =yi (1≤i≤k-1)且xk＜yk。 例：S1=‘ab12cd ’，S2=‘ab12’，S3=‘ab13’