数据结构ch04学习教案.pptx

《数据结构ch04学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构ch04学习教案.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(sh j ji u)ch04第一页，共36页。2023/2/72023/2/72 2 在计算机的应用中，非数值处理问题的应用越来越多。如在汇编在计算机的应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。等也是字符串数据。字符串一般简称为串，可以将它看作是一种特殊的线性表，这字符串一般简称为串，可以将它看作是一种特殊的线性表，这

2、种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。字符集。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象，作为操作对象，而在串中，则是以而在串中，则是以“串的整体串的整体”或一部分作为操作对象。因此或一部分作为操作对象。因此(ync)，线性表和串的操作有很大的不同。，线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。作。本章本章本章本章(bn zhn)(bn zhn)学习学习学习学习导

3、读导读导读导读第1页/共36页第二页，共36页。2023/2/72023/2/73 3 串是一种特殊的线性表，它的数据对象是字符集合。串是一种特殊的线性表，它的数据对象是字符集合。4.1.1 4.1.1 串的定义串的定义 串（或字符串）是由零个或多个字符组成的有限序列。一般记作：串（或字符串）是由零个或多个字符组成的有限序列。一般记作：s=s=c0c1c2cn-1c0c1c2cn-1 (n0)(n0)其中其中(qzhng)(qzhng)：s s为串名，用双引号括起来的字符序列是串的值；为串名，用双引号括起来的字符序列是串的值；ci(0in-1)ci(0in-1)可以是字母、数字或其它字符；双引

4、号为串值的定界符，不是串的一部分；字符串字符的数目可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n n称为串的长度。称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串零个字符的串称为空串，通常以两个相邻的双引号来表示空串 如：如：s=s=，它的长度为零；，它的长度为零；仅由空格组成的的串称为空格串仅由空格组成的的串称为空格串 如：如：s=s=；4.1 串及其运算串及其运算(yn sun)第2页/共36页第三页，共36页。2023/2/72023/2/74 4 若串中含有空格，在计算串长时，空格应计入若串中含有空格，在计算串长时，空格应计入(

5、j r)串的长度中串的长度中 如：如：s=Im a student的长度为的长度为13。注意：在注意：在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，语言中，用单引号引起来的单个字符与单个字符的串是不同的，如如s1=a与与s2=a两者是不同的，两者是不同的，s1表示字符，表示字符，s2表示字符串。表示字符串。当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。例如，例如

6、，com、om、a和和man都是都是commander的子串。子串在主串中的的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串位置是指子串中第一个字符在主串中的位置序号。如子串man在主串在主串commander中的位置为中的位置为4。第3页/共36页第四页，共36页。2023/2/72023/2/75 5 串是一种简单的数据结构，它的逻辑(lu j)结构与线性表十分相似，区别仅在于串的数据对象是字符集。串的基本运算与线性表的基本运算有很大差别。通常在串的基本运算中，以“串的整体”作为操作对象；而在线性表的基本运算中，大多以“单个元素”作为操作对象。4.1.2 串的基本运

7、算串的基本运算 串的常用基本运算主要有：串的常用基本运算主要有：1Strassign(s,chars)功能：赋值运算功能：赋值运算 将串常量将串常量chars的值赋给串变量的值赋给串变量s。例如例如(lr)：执行：执行strassign(s，abcd)运算之后，运算之后，s的值为的值为abcd。第4页/共36页第五页，共36页。2023/2/72023/2/76 62Assign(s,t)功能：赋值运算。将串变量功能：赋值运算。将串变量t的值赋给串变量的值赋给串变量s。例如：例如：t=abcd，则执行，则执行Assign(s,t)运算之后，运算之后，s的值为的值为abcd。3Equal(s,t

8、)功能：判相等运算。若功能：判相等运算。若s与与t的值相等则运算结果的值相等则运算结果(ji gu)为为1，否，否则为则为0。4Length(s)功能：求串长运算。求串功能：求串长运算。求串 s序列中字符的个数，即串的长度。序列中字符的个数，即串的长度。5Concat(s,t)功能：联接运算。将串功能：联接运算。将串t的第一个字符紧接在串的第一个字符紧接在串 s的最后一个字符的最后一个字符之后，联接得到一个新串。例如之后，联接得到一个新串。例如s=man,t=kind，则执行，则执行Concat(s,t)运算后得到的新串为运算后得到的新串为mankind。第5页/共36页第六页，共36页。20

9、23/2/72023/2/77 7 6Insert(s,pos,t)功能：插入运算，当1pos Length(s)+1时，在串 s的第 pos 个字符之前插入串 t。7Delete(s,pos,len)功能：删除运算。当1posLength(s)且0lenLength(s)-pos+1时，从串s中删去从第pos个字符起长度为len的子串。8Replace(s,pos,len,t)功能：置换运算。当1posLength(s)且0lenLength(s)-pos+1时，用串t替换串s中从第 pos 个字符起长度为len的子串。对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面

10、(xi mian)仅介绍几种在C语言中常用的串运算，其它的串操作见文件。第6页/共36页第七页，共36页。2023/2/72023/2/78 8 定义下列几个变量：char s120=“dirtreeformat”,s220=“file.mem”;char s330,*p;int result;(1)求串长(length)int strlen(char s);/求串的长度 例如：printf(“%d”,strlen(s1);输出13 （2）串复制(copy)char*strcpy(char to,char from);该函数将串from复制到串to中，并且返回一个指向(zh xin)串to的开

11、始处的指针。例如：strcpy(s3,s1);/s3=“dirtreeformat”第7页/共36页第八页，共36页。2023/2/72023/2/79 9 (3)联接(concatenation)char strcat(char to,char from)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例1、求子串 求子串的过程(guchng)即为复制字符序列的过程(guchng)，将串S中的第pos个字符开始长度为len的字符复制到串T中。void substr(string sub,string s,int pos,int len)if(posstrlen(s

12、)-1|len0)n=strlen(s);m=strlen(t);i=pos;while(in-m+1)substr(sub,s,i,m);if(strcmp(sub,t)!=0)+i;else return(i);return(0);第9页/共36页第十页，共36页。2023/2/72023/2/711114.2 串的存储串的存储(cn ch)结构结构 串是一种特殊的线性表，其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符。串的存储结构表示有两种方法：静态存储和动态(dngti)存储 静态存储采用顺序存储结构，动态(dngti)存储采用的是链式存储和堆存储结构。4.2.1 串的

13、顺序存储结构及其基本运算的实现 1顺序存储结构（静态）串的顺序存储结构是采用与其逻辑结构相对应的存储结构，将串中的各个字符按顺序依次存放在一组地址连续的存储单元里，逻辑上相邻的字符在内存中也相邻。第10页/共36页第十一页，共36页。2023/2/72023/2/71212 类类似似于于线线性性表表的的顺顺序序存存储储结结构构，用用一一组组地地址址连连续续的的存存储储单单元元存存储储串值的字符序列。串值的字符序列。这这是是一一种种静静态态(jngti)存存储储结结构构，串串值值的的存存储储分分配配是是在在编编译译时时完完成成的的。因因此此，需需要要预预先先定定义义串串的的存存储储空空间间大大小

14、小。如如果果定定义义的的空空间间过过大大，则则会会造造成成空空间间浪浪费费；如如果果定定义义的的空空间间过过小小，则则会会限限制制串串的的某某些些运运算算，如如联联接、置换运算等。接、置换运算等。2基本运算在顺序存储结构上的实现基本运算在顺序存储结构上的实现在顺序存储结构中，串的类型定义描述如下：在顺序存储结构中，串的类型定义描述如下：#define MaxLen;/定义能处理的最大的串长度定义能处理的最大的串长度 typedef struct char strMaxLen;/定义可容纳定义可容纳MaxLen个字符的字符数组个字符的字符数组 int curlen;/定义当前实际串长度定义当前实

15、际串长度 string;第11页/共36页第十二页，共36页。2023/2/72023/2/71313以下给出采用以下给出采用(ciyng)顺序存储结构时串的联接运算。顺序存储结构时串的联接运算。（1）Concat(s,t)string Concat(string s,string t)/将串将串t的第一个字符紧接在串的第一个字符紧接在串 s 的最后一个字符之后的最后一个字符之后 string ch;int i;ch.curlen=s.curlen+t.curlen;/将将s.str0s.strs.curlen-1复制到复制到ch for(i=0;is.curlen;i+)ch.stri=s.

16、stri;/将将t.str0t.strt.curlen-1复制到复制到ch for(i=0;it，则输出正数；，则输出正数；如果如果st，则输出负数。，则输出负数。算法如下：算法如下：int strcmp(string s,string t)int i,st_len;if(s.cur1en t.cur1en)/求取求取s和和t长度短者长度短者 st_len=s.cur1en;else 第13页/共36页第十四页，共36页。2023/2/72023/2/71515else st_len=t.cur1en;for(i=0;(ist_len)&(s.stri=t.stri);i+);if(i=st_

17、len)if(s.cur1en=t.cur1en)/s=t return 0;else if(s.cur1ent.cur1en)/st return 1;else return s.stri-t.stri;/st或或st第14页/共36页第十五页，共36页。2023/2/72023/2/716164.2.2 串的链式存储结构及其基本运算的实现串的链式存储结构及其基本运算的实现 1链式存储结构链式存储结构 顺序串上的插入和删除操作不方便，需要顺序串上的插入和删除操作不方便，需要(xyo)移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。移动大量的字符。因此，我们

18、可用单链表方式来存储串值，串的这种链式存储结构简称为链串。用单链表存放串，每个结点仅存储一个字符，如图用单链表存放串，每个结点仅存储一个字符，如图4-1所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图4-2所示每个结点存放所示每个结点存放4个字符。个字符。第15页/共36页第十六页，共36页。2023/2/72023/2/71717图图4-1 结点大小为结点大小为1的链式存储的

19、链式存储(cn ch)结构结构 图图4-2 结点大小结点大小(dxio)为为4的链式存储结的链式存储结构构第16页/共36页第十七页，共36页。2023/2/72023/2/71818 2 2基本运算在链式存储结构上的实现基本运算在链式存储结构上的实现 链式存储结构的链式存储结构的C C语言定义如下：语言定义如下：#define CHUNKSIZE#define CHUNKSIZE ;/;/定义结点的大小定义结点的大小 typedef struct Chunk /typedef struct Chunk /结点结构结点结构 char strCHUNKSIZE;char strCHUNKSIZE

20、;struct Chunk *next;struct Chunk *next;Lstring;Lstring;一个链串由头指针唯一确定一个链串由头指针唯一确定(qudng)(qudng)。这种结构便于进行插入和删除运算，但存储空间利用率太低。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点

21、，以表示串的终结。时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。第17页/共36页第十八页，共36页。2023/2/72023/2/71919 对于结点大小不为对于结点大小不为1 1的链串，其类型定为义只需对上述的链串，其类型定为义只需对上述(shngsh)(shngsh)的结的结点类型做简单的修改即可，如结点大小为点类型做简单的修改即可，如结点大小为4 4的定义为：的定义为：#define nodesize 80#define nodesize 80 typedef struct node typedef struct node char data

22、4;char data4;struct node*next;struct node*next;lstring;lstring;采用链式存储结构（结点大小为采用链式存储结构（结点大小为1 1），实现串的联接、求子串以及串的），实现串的联接、求子串以及串的置换基本运算见教科书置换基本运算见教科书 P83 P83。第18页/共36页第十九页，共36页。2023/2/72023/2/72020 4.2.3 串的堆分配存储结构及其基本运算的实现串的堆分配存储结构及其基本运算的实现 1堆分配存储结构堆分配存储结构 堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空

23、间是在程序执行过程中动态分配的。所以也称为堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。所以也称为(chn wi)动态存储分配的顺序表。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。动态存储分配的顺序表。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。在在C语言中，存在一个称为语言中，存在一个称为(chn wi)“堆堆”的自由空间，由动态分配函数的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则返

24、回这段空间的起始地址，作为串的基址。由分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。释放串不再需要的空间。第19页/共36页第二十页，共36页。2023/2/72023/2/72121 2基本运算在堆分配基本运算在堆分配(fnpi)存储结构上的实现存储结构上的实现 在在C和和C+语言中可利用语言中可利用malloc和和free两个函数实现动态存储分配两个函数实现动态存储分配(fnpi)。函数。函数malloc为每个新产生的串分配为每个新产生的串分配(fnpi)一块实际所需大小的空间，若分配一块实际所需大小的空间，若分配

25、(fnpi)成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。C语言对堆分配语言对堆分配(fnpi)存储结构的定义如下：存储结构的定义如下：typedef struct char*str;int curlen;Hstring;第20页/共36页第二十一页，共36页。2023/2/72023/2/72222堆分配存储中求子串和串的联接运算：堆分配存储中求子串和串的联接运算：（1 1）SubStr(s,pos,len)SubStr(s,p

26、os,len)Hstring SubStr(Hstring&sub,Hstring s,int pos,int len)Hstring SubStr(Hstring&sub,Hstring s,int pos,int len)/用用subsub返回串返回串s s的第的第pospos个字符起长度为个字符起长度为lenlen的子串的子串 int i;int i;if(poss.curlen-1|lens.curlen)if(poss.curlen-1|lens.curlen)return return error;error;/参参数数不不正正确确(zhngqu)(zhngqu)时返回错误提示时返

27、回错误提示 if(sub.str)free(sub.str);/if(sub.str)free(sub.str);/释放旧空间释放旧空间 if(!len)/if(!len)/空子串空子串 sub.str=NULL;sub.str=NULL;sub.curlen=0;sub.curlen=0;else else sub.str=(char*)malloc(len*sizeof(char);sub.str=(char*)malloc(len*sizeof(char);for(i=0;ilen;i+)/for(i=0;ilen;i+)/非空子串非空子串 sub.stri=s.strpos+i;sub

28、.stri=s.strpos+i;sub.curlen=len;sub.curlen=len;return ok;第21页/共36页第二十二页，共36页。2023/2/72023/2/72323 （2）Concat(s,t)Hstring Concat(HString&s，HString s1，HString s2)/联接串联接串s1和串和串s2形成形成(xngchng)新串新串s,并返回并返回 int i;if(s.str)free(s.str);/释放旧空间释放旧空间 if(!(s.str=(char*)malloc(s1.curlen+s2.curlen)*sizeof(char)exi

29、t(overflow);for(i=0;is1.curlen;i+)/非空子串非空子串 s.stri=s1.stri;for(i=0;is2.curlen;i+)/非空子串非空子串 s.strs1.curlen+i=s2.stri；s.curlen=s1.curlen+s2.curlen;return ok;第22页/共36页第二十三页，共36页。2023/2/72023/2/724244.3 串的串的模式匹配模式匹配 模式匹配：子串定位运算称为模式匹配模式匹配：子串定位运算称为模式匹配(Pattern(Pattern Matching)Matching)或串匹配或串匹配(String Mat

30、ching)(String Matching)。模式匹配成功是指在目标串模式匹配成功是指在目标串s s中找到一个模式串中找到一个模式串t t；模式匹配不成功则指目标串模式匹配不成功则指目标串s s中不存在模式串中不存在模式串t t。此运算的应用非常广泛。例如，在文本编辑程序中，此运算的应用非常广泛。例如，在文本编辑程序中，经常要查找某一特定单词在文本中出现的位置。显然，经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应解此问题的有效算法能极大地提高文本编辑程序的响应性能。性能。本节主要讨论两种串的模式匹配算法，都采用顺序存储本节主要讨论两种串的模式

31、匹配算法，都采用顺序存储结构结构(jigu)(jigu)。在串匹配中，一般将主串称为目标串，子串称之为在串匹配中，一般将主串称为目标串，子串称之为模式串。设模式串。设S S为目标串，为目标串，T T为模式串，设：为模式串，设：S=“s0s1s2sn-1”T=“t0t1tm-1”S=“s0s1s2sn-1”T=“t0t1tm-1”第23页/共36页第二十四页，共36页。2023/2/72023/2/72525 4.3.1 Brute-Force算法 Brute-Force算法的基本思想是：从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二

32、个字符起再重新和串t进行比较。依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功(chnggng)，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功(chnggng)。假设s=“cddcdc”，t=“cdc”，则模式匹配过程下图所示：第24页/共36页第二十五页，共36页。2023/2/72023/2/72626Brute-Force算法的算法的C语言描述如下：语言描述如下：int Index(string s,string t)int i,j;i=0;/指向串指向串s的第的第1个字符个字符j=0;/指向串指向串t的第的第1个字符个

33、字符while(is.curlen)&(j=t.curlen)return(i-t.curlen);/匹配成功，返回模式串匹配成功，返回模式串t在串在串s中的起始位置中的起始位置 else return 0;/匹配失败返回匹配失败返回0 第25页/共36页第二十六页，共36页。2023/2/72023/2/72727 一般情况下，上述算法的实际执行效率一般情况下，上述算法的实际执行效率(xio l)(xio l)与字符与字符 t.str0 t.str0在在串串s s中是否频繁出现有密切关系，例如，中是否频繁出现有密切关系，例如，s s 是一般的英文文稿，是一般的英文文稿，t t=“hello”

34、=“hello”，s s中有中有5%5%的字母是的字母是“h”“h”，则在上述算法执行过程中，对于，则在上述算法执行过程中，对于95%95%的情况可以只进行一次对应位的比较就将的情况可以只进行一次对应位的比较就将t t向右移动一位，时间复杂度下降向右移动一位，时间复杂度下降为为O(s.curlen)O(s.curlen)，这时算法接近最好情况。，这时算法接近最好情况。然而，在有些情况下，该算法效率然而，在有些情况下，该算法效率(xio l)(xio l)却很低。如当却很低。如当 s=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab s=aaaaaaa

35、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab，t=“aaaaaab“t=“aaaaaab“每次都是在模式串的最后位置上字符不匹配每次都是在模式串的最后位置上字符不匹配 即即 t.curlen s.curlen t.curlen s.curlen时，该算法效率时，该算法效率(xio l)(xio l)却很低。由于通常却很低。由于通常有有t.curlen s.curlent.curlen s.curlen，因此最坏情况的时间复杂度为，因此最坏情况的时间复杂度为O(s.curlen*t.curlen)O(s.curlen*t.curlen)。第26页/共36页第二十

36、七页，共36页。2023/2/72023/2/72828 4.3.2 KMP 算法 由D.E.Knuth、J.H.Morris和V.R.Pratt共同(gngtng)提出了一个改进算法，消除了Brute-Force算法中串s指针的回溯，完成串的模式匹配。时间复杂度为O(s.curlen+t.curlen)，这就是Knuth-Morris-Pratt算法，简称KMP 算法。为了进一步讨论KMP算法，让我们首先讨论一个例子。假设s=“abacabab”，t=“abab”，第一次匹配过程如下图所示：第27页/共36页第二十八页，共36页。2023/2/72023/2/72929 此时不必从i=l，j

37、=0重新开始第二次匹配。因为(yn wi)t.str0t.str1，s.str1=t.str1，必有s.str1t.str0，又因t.str0=t.str2，s.str2=t.str2，所以必有s.str2=t.str0。因此，第二次匹配可直接从i=3，j=1开始。进一步分析，t.str1=t.str3，s.str3 t.str3，必定s.str3 t.str1，所以第二次匹配也不必进行，可以直接进行第三次匹配，即i=3，j=0。由此可见，当s.stri和t.strj比较不相等时，串s的指针i不必回溯。第28页/共36页第二十九页，共36页。2023/2/72023/2/73030KMP算法算

38、法(sun f)的基本思想：的基本思想：设目标串为设目标串为s，模式串为，模式串为t i、j 分别为指示分别为指示s和和t的指针，的指针，i、j的初值均为的初值均为0。若有若有 si=tj，则，则i和和j分别增分别增1；否则，；否则，i不变，不变，j退回至退回至j=nextj的位置的位置(也也可理解为串可理解为串s不动，模式串不动，模式串t向右移动到向右移动到si与与tnextj对齐对齐)；比较比较 si 和和 tj。若相等则指针各增。若相等则指针各增1；否则；否则 j 再退回到下一个再退回到下一个j=nextj 的位的位置置(即模式串继续向右移动即模式串继续向右移动)，再比较，再比较 si

39、和和 tj。依次类推，直到下列两种情况之一：依次类推，直到下列两种情况之一：1)j 退回到某个退回到某个j=nextj时有时有 si=tj，则指针各增，则指针各增1，继续匹配；，继续匹配；2)j 退回至退回至 j=-1，此时令指针各增，此时令指针各增l，即下一次比较，即下一次比较 si+1和和 t0。第29页/共36页第三十页，共36页。2023/2/72023/2/73131 KMP算法的描述如下：#define MaxLen /定义最大串存储空间int Index_KPM(string s,string t)int i,j,nextMaxLen;GetNext(t，next);/先求得模式

40、串的next函数(hnsh)值i=0;/指向串s的第1个字符j=0;/指向串t的第1个字符while(is.curlen)&(j=t.curlen)return(i-t.curlen);/匹配成功 else return(0);/匹配失败 第30页/共36页第三十一页，共36页。2023/2/72023/2/732324.4 串的应用串的应用(yngyng)文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍(shj)的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽

41、管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。为了编辑方便起见，用户可以通过换页符和换行符将文本划分为若干页或将每页划分为若干行。可将整个文本看成是一个文本串，页是文本串的子串，而行则是页的子串。第31页/共36页第三十二页，共36页。2023/2/72023/2/73333假设有下列一段假设有下列一段C源程序：源程序：main()float a,b,max;scanf(%f,%f,&a,&b);if(ab)max=a;else max=b;若用若用n表示换行符，该文本串在内存中的存储表示换行符，该文本串在内存中的存储(cn

42、ch)映像如下表所示映像如下表所示：文本文本(wnbn)(wnbn)串的内存串的内存存储映像存储映像 第32页/共36页第三十三页，共36页。2023/2/72023/2/73434 为为了了管管理理(gunl)(gunl)文文本本串串中中的的页页和和行行，在在进进入入文文本本编编辑辑时时，编编辑辑程程序序先先为为文文本本串串建建立立相相应应的的页页表表和和行行表表，即即建建立立各各子子串串的的存存储储映映像像。页页表表的的每每一一项项列列出出页页号号和和该该页页的的起起始始行行号号，行行表表的的每每一一项项则则指指示示每每一一行行的的行行号号、起起始始地地址址和和该该行行子子串串的的长长度度

43、。以以表表4-24-2为为例例，假假设设文文本本串串只只占占一一页页，起起始始行行号号为为100100，起起始始地地址址为为200200，则则该该文文本本串串的的行行表如下所示。表如下所示。行表行表 第33页/共36页第三十四页，共36页。2023/2/72023/2/73535下面来讨论文本的编辑。下面来讨论文本的编辑。（1）插插入入一一行行时时，首首先先在在文文本本末末尾尾的的空空闲闲工工作作区区写写入入该该行行的的串串值值，然然后后，在在行行表表中中建建立立该该行行的的信信息息，插插入入后后，必必须须保保证证行行表表中中行行号号从从小小到到大大的的顺顺序序(shnx)。若若插插入入行行1

44、45，则行表中从，则行表中从150开始的各行信息必须向下平移一行。开始的各行信息必须向下平移一行。（2）删删除除一一行行时时，则则只只要要在在行行表表中中删删除除该该行行的的行行号号，后后面面的的行行号号向向前前平平移移。若若删删除除的的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修修改改文文本本时时，在在文文本本编编辑辑程程序序中中设设立立了了页页指指针针，行行指指针针和和字字符符指指针针，分分别别指指示示当当前前操操作作的的页页、行行和和字字符符。若若在在当当前前行行内内插插入入或或删删除除若若干干字字符符，则则

45、要要修修改改行行表表中中当当前前行行的的长长度度。如如果果该该行行的的长长度度超超出出了了分分配配给给它它的的存存储储空空间间，则则应应为为该该行行重重新新分分配配存存储储空空间间，同同时还要修改该行的起始位置。时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可自行设计其中的算法。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可自行设计其中的算法。第34页/共36页第三十五页，共36页。2023/2/72023/2/73636 串串串串是是是是一一一一种种种种特特特特殊殊殊殊的的的的线线线线性性性性表表表表，其其其其元元元元素素素素为为为为字字字字符符符符。本本

46、本本章章章章讨讨讨讨论论论论了了了了串串串串的的的的顺顺顺顺序序序序存存存存储储储储结结结结构构构构、链链链链式式式式存存存存储储储储结结结结构构构构和和和和堆堆堆堆分分分分配配配配存存存存储储储储结结结结构构构构。基基基基于于于于串串串串的的的的存存存存储储储储结结结结构构构构，可可可可以以以以实实实实现现现现(shxin)(shxin)(shxin)(shxin)串串串串的的的的各各各各种种种种基基基基本本本本运运运运算算算算，完完完完成成成成对对对对串串串串的的的的处处处处理理理理。采采采采用用用用不不不不同同同同的的的的存存存存储储储储结结结结构构构构，串的运算效率不同。串的运算效率不

47、同。串的运算效率不同。串的运算效率不同。串串串串的的的的模模模模式式式式匹匹匹匹配配配配是是是是一一一一种种种种较较较较复复复复杂杂杂杂的的的的串串串串运运运运算算算算，是是是是模模模模式式式式串串串串在在在在目目目目标标标标串串串串中中中中的的的的定定定定位位位位运运运运算算算算。Brute-ForceBrute-ForceBrute-ForceBrute-Force算算算算法法法法简简简简单单单单易易易易懂懂懂懂，但但但但效效效效率率率率较较较较低低低低。KMPKMPKMPKMP算算算算法法法法对对对对它它它它进进进进行行行行了了了了改改改改进，消除了目标串指针的回溯，提高了算法的效率。进，消除了目标串指针的回溯，提高了算法的效率。进，消除了目标串指针的回溯，提高了算法的效率。进，消除了目标串指针的回溯，提高了算法的效率。本章本章本章本章(bn(bn(bn(bn zhn)zhn)zhn)zhn)小结小结小结小结第35页/共36页第三十六页，共36页。