数据结构-第四章课件.ppt

1、数据结构课程的内容数据结构课程的内容第第4章章 串（串（String）4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式4.1 4.1 串类型的定义串类型的定义串串即字符串，是由零个或多个字符组成的有限序列，是数据即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。元素为单个字符的特殊线性表。4.1 4.1 串类型的定义串类型的定义记为：记为： s = a1 , a2 , . , an (n0 ) 串名串名串值（用串值（用 括

2、起来）括起来）隐含结束符隐含结束符0 ，即即ASCII码码NULL说明：串是一种在数据元素的组成上具有一定约束条件的说明：串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符（字线性表，即要求组成线性表的所有数据元素都是字符（字母、数字或其他字符），所以，人们经常这样定义串：串母、数字或其他字符），所以，人们经常这样定义串：串是一个有穷字符序列。是一个有穷字符序列。4若干术语：若干术语：串长：串长：空白串：空白串：子串：子串：子串位置：子串位置：字符位置：字符位置：串相等：串相等：串中字符个数（串中字符个数（n0n0）. n=0 . n=0 时称为空串时称

3、为空串 。由一个或多个空格符组成的串。由一个或多个空格符组成的串。串串s s中任意个连续的字符序列叫中任意个连续的字符序列叫s s的子串的子串; S; S叫叫主串主串。子串的第一个字符的序号。子串的第一个字符的序号。字符在串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。串长度相等，且对应位置上字符相等。 注：空串是任意串的子串。任意串是其自身的子串。注：空串是任意串的子串。任意串是其自身的子串。5串常量和串变量串常量和串变量通常在程序中使用的串可分为：串常量和串变量。通常在程序中使用的串可分为：串常量和串变量。串变量：串变量和其它类型的变量一样，其值是可以改变的。串变量：串变量

4、和其它类型的变量一样，其值是可以改变的。 串常量：串常量和整常数、实常数一样，在程序中只能被引用串常量：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。但不能改变其值。即只能读不能写。 串常量由直接量来表示的：串常量由直接量来表示的： 【例】【例】Error（“overflow”）中）中“overflow”是直接量。是直接量。串常量命名串常量命名 有的语言允许对串常量命名，以使程序易读、易写。有的语言允许对串常量命名，以使程序易读、易写。 【例】【例】C+中，可定义串常量中，可定义串常量path const char path=dir/bin/appl; 练练1：

5、串是由串是由 字符组成的序列，一般记字符组成的序列，一般记为为 。练练2：现有以下现有以下4个字符串：个字符串：a =BEI b =JING c = BEIJING d = BEI JING问：问： 他们各自的长度？他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1练练3：空串和空白串有无区别？空串和空白串有无区别？答：答：有区别。空串有区别。空串(Null String)(Null String)是指长度为零的串；而空白是指长度为零的串；而空

6、白串串(Blank String),(Blank String),是指包含一个或多个空白字符是指包含一个或多个空白字符 ( (空空格键格键) )的字符串的字符串. .0个或多个个或多个S=a1a2anADT StingObjects: D=ai | aiCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: / 有有1313种之多种之多StrAssign(&T, chars) / 串赋值，生成值为串赋值，生成值为charschars的串的串T TStrCompare(S,T) / 串比较，若串比较，若ST

7、ST，返回值大于，返回值大于0 0 StrLength(S) / 求串长，即返回求串长，即返回S S的元素个数的元素个数 Concat(&T, S1, S2) / 串连接，用串连接，用T T返回返回S1S1S2S2的新串的新串SubString(&Sub, S, pos, len) / 求求S S中中pospos起长度为起长度为lenlen的子串的子串Index(S, T, pos) / 返回子串返回子串T T在在pospos之后的位置之后的位置 Replace(&S, T,V) / 用子串用子串V V替换子串替换子串T TADT Sting串的抽象数据类型定义（串的抽象数据类型定义（参见教材

8、参见教材P71）最最小小操操作作子子集集 设设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：。求：练习练习： StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)=Replace(s, STUDENT,q)=144STUDENTO30 （ s中没有中没有t！）！）I AM A WORKER再问：再问：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？4.2串的表示和实现串的表示和实

9、现 定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列 堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列, ,但存储空间是在程序执行过程中动态但存储空间是在程序执行过程中动态分配而得。分配而得。 串的块链存储表示串的块链存储表示链式方式存储链式方式存储首先强调：首先强调：串与线性表的运算有所不同，是以串与线性表的运算有所不同，是以“串的整体串的整体”作作为操作对象，例如查找某子串，在主串某位置上插入一个子串为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串

10、有三种机内表示方法：等。串有三种机内表示方法：顺序顺序存储存储链式链式存储存储定长顺序存储特点：定长顺序存储特点：用一组连续的存储单元来存放串，直用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的接使用定长的字符数组来定义，数组的上界预先给出上界预先给出，故，故称为静态存储分配称为静态存储分配。例如：例如：#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ;SString s; /s是一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。注：注：一般用一般用

11、SString0来存放串长信息；来存放串长信息；C语言约定在串尾加结束符语言约定在串尾加结束符 0，以利操作加速，但不计入串长；，以利操作加速，但不计入串长；若字符串超过若字符串超过Maxstrlen 则自动截断（因为静态数组存不则自动截断（因为静态数组存不 进去）。进去）。 讨论：想存放超长字符串怎么办？讨论：想存放超长字符串怎么办？静态数组有缺陷！静态数组有缺陷！实现方式：参见教材实现方式：参见教材P73编程两例，两串连接和编程两例，两串连接和求子串求子串改用动态分配的一维数组改用动态分配的一维数组“堆堆”！例：例：用顺序存储方式实现求子串函数用顺序存储方式实现求子串函数SubString

12、(&Sub, S, pos, len) Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法则告警不合法则告警 Sub1len=Spospos+len-1; Sub0=len; return OK;将串将串S S中从第中从第pospos个字符开始长度为个字符开始长度为lenlen的字符序列复的字符序列复制到串制到串SubSub中中（注：串（注：串SubSub的预留长度与的预留长度与S S一样）一样）s = a1 , a2 , . , a

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

14、得。但存储空间是在程序执行过程中动态分配而得。约定：约定：所有按堆存储的串，其关键信息放置在：所有按堆存储的串，其关键信息放置在：Status StrInsert ( HString &S, int pos, HString T ) /在串在串S的第的第pos个字符之前（包括尾部）插入串个字符之前（包括尾部）插入串Tif (posS.length+1) return ERROR; /pos不合法则告警不合法则告警 if(T.length) /只要串只要串T不空，就需要重新分配不空，就需要重新分配S空间，以便插入空间，以便插入T if (!（S.ch=(char*)realloc(S.ch, (

15、S.length+T.length)*sizeof(char) ) exit(OVERFLOW); for ( i=S.length-1; i=pos-1; -i ) /为插入为插入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例：例：用用“堆堆”实现串插入操作实现串插入操作

16、(教材教材P75) Status StrAssign(HString &T, char *chars)if (T.ch) free(T.ch);for (i=0, c=chars; c; +i, +c); /求串长度求串长度if (!i) T.ch = NULL; T.length = 0;else if (!(T.ch = (char*)malloc(i*sizeof(char) exit(OVERFLOW); T.ch0.i-1 = chars0.i-1; T.length =i;Return OK;/StrAssign指针变量指针变量C也可以自增！也可以自增！意即每次后移一个数据意即每次

17、后移一个数据单元。单元。附：堆分配存储表示附：堆分配存储表示直到终值为直到终值为“假假”停止，串尾特征是停止，串尾特征是0NULL=0显然，若显然，若数据元素很多，用法数据元素很多，用法2 2存储更优存储更优称为称为块链结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点（数据域）大小取链表结点（数据域）大小取1 1法法2 2：链表结点（数据域）大小取链表结点（数据域）大小取n(n(例如例如n=4)n=4) A B C I NULLheadheadA B C D E F G H I # # # NULL16headA B C

18、D E F G H I J # # NULLheadA B C X F G H I Y Z D E J # # # NULL虽然提高结点的大小使得存储密度增大，但是做插入、删除运虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。算时，可能会引起大量字符的移动，给运算带来不便。 #define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域结点中的数据域 struct Chunk * nex

19、t ; /结点中的指针域结点中的指针域Chunk; 块链类型定义：块链类型定义：例略例略typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head; /头指针头指针 Chunk *tail; /尾指针尾指针 int curLen; /结点个数结点个数 Lstring; 再次强调：再次强调：串与线性表的运算有所不同，是以串与线性表的运算有所不同，是以“串的串的整体整体”作为操作对象，例如查找某子串，在主串某位作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。置上插入一个子串等。这类操作中均涉及到这类操作中均涉及到定位问题定位问题，称为，

20、称为串的模式匹配串的模式匹配。它是串处理系统中最重要的操作之一。它是串处理系统中最重要的操作之一。194.3 串的模式匹配算法串的模式匹配算法模式匹配模式匹配(Pattern Matching) (Pattern Matching) 即即子串定位运算（子串定位运算（IndexIndex函数）函数）。算法目的：算法目的：确定主串中所含子串第一次出现的位置（定位）确定主串中所含子串第一次出现的位置（定位） 即如何实现即如何实现 Index(S,T,pos)函数（见教材函数（见教材P72）初始条件：初始条件：串串S S和和T T存在，存在，T T是非空串，是非空串，1posStrLength(s)1

21、posStrLength(s)操作结果：操作结果：若主串若主串S S中存在和串中存在和串T T值相同的子串，则返回它在主值相同的子串，则返回它在主串串S S中第中第pospos个字符之后第一次出现的位置；否则函数值为个字符之后第一次出现的位置；否则函数值为0 0。注：注：S S称为被匹配的串，称为被匹配的串，T T称为模式串。若称为模式串。若S S包含串包含串T T，则称，则称“匹配成功匹配成功”。否则称。否则称 “ “匹配不成功匹配不成功” ” 。 BF BF算法设计思想：算法设计思想： 将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较，个字符比较， 若若相等

22、相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串的下一字符（，从主串的下一字符（pos+1pos+1）起，重新与第一个）起，重新与第一个字符比较。字符比较。 BF算法算法 （又称古典或经典的、朴素的、穷举的）（又称古典或经典的、朴素的、穷举的） KMP算法算法（特点：速度快）（特点：速度快）算法算法种类：种类： 直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值。返回值为为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 .0

23、 .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 BF BF算法的实现算法的实现即即Index（）操作的实现（）操作的实现 （见教材（见教材P79） S=a b a b c a b c a c b a bT=T=a b c a cpos=5相当于子串向右滑动一个字符位置相当于子串向右滑动一个字

24、符位置匹配成功后指针仍要回溯！因为要返回的是被匹匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。配的首个字符位置。i ij j例例： S=S=ababcabcacbab，T=T=abcac，pos=1pos=1， 求：串求：串T T在串在串S S中第中第pospos个字符之后的位置。个字符之后的位置。 解：解：此题的此题的BF算法：算法：int IndexBF(Sstring S,Sstring T)i=1;j=1;while(i=s0 &jT0) return i-T0;else return 0;讨论：讨论：若若n n为主串长度，为主串长度，m m为子为子串长度，则串的串长度，

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

26、设计思想算法设计思想 KMP算法的推导过程算法的推导过程 KMPKMP算法的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） KMPKMP算法的算法的时间复杂度时间复杂度能否利用已经部分匹配的结果而加快模式串的滑动速度？能否利用已经部分匹配的结果而加快模式串的滑动速度？能！而且主串能！而且主串S S的指针的指针i i不必回溯！可提速到不必回溯！可提速到O(n+m)O(n+m)！例：例： KMP KMP算法设计思想：算法设计思想： ( (参见教材参见教材P80-84P80-84）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a

27、 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=6i=6需要讨论两个问题：需要讨论两个问题： 如何如何“记忆记忆”部分匹配结果？部分匹配结果？ 如何由如何由“记忆记忆”结果计算出主串结果计算出主串S S第第i i个字符应该与模式个字符应该与模式T T中中哪个字符再比较？即确定模式哪个字符再比较？即确定模式T T中的新比较起点中的新比较起点k k. .i ii ii ik kk k a b aa b c KMP算法的推导过程：算法的推导

28、过程：（见教材（见教材P81）抓住部分匹配结果的两个特征：抓住部分匹配结果的两个特征：两式联立可得：两式联立可得：T1Tk-1=Tj-(k-1)j-(k-1) Tj-1注意：注意：j 为当前已知的失配位置，我们的目标是计算新起点为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数仅剩一个未知数k，理论上已可解，且，理论上已可解，且k仅与模式串仅与模式串T有关！有关！ 则则S S前前i-1i-1i-(k-1)i-(k-1)位位T T的的j-1j-1j-(k-1)j-(k-1)位位 即即(4-3(4-3）式含义）式含义S=a b a b c a b c a c b a bT=T=a b

29、 c a ci ik k则则T T的的k-1k-11 1位位S S前前i-1i-1i-(k-1)i-(k-1)位位 即即(4-2(4-2）式含义）式含义i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符 处失配处失配设目前应与设目前应与T的第的第k字符开始比较字符开始比较 KMP算法的推导过程算法的推导过程(续）续）：根据模式串根据模式串T的规律：的规律： T1Tk-1=Tj-(k-1)j-(k-1) Tj-1和已知的和已知的当前失配位置当前失配位置j ，可以归纳出计算新起点，可以归纳出

30、计算新起点 k的表达式。的表达式。令令k = next j ，则，则next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况讨论：讨论： next j 有何意义？有何意义？ 一旦失配，应从模式串一旦失配，应从模式串T中第中第next j 个字符开始与个字符开始与S的失配的失配点点i 重新匹配重新匹配! next j 怎么求？怎么求？ 后面会举例（参见教材后面会举例（参见教材P81）第一步，先第一步，先把模式把模式T所有可能的失配点所有可能的失配点j所对应的所对应的nextj计算出来计算出来；第二步：执行定位函数第二步：

31、执行定位函数index_kmp （与（与BF算法模块非常相似）算法模块非常相似） KMP KMP算法的实现算法的实现即即Index( )操作的实现操作的实现 （见教材（见教材P82） Int Index_KMP(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return0;/Index_KMP例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位

32、nextj :next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：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 和和T1T2=T2 2 T3 3 j=5时时, k=2，3，4，要查看，要查看T1=T4 4 、T1T2=T3 3T4 和和 T1T2T3

33、 3=T2 2T3 3T4以此类推，可得后续以此类推，可得后续nextj值。值。讨论两个有关讨论两个有关next j 的问题：的问题： 怎样简捷计算怎样简捷计算nextj？ 可用递推法编程实现！可用递推法编程实现！（参见（参见P83简捷算法）简捷算法）计算计算nextj的时间为的时间为O(m)void get_next(SString T, int &next ) /next函数值存入数组函数值存入数组nexti=1; next1=0; j=0;while(iT0 ) if(j= = 0|Ti= = Tj)+i;+j;nexti=j;else j=nextj; / get_nextvoid g

34、et_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;else nextvali=nextvalj; else j=nextvalj; / get_nextval next j 是否完美无缺？是否完美无缺？答：未必，例如当答：未必，例如当S=a b a a a a b,T=a a a a b时时仍有多余动作仍有多余动作（参见（参见P84改进算法改进算法,

35、 称为称为nextval j ）i=1; j=0next1=0iT0j=0 | Ti=Tj+i; +j;nextj=j;j=nextj;ENDYYNN附：求解附：求解nextj 算法流程图算法流程图:例如：求例如：求abaabcac模式串的模式串的next函数函数next1=0next2=1 pnext1!= p1next3=1 pnext2!= p2next4=2 pnext3 = p3next5=2 pnext4!= p4 pnextnext4= p4next6=3 pnext5 = p5next7=1 pnext6!= p6 pnext3!=p6 pnext3!=p6next8=2 pn

36、ext7 = p7next函数的改进算法函数的改进算法前面定义的前面定义的next函数在某些情况下还是有缺陷函数在某些情况下还是有缺陷例如：模式例如：模式aaaab与主串与主串aaabaaaab匹配情况：匹配情况：模式：模式： 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 i != P != Pj j，= S S

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

38、此时效率不高的原因为： KMP KMP算法的算法的时间复杂度时间复杂度注意：注意：由于由于BF算法在一般情况下的时间复杂度也近似于算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍，所以至今仍被采用。被采用。而此时而此时KMPKMP的情况是：由于指针的情况是：由于指针i i无须回溯，比较次数仅为无须回溯，比较次数仅为n,n,即使加上计算即使加上计算nextjnextj时所用的比较次数时所用的比较次数m m，比较总次数也仅，比较总次数也仅为为n+m=n+m=O(nm)，大大快于大大快于BFBF算法。算法。回顾回顾BFBF的最恶劣情况：的最恶劣情况：S S与与T T之间存在大量的部分匹配，比较总之间存在大量的部分匹配，比较总次数为：次数为： (n-m+1)*mO(n*m)因为主串指针因为主串指针i i不必回溯，所以从外存输入文件时可以做不必回溯，所以从外存输入文件时可以做到边读入边查找，到边读入边查找，“流式流式”作业！作业！本章结束本章结束