《2022年数据结构《串存储与基本操作的实现》分享 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构《串存储与基本操作的实现》分享 .pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第4 章、串存储与基本操作的实现1 / 18第四章串存储与基本操作的实现本章学习要点熟悉串的相关概念以及串与线性表的关系重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题“串” (string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。4.1 串的基本概念4.1.1 串的概念1串的定义串（string）是
2、由 n 个字符组成的有限序列，记为：S=”a0a1a2an-1” (n0)。其中，S 是串的名字， 字符序列 a0a1a2an-1是串的值， ai(0in-1)可以是字母、 数字或其他字符元素；由于在 C 语言系统中数组元素的下标是从0 开始的，所以串中所含元素的序号等于该元素的下标值加 1；串中所含字符的个数n 称为该串的 长度 ，长度为 0 的字符串称为空串（null string ） 。从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。例如 ：（1）A=“X123 ” (长度为 4 的串 ) （2）B=“12345654321 ” (长度为 11 的串 ) （3）C= “Bei
3、 Jing ” (长度为 8 的串 ) （4）D= “” (长度为 0 的空串 ) （5）E=“This is a string” (长度为 16 的串 ) （6）F=“ is a ” (长度为 6 的串 ) 2子串、主串和位置串中任意连续的字符组成的子序列称为该串的子串 ；相应地，包含子串的串称为主串 。串中的字符在串序列中的序号称为该字符在该串中的位置 ；子串的第一个字符在主串中的位置称为子串在主串中的 位置 。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n 的字符串具有n(n+1)/2 个子串。例如 ：在上例的 (6)中串 F 就是 (5)中
4、串 E 的子串，且子串F 在主串 E 中的位置是5。由于空格符也是一个字符，所以在串G= “abc defghne” 中包含有子串 “c def ”,而串“cdef ”不是串 G 的子串。串G 中第一个字符 ,e?的位置是 6，第二个字符 ,e?的位置是 11。3串的比较如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B 的比较过程是： 从前往后逐个比较对应位置上的字符的ASCII 码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：（1）两个串同时结束，表示A 等于 B；（2）A 中字符的 ASCII 码值大于B 中相应位置上字符的ASCII 码值或 B 串
5、结束，表示A 大于 B；（3）B 中字符的 ASCII 码值大于 A 中相应位置上字符的ASCII 码值或 A 串结束，表示A 小于 B。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日2 / 18例如：“ abc” =“ abc” , “ abc” “ abcdefg ” , “ 132” “ 123456 ”“ ABab” “ 2+3”。4空格串由一个或多个空格字符组成的串称为空格
6、串 ，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。4.1.2 串的基本操作尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。串的基本操作主要有：（ 1）StrAssign(&T,chars) 由字符串常量chars 生成字符串T 的操作。（ 2）StrCopy(&T,S) 由串 S 复制生成串T 的操作。（ 3）StrComp
7、are(S,T)若 S=T 返回 0，ST 返回正数， ST 返回负数。（ 4）StrLength(S) 返回串 S 的长度。（ 5）Concat(&T,S1,S2) 将串 S1 和 S2 连接起来生成串T 的操作。（ 6）SubString(&Sub,S,pos,len) 以串 S 中 pos 位置开始的len 个字符生成子串Sub 的操作。（ 7）Index(S,T,pos)返回子串T 在 S 中 pos个字符以后出现的位置。（ 8）Replace(&S,T,V) 将串 S 中所有不重叠子串T 替换为串V 的操作。（ 9）StrInsert(&S,pos,T) 在串 S 中第 pos 个字
8、符前插入串T 的操作。（ 10）StrDelete(&S,pos,len) 删除串 S 中第 pos个字符开始的len 个字符的操作。4.2 串的存储表示与实现既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。本章主要介绍串的3 种存储表示方法：（ 1）串的定长顺序存储表示法（ 2）串的堆分配存储表示法（ 3）串的块链式存储表示法4.2.1 串的定长顺序存储表示串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序列。在串的定长
9、顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。1定长顺序存储结构在 C+运行环境中，定长顺序结构定义为：#includeiostream.h #includestdio.h #define MAXLEN 255 / 定义串的最大长度为255typedef char SStringMAXLEN+1; /定义定长顺序存储类型SString名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - -
10、- - - - 数据结构第4 章、串存储与基本操作的实现3 / 182基本操作的C+程序实现（1）求串长度操作int Length_SS(SString S) 操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。int Length_SS(SString S) int i=0; while(Si)i+; return i; （2）串连接操作int Concat_SS(SString &T,SString S1,SString S2) 该操作将串S1、S2 连接生成串T，如果在连接过程中产生了截断（即 S1 的长度加上S2的长度大于 MAXLEN ）则返回 0，否则返回1。int C
11、oncat_SS(SString &T,SString S1,SString S2) int i,j,k; i=j=k=0; while(Ti+=S1j+); i-; while(iMAXLEN&(Ti=S2k) i+;k+; Ti=0; if(i=MAXLEN)&S2k) /*判断是否产生截断*/return(0); else return(1); （3）求子串操作int SubString_SS(SString &Sub,SString S,int pos,int len) 该操作截取串S 中从第 pos 个字符开始的连续的len 个字符生成子串Sub，如果位置 pos 和长度len 合理
12、则返回1，否则返回0. int SubString_SS(SString &Sub,SString S,int pos,int len) int i=0; if(pos1|lenLength_SS(S)+1) /*判断位置和长度是否合理*/return 0; while(ilen) Subi=Si+pos-1; i+; Subi=0; return 1; （4）初始化串操作int StrAssign_SS(SString &T,char *s) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
13、 - 第 3 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日4 / 18该操作用字符数组s，初始化定长顺序串T。如果不产生截断（长度合理）返回1，否则返回0。int StrAssign_SS(SString &T,char *s) int i=0; while(iT 则返回正数 ,如果 S=T 则返回 0,否则返回负数。int StrCompare_SS(SString S,SString T) int i=0; while(Si&Ti&(Si=Ti)i+; return (int)(Si-Ti); （7）串的替换操作int Replace_S
14、S(SString &S,int n,int m,SString T) 该操作将串S 中从第 n 个字符开始的连续的m 个字符替换成串T 中的字符，如果n 和 m 的选取合理则返回1，否则返回0。int Replace_SS(SString &S,int n,int m,SString T) SString S1; int len=Length_SS(T); int i=n-1,j=0,k=n+m-1; /*i 为开始替换位置，j 指向第一个替换字符，k 为剩余字符的开始位置*/if(n1|mLength_SS(S)+1|Length_SS(S)+len-mMAXLEN) /*判断位置是否合理
15、*/return(0); StrCopy_SS(S1,S); /* 将剩余部分复制到S1 中*/while(Si+=Tj+); /* 替换 S 中指定部分的字符*/i-; while(Si+=S1k+); /*将剩余部分复制到S 中*/return(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 数据结构第4 章、串存储与基本操作的实现5 / 18（8）主函数演示程序main() void main_SS() SStr
16、ing s1,s2,s3,sub,T; char str1100,str2100; int l1,l2,l3,pos,len,n; while(1) coutstr1 ”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。cin.getline(str2,sizeof(str2); StrAssign_SS(s1,str1); StrAssign_SS(s2,str2); l1=Length_SS(s1); l2=Length_SS(s2); cout(2) 求串长操作： ns1 的长度 =l1 ，s2的长度 =l2endl; n=StrCompare_SS(s1,s2); cout0
17、)couts2n; else if(n=0)couts1=s2n; else couts1s2n; Concat_SS(s3,s1,s2); cout(4) 串连接操作： ns1+s2=s3endl; l3=Length_SS(s3); couts1+s2 的长度 =l3endl; coutposlen; if(SubString_SS(sub,s3,pos,len) coutsub=subendl; else cout 位置不正确 n; coutposlen; cout 输入替换串 :n; cin.get(); cin.getline(str1,sizeof(str1); StrAssign
18、_SS(T,str1); if(Replace_SS(s3,pos,len,T) cout 替换结果为 :ns3=s3endl; else cout 替换不成功 !n; （程序运行过程略）3定长顺序存储的特点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日6 / 18（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；（2）在串删除和串插入操作时必须移动大量的字符；（
19、3）如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN ，则按约定采取“截尾”法处理，这将导致操作结果的不合理。4.2.2 串的堆分配存储表示由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。用堆分配存储表示串的方法是：在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。1串的堆分配存储结构在 C+运行环境中，堆分配存储结构定义为struct HString c
20、har *ch; / 串变量中字符数组的首地址int length; / 串的长度; 2在堆分配存储结构中串基本操作的C+程序实现（1）串的赋值操作void StrAssign_HS(HString &T,char str) 该操作由字符串常量str 生成一个 HString 型串 T。void StrAssign_HS(HString &T,char str) int len=0,i; while(strlen)len+; /计算串的长度T.length=len; if(!len)T.ch=NULL; / 对空串进行初始化else T.ch=new charlen+1; /在堆内存中分配相应
21、大小的存储空间for(i=0;T.chi=stri;i+); / 将数据从 str复制到 T.ch 中 （2）求串长的操作int Length_HS(HString S) 该操作返回串S 的长度，如果S 为空串则返回0。int Length_HS(HString S) return(S.length); （3）串的比较操作int StrComp_HS(HString S,HString T) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - -
22、 - - - 数据结构第4 章、串存储与基本操作的实现7 / 18该操作比较串S、T 的大小。int StrComp_HS(HString S,HString T) int i; for(i=0;iT.length&iS.length;i+) if(S.chi!=T.chi)break; return(int)(S.chi-T.chi); （4）串的清空操作void ClearString_HS(HString &S) 该操作清空串S 所占的堆空间。void ClearString_HS(HString &S) if(S.ch) deleteS.ch; S.ch=NULL; S.length=
23、0; （5）串的连接操作void Concat_HS(HString &T,HString S1,HString S2) 该操作计算串S1、S2 的连接串 T。void Concat_HS(HString &T,HString S1,HString S2) int i,j,k; T.length=S1.length+S2.length; i=j=k=0; T.ch=new charT.length+1; /分配链接串的储存空间while(T.chi+=S1.chj+); /将 S1 复制到 Ti-; while(T.chi+=S2.chk+); /将 S2连接到 T 的末尾 （6）求子串的算法
24、int SubString_HS(HString &Sub,HString S,int pos,int len) 该操作求串S中 pos 个字符开始的len 个字符组成的子串Sub， 如果位置合理返回1 否则返回0。int SubString_HS(HString &Sub,HString S,int pos,int len) int i; if(pos1|lenS.length+1) return(0); /如果位置不合理时返回0 值Sub.ch=new charlen+1; /动态分配子串的存储空间Sub.length=len; for(i=0;ilen;i+) Sub.chi=S.chp
25、os+i-1; /将子串复制到Sub中Sub.chi=0; Return(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日8 / 18（7）串插入操作的算法int StrInsert_HS(HString &S,int pos,HString H) 该操作在串S的第 pos 个字符前面插入字符串H，如果位置合理返回1，否则返回0。int StrInsert_HS(HString
26、 &S,int pos,HString H) int i,j,k; HString S1; if(posS.length+1) return 0; /位置不合理返回0 值S1.length=S.length+H.length; S1.ch=new charS1.length+1; /重新分配空间for(i=0;ipos-1;i+)S1.chi=S.chi; /取 S 中 pos 前段内容k=i; j=0; while(S1.chi+=H.chj+); /将 H 插入i-; while(S1.chi+=S.chk+); /取 S 中剩余的内容deleteS.ch; S=S1; return 1;
27、 （8）串替换操作的算法int Replace_HS(HString &S,int n,int m,HString T) 该操作将串S中第 n 个字符开始的m 个字符替换为串T，如果位置n 和字符数m 合理返回1 否则返回 0。int Replace_HS(HString &S,int n,int m,HString T) int i,j=0,k=n+m-1; HString S1; if(n1|mS.length+1)return(0); /长度或位置不合理S1.length=S.length+T.length-m; S1.ch=new charS1.length+1; /重新分配储存空间f
28、or(i=0;in-1;i+)S1.chi=S.chi; /取 S中前面的部分while(S1.chi+=T.chj+); /取 T 中的内容i-; while(S1.chi+=S.chk+); /取 S中剩余的部分deleteS.ch; S=S1; return(1); （9）主函数演示程序main() void main_HS() HString S1,S2,S,sub,V,T; SString ss1,ss2; int n,pos,len; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -
29、- - 第 8 页，共 18 页 - - - - - - - - - 数据结构第4 章、串存储与基本操作的实现9 / 18while(1) cout(1) 串初始化操作：n 输入两个字符串:n; cin.getline(ss1,sizeof(ss1); cin.getline(ss2,sizeof(ss2); StrAssign_HS(S1,ss1); StrAssign_HS(S2,ss2); cout(2) 求串长操作： nlen1=Length_HS(S1)endl; coutlen2=Length_HS(S2)endl; cout0) coutS2n; else if(n0)coutS
30、1S2n; else coutS1=S2n; Concat_HS(S,S1,S2); cout(4) 串连接操作： n:s1+s2=S.chendl; coutlength=Length_HS(S)endl; coutposlen; if(SubString_HS(sub,S,pos,len) coutsub=sub.chendl; else cout 位置不对 !n; coutpos;cin.get(); cout 输入要插入的子串V:n; cin.getline(ss1,sizeof(ss1); StrAssign_HS(V ,ss1); if(StrInsert_HS(S,pos,V)
31、cout 插入结果为s=S.chendl; else cout 位置不对 !n; coutposlen;cin.get(); cout 输入替换串T:n; cin.getline(ss1,sizeof(ss1); StrAssign_HS(T,ss1); if(Replace_HS(S,pos,len,T) cout 结果为s=S.chendl; else cout 位置不对 !n; 3堆分配存储表示的特点从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符串处理的应用程名师资料总结 - -
32、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日10 / 18序中常被采用。4.2.3 串的块链式存储表示1块链式存储的概念和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中的每个数据元素是一个字符，在用链表存储串值时，存在一个“结点大小”的问题，即每个结点最多可以存放多少个串中字符。对于串 “abcdefghijk ” ，如果采用每个结点存放一个字符的链表结构存储，其存储方式如图4.1(a)所
33、示； 如果采用每个结点存放三个字符的链表结构存储，其存储方式如图4.1(b)所示。由于串长不一定是结点大小的整数倍，所以在链表的最后一个结点不一定能被串中的字符占满，此时可补上若干个非串值字符 ,#? （或其它非串值字符） 。为了便于进行串的操作，当以链表存储串值时，除了头指针head 外还可以附设一个指向尾结点的指针 tail，并给出当前串的长度。称如此定义的串的存储结构为串的块链式存储结构。2块链式存储结构的表示在 C+运行环境中，可将块链式存储结构表示如下：#define CHUNKSIZE 80 / 定义每个结点的大小struct Chunk char chCHUNKSIZE; / 块
34、内的字符数组Chunk* next; / 指向下一个结点的指针; / 块结构的类型定义struct LString Chunk *head,*tail; / 串的头指针和尾指针int curlen; / 串的长度; / 块链式结构的类型定义在一般情况下，对串的操作只需要从前向后扫描即可，故对串值不必建立双向链表。设尾指针的目的是为了便于进行串的连接操作，在串连接时需要处理第一个串尾结点中的无效字符。3块链式存储的存储密度在串的块链式存储结构中，结点大小的选择很重要，它直接影响到串处理操作的效率。如果块选取的充分大时（可在一个块中存储串的所有字符）即为定长存储；如果每个块只放一个字符时即为链表存
35、储。为了便于研究串值的存储效率我们给出如下存储密度 的计算公式：实际分配的存储位串值所占的存储位串值的存储密度假定 next 指针变量占用4个字节， 每个字符占用1 个字节， 每个块中存放m 个字符， 那么串值的存储密度可以表示为=m/(m+4)。显然，存储密度小（比如每个块存放1 个字符时 =20% ） ，运算处理方便，但是存储占用量大；存储密度大（比如每个块存放80 个字符时 =20/21=95%） ，虽然存储占用量小，但是串值的运算处理（比如串的插入、删除、连接和替换等操作）不太方便。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
36、 - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 数据结构第4 章、串存储与基本操作的实现11 / 184块链式存储表示的特点在一般情况下，对以块链式存储表示的串进行操作时比较麻烦，比如在串中插入一个子串时可能需要分割结点，连接两个串时，如果第一个串的最后一个结点没有填满，还需要添加其它字符。总的来说，用链表作为串的存储方式是不太实用的。因此，串的块链式存储结构不如定长顺序存储和堆分配存储结构灵活，它占用存储空间大且操作复杂。4.3 串的模式匹配设 S 和 T 是两个给定的串，在串S 中寻找串值等于T 的子串的过程称为模式匹配
37、。其中，串S称为主串，串T 称为 模式 。如果在串S 中找到等于串T 的子串，则称 匹配成功 ；否则 匹配失败 。模式匹配是各种串处理系统中最重要的操作之一。模式匹配的操作记为Index(S,T,pos)，该函数的功能是，从串S 的第 pos 个字符开始的字符序列中查找值等于T 的子字符串。如果匹配成功，函数返回T 在 S 中第 pos 个字符以后的串值中第一次出现的开始位置；否则函数返回0值。显然这里隐含要求模式串T 不能为空串。4.3.1 串模式匹配的 BF 算法模式匹配最简单、最直观的算法是BF（Brute-Force,布鲁特 -福斯）算法。该算法在计算过程中，分别利用指针i 和指针 j
38、 指示主串S和模式 T 中当前正待比较的字符下标。算法的基本思想是：从主串 S 的第 pos 个字符起和模式T 的第一个字符比较，若相等，则继续逐个比较后面的字符；否则从主串 S 的下一个字符起再重新和模式T 的第一个字符开始逐个比较。以此类推，直至模式T 中的每个字符依次和主串S 中的一个连续的字符序列相等，则称匹配成功，函数返回T 的第一个字符在S 中的位置，否则匹配不成功，函数返回0 值。BF 算法表示的串查找函数int IndexBF_SS(SString S,SString T,int pos) 的 C+语言表示为：int IndexBF_SS(SString S,SString T
39、,int pos) / 求子串 T 在 S 中从 pos 个位置开始首次出现的位置int i=pos-1,j=0; if(iLength_SS(S)+1) return(0); while(Si+j&Tj) if(Si+j=Tj)j+; / 若字符相等，则继续比较后续字符else i+; j=0; / 若不相等，则重新开始新一轮比较 if(!Tj) return(i+1); / 若匹配成功，则返回T 首次出现的开始位置else return(0); / 若匹配不成功，则返回0 在一般情况下，BF 算法的时间复杂度为O(m+n) ，其中 m,n 分别为串S 和 T 的长度。但是在有些情况下，该算
40、法的效率很低。例如 ：S=“ aaaaaa ,aaaaab ” 共有 52 个,a?和 1 个,b?,T=“ aaaaaaab ” 共有 7 个,a? 和 1 个 ,b? 。由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针i 回溯到 i+1 的位置上， 并从模式的第一个字符开始重新比较。 从图 4.2 所示的匹配过程可以直观地算出，初始位置指针i 一共要回溯52-7=45次，总的比较次数为：8(45+1)=368 次。所以， 在最坏的情况下BF 算法的时间复杂度为O(mn)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
41、 - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日12 / 184.3.2 模式匹配的 KMP 算法模式匹配的另一种算法是由D.E.Knuth,J.H.Morris和 V.R.Pratt 同时发现的，称之为克努特-莫里斯-普拉特操作，简称KMP 算法，他是一种改进的模式匹配算法。此算法可使时间复杂度在O(m+n)的数量级上完成串的模式匹配操作。1模式的 next 数组模式匹配的KMP算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针 i,而是利用已经得到的“部分匹配”的
42、结果将模式T 向右“滑动”尽可能远的一段距离后，再继续进行比较。 为此需要引入一个有关模式串T 的整型数组next，其中第 j 个元素 nextj-1表示当模式串 T中的第 j 个字符与主串S中相应字符匹配失败时，在模式T 中需要重新和主串S中该字符进行比较的字符的下标值。next 数组定义为：其它情况且时当01-Tj,1,k-Tjk,-Tj1-Tk,T1,T0,0|max01jkkjjnext其中 nextj=k 表明，存在整数k 满足条件 0kj ，并且在模式T 中存在下列关系：“ T0T1 Tk-1 ” =“ Tj-kTj-k+1Tj-1 ” ，而对任意的整数k1(0kk1j) 都有：“
43、 T0T1 Tk1-1” “ Tj-k1Tj-k1+1Tj-1 ”例如 ：（1）模式 T=“ aaaaaaab ” 的 next 数组为 next=-1,0,1,2,3,4,5,6 （2）模式 T=“ abaabcac” 的 next 数组为 next=-1,0,0,1,1,2,0,1 （3）模式 T=“ ababcabcacbab” 的 next 数组为 next=-1,0,0,1,2,0,1,2,0,1,0,0,1 2next 数组的算法实现由定义可知， next0=-1,next1=0 ，假设现已求得next0,next1,nextj,那么可以采用以下递推的方法求出nextj+1。令 k
44、=nextj ，(1)如果 k=-1 或 Tj=Tk, 则转入步骤 (3) (2)取 k=nextk, 再重复操作 (1)、(2) (3)nextj+1=k+1; 计算 next 数组的算法void GetNext(char* T,int* next)用 C+语言实现如下void GetNext(char* T,int* next) int i=0,k=-1,n=0; next0=-1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - -
45、- - - 数据结构第4 章、串存储与基本操作的实现13 / 18while(Tn)n+; /计算模式串T 的长度 nwhile(in-1) if(k=-1|Ti=Tk) next+i=+k; else k=nextk; void main() char p650=ababcabcacbab,abaabcac,aaabcaab,abcabca,babbabab,abcaabbabcabaac; int next50,i,j; for(i=0;i6;i+) GetNext(pi,next); /计算模式串pi 的 next 数组for(j=0;pij;j+)coutnextj ; /显示输出 p
46、i 的 next 数组coutendl; 运行结果为：-1 0 0 1 2 0 1 2 0 1 0 0 1 -1 0 0 1 1 2 0 1 -1 0 1 2 0 0 1 2 -1 0 0 0 1 2 3 -1 0 0 1 1 2 3 2 -1 0 0 0 1 1 2 0 1 2 3 4 2 1 13KMP 模式匹配算法的实现KMP 模式匹配算法int Index_KMP(SString S,SString T,int pos)的 C+语言实现int Index_KMP(SString S,SString T,int pos) int i=pos-1,j=0; /i 指向 S 中第一个比较字符
47、，j 指向 T 中第一个字符int m=Length_SS(T), n=Length_SS(S); int *next=new intm; /定义模式 T 的 next 数组if(in+1) return 0; /位置不合理返回0 值GetNext(T,next); /计算 next while(in&j=m) return(i-m+1); /匹配成功else return(0); void main() SString S,T; int pos,n; coutS; coutT; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
48、名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 数据结构讲义2012 年 11月 11 日14 / 18coutpos; if(n=Index_KMP(S,T,pos) cout 首次匹配地址为:nendl; else cout 匹配不成功 !n; 【例 4.1】编写程序，分别计算模式匹配过程中，BF 算法和 KMP 算法的元素比较次数。（ 1）函数 int IndexBF(SString S,SString T,int& num)的功能是通过BF 算法返回串T 在 S中首次出现的位置，参数num 表示匹配过程中元素的比较次数。int
49、IndexBF(SString S,SString T,int& num) int i=0,j=0; num=0; if(iLength_SS(S) return(0); while(Si+j&Tj) num+; if(Si+j=Tj)j+; /若字符相等，则继续比较后续字符else i+; j=0; /若不相等，则重新开始新一轮比较 if(!Tj) return(i+1); /若匹配成功，则返回T 首次出现的开始位置else return(0); /若匹配不成功，则返回0 （ 2）函数 int IndexKMP(SString S,SString T,int& num)的功能是通过KMP 算
50、法返回串T 在 S 中首次出现的位置，参数num 表示匹配过程中字符元素的比较次数。int IndexKMP(SString S,SString T,int& num) int i=0,j=0; /i 指向 S 中第一个比较字符，j 指向 T 中第一个字符int m=Length_SS(T), n=Length_SS(S); int *next=new intm; /定义模式 T 的 next 数组if(in) return 0; /位置不合理返回0 值GetNext(T,next); /计算 nextnum=0; while(in&j=m) return(i-m+1); /匹配成功else