第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 1数据结构数据结构第四章第四章 串串01八月八月2024第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 2第四章第四章 串串串的逻辑结构和线性表极为相似，区别仅在于串的逻辑结构和线性表极为相似，区别仅在于串的串的数据对象约束为字符集数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以表的基本操作中，大多以“单个元素单个元素”作为操作对象，作为操作对象，如：在线性表中查找某个元素、求取某个元素、在如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以而在串的基本操作中，通常以“串的整体串的整体”作为操作为操作对象作对象，如：在串中查找某个子串、求取一个子串、在串的如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。某个位置上插入一个子串以及删除一个子串等。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 34.1 4.1 串的定义串的定义是由零个或多个字符组成的有限序列，一般记为是由零个或多个字符组成的有限序列，一般记为s=“a1a2an”(n 0)其中，其中，s是串名，用单引号（也可以是用双引号括起来是串名，用单引号（也可以是用双引号括起来的）括起来的字符序列是串的值。的）括起来的字符序列是串的值。ai可以是字母、数字或可以是字母、数字或其他字符；串中字符的个数其他字符；串中字符的个数n成为成为串的长度串的长度。子串子串：串中任意个：串中任意个连续连续的字符组成的子序列。的字符组成的子序列。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。位置位置：字符在序列中的序号。子串在主串中的位置则：字符在序列中的序号。子串在主串中的位置则以子串的以子串的第一个第一个字符在主串中的位置来表示。字符在主串中的位置来表示。相等相等：两个串的长度相等，并且对应位置的字符都相：两个串的长度相等，并且对应位置的字符都相等。等。注意区分注意区分空串空串与与空格串空格串的区别。的区别。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 44.1 4.1 串的定义串的定义串的串的逻辑结构和构和线性表的区性表的区别:1.串的数据对象约束为字符集。串的数据对象约束为字符集。2.线性表的基本操作大多以线性表的基本操作大多以“单个元素单个元素”为操作对为操作对象，而串的基本操作通常以象，而串的基本操作通常以“串的整体串的整体”作为操作对象。作为操作对象。对于串可以定义以下运算：对于串可以定义以下运算：1.置串为一个空串；置串为一个空串；2.判断一个串是否为空串判断一个串是否为空串3.求一个串的长度；求一个串的长度；4.将两个串拼接在一起构成一个新串；将两个串拼接在一起构成一个新串；5.在在一一个个串串中中，求求从从串串的的第第i个个字字符符开开始始连连续续j个个字字符符所构成的子串；所构成的子串；6.如如果果串串S2是是S1的的子子串串，则则可可求求串串S2在在串串S1中中第第一一次出现的位置。次出现的位置。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 54.1 4.1 串的定义串的定义串的抽象数据串的抽象数据类型的定型的定义ADTString数据对象：数据对象：Dai|aiCharacterSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n基本操作：基本操作：StrAssign(&T,chars)初始条件：初始条件：chars是字符串常量。是字符串常量。操作结果：把操作结果：把chars赋为赋为T的值。的值。StrCopy(&T,S)初始条件：串初始条件：串S存在。操作结果：由串存在。操作结果：由串S复制得串复制得串T。DestroyString(&S)初始条件：串初始条件：串S存在。操作结果：串存在。操作结果：串S被销毁。被销毁。StrEmpty(S)初始条件：串初始条件：串S存在。存在。操作结果：若操作结果：若S为空串，则返回为空串，则返回TRUE，否则返回，否则返回FALSE。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 64.1 4.1 串的定义串的定义串的抽象数据串的抽象数据类型的定型的定义StrCompare(S,T)初始条件：串初始条件：串S和和T存在。存在。操作结果：若操作结果：若ST，则返回值，则返回值0；若；若S=T，则返回值则返回值=0；若；若ST，则返回值，则返回值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;elsereturni;/while/ifreturn0;/S中不存在与中不存在与T相等的子串相等的子串/Index第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 114.2 4.2 串的表示和实现串的表示和实现串的串的顺序存序存储结构构PROGRAMPEX1;PROGRAMPEX1;03)单单字字节节存存储储方方式式：计计算算机机以以字字节节编编址址时时带带结结束束符符P R O G R A M P E X 1 ;2 ）非非紧紧缩缩格格式式： 1个个字字符符/字字长长度度隐隐式式表表示示14 P R OG R A MP EX1;1 ）紧紧缩缩格格式式： 1个个字字符符/字字节节长长度度显显式式表表示示存储密度存储密度=串值所占存储字节实际分配的存储字节串值所占存储字节实际分配的存储字节第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 124.2 4.2 串的表示和实现串的表示和实现一、串的定一、串的定长顺序存序存储表示表示#defineMAXSTRLEN255/用户可在用户可在255以内定义最大串长以内定义最大串长typedefunsignedcharSStringMAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度串的实际长度可在这个予定义长度的范围内随意设定，串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为超过予定义长度的串值则被舍去，称之为“截断截断”。按这种串的表示方法实现的串的运算时，其基本操作按这种串的表示方法实现的串的运算时，其基本操作为为“字符序列的复制字符序列的复制”。需预先定义一个串允许的最大字符个数需预先定义一个串允许的最大字符个数浪费空间、插入删除操作不便浪费空间、插入删除操作不便第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 13一、串的定长顺序存储表示一、串的定长顺序存储表示例如：串的例如：串的联接算法中需分三种情况接算法中需分三种情况处理：理：StatusConcat(SStringS1,SStringS2,SString&T)/用用T返返回由回由S1和和S2联接而成的新串。若未截断，联接而成的新串。若未截断，则返回则返回TRUE，否则，否则FALSE。if(S10+S20=MAXSTRLEN)/未截断未截断T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;elseif(S10T,则返回值则返回值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.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 17三、三、 串的块链存储表示串的块链存储表示(a)单链表表示单链表表示a006003b013006c008013d026008e011026f011003Heads(b)循环表表示循环表表示a006003b013006c008013d026008e011026f003011011Heads第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 18三、三、 串的块链存储表示串的块链存储表示类C语言描述言描述#defineCHUNKSIZE80/可由用户定义的块大小可由用户定义的块大小typedefstructchunk/结点结构结点结构charchCUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构串的链表结构Chunk*head,*tail;/串的头和尾指针串的头和尾指针intcurlen;/串的当前长度串的当前长度LString;第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 194.3 4.3 串的模式匹配算法串的模式匹配算法模式匹配模式匹配模式匹配：模式匹配：子串（又称子串（又称模式串模式串）在主串中的）在主串中的定位定位操操作。这是串的一种重要操作，很多软件，若有作。这是串的一种重要操作，很多软件，若有“编辑编辑”菜单项的话，则其中必有菜单项的话，则其中必有“查找查找”子菜单项。子菜单项。首先，回忆一下串匹配首先，回忆一下串匹配(查找查找)的定义的定义:INDEX(S,T,pos)初始条件：初始条件：串串S和和T存在存在,T是非空串，是非空串，1posStrLength(S)。操作结果：操作结果：若主串若主串S中存在和串中存在和串T值相同的子串值相同的子串,则返回它在主串则返回它在主串S中第中第pos个字符之后第一次出现的位置个字符之后第一次出现的位置;否则函数值为否则函数值为0。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 204.3 4.3 串的模式匹配算法串的模式匹配算法1.简单算法算法设主串设主串S=“ababcabcacbab”,模式串模式串T=“abcac”。则普通算。则普通算法的匹配过程如下：法的匹配过程如下：第一趟匹配第一趟匹配ababcabcacbababcac第二趟匹配第二趟匹配ababcabcacbababcac第三趟匹配第三趟匹配ababcabcacbababcac第四趟匹配第四趟匹配ababcabcacbababcac第五趟匹配第五趟匹配ababcabcacbababcac第六趟匹配第六趟匹配ababcabcacbababcac第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 214.3 4.3 串的模式匹配算法串的模式匹配算法1.简单算法算法intIndex(SStringS,SStringT,intpos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。个字符之后的位置。若不存在，若不存在，则函数值为则函数值为0。其中，其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&jT0)returni-T0;elsereturn0;/Index第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 224.3 4.3 串的模式匹配算法串的模式匹配算法2.首尾匹配算法首尾匹配算法先比较模式串的第一个字符，再比较模式串的最后一个字先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第符，最后比较模式串中从第二个到第n-1个字符。个字符。abcba主串主串:ababcabcaaabcbaabc模式串模式串:aa(2次次)aaa(1+2次次)aaabba(2+4次次)aaaa(2+2次次)aa(2次次)abcba(5次次)上述两种算法的时间复杂度为上述两种算法的时间复杂度为O(m n)第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 234.3 4.3 串的模式匹配算法串的模式匹配算法3、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法算法设主串设主串S=“ababcabcacbab”,模式串模式串p=“abcac”。则普通算。则普通算法的匹配过程如下：法的匹配过程如下：第一趟匹配第一趟匹配ababcabcacbababcac第二趟匹配第二趟匹配ababcabcacbababcac第三趟匹配第三趟匹配ababcabcacbababcac第四趟匹配第四趟匹配ababcabcacbababcac第五趟匹配第五趟匹配ababcabcacbababcac第六趟匹配第六趟匹配ababcabcacbababcac第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 24abcac第一趟匹配第一趟匹配ababcabcacbab第二趟匹配第二趟匹配ababcabcacbababcac第三趟匹配第三趟匹配ababcabcacbab(a)bcac改进后的匹配情况：改进后的匹配情况：第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 25改进后的模式匹配算法改进后的模式匹配算法 KMP算法算法希希望望某某趟趟在在si和和pj匹匹配配失失败败后后，指指针针i不不回回溯溯，模模式式p向向右右“滑滑动动”至至某某个个位位置置上上，使使得得pk对对准准si继继续续向向右右进进行行。显显然然，现现在在问问题题的的关关键键是是串串p“滑滑动动”到到哪哪个个位位置置上上？不不妨妨设设位位置置为为k，即即si和和pj匹匹配配失失败败后后，指指针针i不不动动，模模式式p向向右右“滑滑动动”，使使pk和和si对对准准继继续续向向右右进进行行比比较较，要要满足这一假设，就要有如下关系成立：满足这一假设，就要有如下关系成立：p1p2pk-1=si-k+1si-k+2si-1(4.1)(4.1)式式左左边边是是pk前前面面的的k-1个个字字符符，右右边边是是si前前面面的的k-1个字符。个字符。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 26改进后的模式匹配算法改进后的模式匹配算法 KMP算法算法而而本本趟趟匹匹配配失失败败是是在在si和和pj之之处处，已已经经得得到到的的部部分分匹匹配结果是：配结果是：p1p2pj-1=si-j+1si-j+2si-1(4.2)因为因为kj，所以有：，所以有：pj-k+1pj-k+2pj-1=si-k+1si-k+2si-1(4.3)(4.3)式式左左边边是是pj前前面面的的k-1个个字字符符，右右边边是是si前前面面的的k-1个字符，通过个字符，通过(4.1)和和(4.3)得到关系：得到关系：p1p2pk-1=pj-k+1pj-k+2pj-1(4.4)结论：结论：某趟在某趟在si和和pj匹配失败后，如果模式串中有满匹配失败后，如果模式串中有满足关系足关系(4)的子串存在，即：模式中的前的子串存在，即：模式中的前k-1个字符与模式个字符与模式中中pj字符前面的字符前面的k-1个字符相等时，模式个字符相等时，模式p就可以向右就可以向右“滑滑动动”至使至使pk和和si对准，继续向右进行比较即可。对准，继续向右进行比较即可。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 27改进后的模式匹配算法改进后的模式匹配算法 （2）next函数函数模模式式中中的的每每一一个个pj都都对对应应一一个个k值值，由由(4.4)式式可可知知，这这个个k值值仅仅依依赖赖与与模模式式p本本身身字字符符序序列列的的构构成成，而而与与主主串串s无无关关。我我们们用用nextj表表示示pj对对应应的的k值值，根根据据以以上上分分析析，next函数有如下性质：函数有如下性质：nextj是一个整数，且是一个整数，且0nextjj为为了了使使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当j=1maxk|1kj且t1t2tk-1=tj-k+1tj-k+2tj-11其他情况nextj=设有模式串：设有模式串：t=abaabcac，则它的，则它的next函数值为：函数值为：j12345678模式串模式串abaabcacnextj01122312第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 29改进后的模式匹配算法改进后的模式匹配算法(3)KMP算法算法在求得模式的在求得模式的next函数之后，匹配可如下进行：函数之后，匹配可如下进行：假设以指针假设以指针i和和j分别指示主串和模式中的比较字符，令分别指示主串和模式中的比较字符，令i的初值为的初值为pos，j的初值为的初值为1。若在匹配过程中。若在匹配过程中si=tj，则，则i和和j分别增，若分别增，若sitj匹配失败后，则匹配失败后，则i不变，不变，j退到退到nextj位置再比较，若相等，则指针各自增，否则位置再比较，若相等，则指针各自增，否则j再退到下一个再退到下一个next值的位置，依此类推。直至下列两种值的位置，依此类推。直至下列两种情况：一种是情况：一种是j退到某个退到某个next值时字符比较相等，则值时字符比较相等，则i和和j分别增继续进行匹配分别增继续进行匹配;另一种是另一种是j退到值为零（即模式退到值为零（即模式的第一个字符失配），则此时的第一个字符失配），则此时i和和j也要分别增，表明也要分别增，表明从主串的下一个字符起和模式重新开始匹配。从主串的下一个字符起和模式重新开始匹配。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 30改进后的模式匹配算法改进后的模式匹配算法(3)KMP算法算法在假设已有在假设已有next函数情况下，函数情况下，KMP算法如下：算法如下：intStrIndex_KMP(char*s,char*t,intpos)/*从串从串s的第的第pos个字符开始找首次与串个字符开始找首次与串t相等的子串相等的子串*/inti=pos,j=1,slen,tlen;while(i=s0&jt0)returni-t0;/*匹配成功，返回存储位置匹配成功，返回存储位置*/elsereturn1;/StrIndex_KMP第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 31voidget_next(SStringT,int*next)/算法算法4.7inti=1;next1=0;intj=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;elsej=nextj;第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 32NextNext函数的缺陷函数的缺陷根据前面定根据前面定义的的Next函数函数对模式串模式串aaaab和主串和主串aaabaaaabj12345模式串模式串aaaabnextj01234改进后的模式匹配算法改进后的模式匹配算法（2）next函数函数nextval函数定义如下函数定义如下：0当当j=1maxk|1=k bmax= a; elsem ax= b; main()floata,b,max;scanf(“%f,%f”,&a,&b);ifabmax=a;elsemax=b;201第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 394.4 4.4 串应用串应用文本编辑软件文本编辑软件行表和行表和页表表行号行号起始地址起始地址长度长度1002018101209171022262410325017104267151052822页号页号起始行号起始行号0100002050031000415005200分别设立页指针、行指针和字符指针分别指向当分别设立页指针、行指针和字符指针分别指向当前操作的页、行和字符。前操作的页、行和字符。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 40本章小结本章小结1.熟悉串的七种基本操作的定义，并能利熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方用这些基本操作来实现串的其它各种操作的方法。法。2.熟练掌握在串的定长顺序存储结构上实熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。现串的各种操作的方法。3.掌握串的堆存储结构以及在其上实现串掌握串的堆存储结构以及在其上实现串操作的基本方法。操作的基本方法。4.了解串操作的应用方法和特点。了解串操作的应用方法和特点。第四章第四章 串串 4.14.1串的串的定义定义 4.24.2串的串的表示和表示和实现实现 4.34.3串的串的模式匹模式匹配算法配算法 4.44.4串应串应用用 41Thank you !Thank you !