第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’
串与线性表的区别： ◆串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 然而，串的基本操作和线性表有很大差别。在线 性表的基本操作中，大多以“单个元素”作为操 作对象，如：在线性表中查找某个元素、求取某 个元素、在某个位置上插入一个元素和删除一个 元素等； ◆ 而在串的基本操作中，通常以“串的整体”作为 操作对象，如：在串中查找某个子串、求取一个 子串、在串的某个位置上插入一个子串以及删除 一个子串等
串与线性表的区别： ◆ 串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 然而，串的基本操作和线性表有很大差别。在线 性表的基本操作中，大多以“单个元素”作为操 作对象，如：在线性表中查找某个元素、求取某 个元素、在某个位置上插入一个元素和删除一个 元素等； ◆ 而在串的基本操作中，通常以“串的整体”作为 操作对象，如：在串中查找某个子串、求取一个 子串、在串的某个位置上插入一个子串以及删除 一个子串等
4.1.2 串的抽象数据类型定义 ADT String{ 数据对象：D={ala:∈CharacterSet,i=l,2,,n,n≥0} 数据关系：R={a,a1∈D,=2,3,n} 基本操作： StrAssign(&T,chars) 初始条件：chars是串常量。 操作结果：赋于串T的值为chars。 StrCopy(&T,S) 初始条件：串S存在。 操作结果：由串S复制得串T。 DestroyString(&S) 初始条件：串S存在。 操作结果：串S被销毁
4.1.2 串的抽象数据类型定义 ADT String{ 数据对象：D = { ai |ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系：R = {| ai-1, ai∈D, i=2,3,…,n } 基本操作： StrAssign (&T, chars) 初始条件：chars 是串常量。 操作结果：赋于串T的值为chars。 StrCopy (&T, S) 初始条件：串S 存在。 操作结果：由串S 复制得串T。 DestroyString (&S) 初始条件：串S 存在。 操作结果：串S 被销毁
StrEmpty (S) 初始条件：串S存在。 操作结果：若S为空串，则返回TRUE,否则返回FALSE。 StrCompare(S,T) 初始条件：串S和T存在。 操作结果：若S>T, 则返回值>0；若S=T,则返回值=0；若S<T, 则返回值<0。 StrLength(S) 初始条件：串S存在。 操作结果：返回串S序列中的字符个数，即串的长度。 ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。 Concat(&T,S1,S2) 初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 Replace(&S,T,V) 初始条件：串S,T和V存在，T是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串
StrEmpty (S) 初始条件：串S 存在。 操作结果：若S 为空串，则返回TRUE，否则返回FALSE。 StrCompare (S, T) 初始条件：串S 和 T 存在。 操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T， 则返回值<0。 StrLength (S) 初始条件：串S 存在。 操作结果：返回串S 序列中的字符个数，即串的长度。 ClearString (&S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 Replace (&S, T, V) 初始条件：串S，T 和 V 存在，T 是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串
SubString(&Sub,S,pos,len) 初始条件：串S存在，l≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S).。 操作结果：若主串$中存在和串T值相同的子串，则返回它 在主串S中第pos个字符之后第一次出现的位置； 否则函数值为0。 StrInsert(&S,pos,T) 初始条件：串S和T存在，1≤pos≤StrLength(S)+1。 操作结果：在串S的第pos个字符之前插入串T。 StrDelete(&S,pos,len) 初始条件：串S存在，1≤pos≤StrLength(Slen+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 }ADT String
SubString (&Sub, S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串S的第 pos 个字符起长度为len的子串。 Index (S, T, pos) 初始条件：串S和T存在，T 是非空串， 1≤pos≤StrLength(S)。 操作结果：若主串S中存在和串T值相同的子串，则返回它 在主串S中第pos个字符之后第一次出现的位置； 否则函数值为0。 StrInsert (&S, pos, T) 初始条件：串S 和 T 存在，1≤pos≤StrLength(S)＋1。 操作结果：在串S 的第 pos 个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件：串S 存在，1≤pos≤StrLength(S)-len+1。 操作结果：从串S 中删除第pos 个字符起长度为len 的子串。 } ADT String
定位函数（算法4.1) ● 基本思想：从主串S中取“第i个字符起、长度和串T相等的子串” 和串T比较，若相等，则求得函数值为i,否则i值增1直至找到相等 的子串或者不存在和T相等的子串为止。 int Index (String S,String T,int pos){ /T为非空串。若主串$中第pos个字符之后存在与T相等的子串， /则返回第一个这样的子串在$中的位置，否则返回0。 if (pos >0){ n StrLength(S);m=StrLength(T);i pos; while（i<∈n-mt1)[ SubString(sub,S,i,m);/取从第i个起长度为m的子串 if (StrCompare(sub,T)!=0)+i; else return i; /找到和T相等的子串 }/while /if return 0; //$中不存在满足条件的子串 }/Index
定位函数（算法4.1） ⚫ 基本思想：从主串S中取“第i个字符起、长度和串T相等的子串” 和串T比较，若相等，则求得函数值为i，否则i值增1直至找到相等 的子串或者不存在和T相等的子串为止。 int Index (String S, String T, int pos){ // T为非空串。若主串S中第 pos 个字符之后存在与T相等的子串， // 则返回第一个这样的子串在S中的位置，否则返回0。 if (pos > 0){ n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1){ SubString (sub,S,i,m); // 取从第i个起长度为m的子串 if (StrCompare(sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } // while } // if return 0; // S 中不存在满足条件的子串 } // Index