严蔚敏数据结构课件第四章

1、4.1 串的抽象数据类型的定义串的抽象数据类型的定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法4.1 串的抽象数据类型的定义如下串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系数据关系：R1 | ai-1, ai D, i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对双引号相列，由一对双引号相括，如括，如: a string 基本操作基本操作： StrAssign (&T, chars) StrCopy (&T, S) Destro

2、yString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S) ADT String StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 cha

3、rs 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。 DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty (S)初始条件：串S存在。操作结果：若 S 为空串，则返回 true， 否则返回 false。 表示空串，空串的长度为零。 StrCompare (S, T)初始条件：初始条件：串 S 和 T 存在。操作结果：操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。例如：例如：StrCompare(data, state)

4、0 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如： Concate( T, man, kind) 求得 T = mankind SubString (&Sub, S, pos, len)初始条件：操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。串 S 存在，1posStrLength(S) 且 0lenStrLength(S)-pos+1。例

5、如：例如： SubString( sub, commander , 4, 3)子串为子串为“串串”中的一个字符子序列中的一个字符子序列求得 sub = man ; SubString( sub, commander , 1, 9)SubString( sub, commander , 9, 1)求得 sub = r 求得 sub = commander SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(student, 5, 0) = 起始位置和子串长度之间存在约

6、束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串 Index (S, T, pos)初始初始条件：条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果：操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置; 否则函数值为0。 假设 S = abcaabcaaabc , T = bca Index(S, T, 1) = 2;Index(S, T, 3) = 6;Index(S, T, 8) = 0; “子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串

7、中的位序位序。 Replace (&S, T, V) 初始条件：串S, T和 V 均已存在， 且 T 是非空串。 操作结果：用 V 替换主串 S 中出现 的所有与（模式串）T 相等的不重叠不重叠的子串。例如：假设 S = abcaabcaaabca, T = bca 若 V = x , 则经置换后得到 S = axaxaax 若 V = bc , 则经置换后得到 S = abcabcaabcbca bca bca StrInsert (&S, pos, T)初始条件：串S和T存在， 1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：

8、S = chater ，T = rac ， 则执行 StrInsert(S, 4, T) 之后得到 S = character StrDelete (&S, pos, len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。 ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串。 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准以该语言的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； st

9、rcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；例如：C语言函数库中提供下列串处理函数： 串赋值串赋值StrAssign、串复制、串复制Strcopy、 串比较串比较StrCompare、求串长、求串长StrLength、 串联接串联接Concat以及求子串以及求子串SubString 等六种操作构成串类型的最小操作子集等六种操作构成串类型的最小操作子集。在上述抽象数据类型定义的13种操作中，即：这些操作不可能利用其他串操作来实现， 反之，其他串操作

10、（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子 集上实现。 例如，可利用串比较、求串长和求子串等操作实现定位函数 Index( S, T, pos )。 StrCompare(SubString(S, i, StrLength(T), T ) S 串 T 串 T 串iposn-m+1算法的基本思想为：算法的基本思想为：? 0int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与 T相等的子串， / 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos 0) / if

11、 return 0; / S中不存在与T相等的子串 / Indexn = StrLength(S); m = StrLength(T); i = pos;while ( i = n-m+1) / whileSubString (sub, S, i, m);if (StrCompare(sub,T) != 0) +i ;else return i ;又如串的置换函数： S 串 T 串 V 串 V 串pospos subinews 串sub= i+mposn-pos+1void replace(String& S, String T, String V) while ( pos = n-m

12、+1 & i) i=Index(S, T, pos); if (i!=0) SubString(sub, S, pos, i-pos); / 不置换子串 Concat(news, news, sub, V); pos = i+m; /if/whileSubString(sub, S, pos, n-pos+1); / 剩余串Concat( S, news, sub );n=StrLength(S); m=StrLength(T); pos = 1;StrAssign(news, NullStr); i=1; 串的逻辑结构和线性表极为相似，区别区别仅在于串的数据对象约束为字符集。 串的基

13、本操作和线性表有很大差别。串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。 在程序设计语言中，串只是 作为输入或输出的常量出现，则只 需存储此串的串值，即字符序列即 可。但在多数非数值处理的程序中， 串也以变量的形式出现。4.2 串的表示和实现串的表示和实现一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示 #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned c

14、har Sstring MAXSTRLEN + 1; / 0号单元存放串的长度一、串的定长顺序存储表示一、串的定长顺序存储表示 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列字符序列的复制的复制” 串串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截截断断” 特点特点: Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; / Concat例如：例如：串的联接算法中需分三种情况

15、处理： 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)T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FAL

16、SE; typedef struct char *ch; / 若是非空串，则按串实用长度分配 /存储区，否则 ch 为NULL int length; / 串长度 HString;二、串的堆分配存储表示二、串的堆分配存储表示 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。 这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制。Status Concat(HString

17、 &T, HString S1, HString S2) / 用T返回由S1和S2联接而成的新串 if (T.ch) delete(T.ch); / 释放旧空间 if (!(T.ch =new charS1.length+S2.length) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat Status SubString

18、(HString &Sub, HString S, int pos, int len) / 用Sub返回串S的第pos个字符起长度为len的子串 if (pos S.length | len S.length-pos+1) return ERROR; if (Sub.ch) delete (Sub.ch); / 释放旧空间 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 return OK; / SubString if(!(Sub.ch = new charlen) return ERROR; Sub.ch0.le

19、n-1 = S.chpos-1.pos+len-2; Sub.length = len;void StrInsert (Hstring& S, int pos, HString T) / 1posStrLength(S)1。在串 S 的 / 第 pos 个字符之前插入串 T slen=S.length; tlen=T.length; / 取得S和T的串长 if (pos slen+1) return; / 插入位置不合法 S1.ch = new charslen ; / S1作为辅助串 S1.ch0.slen-1 = S.ch0.slen-1; / 暂存 S if (tlen0) /

20、T 非空，则为S重新分配空间并插入T / StrInsert _HSq S.ch = new charslen + tlen ; / 为 S 重新分配空间for ( i=0, k=0; ipos-1; i+) S.chk+ = S1.chi; / 保留插入位置之前的子串for ( i=0; itlen; i+) S.chk+ = T.chi; / 插入Tfor ( i=pos; i 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i mijijijinj T 串一、简单算法一、简单算法int Index(SString S, SS

21、tring T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 / 其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index 先比较模式串的第一个第一个字符， 再比较模式串的最后一个最后一个字符， 最后比较模式串中从第二个 到第 n-1 个字符。二、首首尾尾匹配算法匹配算法int Index_FL(SString S, SString T, int pos) sLength = S0; tLength

22、 = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; 检查中间字符的匹配情况检查中间字符的匹配情况 k = 1; j = 2; while ( j tLength & Si+k = Tj) +k; +j; if ( j = tLength ) r

23、eturn i; else +i; / 重新开始下一次的匹配检测KMP算法的时间复杂度可以达到O(m+n) 当 Si Tj 时，假设此时应与模式中第k（kj）个字符继续比较，则模式中前k-1个字符的子串必须满足：T1.k-1=Si-k+1.i-1 已经得到的结果: Si-j+1.i-1 = T1.j-1 在上式中取任意多个从右到左的子串仍然相等，取k-1个，有 Si-k+1.i-1 = Tj-k+1.j-1 则有 Tj-k+1.j-1 = T1.k-1三、三、KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法能向右滑动多远？ t1 tk tj tm s

24、1 si sn s1 si sn p1 tk tj tm 显然应有：sik+1si1 = t1tk1。 s t1 而由前次的比较应有：sik+1si1 = tjk+1 tj1。 于是得到这样的结果：t1tk1 = tjk+1 tj1。一个模式的next(j) j ： 1 2 3 4 5 6 7 8 9 模式 ： a b a a b a a a b nextj ：初始化：next1 = 0。0 没有相应的k，next(j)为1。1 1 k = 2，下次从第二个元素开始比较。2 2 依次以此类推可得其余元素的next(j)。3 4 52滑动不会造成遗漏 引理引理 1： 正文S和模式P比较时，若si

25、pj，则 S没有以sik0+1(nextjk01时，假设结论不成立，即存在这样的k0，那么有p1 p2 pk01= sik0+1sik0+2 si1。 从而有， p1 p2 pk01= pjk0+1pjk0+2 pj1 (7.3) 由假设有nextjk0i。 这与nextj是满足(7.3)式的最大值相矛盾；所以结论成立。定义：定义：模式串的next函数其它情况且时当 1 pppppjk1 |Maxk1j 0j1 - j1k- j1 -k21next int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos;

26、j = 1; while (i = S0 & j T0) return i-T0; / 匹配成功 else return 0; / Index_KMP这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串 求 next 函数值的过程是一个递推过程，分析如下:已知已知：next1 = 0；假设假设：nextj = k；又 Tj = Tk则则： nextj+1 = k+1若若： Tj Tk则则 需往前回朔，检查 Tj = T ？next(j)的计算 如何来计算模式P的next(j)? 首先，我们由定义可知next(1) = 0； 其次，显然有next(2) = 1； 现在我们来考虑n

27、ext(j+1)。 由next(j)=k可知模式中有：p1pk1= pjk+1pj1。 现在存在两种情况： pk = pj或者pk pj。 如果pk = pj，于是p1 pk1pk= pjk+1 pj1pj。从而有 next(j+1) = next(j) +1。next(j)的计算 如果pk pj，显然next(j+1) next(j)。 这实际是在将p1 pk1pk与pjk+1 pj1pj相匹配时，出现了pj与pk失佩。 p1 pk1 pk pjk+1 pjk+1 pj p1 pk1 pkpk pjn下一步拿p1 pk1pk中哪个元素和pj相比较呢？滑动多远？n向右滑动next(k)，即比较

28、pnext(k)和pj。n若这时有pnext(k) = pj，则next(j+1) = next(k) + 1；n若这时有pnext(k) pj，则再重复以上的做法，直至k = 1。next(j)的计算 int nextMaxStrLen; void get_next(SString P) j = 1; next1 = 0; k = 0； while(j = P0) if (k = 0Pk = Pj) +k; +j; nextj = k;/next(j+1)=k +1 else k = nextk; 初始化循环逐个计算元素j的next(j)若pk = pj，则next(j+1)=k +1。注意

29、此处的k, j都加了1。若pk pj，则比较pnext(k)和pj一个模式的next(j) j ： 1 2 3 4 5 6 7 8 9 模式 ： a b a a b a a a b nextj ：初始化：j = 1; next1 = 0; k = 0；10第一趟：j = 1; k = 0； k = 0 +k; +j; nextj = k;即，k = 1; j = 2; next(2) =1。 第二趟： j = 2; k = 1 P1 P2 k = nextk = 0 k = 0 +k; +j; nextj = k;即，k = 1; j = 3; next(3) =1。 1第三趟： j = 3; k = 1。 P1 = P3 +k; +j; nextj = k;即，k = 2; j = 4; next(4) =2。 2第四趟：j = 4; k = 2。 P2 P4 k = next2 = 1 P1 = P4 / k = 1 +k; +j; nextj = k;即，k = 2; j = 5; next(5) =2。 2第五趟：j = 5; k = 2。 P2 = P5 +k; +j; nextj = k;即，k = 3; j = 6; next(6) =3。 3第