数据结构课件：第四章.串[28].ppt

1、第四章第四章一、字符串（一、字符串（stringstring）2第一节字符串第一节字符串n字符串是字符串是n(0)n(0)个字符的有限序列，记作：个字符的有限序列，记作： S = S = a a1 1a a2 2a a3 3a an nn其中，其中，S S 是串名字是串名字 a a1 1a a2 2a a3 3a an n是串值是串值 a ai i 是串中字符是串中字符 n n 是串的长度是串的长度( (串中字符的个数串中字符的个数) )n例如例如, , S = S = “Shenzhen UniversityShenzhen University” 第章串第章串二、字符串术语二、字符串术语3

2、第一节字符串第一节字符串n空串：不含任何字符的串，串长度空串：不含任何字符的串，串长度=0=0n空格串：仅由一个或多个空格组成的串空格串：仅由一个或多个空格组成的串n子串：由串中任意个连续的字符组成的子序列。子串：由串中任意个连续的字符组成的子序列。n主串：包含子串的串。主串：包含子串的串。 如：如：A=A=Shenzhen Shenzhen UniversityUniversity B= B=UniversityUniversity A A为主串，为主串，B B为为子串。子串。第章串第章串二、字符串术语二、字符串术语4第一节字符串第一节字符串n位置：字符在序列中的序号。子串在主串中的位置：字

3、符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。位置以子串第一个字符在主串中的位置来表示。n串相等的条件：当两个串的长度相等且各个对串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。应位置的字符都相等时才相等。n模式匹配：确定子串在主串中首次出现的位置模式匹配：确定子串在主串中首次出现的位置的运算的运算 第章串第章串三、字符串与线性表的关系三、字符串与线性表的关系5第一节字符串第一节字符串n串的逻辑结构和线性表极为相似，它们都是线串的逻辑结构和线性表极为相似，它们都是线性结构性结构n串中的每个字符都仅有一个前驱和一个后继串中的每个字符都仅有一个前驱和

4、一个后继第章串第章串三、字符串与线性表的关系三、字符串与线性表的关系6第一节字符串第一节字符串串与线性表又有区别，主要表现为：串与线性表又有区别，主要表现为：n串的数据对象约定是字符集串的数据对象约定是字符集n在线性表的基本操作中，以在线性表的基本操作中，以“单个元素单个元素”作为作为操作对象操作对象n在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为作为操作对象，如：在串中查找某个子串、在串的操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。某个位置上插入一个子串等。第章串第章串一、定长顺序存储表示一、定长顺序存储表示7第二节串的表示和实现第二节串的表示

5、和实现n用一组地址连续的存储单元存储字符序列用一组地址连续的存储单元存储字符序列n如如C C语言中的字符串定义语言中的字符串定义( (以以“00”为串结束标为串结束标志志) ) char StrMAXSTRLEN+1; char StrMAXSTRLEN+1;n定义了长度为定义了长度为MAXSTRLENMAXSTRLEN字符存储空间字符存储空间n字符串长度可以是小于字符串长度可以是小于MAXSTRLENMAXSTRLEN的任何值的任何值（最长串长度有限制，多余部分将被截断）（最长串长度有限制，多余部分将被截断）第章串第章串二、堆分配存储表示二、堆分配存储表示8第二节串的表示和实现第二节串的表示

6、和实现n在程序执行过程中，在程序执行过程中，动态分配动态分配（mallocmalloc）一组一组地址连续的存储单元存储字符序列地址连续的存储单元存储字符序列n在在C C语言中，由语言中，由malloc()malloc()和和free()free()动态分配与动态分配与回收的存储空间称为堆回收的存储空间称为堆n堆分配存储结构的串既有顺序存储结构的特点，堆分配存储结构的串既有顺序存储结构的特点，处理方便处理方便, ,操作中对串长又没有限制操作中对串长又没有限制, ,更显灵活更显灵活第章串第章串三、链存储表示三、链存储表示9第二节串的表示和实现第二节串的表示和实现n采用链表方式存储串值采用链表方式存

7、储串值n每个结点中，可以存放一个字符，也可以存放每个结点中，可以存放一个字符，也可以存放多个字符多个字符第章串第章串Hell0 SSS h e nda # #一、求子串位置函数一、求子串位置函数Index()Index()10第三节串的匹配算法第三节串的匹配算法n子串的定位操作通常称做串的模式匹配子串的定位操作通常称做串的模式匹配n算法（穷举法）：算法（穷举法）： 从主串的指定位置开始，将主串与模式（要查从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较，找的子串）的第一个字符比较，1.1.若相等，则继续逐个比较后续字符；若相等，则继续逐个比较后续字符；2.2.若不等，从主串的

8、下一个字符起再重新和模式若不等，从主串的下一个字符起再重新和模式的字符比较的字符比较第章串第章串一、求子串位置函数一、求子串位置函数Index()Index()11第三节串的匹配算法第三节串的匹配算法nInt Index(Sstring S, Sstring T, int pos) /S S为主串，为主串，T T为模式，串的第为模式，串的第0 0位置存放串长度；串采用顺序存储结构位置存放串长度；串采用顺序存储结构i = pos; j = 1;/ 从第一个位置开始比较while (i=S0 & j T0) return i-T0;/ 返回与模式第一字符相等else return 0;/ 匹配不成

9、功/ 的字符在主串中的序号第章串第章串一、求子串位置函数一、求子串位置函数Index()Index()12第三节串的匹配算法第三节串的匹配算法n在最好的情况下，除比较成功的位置外，其余在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时位置仅需比较一次（模式第一个字符），其时间复杂度为：间复杂度为：O(n+m)O(n+m)(n，m分别为主串和模式的长度)n但在最坏的情况下，如模式为但在最坏的情况下，如模式为0000000100000001，主串为主串为0000000000000000000000000000000001000000000000000000000000

10、0000000001, ,则每次模式的前则每次模式的前7 7个个0 0都要与主串逐一比较，因都要与主串逐一比较，因此，其时间复杂度为：此，其时间复杂度为：O(nO(n* *m)m)第章串第章串二、二、KMPKMP算法算法13第三节串的匹配算法第三节串的匹配算法n是是indexindex函数的一种改进函数的一种改进, ,由由D.E.D.E.K Knuth(nuth(克努特克努特) )J.H.J.H.M Morris(orris(莫里斯莫里斯) )V.R.V.R.P Pratt(ratt(普拉特普拉特) )发现发现n当一趟匹配过程中出现字符比较不等当一趟匹配过程中出现字符比较不等( (失配失配)

11、)时时1.1.不需回溯不需回溯i i指针指针2.2.利用已经得到的利用已经得到的“部分匹配部分匹配”的结果的结果3.3.将模式向右将模式向右“滑动滑动”尽可能远的一段距离尽可能远的一段距离( (nextj)nextj)后，继续进行比较后，继续进行比较第章串第章串二、二、KMPKMP算法算法( (举例举例) )14第三节串的匹配算法第三节串的匹配算法n假设主串假设主串ababcabcacbab,ababcabcacbab,模式模式abcac,abcac,改进算法的匹配过程如下改进算法的匹配过程如下 i=3i=3 第一趟匹配第一趟匹配 a b a b c a b c a c b a ba b a

12、b c a b c a c b a b a b c a b c j=3 j=3 i=3-7i=3-7 第二趟匹配第二趟匹配 a b a b c a b c a c b a ba b a b c a b c a c b a b a b c a c a b c a c j=1 j=1 i=7-10i=7-10 第三趟匹配第三趟匹配 a b a b c a b c a c b a ba b a b c a b c a c b a b a b c a c a b c a c j=2 j=2第章串第章串二、二、KMPKMP算法算法15第三节串的匹配算法第三节串的匹配算法n假设主串为假设主串为s s1 1

13、s s2 2s s3 3s sn n, ,模式串为模式串为p p1 1p p2 2p p3 3p pm mn若主串中第若主串中第i i个字符与模式串中第个字符与模式串中第j j个字符个字符“失失配配”( (s si i!=p!=pj j),),说明，模式串中前面说明，模式串中前面j-1j-1个字符个字符与主串中对应位置的字符相等，即：与主串中对应位置的字符相等，即：p p1 1p p2 2p pj-kj-kp pj-k+1j-k+1p pj-k+2j-k+2p pj-1j-1 = = s si-j+1i-j+1s si-j+2i-j+2s si-ki-ks si-k+1i-k+1s si-k+

14、2i-k+2s si-1i-1第章串第章串二、二、KMPKMP算法算法16第三节串的匹配算法第三节串的匹配算法n现假定主串中第现假定主串中第i i个字符需要与模式串中第个字符需要与模式串中第k(kj)k(kj)个字符比较个字符比较, ,则说明，模式串中前则说明，模式串中前k-1k-1个个字符与主串中对应位置的字符相等，即有以下字符与主串中对应位置的字符相等，即有以下关系成立：关系成立： p p1 1p p2 2p pk-1k-1 = = s si-k+1i-k+1s si-k+2i-k+2s si-1i-1第章串第章串二、二、KMPKMP算法算法17第三节串的匹配算法第三节串的匹配算法n比较比

15、较: :p p1 1p p2 2p pj-kj-kp pj-k+1j-k+1p pj-k+2j-k+2p pj-1j-1 = = s si-j+1i-j+1s si-j+2i-j+2s si-ki-ks si-k+1i-k+1s si-k+2i-k+2s si-1i-1 p p1 1p p2 2p pk-1k-1 = = s si-k+1i-k+1s si-k+2i-k+2s si-1i-1n由以上两式，有下式成立：由以上两式，有下式成立： p p1 1p p2 2p pk-1k-1 = = p pj-k+1j-k+1p pj-k+2j-k+2p pj-1j-1第章串第章串二、二、KMPKMP

16、算法算法18第三节串的匹配算法第三节串的匹配算法 p p1 1p p2 2p pk-1k-1 = = p pj-k+1j-k+1p pj-k+2j-k+2p pj-1j-1n上式是只依赖于模式串的关系式上式是只依赖于模式串的关系式n上式说明上式说明, ,在主串中第在主串中第i i个字符个字符“失配失配”时时, ,仅仅需与模式串中的第需与模式串中的第k k个字符再开始比较（主串个字符再开始比较（主串不需要回溯）不需要回溯）第章串第章串二、二、KMPKMP算法算法19第三节串的匹配算法第三节串的匹配算法n或者换言之或者换言之, ,在模式串中第在模式串中第j j个字符个字符“失配失配”时时, ,模式

17、串模式串第第k k个字符个字符再同主串中对应的失配位置再同主串中对应的失配位置( (i)i)的字符继续进行比较的字符继续进行比较 p p1 1p p2 2p pk-1k-1 = = p pj-k+1j-k+1p pj-k+2j-k+2p pj-1j-1nk k值可以在作串的匹配之前求出值可以在作串的匹配之前求出n一般用一般用nextnext函数求取函数求取k k值值第章串第章串二、二、KMPKMP算法算法( (nextnext函数函数) )20第三节串的匹配算法第三节串的匹配算法nnextnext函数定义为：函数定义为：0 0当当j=1j=1时时nextj =nextj =maxk | 1kj

18、maxk | 1kj且且p p1 1p pk-1k-1= =p pj-k+1j-k+1p pj-1j-11 1其它情况其它情况n如如k=2,k=2,则则p p1 1=p=pj-1 j-1 ( (有有1 1个字符相同个字符相同)除除j=2j=2外外; ; nk=3,k=3,则则p p1 1p p2 2=p=pj-2j-2p pj-1j-1( (有有2 2个字符相同个字符相同) ); ;第章串第章串二、二、KMPKMP算法算法( (nextnext函数函数) )21第三节串的匹配算法第三节串的匹配算法n求求nextjnextj值的办法值的办法1. 1. next1=0, next2=1next1=

19、0, next2=12. 2. 若若T Tj-1j-1=T=Tnextinexti, i, i初值为初值为j-1 j-1 或或 i=nextii=nexti 则则nextj = nexti+1nextj = nexti+1 除非除非i=0, i=0, 些时些时nextj=1nextj=1第章串第章串二、二、KMPKMP算法算法( (nextnext函数函数) )22第三节串的匹配算法第三节串的匹配算法n求求nextjnextj值的算法值的算法1. 1. j j的初值为的初值为1, next1=0, i=01, next1=0, i=03. While(j3. While(j模式串长度模式串长度

20、) ) (1). (1).若若i=0i=0或者或者T Ti i=T=Tj j, ,则则i+,j+,nextj=ii+,j+,nextj=i (2). (2).否则否则, ,i=nextii=nexti 第章串第章串二、二、KMPKMP算法算法( (nextnext函数函数 C C语言实现语言实现) )23第三节串的匹配算法第三节串的匹配算法nint get_next(Sstring T, int next) /求模式串求模式串T T的的nextnext函数值并存入数组函数值并存入数组nextnext。/第第0 0位置存放串长度；串采用顺序存储结构位置存放串长度；串采用顺序存储结构j = 1;

21、next1 = 0; i = 0;/ 从第一个位置开始比较while (j=T0) / T0中存放串长度 if (i=0) | Ti = Tj)+i; +j; nextj=i; / 继续比较后继字符 else i = nexti;/ 模式串向右移第章串第章串二、二、KMPKMP算法算法( (nextnext函数函数 举例举例) )24第三节串的匹配算法第三节串的匹配算法n现有模式串现有模式串ababcabd,ababcabd,求其求其nextnext值值第章串第章串j12345678模式串ababcabdnextj01123123二、二、KMPKMP算法算法( (nextnext函数函数 举例

22、举例) )25第三节串的匹配算法第三节串的匹配算法n现有模式串现有模式串abaababacaabaababaca, ,求其求其nextnext值值第章串第章串j1 2 3 4 5 6 7 8 9 10模式串a b a a b a b a c anextj0 1 1 2 2 3 4 3 4 1二、二、KMPKMP算法算法( (利用利用nextnext函数函数) )26第三节串的匹配算法第三节串的匹配算法n利用利用nextnext函数函数, ,可写出可写出KMPKMP算法如下：算法如下：1. 1. 令令i i的初值为的初值为pos,jpos,j的初值为的初值为1 12. 2. While(iWhi

23、le(i主串长度主串长度) )且且( (jj模式串长度模式串长度) ) (1). (1).若若j=0j=0或者或者s si i=p=pj j, ,则则i+, j+i+, j+ (2). (2).否则否则, ,j=nextjj=nextj j=0j=0表示第一个字符失配表示第一个字符失配第章串第章串二、二、KMPKMP算法算法( (C C语言实现语言实现) )27第三节串的匹配算法第三节串的匹配算法nint Index_KMP(Sstring S, Sstring T, int pos) /S S为主串，为主串，T T为模式，串的第为模式，串的第0 0位置存放串长度；串采用顺序存储结构位置存放串

24、长度；串采用顺序存储结构i = pos; j = 1;/ 从第一个位置开始比较while (i=S0 & j T0) return i-T0;/ 返回与模式第一字符相等else return 0;/ 匹配不成功/ 的字符在主串中的序号 第章串第章串二、二、KMPKMP算法算法( (时间复杂度时间复杂度) )28第三节串的匹配算法第三节串的匹配算法nIndex_KMP()Index_KMP()函数的时间复杂度为函数的时间复杂度为O(n)O(n)n为了求模式串的为了求模式串的nextnext值值, ,其算法与其算法与Index_KMPIndex_KMP很很相似相似, ,其时间复杂度为其时间复杂度为O(m)O(m)n因此因此, ,KMPKMP算法的时间复杂度为算法的时间复杂度为O(n+m)O(n+m)第章串第章串