数据结构 第4 章 字符串.ppt

《数据结构 第4 章 字符串.ppt》由会员分享，可在线阅读，更多相关《数据结构 第4 章 字符串.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中1、串的概念；串的概念；2、串的存储结构；串的存储结构；3、串的运算。串的运算。教学内容教学内容 数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中x的值为整数的值为整数123。x的值为字符串的值为字符串123。串的串的值值值值串的串的长度长度长度长度串的串的名名名名4.1串类型的定义串类型的定义 串（串（串（串（也称也称也称也称字符串字符串字符串字符串）：）：）：）：是由是由0个或多个字符组成的有限序列。个或多个字符组成的有限序列。通

2、常记为：通常记为：s=“a1a2a3aian”(n0)。字母、数字或其他字符字母、数字或其他字符 必须有！必须有！不属于串！不属于串！作用：避免与作用：避免与变量名变量名或或数的常量数的常量混淆。混淆。例：例：x=“123”x=123test=“test”基本概念基本概念 数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中空串：空串：空串：空串：不含任何字符的串，串长度不含任何字符的串，串长度=0，用符号，用符号 表示表示。空格串：空格串：空格串：空格串：仅由一个或多个空格组成的串。仅由一个或多个空格组成的串。子串：子串：子串：子串：由串中由串中任意任意个个连续连续的字符组

3、成的子序列。的字符组成的子序列。例：例：S=“JINAN”S1=“”、S2=“NA”、S=“JINAN”主串：主串：主串：主串：包含子串的串。包含子串的串。位置：位置：位置：位置：字符在序列中的序号。字符在序列中的序号。子串在主串中的位置是子串的子串在主串中的位置是子串的首字符首字符首字符首字符在主串中的位置。在主串中的位置。子串。子串。S4=“JAN”非子串（非子串（非非串串S中的中的连续连续字符所组成）。字符所组成）。在在S中的位置：中的位置：3在在S中的位置：中的位置：1串相等的条件：串相等的条件：串相等的条件：串相等的条件：当两个串的长度相等且各个对应位置的字符都当两个串的长度相等且各

4、个对应位置的字符都相等时才相等。相等时才相等。例：例：S=“JINAN”S1=“JINAN”SS1 空串是任意串的子串，任意串是其自身的子串。空串是任意串的子串，任意串是其自身的子串。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中串的逻辑结构：串的逻辑结构：串的逻辑结构：串的逻辑结构：和线性表极为相似。和线性表极为相似。串的基本操作：串的基本操作：串的基本操作：串的基本操作：和线性表有很大差别。和线性表有很大差别。区别：区别：串的数据对象约定是字符集。串的数据对象约定是字符集。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象；作为

5、操作对象；在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为作为操作对象。操作对象。例如：在串中查找某个子串、求例如：在串中查找某个子串、求 取一个子串、在串的某个位置上插入一个子取一个子串、在串的某个位置上插入一个子 串以及删除一个子串等。串以及删除一个子串等。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中串的抽象数据类型的定义串的抽象数据类型的定义ADTString数据对象：数据对象：Dai|aiCharacterSetCharacterSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n基本操作：基本操作

6、：StrAssignStrAssign(&T,chars)(&T,chars)初始条件：初始条件：chars是字符串常量。是字符串常量。操作结果：操作结果：把把chars赋为赋为T的值。的值。StrCopyStrCopy(&T,S)(&T,S)初始条件：初始条件：串串S存在。存在。操作结果：操作结果：由串由串S复制得串复制得串T。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中DestroyStringDestroyString(&S)(&S)初始条件：初始条件：串串S存在。存在。操作结果：操作结果：串串S被销毁。被销毁。StrEmptyStrEmpty(S)(S)初始条

7、件：初始条件：串串S存在。存在。操作结果：操作结果：若若S为空串，则返回为空串，则返回TRUE，否则返回否则返回FALSE。StrCompareStrCompare(S,T)(S,T)初始条件：初始条件：串串S和和T存在。存在。操作结果：操作结果：若若ST，则返回值则返回值0；若若S=T，则返回值则返回值=0；若若ST，则返回值则返回值0。“串值大小串值大小”是按是按“词典次序词典次序”进行比较的，如：进行比较的，如：StrCompare(“data”,“stru”)0数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StrLengthStrLength(S)(S)初始条件

8、：初始条件：串串S存在。存在。操作结果：操作结果：返回返回S的元素个数，称为串的长度。的元素个数，称为串的长度。ConcatConcat(&T,S1,S2)(&T,S1,S2)初始条件：初始条件：串串S1和和S2存在。存在。操作结果：操作结果：用用T返回由返回由S1和和S2联接联接而成的新而成的新串。串。SubStringSubString(&Sub,S,pos,(&Sub,S,pos,lenlen)初始条件：初始条件：串串S存在，存在，1posStrLength(S)且且0lenStrLength(S)pos+1。操作结果：操作结果：用用Sub返回串返回串S的第的第pos个字符起长度个字符起

9、长度为为len的子串。的子串。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中Index(S,T,pos)Index(S,T,pos)初始条件：初始条件：串串S和和T存在，存在，T是非空串，是非空串，1posStrLength(S)。操作结果：操作结果：若主串若主串S中存在和串中存在和串T值相同的子串，则返回值相同的子串，则返回它在主串它在主串S中第中第pos个字符之后第一次出现的个字符之后第一次出现的位置；否则函数值为位置；否则函数值为0。Replace(&S,T,V)Replace(&S,T,V)初始条件：初始条件：串串S、T和和V存在，存在，T是非空串。是非空串。操

10、作结果：操作结果：用用V替换主串替换主串S中出现的所有与中出现的所有与T相等的相等的不重叠不重叠不重叠不重叠 的子串。的子串。假设假设S=“abcacabcaca”，T=“abca”V=“ab”，则置换之后的则置换之后的S=“abcabca”，而不是而不是“abbca”。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中 StrInsertStrInsert(&S,pos,T)(&S,pos,T)初始条件：初始条件：串串S和和T存在，存在，1posStrLength(S)1。操作结果：操作结果：在串在串S的第的第pos个字符之前插入串个字符之前插入串T。StrDeleteS

11、trDelete(&S,pos,(&S,pos,lenlen)初始条件：初始条件：串串S存在，存在，1posStrLength(S)-len+1。操作结果：操作结果：从串从串S中删除第中删除第pos个字符起长度为个字符起长度为len的子串。的子串。ClearStringClearString(&S)(&S)初始条件：初始条件：串串S存在。存在。操作结果：操作结果：将将S清为空串。清为空串。ADTString数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中在以上操作中，串赋值在以上操作中，串赋值StrAssign、串比较串比较StrCompare、求求串长串长StrLeng

12、th、串联接串联接Concat以及求子串以及求子串SubString等五种操等五种操作构成串类型的最小操作子集，即作构成串类型的最小操作子集，即这些操作不可能利用其他串操这些操作不可能利用其他串操这些操作不可能利用其他串操这些操作不可能利用其他串操 作来实现作来实现作来实现作来实现。除串清除除串清除ClearString和串销毁和串销毁DestroyString以外的其他串以外的其他串操作均可在最小操作子集上实现。操作均可在最小操作子集上实现。例如，可利用判等、求串长和求子串等操作实现定位函数例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T,pos)：在主串在主串S中取从第

13、中取从第i（i的初值为的初值为pos）个字符个字符起、长度和串起、长度和串T相等的子串同串相等的子串同串T比较，若相等，则求得函数比较，若相等，则求得函数值为值为i，否则否则i值增值增1，直至串，直至串S中从第中从第i个字符起直到串尾的个字符起直到串尾的子串长度小于串子串长度小于串T的长度为止。的长度为止。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中intIndex(StringS,StringT,intpos)/T为非空串。若为非空串。若S中第中第pos个字符之后存在与个字符之后存在与T相等的子相等的子/串，则返回第一个这样的子串在串，则返回第一个这样的子串在S中的

14、位置，否则返回中的位置，否则返回0。if(pos0)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;/找到和找到和T相等的子串相等的子串/while/ifreturn0;/S中不存在满足条件的子串中不存在满足条件的子串/Index数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中4.2串的表示和实现串的表示和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构因为串是特殊的线性表，故其

15、存储结构与线性表的存储结构类似，只不过类似，只不过组成串的结点是单个字符组成串的结点是单个字符组成串的结点是单个字符组成串的结点是单个字符。4.2.1定长顺序存储表示定长顺序存储表示 定长顺序存储表示定长顺序存储表示，也称为，也称为静态存储分配的顺序串静态存储分配的顺序串。它是。它是用一组用一组地址连续地址连续地址连续地址连续的存储单元来的存储单元来依次存放依次存放依次存放依次存放串中的字符序列。串中的字符序列。“定长定长”、“静态静态”的意思可简单地理解为一个确定的存储空的意思可简单地理解为一个确定的存储空间，它的长度是不变的。间，它的长度是不变的。数据结构数据结构第四章第四章串串制作：制作

16、：计算机科学与技术系 徐振中可直接使用定长的字符数组来定义一个串，可直接使用定长的字符数组来定义一个串，数组的上界数组的上界 预先给出：预先给出：#definemaxstrlen255/可在可在255以内定义最大串长。以内定义最大串长。typedefunsigndecharsstringmaxstrlen+1;/0号单元存放串的长度。号单元存放串的长度。串的实际长度可在这个预定义长度的范围内随意设定，串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为超过预定义长度的串值则被舍去，称之为“截断截断”。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系

17、 徐振中例：对于串例：对于串ch=“Thisisadog.”用上述两种方法分别表示为：用上述两种方法分别表示为：Thisisadog.014Thisisadog.串长串长串长串长的两种表示方法：的两种表示方法：一种是在串的存贮区首地址一种是在串的存贮区首地址显式地显式地显式地显式地记录串的长度。记录串的长度。另一种是另一种是隐式的隐式的隐式的隐式的，在串之后加入一个串的结束标志。，在串之后加入一个串的结束标志。PASCAL语言中的串类型就采用这种方法。语言中的串类型就采用这种方法。如如C中使用中使用“0”，“0”不计入串长。不计入串长。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技

18、术系 徐振中 定长顺序存储表示时串的操作的实现定长顺序存储表示时串的操作的实现 1、串联接、串联接Concat(&T,S1,S2)假设串假设串T是由串是由串S1联结串联结串S2得到的，则只要进行相应的得到的，则只要进行相应的“串值复制串值复制”操作即可，需要时进行操作即可，需要时进行“截断截断”。串串T值值S10+S20 MAXSTRLENS10MAXSTRLENS10=MAXSTRLEN结果正确结果正确结果正确结果正确 结果结果结果结果 S2S2被被被被“截断截断截断截断”结果结果结果结果 T=S1T=S1数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StatusCo

19、ncat(SString&T,SStringS1,SStringS2)if(S10+S20=MAXSTRLEN)if(S10+S20=MAXSTRLEN)/未截断未截断T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;elseelseif(S10MAXSTRSIZE)if(S10MAXSTRSIZE)/截断截断T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;elseelse/截断截断(仅取仅取S1)T0.MAXSTRLEN=S

20、10.MAXSTRLEN;uncut=FALSE;returnuncut;/Concat串联接串联接Concat算法描述算法描述数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中2、求子串、求子串SubString(&Sub,S,pos,len)求子串的过程即为复制字符序列的过程，将串求子串的过程即为复制字符序列的过程，将串S中的第中的第pos个字符开始的长度为个字符开始的长度为len的字符串复制到的字符串复制到串串Sub中。中。注：注：注：注：1)、不会出现、不会出现“截断截断”的情况。的情况。2)、可能出现、可能出现“参数非法参数非法”的情况，应返回的情况，应返回ERR

21、OR。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StatusSubString(SString&Sub,SStringS,intpos,intlen)if(posS0|lenS0-pos+1)returnERROR;Sub1len=Spospos+len-1;Sub0=len;returnOK;/SubString求子串求子串SubString算法描述算法描述数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中 定长顺序存储表示时串操作的缺点定长顺序存储表示时串操作的缺点 1、需事先预定义串的最大长度，、需事先预定义串的最大长度，这在程序运行前是很

22、难估计的。这在程序运行前是很难估计的。2、由于定义了串的最大长度，使得、由于定义了串的最大长度，使得串的某些操作受限（截尾），如串的某些操作受限（截尾），如串的联接、插入、置换等运算。串的联接、插入、置换等运算。克服办法：克服办法：不限定最大长度不限定最大长度动态分配串值的存储空间。动态分配串值的存储空间。作业：作业：4.1、4.34.5、4.12、4.13数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中4.2.2堆分配存储表示堆分配存储表示 堆存储结构的特点：堆存储结构的特点：堆存储结构的特点：堆存储结构的特点：仍以一组空间足够大的、仍以一组空间足够大的、地址连续地址连

23、续的的存储单元存储单元依次存放依次存放串值字符序列，但它们的存储空间是在程序串值字符序列，但它们的存储空间是在程序执行过程中执行过程中动态分配动态分配动态分配动态分配的。的。通常，通常，C语言中提供的串类型就是以这种存储方式实现的。语言中提供的串类型就是以这种存储方式实现的。由动态分配函数由动态分配函数malloc()分配一块实际串长所需要的存储空间分配一块实际串长所需要的存储空间（“堆堆”），如果分配成功，则返回此空间的起始地址，作为串的），如果分配成功，则返回此空间的起始地址，作为串的基址。由基址。由free()释放串不再需要的空间。释放串不再需要的空间。数据结构数据结构第四章第四章串串制

24、作：制作：计算机科学与技术系 徐振中用堆存放字符串时，其结构用用堆存放字符串时，其结构用C语言定义如下：语言定义如下：typedefstructchar*ch;/若非空则按串长分配存储区，否则若非空则按串长分配存储区，否则ch为为NULLintlength;/串长度串长度HString;这类串操作的这类串操作的实现算法实现算法实现算法实现算法为：为：1、为新生成的串分配一个存储空间；为新生成的串分配一个存储空间；2、进行串值的复制。进行串值的复制。串插入操作串插入操作StrInsert(&S,pos,T)的的实现算法实现算法实现算法实现算法为：为：1、为串为串S重新分配大小等于串重新分配大小等

25、于串S和串和串T长度之和的存储空间；长度之和的存储空间；2、进行串值的复制。、进行串值的复制。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StatusStrInsert(Hstring&S,intpos,HStringT)if(posS.length+1)returnERROR;/插入位置不合法插入位置不合法if(T.length)/T非空，则为非空，则为S重新分配空间并插入重新分配空间并插入Tif(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);for(i=S.len

26、gth-1;i=pos-1;-i)/为插入为插入T而腾出位置而腾出位置S.chi+T.length=S.chi;S.chpos-1pos+T.length-2=T.ch0T.length-1;/插入插入TS.length+=T.length;returnOK;/StrInsert例：例：S=ABCDET=XYpos=4ABCDEABCDES.chiPos-1EDtypedefstructchar*ch;intlength;HString;iXYXY数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StatusConcat(HString&T,HStringS1,HStrin

27、gS2)if(T.ch)free(T.ch);/释放旧空间释放旧空间if(!(T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);T.ch0S1.length-1=S1.ch0S1.length-1;T.length=S1.length+S2.length;T.chS1.lengthT.length-1=S2.ch0S2.length-1;returnOK;/Concat串联接串联接Concat算法描述算法描述数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中StatusSubString(H

28、String&Sub,HStringS,intpos,intlen)if(posS.length|lenS.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);/释放旧空间释放旧空间if(!len)Sub.chSub.ch=NULL;Sub.length=0;=NULL;Sub.length=0;/空子串空子串elseSub.ch=(char*)malloc(len*sizeof(char);Sub.ch0len-1=Spos-1pos+len-2;Sub.length=len;/完整子串完整子串 returnOK;/SubString求子串求子串S

29、ubString算法描述算法描述数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中statusStrcopy(HString&T,HStringS)if(T)free(T.ch);n=S.length;ifn!=0T.ch=(char*)malloc(n*sizeof(char);T.ch0.n-1=S.ch0.n-1;returnOK;Strcopy串复制串复制Strcopy算法描述：算法描述：数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中statusStrAssign(HString&T,char*chars)if(T.ch)free(T.ch)

30、;/释放释放T原有的空间原有的空间for(i=0，c=chars;c;+i,+c);/求求chars的长度的长度iif(!i)T.ch=NULL;T.length=0;elseif(!(T.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);T.ch0.i-1=chars0.i-1;T.length=i;returnOK;StrAssign串常量赋值串常量赋值StrAssign算法描述：算法描述：数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中intStrCompare(HStringS,HStringT)for(i=0;iS.le

31、ngth&iT.length;+i)if(S.chi!=T.chi)returnS.chi-T.chi;returnS.length-T.length;/StrCompare串比较串比较StrCompare算法描述：算法描述：数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中statusClearString(HString&S)/将串将串S清为空串清为空串if(S.ch)free(S.ch);S.ch=NULL;S.length=0;ReturnOK;ClearString清空串清空串ClearString算法描述：算法描述：数据结构数据结构第四章第四章串串制作：制作：计

32、算机科学与技术系 徐振中堆存储结构的优点：堆存储结构的优点：堆存储结构的优点：堆存储结构的优点：堆存储结构既有顺序存储结构的堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。何限制，更显灵活，因此在串处理的应用程序中常被采用。定长顺序存储表示和堆分配存储表示通常为高级程序定长顺序存储表示和堆分配存储表示通常为高级程序 设计语言所采用。设计语言所采用。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中4.2.3串的块链存储表示串的块链存储表示 串值

33、也可用链表来存储，和线性表的链式存储类似。可用单串值也可用链表来存储，和线性表的链式存储类似。可用单链表存放字符串，链表存放字符串，串的这种链式存储结构简称为串的这种链式存储结构简称为链串链串链串链串。链串链串链串链串与与单单 链表链表的差异只是它的的差异只是它的结点数据域为单个字符结点数据域为单个字符结点数据域为单个字符结点数据域为单个字符。SABCDE SABCDE这种存储结构方便于串的插入和删除操作，但是空间利用率这种存储结构方便于串的插入和删除操作，但是空间利用率不高，因为存放每一个字符要不高，因为存放每一个字符要“搭配搭配”一个指向下一字符的地址，一个指向下一字符的地址，而地址所占空

34、间是比较大的。而地址所占空间是比较大的。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中为了提高空间的利用率，可以使每个结点存放多个字符（为了提高空间的利用率，可以使每个结点存放多个字符（事事实上这是实上这是顺序串顺序串顺序串顺序串和和链串链串链串链串的综合的综合(折衷折衷)），称为），称为块链结构块链结构块链结构块链结构。SABCDESA B CD E#存储密度存储密度 =数据元素所占存储位数据元素所占存储位实际分配的存储位实际分配的存储位实际应用时，可以根据问题所需来设置结点的大小。实际应用时，可以根据问题所需来设置结点的大小。例如：在编辑系统中，整个文本编辑区可以看

35、成是一例如：在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即：同一行的个串，每一行是一个子串，构成一个结点。即：同一行的串用定长结构（串用定长结构（80个字符），行和行之间用指针相联接。个字符），行和行之间用指针相联接。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中结点结构用结点结构用C语言定义如下：语言定义如下：#defineCHUNKSIZE80/可由用户定义的块大小可由用户定义的块大小typedefstructChunk/结点结构结点结构charchCUNKSIZE;structChunk*next;Chunk;为了便于进行串的操作

36、（联接），当以块链存储串值时，为了便于进行串的操作（联接），当以块链存储串值时，除除头指针头指针外还可附设一个外还可附设一个尾指针尾指针指示链表中的最后一个结点，指示链表中的最后一个结点，并给出当前串的长度。其结构用并给出当前串的长度。其结构用C语言定义如下：语言定义如下：typedefstruct/串的链表结构串的链表结构Chunk*head,*tail;/串的头和尾指针串的头和尾指针intcurlen;/串的当前长度串的当前长度LString;数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中4.3串的模式匹配算法串的模式匹配算法模式匹配模式匹配：子串定位运算。子串定位

37、运算。(串匹配串匹配)就是在主串中找出子串出现的位置。就是在主串中找出子串出现的位置。就是在主串中找出子串出现的位置。就是在主串中找出子串出现的位置。用函数用函数Index(S,T,pos)实现。实现。在在串匹配串匹配中中，将将主串主串S称为称为目标目标(串串)，子串子串T称为称为模式模式(串串)。如果在如果在主串主串S中能够找到中能够找到子串子串T，则则称称匹配成功匹配成功匹配成功匹配成功，返回返回返回返回第一第一 个和个和子串子串T中第一个字符相等的字符在中第一个字符相等的字符在主串主串S中的中的序号序号序号序号；否则否则，称称匹配失败匹配失败匹配失败匹配失败，返回返回返回返回 0 0。数

38、据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中当用当用模式模式依次从依次从目标目标的头部往后移，移到的位置就的头部往后移，移到的位置就叫叫位移位移位移位移，每次移动后要看，每次移动后要看模式模式里的字符和里的字符和目标目标中相应的中相应的字符是否相等，若都相等，这次位移就叫字符是否相等，若都相等，这次位移就叫有效位移有效位移有效位移有效位移（其（其实就是从这个位置开始的实就是从这个位置开始的匹配成功匹配成功），否则叫），否则叫无效位移无效位移无效位移无效位移。模式匹配模式匹配是各种处理系统中最重要的操作之一，也是各种处理系统中最重要的操作之一，也是一个比较复杂的串操作。模

39、式匹配的算法不同，效率是一个比较复杂的串操作。模式匹配的算法不同，效率将有很大差别。同一算法应用不同，效率亦有很大差别。将有很大差别。同一算法应用不同，效率亦有很大差别。数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中朴素的模式匹配算法朴素的模式匹配算法算法思想：算法思想：从从主串主串S的第的第pos个字符起和个字符起和模式模式T的第一个字符比较之，的第一个字符比较之，若相同，则继续比较后续字符；否则从若相同，则继续比较后续字符；否则从主串主串S的下一个字符起再的下一个字符起再重新和重新和模式模式T的字符比较之。的字符比较之。例：例：S=JINANSHI，T=NAN。J

40、I N A NS H IN A N不匹配不匹配NAN不匹配不匹配NAN匹配匹配NAN匹配匹配匹配匹配3数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中当采用定长顺序存储结构时，实现此操作的算法如下：当采用定长顺序存储结构时，实现此操作的算法如下：intIndex(SStringS,SStringT,intpos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。个字符之后的位置。/若不存在，则函数值为若不存在，则函数值为0。/其中，其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&jT0)returni-T0;

41、elsereturn0;/Index数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中4.1有关概念有关概念串（或字符串）、串（或字符串）、串名、串值、串的长度、空串、空格串、串名、串值、串的长度、空串、空格串、子串、主串、位置、子串在主串中的位置。子串、主串、位置、子串在主串中的位置。总总结结4.2串的存储表示串的存储表示1.串的定长顺序存储表示串的定长顺序存储表示2.串的变长顺序存储（堆分配存储）表示串的变长顺序存储（堆分配存储）表示3.串的块链存储表示串的块链存储表示4.3串的常用运算串的常用运算在串的基本操作中，通常已在串的基本操作中，通常已“串的整体串的整体”作为

42、操作对象。作为操作对象。串的操作有很多，串赋值串的操作有很多，串赋值StrAssign,串的比较串的比较StrCompare,求串长求串长StrLength,串连接串连接Concat,以及求子串以及求子串SubString等等5种操作构成串类型的最小操作子集。种操作构成串类型的最小操作子集。作业：作业：4.25数据结构数据结构第四章第四章串串制作：制作：计算机科学与技术系 徐振中1.熟悉串的七种基本操作的定义，并能利用这些基本操作熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。来实现串的其它各种操作的方法。2.熟练掌握串的定长顺序存储结构及其实现串的各种操作熟练掌握串的定长顺序存储结构及其实现串的各种操作的基本方法。的基本方法。3.了解串的堆存储结构及其实现串的各种操作的基本方法。了解串的堆存储结构及其实现串的各种操作的基本方法。教学要求教学要求 4.掌握朴素的模式匹配算法。掌握朴素的模式匹配算法。