《串类型的定义串的表示与实现的模式匹配算法串操作应用举例》由会员分享，可在线阅读，更多相关《串类型的定义串的表示与实现的模式匹配算法串操作应用举例（55页珍藏版）》请在金锄头文库上搜索。
1、n n串类型的串类型的定义定义n n串的串的表示表示和和实现实现n n串的串的模式匹配算法模式匹配算法n n串串操作应用举例操作应用举例1、了解串的概念；、了解串的概念；学习要点学习要点2、熟悉串的基本运算的定义、熟悉串的基本运算的定义及实现方法；及实现方法；3、掌握基本串匹配算法。、掌握基本串匹配算法。 在在较早较早的程序设计语言中，字符串的程序设计语言中，字符串（简称串）是作为（简称串）是作为输入或输出的常量输入或输出的常量（是直接量，不参加运算）出现，而非数出现，而非数值处理的对象基本上是字符串数据。这值处理的对象基本上是字符串数据。这就要求字符串也能以就要求字符串也能以变量变量的形式出
2、现，的形式出现，能进行一系列字符串能进行一系列字符串操作操作（运算） 。目目前前大多数程序设计语言都支持串这种数大多数程序设计语言都支持串这种数据类型。据类型。 1、串、串 2、串长串长：串中所包含的字符个数。串中所包含的字符个数。 3、空串空串：长度为零的串，它不包含任何字符。长度为零的串，它不包含任何字符。记作记作“” 4、子串串：串中任意个串中任意个连续的连续的字符组成的子序列。字符组成的子序列。 5、主串主串：包含子串的串。包含子串的串。4.14.1串类型的定义串类型的定义基本概念基本概念：零个或多个字符组成的有限序列，即数零个或多个字符组成的有限序列，即数据元素为字符的线性表。一般记
3、为据元素为字符的线性表。一般记为S=a1a2.an，其中，其中，S是是串名串名，单引号括起的字符序列是单引号括起的字符序列是串值串值。7、子串在主串中的位置、子串在主串中的位置：子串在主串中子串在主串中第一第一次出现次出现时，子串的时，子串的第一个字符第一个字符在主串在主串中的位置。中的位置。6、字符在串中的位置、字符在串中的位置：字符在序列中的序号。字符在序列中的序号。8、两个串相等、两个串相等：两个串的长度相等，并且各两个串的长度相等，并且各个个对应位置的字符都相等对应位置的字符都相等时才相等。时才相等。9、空格串、空格串：由一个或由一个或多个多个空格组成的串，空格组成的串，其长度为串中空
4、格字符的个数。它其长度为串中空格字符的个数。它与空串与空串是不同的概念。是不同的概念。串的串的逻辑结构逻辑结构和线性表极为相似，区和线性表极为相似，区别仅在于串的数据对象为字符集。别仅在于串的数据对象为字符集。串的基本操作和线性表有很大差别：串的基本操作和线性表有很大差别：在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单单个元素个元素”作为操作对象；作为操作对象；在串的基本操作中，通常以在串的基本操作中，通常以“串的整串的整体体”作为操作对象作为操作对象。ADTString 数据对象数据对象：Dai|aiCharacterSet,i=1,2,.,n,n0数据关系数据关系：R1|ai
5、-1,aiD,i=2,.,n 基本操作：基本操作：ADTStringADT串的定义串的定义StrAssign(&T,chars)/串赋值串赋值初始条件：初始条件：chars是字符串常量是字符串常量。操作结果：操作结果：把把chars赋为赋为T的值的值。StrCopy(&T,S)/串复制串复制初始条件：初始条件：串串S存在。存在。操作结果：操作结果：由串由串S复制得串复制得串T。DestroyString(&S)/串串销毁销毁初始条件初始条件：串：串S存在。存在。操作结果：操作结果：串串S被销毁。被销毁。StrEmpty(S)/串判空串判空初始条件：初始条件：串串S存在。存在。操作结果：操作结果
6、：若若 S 为空串，则返为空串，则返TRUE， 否则返回否则返回FALSE。StrCompare(S,T)/串串比较比较例如：例如：StrCompare(data, state) 0初始条件：初始条件：串串S和和T存在。存在。操作结果：操作结果：若若S T，则返回值则返回值 0；若若S T，则返回值则返回值 0；若若S T，则返回值则返回值 0StrLength(S)/求串长求串长初始条件：串 S 存在。操作结果：返回 S 的元素个数， 称为串的长度。Concat(&T,S1,S2)/串联接串联接例如：Concate(T, man , kind )求得求得T= mankind 初始条件：初始条
7、件：串串S1和和S2存在。存在。操作结果：操作结果：用用T返回由返回由S1和和S2联接而成的新串。联接而成的新串。SubString(&Sub,S,pos,len)/求子串求子串初始条件：初始条件：串串S存在，存在，1posStrLength(S)且且0lenStrLength(S)-pos+1。操作操作结果：结果：用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长度为len的子串。的子串。子串为子串为“串串”中的一个字符子序列。中的一个字符子序列。SubString(sub, commander ,1,9)求得求得sub= commander SubString(sub, com
8、mander ,9,1)求得求得sub= r 例如：例如：SubString(sub, commander ,4,3)求得求得sub= man ;SubString(sub, student ,5,0)得得sub= 关于参数关于参数len（子串长度）的说明：子串长度）的说明：长度为长度为0的子串为的子串为“合法合法”串串空串。空串。事实上对任何串事实上对任何串S和和位置位置pos都有：都有：SubString(sub, commander ,4,7)得得sub= mander SubString(sub,S,pos,0)得得sub= ；有时对有时对len放宽到放宽到lenStrLength(S
9、)-pos+1，此时规定此时规定SubString(sub,S,pos,len)的的值取值取S的第的第pos个字符到个字符到S的最后一个字符的最后一个字符作为作为子串（长为子串（长为StrLength(S)-pos+1）。）。Index (S,T,pos) /(子子)串串(位置位置)定位定位 初始初始条件：条件：串串S S和和T T存在，存在，T T是非空串，是非空串， 1posStrLength(S)1posStrLength(S)。 操作结果：操作结果：若主串若主串 S S 中存在和串中存在和串T T值相同值相同 的子串的子串, , 则返回它在主串则返回它在主串S S中第中第 pospos
10、个字符之后第一次出现的位个字符之后第一次出现的位 置置; ;否则函数值为否则函数值为0 0。假设假设S= abcaabcaaabc ,T= bca Index(S,T,1)=Index(S,T,3)=Index(S,T,8)= “子串在主串中的位置子串在主串中的位置”意指子串意指子串中的第一个字符在主串中的位序。中的第一个字符在主串中的位序。2;6;0;Replace(&S,T,V) /串串替换替换初始条件：初始条件：串串S, T和和 V 均已存在，均已存在， 且且 T 是非空串。是非空串。操作结果：操作结果：用用V V替换主串替换主串S S中出现的所有与中出现的所有与 （模式串）（模式串）
11、T T相等的不重叠的子串。相等的不重叠的子串。 例如：例如：假设假设S= abcaabcaaabca ,T= bca 若若V= x ,则经置换后得到则经置换后得到S= axaxaax 若若V= bc ,则经置换后得到则经置换后得到S= abcabcaabc StrInsert(&S, pos, T) /串串插入插入例如：例如：S= chater ，T= rac ，则执行则执行StrInsert(S,4,T)之后得到之后得到S= character 初始条件：初始条件：串串S和和T存在，存在，1posStrLength(S)1。操作结果：操作结果：在串在串S的第的第pos个字符之前插入个字符之前
12、插入串串T。StrDelete(&S,pos,len)/串串删除删除初始条件：初始条件：串串S存在存在，1posStrLength(S)-len+1。操作结果：操作结果：从串从串S中删除第中删除第pos个字符个字符起长度为起长度为len的子串。的子串。ClearString(&S) /串串清除清除初始条件：初始条件：串串S存在。存在。操作结果：操作结果：将将S清为空串。清为空串。在上述抽象数据类型定义的在上述抽象数据类型定义的13种操作中，种操作中，串赋值串赋值StrAssign、串复制串复制Strcopy、串比较串比较StrCompare、求串长求串长StrLength、串联接串联接Conc
13、at以及求子串以及求子串SubString等六种操作构成串类型的最小操作子集。等六种操作构成串类型的最小操作子集。这些操作不可能利用其他串操作来实现，这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除反之，其他串操作（除串清除ClearString和串和串销毁销毁DestroyString外）可在这个最小操作子外）可在这个最小操作子集上实现。集上实现。例如，可利用可利用串比较串比较、求串长和求子串等求串长和求子串等操作实现定位函数操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T),T) TT串串串串 TT串串串串
14、iposStrLength(S) StrLength(T) +1算法的基本思想：算法的基本思想：?=0S串串 在pos到到StrLength(S) StrLength(T) +1范围内范围内寻求使下式成立的寻求使下式成立的i值值TT串串串串ipos+1intIndex(StringS,StringT,intpos)/T为非空串。若主串为非空串。若主串S中第中第pos个字符之后存在与个字符之后存在与T相等的相等的/子串，则返回第一个这样的子串在子串，则返回第一个这样的子串在S中的中的位置，否则返回位置，否则返回0if(pos0)n=StrLength(S);m=StrLength(T);i=po
15、s;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;elsereturni;return0;/S中不存在与中不存在与T相等的子串相等的子串/Index利用利用最小操作子集最小操作子集中的操作也可实现中的操作也可实现串判空串判空StrEmpty(S)、串替换串替换Replace(&S,T,V)、串删除串删除StrDelete(&S,pos,len)、 串插入串插入 StrInsert(&S, pos, T) 等操作。等操作。留作习题若在程序设计语言中，串只是作为若在程序设计语言中，串只是作为输入或输出的常量出现，则只需存
16、储此输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形非数值处理的程序中，串也以变量的形式出现。式出现。4.24.2 串的串的表示表示和实现和实现串有三种机内表示方法串有三种机内表示方法: 一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示用一组地址连续的存储单元存储串值的字符用一组地址连续的存储单元存储串值的字符序列。该结构可用定长数组描述如下：序列。该结构可用定长数组描述如下：#defineMAXSTRLEN255/可在可在255以内定义最大串长以内定义最大串长typedefunsigne
17、dcharSstringMAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度一、串的定长顺序存储表示一、串的定长顺序存储表示 对串的长度有两种表示方法对串的长度有两种表示方法: : 1. 1.以下标为以下标为0 0的数组分量存放串的实际长度的数组分量存放串的实际长度 ( (如如 PASCALPASCAL语言语言) ,) ,特点是便于进行某些操作特点是便于进行某些操作； 2.2.在串值后面加不计入串长的结束标记在串值后面加不计入串长的结束标记字符字符(如如C C 语言采用语言采用“0”0”), ,此时的此时的串长为隐含值串长为隐含值, ,特点是特点是 访问容易访问容易, ,但删除或插
18、入麻烦但删除或插入麻烦。说明说明： 串的实际长度可在预定义长度的范围内随意设定，串的实际长度可在预定义长度的范围内随意设定， 超过预定义长度的串值则被超过预定义长度的串值则被 “ “截断截断” ” 。 对超长部分实施截断操作正是对超长部分实施截断操作正是串的定长顺序存储串的定长顺序存储表示的表示的弊端弊端。为克服此弊端，惟有不限定最大。为克服此弊端，惟有不限定最大串串 长，即动态分配串值的存储空间。长，即动态分配串值的存储空间。 以下以以下以串联接串联接为例进行讨论为例进行讨论在这种存在这种存储结构表示下如何实现串的操作储结构表示下如何实现串的操作： 假设T,S1,S2都是 Sstring型变
19、量, T为S1联结S2后所得之串,则联接运算Concat(&T,S1,S2)是将S1和S2的值分别传送到T的相应位置上,超过超过MAXSTRLEN的部分截断之的部分截断之。 其运算结果可能有三种情况：1)S10+S20MAXSTRLEN2)S10+S20MAXSTRLEN3)S10MAXSTRLEN1)S10+S20MAXSTRLEN串S1串S2串 TS10S20S10+S20MAXSTRLENMAXSTRLENMAXSTRLEN2)S10+S20MAXSTRLEN串 S1串 S2串 TS10S20MAXSTRLENMAXSTRLENMAXSTRLEN截去串串S2被全部截去。被全部截去。3)S
20、10MAXSTRLEN串 S1串 S2串 TS10S20S10MAXSTRLENMAXSTRLENMAXSTRLENStatusConcat(SString &T, SString S1, SString S2) if (S10+S20=MAXSTRLEN) / 不截断不截断 T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else/ 截断截断if (S10MAXSTRSIZE) T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MA
21、XSTRLEN; uncut = FALSE; else T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; return uncut; / Concatq在串的顺序存储结构中，在串的顺序存储结构中，实现实现串串操作的操作的原操作为原操作为“字符序列的复制字符序列的复制”，操作的时间，操作的时间复杂度基于字符序列的长度。复杂度基于字符序列的长度。二、串的堆分配存储表示二、串的堆分配存储表示 堆分配存储类似于线性表的顺序存储结构，堆分配存储类似于线性表的顺序存储结构，仍仍以以一组地址连续的存储单元存储串值的字符序
22、列，一组地址连续的存储单元存储串值的字符序列，但但它它们的存储空间是在程序执行过程中动态分配而得的。们的存储空间是在程序执行过程中动态分配而得的。在C语言中是由动态分配函数malloc()和free()来管理一个称之为“堆（heap）”的自由存储区的。该存储结构类型描述如下：该存储结构类型描述如下：typedefstructchar*ch ;/ 若是非空串，则按串长分配存储区， /否则ch为NULLint length; / 串长度 一个串值的确定是通过串在堆中的起始位置一个串值的确定是通过串在堆中的起始位置和串的长度实现的。和串的长度实现的。HString; 这类串操作实现的算法为: 先为新
23、生成的串（若该串已存在,则先释放其所占空间）分配一个长度适当长度适当的的存储空间，然后进行串值的复制。q这种存储结构表示时的串这种存储结构表示时的串操作仍基于操作仍基于“字符序列的复制字符序列的复制”进行的。进行的。为此，串名与串值之间要建立一个对照表。为此，串名与串值之间要建立一个对照表。 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 HString a,b ;串名串名 基址基址ch 长度长度lengtha20004b20124D ataStructureBo o k162000 串插入算法串插入算法StatusStrInsert(Hstring &S, i
24、nt pos, Hstring T) /在串S的第pos个字符之前插入串TS.ch01pos-1T.lengthif(pos S.length+1) returnERROR；if(T.length )/T非空，则重新分配空间，插入Tif(!(S.ch=(char*)ralloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERELOW) ； for(i=S.length-1;ipos - 1;-i)/插入T而腾出位置S.chi+T.length=S.chi；S.chpos-1.pos+T.length-2=T.ch0.T.length-1;/插入TS
25、.length=T.length;returnOK;堆分配存储堆分配存储结构表示时的（结构表示时的（只含最小操作子集只含最小操作子集）基本操作的算法描述基本操作的算法描述StatusStrAssign(HString&T,char*chars)/生成一个其值等于串常量chars的串Tif(T.ch)free(T.ch);/若串T已存在,释放其所占空间for(i=0,c=chars;c;+i,+c);if(!i)T.ch=null;T.length=0;elseif(!(T.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);T.ch0.i-1=chars
26、0.i-1;T.length=i;returnOK;intStrLength(HStrings)returns.length;intStrCmpare(HStringS,HStringT)for(i=0;iS.length&iT.length;+i)if(S.chi!=T.chi)return(S.chiT.chi);returnS.lengthT.length;StatusClearString(HString&S)if(S.ch)free(S.ch);s.ch=null;S.length=0;returnOK;Status Concat(HString &T, HString S1, HS
27、tring S2) / 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); / 释放旧空间 if (!(T.ch = (char *) malloc( (S1.length+S2.length)*sizeof(char) exit(OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; returnOK; / Concat Status SubString(HS
28、tring &Sub, HString S, int pos, int len) if (pos S.length | len S.length-pos+1) returnERROR;if ( Sub.ch ) free ( Sub.ch ); / 释放旧空间 if ( !len ) Sub.ch = NULL; Sub.length = 0; / 空子串 else/ 完整子串Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; return OK; / Sub
29、String三、串的块链存储表示三、串的块链存储表示 可采用链表方式存储串值，每个结可采用链表方式存储串值，每个结点可以存放一个字符，点可以存放一个字符，也可以存放多个字符也可以存放多个字符 （如图如图所示所示）。 为便于进行串的操作，当以链表存储串值时，为便于进行串的操作，当以链表存储串值时，还需还需增设尾指针增设尾指针指示链表中的最后一个结点，指示链表中的最后一个结点，并给并给出当前串的长度出当前串的长度，如此定义的结构就称为，如此定义的结构就称为块链结构块链结构. .描述如下：描述如下：A B C DE F G HI # # #head head A B C I #defineCHUNK
30、SIZE80/可由用户定义的块大小可由用户定义的块大小typedefstructChunk/结点结构结点结构charchCHUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构串的链表结构Chunk*head,*tail;/串的头和尾指针串的头和尾指针intcurlen;/串的当前长度串的当前长度LString; 在链式存储结构中，结点大小的选择直接影响着串处理的效率。在各种串的处理系统中，所要处理的串往往很长或很多。因此需考虑串的存储密度。存储密度存储密度 = 数据元素所占存储位实际分配的存储位 链式存储结构类似线性链表，由于串结构的特殊性链
31、式存储结构类似线性链表，由于串结构的特殊性, , 要考虑每个结点是存放一个字符还是多个字符。一个字要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但存储效率低。符的，插入、删除、求长度非常方便，但存储效率低。 多个字符的，改善了效率，在处理不定长的大字符串多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。未充分利用的结点。 例如例如:在编辑系统中，整个文本编在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一辑区可以看成是一个串，每一行是一个子串，
32、构成一个结点。即个子串，构成一个结点。即:同一行的同一行的串用定长结构串用定长结构(80个字符个字符),行和行之行和行之间用指针相联接。间用指针相联接。实际应用时，可以根据问题所需来设实际应用时，可以根据问题所需来设置结点的大小。置结点的大小。4.34.3串的模式匹配算法串的模式匹配算法子子串串位置位置定位定位操作操作Index(S,T,pos)通常称作通常称作串的串的模式匹配模式匹配（其中（其中T被被称为称为模式串模式串）, ,是各种串处理系统中最重要是各种串处理系统中最重要的操作之一。很多软件若有的操作之一。很多软件若有“编辑编辑”菜单项的话，则其中必有菜单项的话，则其中必有“查找查找”子
33、子菜单项。查找即为菜单项。查找即为模式匹配。模式匹配。INDEX(S,T,pos)初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果：若主串S中存在和串T值相同的 子串返回它在主串S中第pos个字符之后 第一次出现的位置; 否则函数值为0 。 回忆一下串定位操作的定义:模式匹配的算法的基本思想算法的基本思想: 从从主串主串S S的第的第 pospos个字符起和个字符起和模式串模式串T T的第一的第一个字符比较，若相等，则逐个比较后续字符个字符比较，若相等，则逐个比较后续字符; ;否则否则从从S S的下一个字符起再重新和的下一个字符起再重新和T T的字符比较。依此的
34、字符比较。依此类推类推, ,直至直至T T中的每个字符依次和中的每个字符依次和S S 中一个连续的中一个连续的字符序列相等为止字符序列相等为止, ,则称匹配成功则称匹配成功, ,返回与返回与T T中第一中第一个字符相等的字符在个字符相等的字符在S S中的中的序号序号; ;否则称匹配不成否则称匹配不成功功, ,返回返回零零。 为此为此, ,设置主串指针设置主串指针i i和模式串指针和模式串指针j j指示当前指示当前两串对应位置上的两串对应位置上的 ( (待比较的待比较的) )字符。字符。 以下展示以下展示模式模式T=T=abcacabcac和和主串S=ababcabcacbabababcabca
35、cbab的匹配的匹配过程过程: :a b a b c a b c a c b a b第一趟匹配第一趟匹配 i=1.a b c a ca b a b c a b c a c b a b第三趟匹配第三趟匹配 i=3.第四趟匹配第四趟匹配 i=4.第五趟匹配第五趟匹配 i=5.第六趟匹配第六趟匹配 i=6.匹配成功第二趟匹配第二趟匹配 i=2.a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b
36、 c a ca b c a c327411j=1.j=1.j=1.j=1.j=1.j=1.3111655T0以定长顺序结构表示串时的简单算法简单算法（不依赖于其它串操作）int Index(SString S, SString T, int pos) i = pos; j = 1; while ( i S0 & j T0) /匹配成功( T0 个对应位置上的字符相同） return i-T0; /返回子串在主串中的位置 else return 0; / Index 本算法思路简单，匹配过程易于理解，通常称作朴素的匹配算法。在某些应用场合，如文本编辑，效率也较高。但当主串中存在多个与模式串“部分
37、匹配”的子串时，就引起主串指针i的多次回溯，从而降低匹配效率。以下介绍的KMP算法就是一种改进算法，其改进在于：不需回溯i指针，而是利用已得“部分匹配”的结果将模式串尽可能远地向右“滑动”。 以模式T=abcac和主串S=ababcabcacbab的匹配过程为例简但介绍KMP算法：a b a b c a b c a c b a b第一趟匹配第一趟匹配 i=1.a b c a c第三趟匹配第三趟匹配 i=3.第四趟匹配第四趟匹配 i=4.第五趟匹配第五趟匹配 i=5.第六趟匹配第六趟匹配 i=6.匹配成功a b a b c a b c a c b a ba b a b c a b c a c b
38、 a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a c(a) b c a c37411j=1.j=1.j=1.j=1.j=1.311655T0“部分匹配” S中的第4、5、6个字符必为 b 、c、a则 i=4.和i=5.的那两趟匹配不必进行，仅需将T向右“滑动”3个字符继续进行i=7、j=2时的比较。a b a b c a b c a c b a b第二趟匹配第二趟匹配 i=2.a b c a c2j=1.1“部分匹配” S中的第2个字符必为 b则 i=1.的那趟匹配不必进行，仅需将T向
39、右“滑动”1个字符继续进行i=3、j=1时的比较。 二二 三三在在KMPKMP算法的算法的关键关键在于当匹配过程中产在于当匹配过程中产生生 “ “失配失配”时，模式串向右时，模式串向右“滑动滑动”的可行距离多远才合适。即当模式串的可行距离多远才合适。即当模式串中第中第j j个字符与主串中相应字符个字符与主串中相应字符“失配失配”时，在模式串中需重新和主串中该时，在模式串中需重新和主串中该字符进行比较的字符的位置。由此引字符进行比较的字符的位置。由此引出模式串的出模式串的nextnext函数函数的概念。的概念。注意，注意，这是一个与主串无关的函数这是一个与主串无关的函数。接下来。接下来的问题是如
40、何求得模式串的的问题是如何求得模式串的nextj nextj 。文本编辑文本编辑 文本编辑程序是文本编辑程序是一个面向用户的系统服务程序，广泛应用于一个面向用户的系统服务程序，广泛应用于源程序的输入和修改。其源程序的输入和修改。其实质是修改字符数实质是修改字符数据的形式或格式据的形式或格式，其基本操作包括串的，其基本操作包括串的查找查找，插入插入和和删除删除等基本功能。等基本功能。4.44.4串串操作应用举例操作应用举例 可将文本划分为若干页，每页又有若干行。具体操作中可将文本看作字符串，称为文本串。页是文本串的子串，行又是页的子串。比如可将一段源程序看成一个文比如可将一段源程序看成一个文本串
41、。输入至内存后如下表所示。本串。输入至内存后如下表所示。m ain() floata,b,m ax; scanf(“% f,% f“,& a,& b); ifabmax=a; elsem ax=b; main()floata,b,max;scanf(“%f,%f”,&a,&b);ifabmax=a;elsemax=b;100101102103104105201209226250282284267 进入编辑时，进入编辑时，先为文本串建立相应的页表和行表，先为文本串建立相应的页表和行表，即建立各子串的存储映象。即建立各子串的存储映象。 页表给出页号和该页的起始行号页表给出页号和该页的起始行号. . 行表则指示每行表则指示每一行的行号、起始地址和该行子串的长度。为查找一行的行号、起始地址和该行子串的长度。为查找方便，行表是按行号递增顺序存储的。如下表所示。方便，行表是按行号递增顺序存储的。如下表所示。 然后需在文本编辑程序中设立然后需在文本编辑程序中设立页指针、行指针页指针、行指针和和字字符指针符指针，分别指示当前操作的页、行和字符。，分别指示当前操作的页、行和字符。从而实从而实现基本操作。现基本操作。行行 号号起起 始始 地地 址址长长 度度1001011021031041052012092262502672828172417152
