第4章 算法数据结构ppt课件.ppt

第4章 串,字符串一般简称串,【学习目标】1. 理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2. 理解串类型的各种存储表示方法。3. 理解串匹配的各种算法。【重点和难点】相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。,为何要单独讨论“串”类型？1） 程序设计中，处理对象很多都是串类型。2） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）。,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,4.1 串类型的定义,4.1 串类型定义,串(string):即字符串，是由零个或多个字符组成的有限序列。 是数据元素为单个字符的特殊线性表。,记为： s = a1 a2 . an (n0 ),ai( 0i n)可以是字母、数字或其它字符；,4.1 串类型定义,长度：串中字符数目 n 称为串的长度。空串：长度为 0 的字符称为空串(Null string)， 我们用表示“空串”。空格串：由一个或多个空格组成的串 称为空格串(black string)。,问：空串和空格串有无区别？,答：有区别。空串(Null String)是指长度为零的串；而空格串(Blank String),是指包含一个或多个空格字符 (空格键)的字符串。它的长度为空格字符的个数,空串是任意串的子串；任意串S都是自身的子串，除S本身外，S的其它子串称为“真子串”,4.1 串类型定义,子串：串 S 中任意个连续的字符组成的子序列叫 S 的子串;主串：包含子串的串 S 叫主串。字符位置：字符在串中的序号。子串位置：子串的第一个字符在主串中的序号。串相等：串长度相等，且对应位置上字符相等。,例1：现有以下4个字符串：a =BEI b =JING c = BEIJING d = BEI JING,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？ 空串是哪个串的子串？ a是不是自己的子串？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,C语言中已有类似串运算函数,串的抽象数据类型定义ADT String 数据对象： D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 基本操作: （教材p71给出13种基本操作） StrAssign(&T, chars) / 串赋值，生成值为chars的串T StrCompare(S,T) / 串比较，若ST，返回值大于0 StrLength(S) / 求串长，即返回S的元素个数 Concat(&T, S1, S2) / 串连接，用T返回S1S2的新串 SubString(&Sub, S, pos, len) / 求S中pos起长度为len的子串 Index(S, T, pos) / 返回子串T在pos之后的位置 Replace(&S, T,V) / 用子串V替换子串T,4.1 串类型定义,注：Concat操作concatenation，把多个短字符串合并为长字符串,复习：C语言中常用的串运算,4.1 串类型定义,注：用C处理字符串时，要调用标准库函数 #include,串比较：int strcmp(char *s1,char *s2); / StrCompare(S,T) 求串长：int strlen(char *s); /StrLength(S) 串连接：char strcat(char *to,char *from) / Concat( / Index(S, T, pos) ,4.1 串类型定义,可利用串比较、求串长和求子串等操作实现定位函数实现Index(S，T，pos),算法的基本思想为：,StrCompare(SubString(S, i, StrLength(T), T ),S 串,T 串,T 串,i,pos,n-m+1,n= StrLength(S) m= StrLength(T),4.1 串类型定义,算法描述：int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与T相等的子串，/ 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index,Index(S, T, pos) / 返回子串T在主串S中第pos之后第一次出现的位置,例1：设 s=I AM A STUDENT,t=GOOD,q=WORKER。求： StrLength(s) StrLength(t) SubString(&sub, s, 8, 7)= SubString(&sub, t, 2, 1)= Index(s, A)= Index(s, t)= Replace( &s, STUDENT, q )=,4.1 串类型定义,14,4,STUDENT,O,3,0,I AM A WORKER,思考：SubString(&sub, q, 5, 0)=,长度为 0 的子串为“合法”串,4.1 串类型定义,例2：设 s =I AM A STUDENT, t =GOOD,求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ？,解：因为SubString(s,6,2)A ；SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)A GOOD STUDENT,4.2 串的表示和实现,4.2串的表示和实现,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。例如查找某子串，在主串某位置上插入一个子串等。,4.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储链式方式存储,串有三种机内表示方法：,顺序存储,链式存储,4.2.1 定长顺序存储表示用一组地址连续的存储单元来存放串值的字符序列。为每个定义的变量分配固定长度存储区#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,4.2串的表示和实现,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”,4.2.1 定长顺序存储表示1.串联接Concat(&T,s1,s2),4.2串的表示和实现,串的联接算法中需分三种情况处理S10+S20MAXSTRLENS10 MAXSTRLEN, S10+ S20MAXSTRLENS10= MAXSTRLEN,S1 sm s1 s2 S2 tn t1 t2 T sm+tn s1 s2 t1 t2 ,T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; ,4.2串的表示和实现,Status Concat(SString S1, SString S2, SString / Concat,T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截断,else if (S10 MAXSTRSIZE) / 截断,else / 截断(仅取S1),T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,4.2.1 定长顺序存储表示2.求子串SubString(&Sub,S,pos,len),4.2串的表示和实现,将串S中从第pos个字符开始、长度为len的字符序列复制到串Sub中(注：串Sub的预留长度与S一样),s = a1 a2 . an,pos,len,Sub ,讨论：在操作中出现串值序列长度超过上界MAXSIZE时，约定截尾法处理。若想存放超长字符串怎么办？改用动态分配的一维数组堆,4.2.1 定长顺序存储表示2.求子串SubString(/,4.2串的表示和实现,子串长度,4.2串的表示和实现,4.2.2 堆分配存储表示仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,通常，C语言中存在一个称之为“堆”的自由存储空间。提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理。,/=串的堆分配存储表示=typedef struct char *ch; / 若是非空串,则按串实际长度分 /配存储区;否则 ch为NULL int length; / 串长度 HString;,4.2串的表示和实现,4.2.2 堆分配存储表示串插入操作：void StrInsert (HString / StrInsert _HSq,C是指针变量，可以自增！意即每次后移一个数据单元。,4.2串的表示和实现,4.2.2 堆分配存储表示Status StrAssign(HString /StrAssign,此处T.ch0没有用来装串长，因为另有T.length 分量,其它基本操作的算法描述见教材P77,4.2串的表示和实现,4.2.3 串的块链存储表示由于串结构的特殊性结构中的每个数据元素是一个字符，则采用链表时，存在一个结点大小问题。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),最后结点未占满，补“#”或其它非串值字符,4.2串的表示和实现,4.2.3 串的块链存储表示,存储密度 =,数据元素所占存储位,实际分配的存储位,结点大小的选择直接影响着串处理效率,法1存储密度为 ；法2存储密度为 ；,1/2,9/15=3/5,存储密度小(法1)，运算处理方便，但占用存储量大显然，若数据元素很多，用法2存储更优称为块链结构,目的：连结操作注意处理第一个串尾无效字符,4.2串的表示和实现,4.2.3 串的块链存储表示块链类型定义：,#define CHUNKSIZE 80 /可由用户定义的块大小typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域 struct Chunk * next ; /结点中的指针域 Chunk;,typedef struct /其次定义用链式存储的串类型 Chunk *head; /头指针 Chunk *tail; /尾指针 int curLen; /结点个数 Lstring; /串类型只用一次，前面可以不加Lstring,4.2串的表示和实现,a b c A B C 1 # # /,块链结构存储示意图,161,head tail curlen,X,链式存储结构对某些操作(如联接)有一定方便之处但总的来说不如另两种灵活，存储量大操作复杂。操作的实现和线性表类似，不作详细讨论。,4.3 串的模式匹配算法,是各种串的处理系统中最重要的操作之一,4.3串的模式匹配算法,定义：子串的定位操作通常称为串的模式匹配。Index(S，T，pos)为典型函数：其中S称为主串，T称为模式串。,回忆：Index(S，T，pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串 S 中存在和串 T 值相同的子串返回它在主串 S 中第 pos 个字符之后第一次出现的位置; 否则函数值为0。,教材P72 算法4.1 用其它操作实现,4.3串的模式匹配算法,下面讨论两种匹配算法：,一、简单算法Index(S,T,pos),二、改进算法KMP算法,4.3串的模式匹配算法,简单算法,S 串,T 串,T 串,i,pos,n-m+1,j,算法设计思想：将主串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 i=pos,pos+1,n-m+1; j=1,2,m;直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0 .,4.3串的模式匹配算法,简单算法例：主串s = ababcabcacbab 与模式t=abcac的匹配过程。,第一趟：a b a b c a b c a c b a b a b c a c,第二趟：a b a b c a b c a c b a b a b c a c,4.3串的模式匹配算法,简单算法,第三趟：a b a b c a b c a c b a b a b c a c,第四趟：a b a b c a b c a c b a b a b c a c,4.3串的模式匹配算法,简单算法,第五趟：a b a b c a b c a c b a b a b c a c,第六趟：a b a b c a b c a c b a b a b c a c,4.3串的模式匹配算法,简单算法算法描述：,int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， /则函数值为0。其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Index,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置,4.3串的模式匹配算法,改进算法KMP(D.E.Knuth,J.H.Morris,V.R.Pratt),改进：每一趟匹配过程中出现字符比较不等时，不需回溯 i 指针（简单匹配算法i=i-j+2），而是利用已经得到的“部分匹配”的结果，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。,第三趟：a b a b c a b c a c b a b a b c a c,第一趟 ：a b a b c a b c a c b a b a b c a c,第二趟：a b a b c a b c a c b a b a b c a c,第三趟：a b a b c a b c a c b a b （a） b c a c,如何由当前部分匹配结果确定模式向右滑动的新比较起点k？,KMP算法假设 主串为“s1 s2 sn”，模式串为“p1 p2 pm”，如在匹配过程中产生“失配”（si pj)，模式串应向右滑动多远，即si 应与模式串的pj前面第几个字符再比较？假设 si应与第k(kj)个字符pk继续比较，则模式中前k-1个字符必须满足下列关系：p1 p2 pk-1= si-k+1 si-k+2 si-1(1)而已得到的部分匹配结果是：pj-k+1 pj-k+2 pj-1= si-k+1 si-k+2 si-1(2)由(1)、(2)得到：p1 p2 pk-1 = pj-k+1 pj-k+2 pj-1,4.3串的模式匹配算法,4.3串的模式匹配算法,KMP算法若令nextj = k，则模式串的next函数如下定义： 0 , j = 1 nextj = max k | 1kj且p1 pk-1 = pj-k+1 pj-1 1 ， 其它,j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2,J 1 2 3 4 5 6 7 8 模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2J=1 next1=0J=2 满足1kJ的k不存在，next2=1J=3 满足1kJ的k=2 p1=a不等于p2=b, next3=1J=4 满足1kJ的k=2，3； k=2 : p1=a 等于 p3=a k=3 : p1p2=ab不等于p2p3=ba, next4=2J=5 满足1kJ的k=2，3, 4； k=2 : p1=a 等于 p4=a k=3 : p1p2=ab不等于p3p4=aa, k=4 : p1p2p3=aba不等于p2p3p4=baa,next5=2,J 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2J=6 满足1kJ的k=2，3, 4，5； k=2 : p1=a 不等于 p5=b k=3 : p1p2=ab 等于 p4p5=ab, k=4：p1p2p3=aba不等于 p3p4p5=aab, k=5: p1p2p3p4 =abaa不等于p2p3p4p5=baab。 next6=3J=7 满足1kJ的k=2，3, 4，5，6； k=2 : p1=a 不等于 p6=c k=3 : p1p2=ab 不等于 p5p6=bc, k=4： p1p2p3=aba不等于 p4p5p6=abc, k=5: p1p2p3p4 =abaa不等于p3p4p5p6=aabc, k=6: p1p2p3p4p5 =abaab不等于 p2p3p4p5p6=baabc, next7=1,J 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2J=8 满足1kJ的k=2，3, 4，5，6，7； k=2 : p1=a 等于 p7=a k=3 : p1p2=ab 不等于 p6p7=ca, k=4：p1p2p3=aba不等于 p5p6p7=bca, k=5: p1p2p3p4 =abaa不等于p4p5p6p7=abca, k=6: p1p2p3p4p5 =abaab不等于 p3p4p5p6p7=aabca, k=7: p1p2p3p4p5p6 =abaabc不等于 p2p3p4p5p6p7=baabca, next8=2,简单匹配 i=i-j+2, j=1;,4.3串的模式匹配算法,KMP算法算法描述：int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,过程示例见教材P82 图4.5,4.3串的模式匹配算法,KMP算法如何求得模式串的next函数值？是一个递推过程，分析如下:已知：next1 = 0； 设： nextj = k，则存在如下关系： p1 p2 pk-1 = pj-k+1 pj-k+2 pj-1 此时： nextj+1 = ？若pk = pj ，则表明：p1 p2 pk = pj-k+1 pj-k+2 pj，即 nextj+1 = nextj +1若pk != pj ，则表明：p1 p2 pk ！ = pj-k+1 pj-k+2 pj ，则又是一个模式匹配问题。 当 pj!= pk时将模式串向右滑动让第j个字符和nextk 比较。若相等则nextj+1 = nextk +1,否则依次类推直至某次匹配相等或不等，如不等则 nextj+1=1。,4.3串的模式匹配算法,KMP算法,算法描述：void get_next(SString / get_next,例如：,4.3串的模式匹配算法,KMP算法next函数存在缺点：分析：例如模式aaaab与主串aaabaaaab匹配时的情况,S: a a a b a a a a b,T: a a a a b,i: 1 2 3 4 5 6 7 8 9,a a a a b,a a a a b,a a a a b,a a a a b,此时效率不高的原因为：子串前4位相同时，主串字符若与其中一个不相等，则不必再与其余3个比较。而实际上还在依次比较,4.3串的模式匹配算法,KMP算法改进思想： 得到nextj=k，而模式中pj=pk，则当主串字符si和pj比较不等时，不需要再和pk比较，而直接和pnextk比较，即此时nextj和nextk相同。,void get_nextval(SString / get_nextval,S: a a a b a a a a b,T: a a a a b,i: 1 2 3 4 5 6 7 8 9,a a a a b,本章小结,串,逻辑结构,存储结构,操作(或运算),s = a1a2 .an,定长顺序存储构,模式匹配算法,函数的实现,模式匹配即子串定位运算，即如何实现 Index(S,T,pos)函数,一、简单算法二、KMP算法,