数据结构：第4章 串

《数据结构：第4章 串》由会员分享，可在线阅读，更多相关《数据结构：第4章 串（36页珍藏版）》请在金锄头文库上搜索。

1、第4章 串第第4章章 串串 4.1 串串类型的定义类型的定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法 第4章 串4.1 串类型的定义串类型的定义 1. 基本概念基本概念l串串(字字符符串串) String：是是零零个个或或多多个个字字符符组组成成的的有有限限序序列列。 一般记为：一般记为：S=a1a2.an (n0) 栈、队列：操作受限的线性表。栈、队列：操作受限的线性表。 串：取值范围受限的线性表，数据对象约束为字符集。串：取值范围受限的线性表，数据对象约束为字符集。 其其中中S是是串串的的名名字字, 用用单单引引号号括括起起来来的的字字符符序序列列是是串

2、串的的值值，ai(1in)可以是字母、数字或其它字符。可以是字母、数字或其它字符。l串的长度：串中字符的个数串的长度：串中字符的个数n。l空空串串(Null String)： n=0时时的的串串称称为为空空串串，用用符符号号“ ”表示表示 。 第4章 串l子子串串：串串中中任任意意个个连连续续的的字字符符组组成成的的子子序序列列称称为为该该串串的的子子 串。串。“ ”为任意串的子串。为任意串的子串。l主串：包含子串的串相应地称为主串。主串：包含子串的串相应地称为主串。第4章 串l位置：字符在串中的序号称为该字符在串中的位置。位置：字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子

3、串的第一个字符在主串子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。中的位置来表示。 A=China Beijing, B=Beijing, C=China, 则它则它们的长度分别为们的长度分别为13、7和和5。B和和C是是A的子串的子串, B在在A中的位置是中的位置是7, C在在A中的位置是中的位置是1。l串串相相等等：当当且且仅仅当当两两个个串串的的值值相相等等时时,称称这这两两个个串串是是相相等等的的，即即只只有有当当两两个个串串的的长长度度相相等等, 并并且且每每个个对应位置的字符都相等时才相等。对应位置的字符都相等时才相等。 l空格串：由一个或多个空格组成的串。与空串不同

4、。空格串：由一个或多个空格组成的串。与空串不同。第4章 串串的基本操作和线性表区别很大。串的基本操作和线性表区别很大。线性表线性表: 大多以大多以“单个元素单个元素”为操作对为操作对象象串串: 通常以通常以“串的整体串的整体”为操作对象为操作对象例，例，查找某个元素；插入某个元素；删除某个元素查找某个元素；插入某个元素；删除某个元素例，例，查找某个子串；截取某个子串；查找某个子串；截取某个子串； 在某个位置插入、删除某个子串在某个位置插入、删除某个子串串的逻辑结构和线性表相似，故看作一种线性表。串的逻辑结构和线性表相似，故看作一种线性表。s = a1a2 an ( n0)第4章 串2. 串的基

5、本运算串的基本运算:l 串赋值串赋值StrAssign(&T, chars) 初始条件初始条件: chars是字符串常量。是字符串常量。 操作结果操作结果: 生成一个值等于生成一个值等于chars的串的串T。 l 串比较串比较StrCompare(S, T) 初始条件初始条件: 串串S和和T存在。存在。 操作结果操作结果: 若若ST, 则返回值则返回值0;如如S=T, 则返回值则返回值=0; 若若ST, 则返回值则返回值0。 l 求串长求串长StrLength(S) 初始条件初始条件: 串串S存在。存在。 操作结果操作结果: 返回串返回串S的长度的长度, 即串即串S中的元素个数。中的元素个数。

6、第4章 串l 串联接串联接Concat(&T, S1, S2) 初始条件初始条件: 串串S1和和S2存在。存在。 操作结果操作结果: 将将T返回由返回由S1和和S2联接而成的新串。联接而成的新串。l 求子串求子串SubString(&Sub, S, pos, len) 初始条件初始条件: 串串S存在存在, 1posStrLength(S)且且 1lenStrLength(S)-pos+1。 操作结果操作结果: 用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长度为len的的 子串。子串。 第4章 串4.2 串的表示和实现串的表示和实现 定长顺序存储表示定长顺序存储表示顺序存储顺序存

7、储 堆分配存储表示堆分配存储表示顺序存储顺序存储 块链存储表示块链存储表示链式存储链式存储第4章 串1. 定长顺序存储表示（定长顺序串）定长顺序存储表示（定长顺序串）define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1; l定定长长顺顺序序串串的的存存储储分分配配是是在在编编译译时时完完成成的的。与与前前面面所所讲讲的的线线性性表表的的顺顺序序存存储储结结构构类类似似, 用用一一组组地地址址连连续续的的存存储储单单元元存存储储串串的的字字符序列。符序列。l超出予定义长度的串值被舍去，称之为超出予定义长度的串值被舍去，称之为“

8、截断截断”。012255第4章 串串长的表示：串长的表示：以下标为以下标为0的数组分量存放串的实际长度；的数组分量存放串的实际长度；串值后加入一个不计入串长的结束标记字串值后加入一个不计入串长的结束标记字符，符，C中中“0”表串值的终结，其表串值的终结，其ASC码码值为值为0。第4章 串算法算法4.2 串联接串联接 strcat( &T，S1，S2 )要求要求: 顺序联接串顺序联接串 S1 和串和串 S2 得到新串得到新串 T 。思想思想: 基于串基于串S1和和S2长度的不同情况，串长度的不同情况，串T可能出现可能出现3种情况种情况:S10+S20MAXSTRLEN，S10+S20MAXSTR

9、LENS10MAXSTRLEN，S10MAXSTRLEN，直接联接，直接联接，T0MAXSTRLEN ；截断截断S2，联接，联接，T0MAXSTRLEN；T S1；第4章 串1255S101255T0T0 = S10 + S201255S20S10+S20MAXSTRLEN第4章 串1255S10S10+S20MAXSTRLEN，S10MAXSTRLEN1255T0 255- -S101255S20 255- -S10T0MAXSTRLEN第4章 串2. 堆分配存储表示（堆串）堆分配存储表示（堆串） 在在C语语言言中中，已已经经有有一一个个称称为为“堆堆”的的自自由由存存储储空空间间，并并可可

10、用用malloc（）和（）和free（）（）函数完成动态存储管理。函数完成动态存储管理。typedef struct char * ch； int length； HString； 应用程序用到的内存分配：栈分配和堆分配。应用程序用到的内存分配：栈分配和堆分配。堆：用户程序动态申请的地址空间。堆：用户程序动态申请的地址空间。栈：保存函数参数和块内局部变量的内存区。栈：保存函数参数和块内局部变量的内存区。void Fun1() void Fun2() int i; int *p=new int10; char p10;.; delete p;.; 第4章 串3. 串的块链存储表示（链串）串的块链

11、存储表示（链串）define CHUNKSIZE typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head; Chunk *tail; int curlen;LString; 第4章 串l存储密度大，一些操作（如插入，删除）有所不便，引存储密度大，一些操作（如插入，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时采起大量字符移动，适合于在串基本保持静态使用方式时采用；用；l存储密度小，运算处理方便，但存储空间量大，若处理存储密度小，运算处理方便，但存储空

12、间量大，若处理过程中，需大量内外存交换，会影响总效率；过程中，需大量内外存交换，会影响总效率；l串的字符集的大小，也会影响串值存储方式的选取。串的字符集的大小，也会影响串值存储方式的选取。第4章 串l作业：作业： 4.14.18第4章 串1. 朴素模式匹配算法朴素模式匹配算法(Brute-Force算法算法) 求子串位置的定位函数求子串位置的定位函数Index( S, T, pos).l模式匹配：子串的定位操作通常称作串的模式匹配。模式匹配：子串的定位操作通常称作串的模式匹配。l目标串：主串目标串：主串S。l模式串：子串模式串：子串T。l匹配成功：若存在匹配成功：若存在T的每个字符依次和的每个

13、字符依次和S中的一个连续中的一个连续字符序列相等，则称匹配成功。返回字符序列相等，则称匹配成功。返回T中第一个字符在中第一个字符在S中的位置。中的位置。l匹配不成功：返回匹配不成功：返回0。4.3 串的模式匹配算法串的模式匹配算法第4章 串lBrute-Force简称为简称为BF算法算法,亦称简单匹配算法亦称简单匹配算法,其基本思路是其基本思路是: 从目标串从目标串s=“s1s2sn”的第一个字符开始的第一个字符开始和模式串和模式串t=“t1t2tm”中的第一个字符比较中的第一个字符比较,若相等若相等,则继续逐个比较后续字符；否则从目则继续逐个比较后续字符；否则从目标串标串s的第二个字符开始重

14、新与模式串的第二个字符开始重新与模式串t的第一的第一个字符进行比较。依次类推个字符进行比较。依次类推,若从目标串若从目标串s的第的第i个字符开始个字符开始,每个字符依次和模式串每个字符依次和模式串t中的对应中的对应字符相等字符相等,则匹配成功则匹配成功,该算法返回该算法返回i；否则；否则,匹匹配失败配失败,函数返回函数返回0。第4章 串 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s的长度为的长度为n(n=6),t的长度为的长度为m(m=3)。用指针用指针i指示目标串指示目标串s的当前比较的当前比较字符位置字符位置,用指针用指针j指示模式串指示模式串t的当前比较

15、字符位置。的当前比较字符位置。BF模模式匹配过程如下所示。式匹配过程如下所示。i = i j +2;j = 1;第4章 串l子串定位子串定位int Index( SString S, SString T, int pos) i= pos; j = 1; while( i=S0 & jT0) return i-T0; else return 0;第4章 串l朴素模式匹配算法的时间复杂度朴素模式匹配算法的时间复杂度 主串长主串长n； 子串长子串长m。可能匹配成功的位置（。可能匹配成功的位置（1 n-m+1)。最好的情况下，最好的情况下， 第第i个位置匹配成功，比较了（个位置匹配成功，比较了（i-1

16、+m）次，平均比较次数：）次，平均比较次数： 最好情况下算法的平均时间复杂度最好情况下算法的平均时间复杂度O(n+m)。最坏的情况下，最坏的情况下， 第第i个位置匹配成功，比较了（个位置匹配成功，比较了（i*m）次，平均比较次数：）次，平均比较次数： 设设nm，最坏情况下的平均时间复杂度为，最坏情况下的平均时间复杂度为O(n*m)。第4章 串2. 模式匹配的改进算法模式匹配的改进算法-KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提共同提出的出的,简称简称KMP算法。该算法较算法。该算法较BF算法有较大改进算法有较大改进,主要主要是消除了主

17、串指针的回溯是消除了主串指针的回溯,从而使算法效率有了某种程度从而使算法效率有了某种程度的提高。的提高。因因p p1 1pp2 2,s,s2 2=p=p2 2, ,必有必有s s2 2pp1 1, ,又因又因p p1 1=p=p3 3,s,s3 3=p=p3 3, ,所所以必有以必有s s3 3=p=p1 1。因此。因此, ,第二次匹配可直接从第二次匹配可直接从i=4, i=4, j=2j=2开始。开始。 第4章 串改进：改进：每趟匹配过程中出现字符比较不等时，不回溯每趟匹配过程中出现字符比较不等时，不回溯主指针主指针i，利用已得到的，利用已得到的“部分匹配部分匹配”结果将模式向结果将模式向右

18、滑动尽可能远的一段距离，继续进行比较。右滑动尽可能远的一段距离，继续进行比较。第4章 串s s1 1 s s2 2 s s3 3s si-j+1i-j+1 s si-j+2i-j+2s si-2i-2 s si-1i-1 s si i s si+1i+1 p p1 1 p p2 2 p pj-2j-2 p pj-1j-1 p pj j p pj+1j+1 p p1 1 p pk-1k-1 p pk k p pk+1k+1 “p1p2pk-1” = “si-k+1si-k+2si-1” “pj-k+1pj-k+2pj-1” = “si-k+1si-k+2si-1”（部分匹配部分匹配） “p1p2

19、pk-1” = “pj-k+1pj-k+2pj-1” (真子串真子串）第4章 串 max k|1kj,且且“p1pk-1”=“pj-k+1pj-1” 当此集合非空时当此集合非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=为此为此,定义定义nextj函数，表明当模式中第函数，表明当模式中第j个字符与主个字符与主串中相应字符串中相应字符“失配失配”时，在模式中需重新和主串时，在模式中需重新和主串中该字符进行比较的字符的位置。中该字符进行比较的字符的位置。第4章 串int Index_KMP (SString S,SString T, int pos) i= pos,j =

20、1; while (i=S0 & jT0) return i-T0; /*匹配成功匹配成功*/ else return 0; /*返回不匹配标志返回不匹配标志*/ 第4章 串l如何求如何求next函数值函数值1. next1 = 0;表明主串从下一字符表明主串从下一字符si+1起和模式串重新起和模式串重新开始匹配。开始匹配。i = i+1; j = 1;2. 设设nextj = k，则，则nextj+1 = ?若若pk=pj，则有，则有“p1pk-1pk”=“pj-k+1pj-1pj” ，如，如果在果在 j+1发生不匹配，说明发生不匹配，说明nextj+1 = k+1 = nextj+1。若若

21、pkpj，可把求，可把求next值问题看成是一个模式匹配问值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。题，整个模式串既是主串，又是子串。第4章 串 p p1 1 p p2 2p pj-k+1j-k+1p pj-1j-1 p pj j p pj+1 j+1 nextjnextj=k=k p p1 1 p pk-1k-1 p pk k p pk+1 k+1 nextknextk=k=k p p1 1 p pk k p pk k+1 +1 nextknextk=k=k” p p1 1 p pk k p pk k+1 +1 nextknextk=k=k l若若pk=pj，则有，则有“

22、p1pk”=“pj-k+1pj”， nextj+1=k+1=nextk+1=nextnextj+1. l若若pk”=pj ，则有，则有“p1pk”=“pj-k”+1pj”， nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1.第4章 串 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串模式串 a b c a a b b c a b c a a b d a b 0nextj1 1 1 2 2 3 1 1 23 45 67 1 2第4章 串lvoid get_next(SString T, int &next) i=

23、1; next1 = 0; j = 0; while( iT0) if(j=0 | Ti = Tj) +i; +j; nexti = j; else j = nextj; 第4章 串lKMPKMP算法的时间复杂度算法的时间复杂度 设设主主串串s s的的长长度度为为n,n,模模式式串串t t长长度度为为m,m,在在KMPKMP算算法法中中求求nextnext数数组组的的时时间间复复杂杂度度为为O(m),O(m),在在后后面面的的匹匹配配中中因因主主串串s s的的下下标标不不减减即即不不回回溯溯, ,比比较较次次数数可可记记为为n,n,所以所以KMPKMP算法总的时间复杂度为算法总的时间复杂度为O

24、(n+m)O(n+m)。KMP算法最大的特点就是主串的指针不需要回溯，整个匹配过程只需从头到尾扫描一遍，这对于处理需要从外设输入的庞大数据很有效，可以一边读入一边匹配。第4章 串lnext函数的改进函数的改进 j 1 2 3 4 5 模式模式 a a a a bnextj 0 1 2 3 4nextvalj 0 0 0 0 4 a a a b a a a a b a a a a a a a a a a a a a a b i = 5; j = 1i=4j=4j=3j=1j=2nextj = k，而，而pj=pk，则则 主串中主串中si和和pj不等时，不等时，不需再和不需再和pk进行比较，进行比

25、较，而直接和而直接和pnextk进行比进行比较。较。第4章 串 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串模式串 a b c a a b b c a b c a a b d a b nextj 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 0nextvalj1 1 0 2 1 3 1 0 1 10 2 1 7 01第4章 串lvoid get_nextval(SString T, int &nextval) i= 1; nextval1 = 0; j = 0; while( iT0) if(j=0 | Ti = Tj) +i; +j; if(Ti != Tj) nextvali = j; else nextvali = nextvalj; else j = nextvalj; nexti = j;第4章 串本章小结本章小结本章基本学习要点如下本章基本学习要点如下: :(1)(1)理解串和一般线性表之间的差异。理解串和一般线性表之间的差异。(2)(2)重点掌握在顺序串上和链串上实现串的基本运算重点掌握在顺序串上和链串上实现串的基本运算 算法。算法。(3)(3)掌握串的模式匹配算法。掌握串的模式匹配算法。(4)(4)灵活运用串这种数据结构解决一些综合应用问灵活运用串这种数据结构解决一些综合应用问 题。题。