最新四章串PPT课件.ppt

《最新四章串PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新四章串PPT课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、一、串及串的基本概念一、串及串的基本概念 串串( (String) String) 即字符串，是由零个或多个字符组成的有即字符串，是由零个或多个字符组成的有限序列，是数据元素为限序列，是数据元素为单个字符单个字符的特殊线性表的特殊线性表。记为：记为： S =a1a2an (n0 ) 串名串名串值（用串值（用 括起来）括起来）隐含结束符隐含结束符/0 ，即即ASCII码码NULL4.1 4.1 串类型的定义串类型的定义StrLength(S)初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：返回返回 S 的元素个数的元素个数,称为串的长度称为串的长度。二、串的抽象数据类型定义二、串的

2、抽象数据类型定义Concat(&T,S1,S2) 初始条件：初始条件：串串 S1 和和 S2 存在。存在。 操作结果：操作结果：用用 T 返回由返回由 S1 和和 S2联接而成的新串。联接而成的新串。或或Concat(S1,S2)用用S1返回由返回由 S1 和和 S2联接而成的新串。联接而成的新串。例如：例如：S1= man , S2= kind Concat( T，S1， S2) 求得求得 T = mankind 或或Concat( S1, S2) 求得求得 S1 = mankind 二、串的抽象数据类型定义二、串的抽象数据类型定义SubString (&Sub, S, pos, len)初

3、始条件：初始条件：串串 S 存在，存在，1posStrLength(S) 且且0lenStrLength(S)-pos+1。操作结果：操作结果：用用 Sub 返回串返回串 S 的第的第 pos 个字符起长个字符起长 度为度为 len 的子串。的子串。例如：例如： SubString( sub, commander , 4, 3) 求得求得 sub = man ;二、串的抽象数据类型定义二、串的抽象数据类型定义Index (S, T, pos) /求子串序号求子串序号初始初始条件：条件：串串S和和T存在，存在，T是非空串，是非空串， 1posStrLength(S)。操作结果：操作结果： 若主串

4、若主串 S 中存在和串中存在和串 T 值相同的子串值相同的子串, 则返则返回回T在主串在主串 S 中第中第pos个字符之后第一次出现的位置个字符之后第一次出现的位置;否则函数值为否则函数值为0。 假设假设 S = abcaabcaaabc , T = bca Index(S, T, 1) = 2;Index(S, T, 3) = 6;Index(S, T, 8) = 0;二、串的抽象数据类型定义二、串的抽象数据类型定义Replace (&S, T, V) 初始条件：初始条件：串串S, T和和 V 均已存在，且均已存在，且 T 是非空串。是非空串。 操作结果：操作结果：用用V替换主串替换主串S中

5、出现的所有与串中出现的所有与串T相等的相等的 不重叠的子串不重叠的子串。假设假设 S = abcaabcaaabca , T = bca 若若 V = x , 则经置换后得到则经置换后得到 S = axaxaax 若若 V = bc , 则经置换后得到则经置换后得到 S = abcabcaabc 二、串的抽象数据类型定义二、串的抽象数据类型定义StrInsert (&S, pos, T)初始条件：初始条件：串串S和和T存在，存在，1posStrLength(S)1。操作结果：操作结果：在串在串S的第的第pos个字符上插入串个字符上插入串T。例如：例如：S = chater，T = rac， 则

6、执行 StrInsert(S, 4, T)之后得到 S = character二、串的抽象数据类型定义二、串的抽象数据类型定义StrDelete (&S, pos, len)初始条件：初始条件：串串S存在存在1posStrLength(S)-len+1。操作结果：操作结果：从串从串S中删除第中删除第pos个字符起长度为个字符起长度为len的子串的子串。 ClearString (&S) 初始条件：初始条件：串串S存在。存在。 操作结果：操作结果：将将S清为空串。清为空串。end String二、串的抽象数据类型定义二、串的抽象数据类型定义对于串的基本操作集可以有不同的定义方法。对于串的基本操作

7、集可以有不同的定义方法。在上述抽象数据类型定义的在上述抽象数据类型定义的1313种操作中，种操作中，串赋值串赋值 StrAssignStrAssign、串比较串比较StrCompareStrCompare、求串长求串长StrLengthStrLength、 串联接串联接ConcatConcat以及求子串以及求子串SubStringSubString等五种操作构成串等五种操作构成串类型的最小操作子集，这些操作不可能利用其它串操类型的最小操作子集，这些操作不可能利用其它串操作来实现作来实现. .其它串操作可在这个最小操作子集上实现。其它串操作可在这个最小操作子集上实现。二、串的抽象数据类型定义二、

8、串的抽象数据类型定义int Index (String S, String T, int pos) 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 串串的逻辑结构和的逻辑结构和线性表线性表极为相似极为相似，区别区别仅在于仅在于串的数据对

9、象约束为字符集串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象；作为操作对象； 在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作作为操作对象。为操作对象。4.2串的表示和实现串的表示和实现v定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字符用一组地址连续的存储单元存储串值的字符序列序列v堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字符用一组地址连续的存储单元存储串值的字符序列序列, ,但存储空间是在程序

10、执行过程中动态分配但存储空间是在程序执行过程中动态分配而得。而得。v串的块链存储表示串的块链存储表示链式方式存储链式方式存储串有三种表示方法：串有三种表示方法：顺序顺序存储存储链式链式存储存储用一组连续的存储单元来存放串，直接使用定长的字符用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分数组来定义，数组的上界预先给出，故称为静态存储分配。配。例如例如： #define MAXSTRLEN 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SStringMAXSTRLEN1 ; SString S; /S是

11、一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。一、定长顺序存储一、定长顺序存储一般用一般用SString0SString0来存放串长信息；来存放串长信息；C C语言约定在串尾加结束符语言约定在串尾加结束符 0 0，但不计入，但不计入串长；串长；若字符串超过若字符串超过MAXSTRLEN, 则自动截断则自动截断 （因为静态数组存不进去）。（因为静态数组存不进去）。 算法描述算法描述q两串连接两串连接Concat(&T,S1,S2) Concat(&T,S1,S2) ( (算法算法4.2)4.2)用用T T返回返回S1S1和和S2S2连接成的新串连接成的新串. . Status Co

12、ncat(SString &T, SString S1, SString S2,) / 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; / Concat串的联接算法中需分三种情况处理： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断 else if (S10 MAXSTRLEN / 截断 else / 截断(仅取S1)T1.S10 = S11.S10;TS10+1.MAXSTR

13、LEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; uncut = FALSE; q求子串求子串 SubString(&Sub,S,pos,len)SubString(&Sub,S,pos,len)将串将串S S中从第中从第pospos个字符开始长度为个字符开始长度为lenlen的字符序列的字符序列复制到串复制到串SubSub中中（注：串（注：串SubSub的预留长度与的预留长度与S S一样）一样）求子串函数求子串函数SubString(& &Sub, S, pos, len)

14、Status SubStringSubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos和和len不合法则告警不合法则告警 Sub1len=Spospos+len-1os+len-1; Sub0=len; return OK;s = a1 , a2 , . , anposlen讨论：讨论：想存放想存放超长超长字符串怎么办？字符串怎么办？静静态数组有缺陷！态数组有缺陷！改用改用动态动态分配的一维数组分配的一维数组“堆堆”！思路思路：利用利用mallocmallo

15、c函数合理预设串长空间。函数合理预设串长空间。特点特点： 若在操作中串值改变，还可以利用若在操作中串值改变，还可以利用reallocrealloc函数按新函数按新串长度串长度增加增加( (堆砌堆砌) )空间。空间。Typedef struct char * *chch; / 若非空串若非空串, ,按串长分配空间按串长分配空间; ; 否则否则 ch = NULLch = NULL int length; /串长度串长度HString仍用一组连续的存储单元来存放串，但存储空间是在程序执行仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。过程中动态分配而得。二、堆分配存储二、

16、堆分配存储Status StrInsert ( HString &S, int pos, HString T ) /在串在串S的第的第pos个字符之前（包括尾部）插入串个字符之前（包括尾部）插入串Tif (posS.length+1) return ERROR; /pos不合法则告警不合法则告警 if(T.length) /只要串只要串T不空，就需要重新分配不空，就需要重新分配S空间，以便插入空间，以便插入T S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char)； for ( i=S.length-1; i=pos-1; -i )

17、 /为插入为插入T而腾出而腾出pos之后的位置之后的位置 S.chi+T.length = S.chi; /从从S的的pos位置起全部字符均后移位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入插入T，略略/0 S.length + = T.length; /刷新刷新S串长度串长度return OK;/StrInsert例：例：用用“堆堆”实现串插入操作实现串插入操作(教材教材P75) Status StrAssign(HString &T, char *chars)if (T.ch) free(T.ch);for (i=0, c

18、=chars; c; +i, +c); /求串求串chars的长度的长度if (!i) T.ch = NULL; T.length = 0;else T.ch = (char*)malloc(i*sizeof(char)； T.ch0.i-1 = chars0.i-1; T.length =i;return OK;/StrAssign附：堆分配存储表示附：堆分配存储表示直到终值为直到终值为“假假”停止，串尾特征是停止，串尾特征是/0NULL=0讨论：讨论：方法方法1 1存储密度为存储密度为 ；方法；方法2 2存储密度为存储密度为 ；若数据元素很多，用方法若数据元素很多，用方法2 2存储更优存储

19、更优称为块链结构称为块链结构三、链式存储：三、链式存储：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。方法方法1 1：链表结点（数据域）大小取链表结点（数据域）大小取1 1方法方法2 2：链表结点（数据域）大小取链表结点（数据域）大小取n(n(例如例如n=4)n=4)1/51/51/21/2 A B C I NULLheadheadA B C D E F G H I # # # NULL#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE

20、 ; /结点中的数据域结点中的数据域 struct Chunk * next ; /结点中的指针域结点中的指针域Chunk; 块链类型定义：块链类型定义：typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head; /头指针头指针 Chunk *tail; /尾指针尾指针 int curLen; /串的当前长度串的当前长度 LString; 算法目的：确定主串中所含子串第一次出现的位置算法目的：确定主串中所含子串第一次出现的位置（定位）（定位） 即如何实现即如何实现 Index(S,T,pos)函数函数4.3 串的模式匹配算法串的模式匹配算法模

21、式匹配模式匹配( (Pattern Matching) Pattern Matching) 即即子串定位运算子串定位运算（IndexIndex函数）函数）。注：注：S S称为被称为被匹配的串匹配的串，T T称为称为模式串模式串。若。若S S包含串包含串T T，则称则称“匹配成功匹配成功”, ,否则称否则称 “匹配不成功匹配不成功” 。 BF算法算法 (又称古典或经典的、朴素的、穷举又称古典或经典的、朴素的、穷举 的的) KMP算法算法（特点：速度快）（特点：速度快）算法算法种类：种类：S=a b a b c a b c a c b a bT=T=a b c a cpos=54.3 串的模式匹配

22、算法串的模式匹配算法返回值为返回值为6 设计思想：设计思想： 将主串的第将主串的第pospos个字符和模式串的第个字符和模式串的第1 1个字符比较，个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串的下一字符起，重新与模式的，从主串的下一字符起，重新与模式的第第 一个字符比较。一个字符比较。 直到主串的一个连续子串字符序列与模式直到主串的一个连续子串字符序列与模式串串相相等等 。返回值为。返回值为S S中与中与T T匹配的子匹配的子串中串中第一个字符第一个字符的序号的序号，即匹配成功。否则，匹配失败，返回值，即匹配成功。否则，匹配失败，返回值 0

23、.0 .一一. .BFBF算法算法 BFBF算法的实现算法的实现S=a b a b c a b c a c b a bT=T=a b c a cpos=5Int Index(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return 0;/Index相当于子串向右滑动一个字符位置相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。配的首个字符位置。i i

24、j j讨论：讨论：BFBF匹配算法最坏的情况下需要比较字符的总次数匹配算法最坏的情况下需要比较字符的总次数例：例：S=aaaaaaab , T=aab , pos=1 n=8,m=3最最坏坏情况是：主串前面情况是：主串前面8-38-3个位置都部分匹配到子个位置都部分匹配到子串的最后一位，即这串的最后一位，即这5 5位比较了位比较了3 3次，最后次，最后3 3位也各位也各比较了一次，还要加上比较了一次，还要加上3 3！比较字符的次数为：比较字符的次数为：5*3+3=18次次若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配匹配算法最坏的情况下需要比较字符的总

25、次数为算法最坏的情况下需要比较字符的总次数为(n-m+1)*mO(n*m)最最坏坏情况是：主串前面情况是：主串前面n-mn-m个位置都部分匹配到子个位置都部分匹配到子串的最后一位，即这串的最后一位，即这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，还要加上位也各比较了一次，还要加上m m！BFBF匹配算法的最坏时间复杂度匹配算法的最坏时间复杂度但一般情况下但一般情况下BFBF算法的时间复杂度为算法的时间复杂度为O(n+m)二、二、KMP算法算法（特点：速度快）（特点：速度快） KMP算法设计思想算法设计思想 KMP算法的推导过程算法的推导过程 KMP算法

26、的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） KMP算法算法的的时间复杂度时间复杂度主串主串S S的指针的指针i i不必回溯不必回溯！模式！模式T T的指针的指针k k向前滑动。可向前滑动。可提速到提速到O(n+m)O(n+m)！ KMPKMP算法设计思想算法设计思想S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i

27、=6i=6需要解决的问题：需要解决的问题： 如何由如何由“记忆记忆”结果计算出主串结果计算出主串S S第第i i个字符应该与个字符应该与模式模式T T中哪个字符再比较？即确定模式中哪个字符再比较？即确定模式T T中的新比较起中的新比较起点点k k. .i ii ii ik kk k a b aa b c KMP算法的推导过程算法的推导过程解释解释: 设主串为设主串为S=S1S2 Sn, 模式串为模式串为T=T1T2TmS1S2 Si-j+1Si-j+2Si-k+1Si-j+kSi-j+k+1Si-2 Si-1 Si Si+1T1 T2 Tj-k+1 Tk Tk+1 Tj-2 Tj-1 Tj=

28、= = = = = = T1 Tk-(j-k) Tk-(j-k-1) Tk-2 Tk-1TkS1S2 Si-j+1Si-j+2Si-k+1Si-j+kSi-j+k+1. Si-2 Si-1 Si Si+1= = = = = 所以T1T2 Tk-1 = Tj-k+1Tj-k+2 Tj-1 Si与与 Tj 处失配处失配设设T 向前滑向前滑动动j-k, Si与与Tk 比较比较 KMP算法的推导过程算法的推导过程(续）：续）：根据模式串根据模式串T的规律：的规律： T1Tk-1=Tj-(k-1)j-(k-1) Tj-1和已知的当前失配位置和已知的当前失配位置j ，可以归纳出计算新起点可以归纳出计算新起

29、点 k的表达式。的表达式。令令 next j =k，则则nextj表明当第表明当第j个字符与主串中相个字符与主串中相应字符应字符“失配失配”时，在模式中需要重新和主串中字符时，在模式中需要重新和主串中字符进行比较的字符的位置。进行比较的字符的位置。next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-11 其他情况其他情况例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :next j 0 当当j1时时max k |1kj 且且T1Tk-

30、1=Tj-(k-1)j-(k-1) Tj-11 其他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：j=1时时, next j 0；因为属于因为属于“j=1”;刚才已归纳：刚才已归纳：j=3时时, k=2，只需查看只需查看T1=T2 2；因不满足，属于其他情况因不满足，属于其他情况j=4时时, k=2,3，k=2时查看时查看T1=T3 3 ,k=3时查看时查看T1T2= T2 T3 3 j=5时时, k=2,3,4， k=2时查看时查看T1=T4 4 (满足满足) k=3时查看时查看 T1T2=T3 3T4(不满足不满足) k=4时查看时查看T1T2T3 3=T2 T3 3T4 j=2时

31、时, next j 1；因为属于因为属于“其他情况其他情况”；例：例： 模模 式式 串串 T： a b a b a a c a 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :0 1 1 2 3 4 1 1讨论：讨论：j=1时时, next j 0；因为属于因为属于“j=1”;j=2时时, next j 1；因为属于因为属于“其他情况其他情况”；j=3时时, k=2，只需查看只需查看T1=T2 2；属于其他情况属于其他情况j=4时时, k=2,3，要查看要查看T1=T3 3, T1 T2=T2T3j=5时时, k=2,3,4，要查看要查看T1=T4 4

32、, ,T1 T2=T3T4,T1T2T3 =T2T3T4 j=6时时, k=2,3,4,5，要查看要查看T1=T5 、T1T2=T4 4T5 、 T1T2T3=T3T4T5, T1T2T3T4=T2T3T4T5计算计算nextj的算法如下的算法如下void get_next(SString T, int &next ) /next函数值存入数组函数值存入数组nexti=1; j=0; next1=0; while(iT0 ) if(j= = 0|Ti= = Tj) +i;+j; nexti=j; else j=nextj; / get_next计算计算nextj的时间为的时间为O(m)演示程序

33、演示程序第一步，先把模式第一步，先把模式T所有可能的失配点所有可能的失配点j所对应的所对应的nextj计算出来；计算出来；第二步：执行定位函数第二步：执行定位函数index_kmp （与与BF算法模块非常相似）算法模块非常相似） KMPKMP算法的实现算法的实现即即Index( )操作的实现操作的实现 （见教材（见教材P82） Int Index_KMP(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return 0;/Index_

34、KMP 演示程序演示程序next函数的改进算法函数的改进算法前面定义的前面定义的nextnext函数在某些情况下还是有缺陷函数在某些情况下还是有缺陷例如：模式例如：模式aaaabaaaab与主串与主串aaabaaaabaaabaaaab匹配情况：匹配情况：模式：模式： a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4S: 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 ba a a a ba a a a ba a a a b当当P Pj j=P=Pnextjnextj时，则时，则如果如果S Si

35、i != P != Pj j，= S Si i != P!= Pnextjnextj因此，因此，S Si i 没有必要继续与没有必要继续与 P Pnextjnextj进行比较，进行比较，而应该直接和而应该直接和P Pnextjnextj的下一个字符的下一个字符P Pnextnextjnextnextj进行比较。进行比较。因此，在计算因此，在计算nextnext函数时，函数时，如果出现如果出现P Pj j=P=Pnextj nextj = = P Pk k则则nextj=nextk=nextnextjnextj=nextk=nextnextj此时效率不高的原因为：此时效率不高的原因为：模式：模式

36、： a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4nextvalj: 0 0 0 0 3S: 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 bNextval4=0,i+,j+例例void get_nextval(SString T, int &nextval ) /next函数修正值存入数组函数修正值存入数组nextvali=1; nextval1=0; j=0;while(iT0 ) if(j= = 0|Ti= =Tj ) +i;+j; if(Ti!=Tj ) nextvali=j; els

37、e nextvali=nextvalj; else j=nextvalj; / get_nextval KMPKMP算法的算法的时间复杂度时间复杂度 因为计算因为计算nextj的时间为的时间为O(m m);且且Index_KMPIndex_KMP函数（函数（没有回溯没有回溯）的匹配时间为）的匹配时间为O(n n);所以所以KMP算法的总时间耗费为：算法的总时间耗费为： O(n+mn+m)注意：注意：由于由于BF算法在一般情况下的时间复杂度也是算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。所以至今仍被采用。因为主串指针因为主串指针i i不必回溯，所以从外存输入文件不必回溯，所以

38、从外存输入文件时可以做到边读入边查找，时可以做到边读入边查找，“流式流式”作业！作业！本章小结本章小结熟悉串的五种基本操作的定义、并能利用这些基熟悉串的五种基本操作的定义、并能利用这些基本操作实现串的其它各种操作的方法；本操作实现串的其它各种操作的方法；熟练掌握在串的定长顺序存储结构上实现串的各熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；种操作的方法；理解串匹配的理解串匹配的KMPKMP算法，熟悉算法，熟悉nextnext函数的定义，掌函数的定义，掌握手工计算给定模式串的握手工计算给定模式串的nextnext函数值和改进的函数值和改进的nextnext函数值；函数值；理解串操作的应用方法和特点。理解串操作的应用方法和特点。 作作 业业书面作业书面作业: p28: 4.4题，4.7题，4.8题 p29: 4.23题上机作业上机作业:串基本操作的实现串基本操作的实现(p119) 52 结束语结束语