数据结构：第04章 串

1、第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 1数据结构数据结构第四章第四章 串串2022年年3月月29日星期二日星期二第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 2第四章第四章 串串串的逻辑结构和线性表极为相似，区别仅在于串的逻辑结构和线性表极为相似，区别仅在于串的串的数据对象约束为字符集数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以表的基本操作中，大多以“单个元素单个元素”作为操作对象，作为操作对象，如：

2、在线性表中查找某个元素、求取某个元素、在如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以而在串的基本操作中，通常以“串的整体串的整体”作为操作为操作对象作对象，如：在串中查找某个子串、求取一个子串、在串的如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。某个位置上插入一个子串以及删除一个子串等。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 34.1 4.1 串的定义串的定义是由零个或多个字符组成的有限序列，一

3、般记为是由零个或多个字符组成的有限序列，一般记为s=“a1a2an”(n 0)其中，其中，s是串名，用单引号（也可以是用双引号括起来是串名，用单引号（也可以是用双引号括起来的）括起来的字符序列是串的值。的）括起来的字符序列是串的值。ai可以是字母、数字或可以是字母、数字或其他字符；串中字符的个数其他字符；串中字符的个数n成为成为串的长度串的长度。子串子串：串中任意个：串中任意个连续连续的字符组成的子序列。的字符组成的子序列。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。位置位置：字符在序列中的序号。子串在主串中的位置则：字符在序列中的序号。子串在主串中的位置则以子串的以子

4、串的第一个第一个字符在主串中的位置来表示。字符在主串中的位置来表示。相等相等：两个串的长度相等，并且对应位置的字符都相：两个串的长度相等，并且对应位置的字符都相等。等。注意区分注意区分空串空串与与空格串空格串的区别。的区别。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 44.1 4.1 串的定义串的定义串的逻辑结构和线性表的区别串的逻辑结构和线性表的区别:1. 串的数据对象约束为字符集。串的数据对象约束为字符集。2. 线性表的基本操作大多以线性表的基本操作大多以“单个元素单个元素”为操作对为操作对象，而串的基本操作通常以象，而串的基本操作通常以

5、“串的整体串的整体”作为操作对象。作为操作对象。 对于串可以定义以下运算：对于串可以定义以下运算：1. 置串为一个空串；置串为一个空串；2. 判断一个串是否为空串判断一个串是否为空串3. 求一个串的长度；求一个串的长度；4. 将两个串拼接在一起构成一个新串；将两个串拼接在一起构成一个新串；5. 在一个串中，求从串的第在一个串中，求从串的第i个字符开始连续个字符开始连续j个字符个字符所构成的子串；所构成的子串；6. 如果串如果串S2是是S1的子串，则可求串的子串，则可求串S2在串在串S1中第一中第一次出现的位置。次出现的位置。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式

6、匹配算法 4.4 串应用 54.1 4.1 串的定义串的定义串的抽象数据类型的定义串的抽象数据类型的定义ADT String 数据对象：数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系：数据关系：R1 | ai-1, ai D, i=2,.,n 基本操作：基本操作：StrAssign (&T, chars)初始条件：初始条件：chars是字符串常量。是字符串常量。操作结果：把操作结果：把chars赋为赋为T的值。的值。StrCopy (&T, S)初始条件：串初始条件：串S存在。操作结果：由串存在。操作结果：由串S复制得串复制得串T。D

7、estroyString (&S)初始条件：串初始条件：串S存在。操作结果：串存在。操作结果：串S被销毁。被销毁。StrEmpty (S)初始条件：串初始条件：串S存在。存在。操作结果：若操作结果：若S为空串，则返回为空串，则返回TRUE，否则返回，否则返回FALSE。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 64.1 4.1 串的定义串的定义串的抽象数据类型的定义串的抽象数据类型的定义StrCompare (S, T)初始条件：串初始条件：串S和和T存在。存在。操作结果：若操作结果：若S T，则返回值，则返回值 0；若；若S =T

8、， 则返回值则返回值 =0；若；若S T，则返回值，则返回值 0) n = StrLength(S); m = StrLength(T); i = pos;while ( i = n-m+1) SubString (sub, S, i, m);if (StrCompare(sub,T) != 0) +i ;else return i ; / while / ifreturn 0; / S中不存在与中不存在与T相等的子串相等的子串 / Index第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 114.2 4.2 串的表示和实现串的表示和实现串的顺序

9、存储结构串的顺序存储结构 PROGRAM PEX1; PROGRAM PEX1;03) 单字节存储方式：计算机以字节单字节存储方式：计算机以字节编址时编址时 带结束符带结束符 P R O G R A M P E X 1 ; 2）非紧缩格式：）非紧缩格式：1个字符个字符/字字 长度隐式表示长度隐式表示14 P R OG R A M P EX1; 1）紧缩格式：）紧缩格式：1个字符个字符/字节字节 长度显式表示长度显式表示 存储密度存储密度=串值所占存储字节实际分配的存储字节串值所占存储字节实际分配的存储字节 第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4

10、串应用 124.2 4.2 串的表示和实现串的表示和实现一、串的定长顺序存储表示一、串的定长顺序存储表示#define MAXSTRLEN 255/ 用户可在用户可在255以内定义最大串长以内定义最大串长typedef unsigned char SStringMAXSTRLEN + 1; / 0号单元存放串的长度号单元存放串的长度串的实际长度可在这个予定义长度的范围内随意设串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为定，超过予定义长度的串值则被舍去，称之为“截断截断” 。按这种串的表示方法实现的串的运算时，其基本操按这种串的表示方法实现的串的运算时，其

11、基本操作为作为“字符序列的复制字符序列的复制”。需预先定义一个串允许的最大字符个数需预先定义一个串允许的最大字符个数浪费空间、插入删除操作不便浪费空间、插入删除操作不便 第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 13一、串的定长顺序存储表示一、串的定长顺序存储表示例如：串的联接算法中需分三种情况处理：例如：串的联接算法中需分三种情况处理：Status Concat(SString S1, SString S2, SString &T) /用用T返返回由回由S1和和S2联接而成的新串。若未截断，联接而成的新串。若未截断， 则返回则返回

12、TRUE，否则否则FALSE。if (S10+S20 = MAXSTRLEN) / 未截断未截断T1.S10 = S11.S10;TS10+1.S10+S20 =S21.S20;T0 = S10+S20; uncut = TRUE; else if (S10 T,则返回值则返回值0;若若S=T返回值返回值=0，若，若ST返回值返回值0;for(i=0; iS.length & iT.length; i+)if(S.chi != T.chi)return (str1.chi - str2.chi);return (S.length -T.length);第四章 串 4.1 串的定义 4.

13、2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 17三、三、 串的块链存储表示串的块链存储表示(a) 单链表表示单链表表示a 006003b 013006c 008013d 026008e 011026f 011003Heads (b) 循环表表示循环表表示a 006003b 013006c 008013d 026008e 011026f 003 011011Heads第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 18三、三、 串的块链存储表示串的块链存储表示类类C语言描述语言描述#define CHUNKSIZE 80 / 可由

14、用户定义的块大小可由用户定义的块大小typedef struct chunk / 结点结构结点结构char chCUNKSIZE;struct Chunk *next; Chunk;typedef struct / 串的链表结构串的链表结构Chunk *head, *tail; / 串的头和尾指针串的头和尾指针int curlen; / 串的当前长度串的当前长度 LString;第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 194.3 4.3 串的模式匹配算法串的模式匹配算法模式匹配模式匹配模式匹配：模式匹配：子串（又称子串（又称模式串模式串）

15、在主串中的）在主串中的定位定位操操作。这是串的一种重要操作，很多软件，若有作。这是串的一种重要操作，很多软件，若有“编辑编辑”菜单项的话，则其中必有菜单项的话，则其中必有“查找查找”子菜单项。子菜单项。首先，回忆一下串匹配首先，回忆一下串匹配(查找查找)的定义的定义:INDEX (S, T, pos)初始条件：初始条件：串串S和和T存在存在,T是非空串，是非空串，1posStrLength(S)。操作结果：操作结果：若主串若主串S中存在和串中存在和串T值相同的子串值相同的子串, 则返回它在主串则返回它在主串S中第中第pos个字符之后第一次出现的位置个字符之后第一次出现的位置; 否则函数值为否则

16、函数值为0。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 204.3 4.3 串的模式匹配算法串的模式匹配算法1. 简单算法简单算法设主串设主串S=“ababcabcacbab”, 模式串模式串T=“abcac”。则普通算。则普通算法的匹配过程如下：法的匹配过程如下：第一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配第四趟匹

17、配a b a b c a b c a c b a ba b c a c第五趟匹配第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配第六趟匹配a b a b c a b c a c b a ba b c a c第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 214.3 4.3 串的模式匹配算法串的模式匹配算法1. 简单算法简单算法int Index(SString S, SString T, int pos) / 返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。个字符之后的位置。 若不存在，若不

18、存在，则函数值为则函数值为0。 其中，其中，T非空，非空，1posStrLength(S)。i = pos; j = 1;while (i = S0 & j T0) return i-T0;else return 0; / Index第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 224.3 4.3 串的模式匹配算法串的模式匹配算法2. 首尾匹配算法首尾匹配算法先比较模式串的第一个字符，再比较模式串的最后一个字先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第符，最后比较模式串中从第二个到第n-1个字符。个

19、字符。abcba主串主串: a b a b c a b c a a a b c b a a b c 模式串模式串: a a ( 2 次次) a a a ( 1+2 次次) a a a b b a ( 2+4 次次) a a a a ( 2+2 次次) a a ( 2次次) a b c b a (5 次次) 上述两种算法的时间复杂度为上述两种算法的时间复杂度为O(m n) 第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 234.3 4.3 串的模式匹配算法串的模式匹配算法3、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris)

20、 算法算法设主串设主串S=“ababcabcacbab”, 模式串模式串p=“abcac”。则普通算。则普通算法的匹配过程如下：法的匹配过程如下：第一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配第四趟匹配a b a b c a b c a c b a ba b c a c第五趟匹配第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配第六

21、趟匹配a b a b c a b c a c b a ba b c a c第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 24a b c a c第一趟匹配第一趟匹配a b a b c a b c a c b a b第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a b(a)b c a c改进后的匹配情况：改进后的匹配情况：第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 25改进后的模式匹配算法改进

22、后的模式匹配算法 KMP算法算法 希望某趟在希望某趟在si和和pj匹配失败后，指针匹配失败后，指针i不回溯，模式不回溯，模式p向右向右“滑动滑动”至某个位置上，使得至某个位置上，使得pk 对准对准 si 继续向右进继续向右进行。显然，现在问题的关键是串行。显然，现在问题的关键是串p“滑动滑动”到哪个位置上？到哪个位置上？不妨设位置为不妨设位置为k，即，即si和和pj匹配失败后，指针匹配失败后，指针i不动，模式不动，模式p向右向右“滑动滑动”，使，使pk和和si对准继续向右进行比较，要满对准继续向右进行比较，要满足这一假设，就要有如下关系成立：足这一假设，就要有如下关系成立：p1 p2 pk-1

23、 =si-k+1 si-k+2 si-1 (4.1)(4.1)式左边是式左边是pk前面的前面的k-1个字符，右边是个字符，右边是si 前面的前面的k-1个字符。个字符。第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 26改进后的模式匹配算法改进后的模式匹配算法 KMP算法算法 而本趟匹配失败是在而本趟匹配失败是在si和和pj之处，已经得到的部分匹之处，已经得到的部分匹配结果是：配结果是：p1 p2 pj-1 =si-j+1 si-j+2 si-1 (4.2)因为因为kj，所以有：，所以有：pj-k+1 pj-k+2 pj-1 =si-k+1 si

24、-k+2 si-1 (4.3)(4.3)式左边是式左边是 pj前面的前面的k-1个字符，右边是个字符，右边是si 前面的前面的k-1个字符，通过个字符，通过(4.1)和和(4.3)得到关系：得到关系：p1 p2 pk-1 =pj-k+1 pj-k+2 pj-1 (4.4)结论：结论：某趟在某趟在si和和pj匹配失败后，如果模式串中有满匹配失败后，如果模式串中有满足关系足关系(4)的子串存在，即：模式中的前的子串存在，即：模式中的前k-1个字符与模式个字符与模式中中pj字符前面的字符前面的k-1个字符相等时，模式个字符相等时，模式p就可以向右就可以向右“滑滑动动”至使至使pk和和si对准，继续向

25、右进行比较即可。对准，继续向右进行比较即可。 第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 27改进后的模式匹配算法改进后的模式匹配算法 （2）next函数函数 模式中的每一个模式中的每一个pj都对应一个都对应一个k值，由值，由(4.4)式可知，式可知，这个这个k值仅依赖与模式值仅依赖与模式p本身字符序列的构成，而与主本身字符序列的构成，而与主串串s无关。我们用无关。我们用nextj表示表示pj对应的对应的k值，根据以上分值，根据以上分析，析，next函数有如下性质：函数有如下性质：nextj是一个整数，且是一个整数，且0nextjj为了使为了

26、使p的右移不丢失任何匹配成功的可能，的右移不丢失任何匹配成功的可能，当存在多个满足当存在多个满足(4.4)式的式的k 值时，应取最大的，这样向值时，应取最大的，这样向右右“滑动滑动”的距离最短，的距离最短，“滑动滑动”的字符为的字符为j-nextj个。个。如果在如果在pj前不存在满足前不存在满足(4.4)式的子串，此时式的子串，此时若若p1pj，则，则k=1; 若若p1=pj，则，则k=0; 这时这时“滑动滑动”的最远，的最远，为为j-1个字符即用个字符即用p1 和和sj+1继续比较。继续比较。改进后的模式匹配算法改进后的模式匹配算法（2）next函数函数next函数定义如下函数定义如下 ：0

27、 当j=1max k | 1kj 且t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 1 其他情况nextj=设有模式串：设有模式串：t=abaabcac，则它的，则它的next函数值为：函数值为： j12345678模式串模式串abaabcac nextj01122312第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 29改进后的模式匹配算法改进后的模式匹配算法(3) KMP算法算法 在求得模式的在求得模式的next函数之后，匹配可如下进行：函数之后，匹配可如下进行：假设以指针假设以指针i和和j分别指示主串和模式中的比较字符，令分别

28、指示主串和模式中的比较字符，令i的初值为的初值为pos，j的初值为的初值为1。若在匹配过程中。若在匹配过程中si=tj，则，则i和和j分别增，若分别增，若sitj 匹配失败后，则匹配失败后，则i不变，不变，j退到退到nextj位置再比较，若相等，则指针各自增，否则位置再比较，若相等，则指针各自增，否则j再退到下一个再退到下一个next值的位置，依此类推。直至下列两种值的位置，依此类推。直至下列两种情况：一种是情况：一种是j退到某个退到某个next值时字符比较相等，则值时字符比较相等，则i和和j分别增继续进行匹配分别增继续进行匹配; 另一种是另一种是j退到值为零（即模式退到值为零（即模式的第一个

29、字符失配），则此时的第一个字符失配），则此时i和和j也要分别增，表明也要分别增，表明从主串的下一个字符起和模式重新开始匹配。从主串的下一个字符起和模式重新开始匹配。 第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 30改进后的模式匹配算法改进后的模式匹配算法(3) KMP算法算法 在假设已有在假设已有next函数情况下，函数情况下，KMP算法如下：算法如下：int StrIndex_KMP(char *s,char *t,int pos)/*从串从串s的第的第pos个字符开始找首次与串个字符开始找首次与串t相等的子串相等的子串*/ int i=pos,j=1,slen,tlen; while (i=s0 & jt0) return i-t0;/*匹配成功，返回存储位置匹配成功，返回存储位置*/ else return 1; /StrIndex_KMP第四章 串 4.1 串的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串应用 31void get_next(SString T, int *next) / 算法算法4.7 int i=1; nex