《数据结构Ch4串》由会员分享，可在线阅读，更多相关《数据结构Ch4串（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构Ch4串Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望Ch.4 串串字符串是一种特殊的线性表，它的每个字符串是一种特殊的线性表，它的每个结点仅有一个字符组成结点仅有一个字符组成早期，串只能出现在输入输出中，以直早期，串只能出现在输入输出中，以直接量形式出现，不参与运算接量形式出现，不参与运算24.1 串定义及运算串定义及运算n 基本概念基本概念v串：零个或多个字符组成的有限序列串：零个或多个字符组成的有限序列记为记为s=“as=“a1 1a a2 2aan n”(n0)”(
2、n0) s s为为串名串名，引号中为，引号中为串值串值a ai i：字母，数字等字符：字母，数字等字符v串长度：串长度：n n，n=0n=0为空串为空串v空白串：空白串：“ ”“ ”和和“”“”之差别之差别34.1 串定义及运算串定义及运算v子串：串中任意个连续字符组成的子序列称为子串：串中任意个连续字符组成的子序列称为该串的该串的子串子串，包含子串的的串称为，包含子串的的串称为主串主串特别地：特别地：空串是任意串的子串空串是任意串的子串 任意串是其自身的子串任意串是其自身的子串v串常量：只能引用，不能改变，一般用直接量串常量：只能引用，不能改变，一般用直接量表示表示有的语言允许对其命名，如有
3、的语言允许对其命名，如C+C+；const char path=“dir/bin/appl”const char path=“dir/bin/appl”v串变量：可读写，一般有名字串变量：可读写，一般有名字44.1 串定义和运算串定义和运算n基本运算基本运算求串长求串长 复制复制 拼接拼接 比较比较 子串定位子串定位 C C中中v比较比较相等：长度相等，且各对应位置上字符亦相等：长度相等，且各对应位置上字符亦 相等相等大小：字典序大小：字典序“axy”“axy” “ba”“ba”54.1 串定义及运算串定义及运算v子串定位子串定位子串在主串中首次出现时，该子串首字符对应主串子串在主串中首次出现
4、时，该子串首字符对应主串中的位置序号中的位置序号A=“This is a string” B=“is” 序号为序号为3 3 6v其它复杂操作：其它复杂操作：均可用基本操作构成均可用基本操作构成 C中有丰富的函数中有丰富的函数64.2 串的存储结构串的存储结构单个字符，故有特殊技巧单个字符，故有特殊技巧1.静态存储分配的顺序串静态存储分配的顺序串直接用定长字符向量来表示，上界预先给定直接用定长字符向量来表示，上界预先给定 #define MaxStrSize 256 /用户定义用户定义 Typedef char SeqStringMaxStrSize; SeqString S; /S是可容纳是可
5、容纳255个字符的顺序串个字符的顺序串v终结符：终结符：0是串终结符，放在串值尾部是串终结符，放在串值尾部v串长属性：若不设终结符串长属性：若不设终结符typedef struct char chMaxStrSize; /可容纳可容纳256字符字符int length;SeqString74.2 串的存储结构串的存储结构2.动态存储分配的顺序串动态存储分配的顺序串用用C的的malloc和和free动态申请和释放向量空间，有两动态申请和释放向量空间，有两种形式：种形式： typedef char *string; /C中串库相当于使用此类中串库相当于使用此类/似定义似定义 typedef str
6、uct char *ch; /若串非空，则按串实际长度分配，否则若串非空，则按串实际长度分配，否则为为NULL int length；Hstring84.2 串的存储结构串的存储结构3.链串链串块链存储块链存储v结点大小结点大小大小为大小为1：大小为大小为3：v存储密度存储密度dd=数据大小数据大小/结点大小结点大小94.3 串的模式匹配算法（串定位运算）串的模式匹配算法（串定位运算）1.朴素的定位算法（串匹配）朴素的定位算法（串匹配）v主串：目标串主串：目标串（正文串（正文串Target，Text）v子串：模式（串）子串：模式（串）（子串，（子串，Pattern）设设T=“t0t1tn-1”
7、P=“p0p1pm-1” （0mn） 通常通常mnv应用：文本编辑，基因匹配等应用：文本编辑，基因匹配等104.3 串的模式匹配算法串的模式匹配算法v思想：思想：对合法的位置对合法的位置0in-m（合法位移合法位移），依次将目标串），依次将目标串中的子串中的子串Ti.i+m-1和模式串和模式串P0.m-1进行比较进行比较若若T i . i+m-1=P0 . m-1(即：即：“titi+1ti+m-1”=“p0p1pm-1”)则称从位置则称从位置i开始的开始的匹配成功匹配成功；否则，存在某个否则，存在某个0jm-1，使，使ti+jpj，则称从，则称从位置位置i开始的开始的匹配失败匹配失败114.
8、3 串的模式匹配算法串的模式匹配算法v有效位移：有效位移：若若Ti.i+m-1=P0.m-1，则，则i称为有效称为有效 位移位移v无效位移：无效位移：若若Ti.i+m-1P0.m-1，则，则i称为无效称为无效 位移位移v总结：总结：朴素的串匹配算法是对合法位移检查其是否朴素的串匹配算法是对合法位移检查其是否 为有效位移为有效位移 有时需在有时需在T中找到所有有效位移中找到所有有效位移 通常找首次出现的有效位移通常找首次出现的有效位移124.3 串的模式匹配算法串的模式匹配算法int NaiveStrMatch ( SeqString T, SeqString P ) /顺序串上实现顺序串上实现
9、 int i, j, k; int m = P.length, n = T.length; for (i = 0; i=n-m; i+) /i为合法位移，检查其是否为有效位移为合法位移，检查其是否为有效位移 j = 0; k=i; /j指向模式，指向模式，k指向目标指向目标 while(jm最坏情况最坏情况发生在：生在：目目标串是串是 an-1b模式串是模式串是 am-1b / 最后一次成功最后一次成功v用链串表示时定位运算类似用链串表示时定位运算类似154.3 串的模式匹配算法串的模式匹配算法2.KMP算法（不带回溯）算法（不带回溯）下标仍从下标仍从1算算n原因分析原因分析P右移右移1位位T
10、：ti-j+1ti ti-j+1ti-j+2 titi+1P： p1pj p1pj-1pj原因：原因：没有利用部分匹配的结果没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快若能将模式串右移一段距离，则速度更快 回溯回溯比较点比较点164.3 模式匹配算法模式匹配算法T: a b b a b aP: a b a失败时有：失败时有：p1=t1，p2=t2，p3t3若将若将P右移右移1位，则位，则p1？t2，因为，因为 p1p2， p2=t2 p1t2 ，故右移，故右移1位后仍失败位后仍失败若将若将P右移右移2位，则位，则p1？t3，因为，因为 p1=p3，p3t3 p1t3，故右移，故
11、右移2位后仍失败位后仍失败结论：结论：上图比较失败时应直接将上图比较失败时应直接将P右移右移3位（即位（即i=1，2，3均为无效均为无效位移），即直接比较位移），即直接比较p1和和t4，比较点不回溯。，比较点不回溯。Note：上述观察告诉我们，分析模式本身，就可知道潜在的有效上述观察告诉我们，分析模式本身，就可知道潜在的有效位移位移174.3 模式匹配算法模式匹配算法若使比较点不回溯（若使比较点不回溯（i不回溯），则当不回溯），则当tipj（Ti-j+1.i-1=P1.j-1， 即即P的前的前j-1个字符与相应个字符与相应T上字符相等：上字符相等： ti-j+1ti-1=p1pj-1）时，）时
12、，P中哪个字符应与中哪个字符应与ti继续比较？继续比较？因为i不动时，必定是将模式右移一段距离，所以不妨设pk（kj）应与ti 继续比较。Knuth发现，k值仅依赖于P的前j个字符的构成，与目标T无关。采用next1.m数组，用nextj=k表示当tipj时，下一 个应与ti比较的是pk若P中任何字符均无需与ti比较，则将p1与ti+1比较，此时令nextj=0。P右移最大 184.3 模式匹配算法模式匹配算法P的右移位数为：的右移位数为：j-nextjti-j+1 ti ti-j+1ti-k+1ti p1pj p1pkpjj-k右移右移j-k？右移右移i-k+1-(i-j+1)=j-k19n
13、算法算法若已知若已知next1m,则匹配算法如下：则匹配算法如下：int KMPMatch ( char T ,char P ) /T0和和P0分别表示长度分别表示长度 n=T0 ; m=P0 ; /长度长度 i=j=1; /开始开始 t1p1 while (i=n & j0) j=k ; /比较比较ti和和pk: tipkelse j=1; i+; /比较比较ti+1和和p1:ti+1p1 /endif，endwhile4.3 模式匹配算法模式匹配算法20n算法算法if (jm) /匹配成功匹配成功 return i-m; /注意成功时，注意成功时，i和和j均多加了均多加了1 else re
14、turn 0; /匹配失败匹配失败v时间：时间：循环主要取决于循环主要取决于i只增不减，因为只增不减，因为nm，所，所以以时间为O(n)4.3 模式匹配算法模式匹配算法21nnext数数组的性的性质整数数整数数组：0nextjj，即，即0 k0，则比比较ti和和pk，此，此时有有:T i-k+1.i-1 =P 1.k-1 /长度度为k-1T i-j+1.i-1 =P 1.j-1 /失失败前部分匹配，前部分匹配，长度度为j-1P j-k+1.j-1 =P1.k-1 / “p1pk-1”=“pj-k+1pj-1”当当tipj时，k的的值应等于串等于串P1j-1中前后中前后缀相等的子串的相等的子串的
15、长度度加加1T：ti-j+1 ti-k+1 ti-1 ti p1pj-k+1pj-1pj / 前前j-1个字符相等个字符相等P右移右移j-k位：位： p1pk-1pk / 前前k-1个字符相等个字符相等 4.3 模式匹配算法模式匹配算法？22当满足性质当满足性质2的的k有多个（即前后缀相等的子串有多有多个（即前后缀相等的子串有多个）时，应取最大的个）时，应取最大的k值。值。原因：原因：k最大，模式最大，模式P右移右移j-k最少，不丢失任何匹配最少，不丢失任何匹配机会。机会。例例: j 1 2 3 4 T a a a a b b b b P a a a b在在P1.3中，中，k=3最大，最大，j
16、-k=1位右移最少，位右移最少，k=2，k=1时失去匹配机会时失去匹配机会即即P1.3中，前后缀相等的中，前后缀相等的最大真子串最大真子串为为P1.2=P2.3，长度，长度+1=3=k 4.3 模式匹配算法模式匹配算法P右移右移1位，匹配成功位，匹配成功P右移右移2位、位、3位均失败位均失败23 4.3 模式匹配算法模式匹配算法真子串不包括自身，但包括空串真子串不包括自身，但包括空串真子串：真子串：”aa” , “a” , “” 长度：长度： 2 1 0 k ： 3 2 124 4.3 模式匹配算法模式匹配算法若若P1j-1不存在首尾相同的字符串，或者说仅存在长度为零的不存在首尾相同的字符串，
17、或者说仅存在长度为零的相同前后缀（空串）子串，则相同前后缀（空串）子串，则k=1，即，即p1与与ti继续比较继续比较特别地，若特别地，若j=1（即（即tip1），则），则P中任何字符无法与中任何字符无法与ti继续比较，继续比较，P右移右移1位，将位，将p1和和ti+1继续比较。按继续比较。按next定义，可取定义，可取next1=0（对（对任何任何P成立）。成立）。综上所述，当综上所述，当ti pj时时 0 j=1 P1j-1中前后缀相等的中前后缀相等的最大真子串的长度加最大真子串的长度加1(包括空串包括空串),即：即： Maxk|1kj 且且”p1pk-1”=“pj-k+1pj-1” /k=
18、1时时,为空串为空串例：例： j 1 2 3 4 5 6 7 8 P a b a a b c a c nextj 0 1 1 2 2 3 1 2nextj=25 4.3 模式匹配算法模式匹配算法nnext数组生成（递推法）数组生成（递推法）设设nexti=j已知，求已知，求nexti+1 (i1)由性质由性质4告知我们，对任何模式告知我们，对任何模式P，总有，总有next1=0成立，给出了递推基础成立，给出了递推基础next1nexti已知，且已知已知，且已知nexti=jP1i-1中有：中有： “p1pj-1”=“pi-j+1pi-1” /最大真子串长度为最大真子串长度为j-1 扩充一个字符
19、扩充一个字符pi后，比较后，比较pjpi 若若pi=pj，则，则P1j=Pi-j+1i即即P1i中前后缀的最大真子串长度为中前后缀的最大真子串长度为j，故，故nexti+1=j+1 或者或者 nexti+1=nexti+126 4.3 模式匹配算法模式匹配算法若若pipj，则将求，则将求next值的问题看成是模式匹配问题，即值的问题看成是模式匹配问题，即P既为主串又为模式串既为主串又为模式串将将P右移，用右移，用nextj=k作下标，比较作下标，比较pkpi即：令即：令jnextj，如此反复比较，如此反复比较pipj至至pi=pj（情况（情况）或者）或者 j=0，令，令nexti+1=1为止为
20、止 /没有一个字符与没有一个字符与pi比较比较例子自己分析例子自己分析？目标串：目标串：p1pi-j+1pi-k+1pi-1 pi模式串：模式串： p1pj-k+1pj-1 pj p1pk-1 pk27 4.3 模式匹配算法模式匹配算法void GetNext (char p , int next) /求模式串求模式串P的的next数组（递推法）数组（递推法）i-主串指针主串指针i=1; j=0; next1=0;m=P0; /模式串长度模式串长度while (i0if (Pi=Pj)next+i=+j; /nexti+1=j+1else /pipjj=nextj; /可改进为书上一样的算法可
21、改进为书上一样的算法28 4.3 模式匹配算法模式匹配算法时间：时间：O(m)KMP算法的时间加上求算法的时间加上求next数组后为数组后为O(n+m)当当nm时，它远远优于朴素匹配，尤其是模式串时，它远远优于朴素匹配，尤其是模式串 中存在很多中存在很多“部分匹配部分匹配”时时但当但当nm时，朴素匹配可能更好时，朴素匹配可能更好nnext数组的改进数组的改进 next性质性质5：若若tipj时，设时，设nextj=k0，应比较，应比较tipk 若已知若已知pk=pj，则必有，则必有ti pk，此时应使用，此时应使用nextk=k (k0)为下标继续比较：为下标继续比较：tipk 29 4.3
22、模式匹配算法模式匹配算法即可用下述方式节省时间：即可用下述方式节省时间：当当pj=pk时，将时，将nextj置为置为nextk此过程可重复！此过程可重复！例：例： j 1 2 3 4 5 j P nextj nextvalj P a a a a b 1 a 0 0 nextj 0 1 2 3 4 2 a 1 0改进改进 nextvalj 0 0 0 0 4 3 a 2 0 pj p2 p3 p4 p5 4 a 3 0 pk p1p2 p3 p4 5 b 4 4tip2,比较比较tipnext2 p2=p1,next2 next1ti p3,tipnext3, p3=p2next3next2304.3 模式匹配算法模式匹配算法n 求求nextval算法算法与书上不一样的算法，请比较与书上不一样的算法，请比较void GetNextVal (char P, int nextval) /求求nextvali=1; j=0; nextval1=0; m=P0;while (i0 & Pi != Pj)j=nextvalj; / 出循环时出循环时j=0或或Pi=Pji+; j+;if (Pi =Pj)nextvali = nextvalj; / 性质性质5elsenextvali = j; / nextvali+1 = j+1时间仍为时间仍为O(m)31
