数据结构课件-(4)[151页].ppt

1、数据结构 第4章串1数据结构电子教案第4章串 数据结构 第4章串2内容提要串（即字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。随着计算机的发展，串在文字编辑、信息检索、词法扫描、符号处理及定理证明等许多领域得到越来越广泛的应用。很多高级语言都具有较强的串处理功能，C语言更是如此。本章将简要介绍串的有关概念和术语、详细介绍串的顺序存储方法和链接存储方法、串的基本运算及其实现、串的模式匹配概念和实现算法，最后通过几个简单实例介绍串的应用。数据结构 第4章串3第4章 串习题习题4 4数据结构 第4章串44.1 串的基本概念串串（或字符串字符串String）是由零个或多个字符组成的有限序列

2、，一般记为：s=“a0a1an-1”（n0）其中，s称为串名串名；用双引号括起来的字符序列称为串值串值；ai（0in1）称为串元素，是构成串的基本单位，它可以是英文字母、数字或其他字符；n称为串的长度长度，它表示串中字符的个数。不包含任何字符的串称为空串空串（Empty String），空串的长度为零。数据结构 第4章串5为了确定串与常数、标识符的区别，通常用定界符将串括起来，一般使用双引号，但定界符不是串的内容，例如，“”“”“#$%&”“12345678”“this is a string”“PROGRAM”注意：注意：上面这6个字符串均用双引号作为定界符，其中：“”是包括一个空格的字符串

3、，通常将一个或多个空格组成的串称为空格串空格串（Blank String）。“”是不包括任何字符的空串。数据结构 第4章串6当且仅当两个串的长度相等且各对应位置上的字符都相等时，则称这两个串是相等的相等的。一个串中任意个连续的字符组成的子序列称为该串的子串子串，包含子串的串相应地称为该子串的主串主串。例如：“a”、“ab”、“abcd”等都是主串“abcde”的子串。通常，字符在序列中的序号称为该字符在串中的位置位置，子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的。例如，有两个字符串A和B分别为：A=“This is a string”B=“is”则A是主串，B是A的子串。B在A

4、中出现了两次，其中首次出现的位置为3，因此，称B在A中的序号（或位置）是3。数据结构 第4章串7为了对字符串进行处理，程序设计语言中常常需要使用两种串：一种为串常量串常量，另一种为串串变量变量。和整数常量、实数常量一样，在程序执行过程中，只能被引用而不能改变其值，常用直接量来表示。和其它类型的变量一样，它必须用名字来标识，在程序执行过程中，其值是可以改变的，但串变量与其它类型变量不同的是：不能使用赋值语句对其进行赋值运算。C语言规定，字符串存储时，每个字符在内存中占用一个字节，并用特殊字符0作为字符串的结束标记。因此，字符串在计算机中实际占用空间比串长多1个字符。数据结构 第4章串8数据结构

5、第4章串9串的存储方法与线性表的存储方法类似。串的存储结构与计算机系统的具体编址方式有着十分密切的关系，它对串的处理效率影响相当大。因此，要根据不同的情况，综合考虑各种因素，选择合适的方法来存储串。此外，由于串是由单个字符组成的，所以存储时有一些特殊的技巧。常用的串的存储方式有：顺序存储结构、链接存储结构和索引存储结构。为简单起见，本节仅介绍字符串的两种存储方法：顺序存储结构和链接存储结构。数据结构 第4章串10串的顺序存储结构的串简称为顺序串顺序串。顺序串是用一组地址连续的存储单元依次存放串中各个字符。但不同的计算机系统对串的顺序存储方式的实现可能不同。在按字节存取的计算机中，由于一个字符只

6、占用一个字节，因此，字符串中相邻的字符是顺序存放在相邻的字节中，这样既节约存储空间，处理又很方便。如图4.1所示。在按字存取的计算机中，串的顺序存储方式有两种：非紧缩存储方式和紧缩存储方式数据结构 第4章串11图4.1 字节编址方式下字符串s的顺序存储方式示意图【例4.1】设字符串s=“data structures”，请给出字节编址方式下字符串s的顺序存储结构。【解】图4.1是字节编址方式下字符串s的顺序存储结构示意图。数据结构 第4章串12 1 1、顺序串的非紧缩存储方式、顺序串的非紧缩存储方式非紧缩存储方式以字为单位顺序存储字符串的每个字符，即一个存储单元只存储一个字符。若字符串的长度为

7、n，则需要n个字的存储单元。如图4.2所示。【例4.2】假设某机器字的存储单元有4个字节，那么一个字可存放4个字符。若字符串s=“data structures”，请给出非紧缩存储方式下字符串s的顺序存储结构。【解】图4.2是字编址方式下，字符串s的非紧缩存储方式示意图，图中的阴影部分为空闲字节。数据结构 第4章串13图4.2 字编址方式下字符串s的非紧缩存储方式示意图 数据结构 第4章串14 2 2、顺序串的紧缩存储方式、顺序串的紧缩存储方式紧缩存储方式以字节为单位顺序存储字符串的每个字符，根据机器字的长度，紧缩存储方法尽可能地将多个字符存放在一个字中。假设某机器字的存储单元包含有4个字节，

8、则一个字可存放4个字符。若字符串的长度为n，则需要n/4个字的存储单元。这样，最后一个单元不一定都能完全利用上，可填充如空格之类的特殊字符或结束字符。如图4.3所示。数据结构 第4章串15【例4.3】假设计算机一个字的存储单元为4个字节，那么一个字可以存放4个字符。若字符串s=“data structures”，请给出紧缩存储方式下字符串s的顺序存储结构。【解】图4.3是字编址方式下，字符串s的紧缩存储方式示意图。图4.3 字编址方式下字符串s的紧缩存储方式示意图 数据结构 第4章串163 3、两种存储方式的分析和比较、两种存储方式的分析和比较串的紧缩存储方式可以节约存储空间，但处理单个字符不

9、太方便，运算效率较低，因为它需要花费较多时间分离同一个字中的字符；非紧缩存储方式浪费存储空间，但处理单个字符或一组连续的字符较为方便。总的来说，紧缩方式的优势较显著，所以多数计算机语言和软件都是采用紧缩方式存储字符串的。这两种方式的共同缺点是：插入一个字符和删除一个字符的运算很难，因为要移动其他元素，才能实现插入和删除运算。这也是顺序存储方法的共同缺点。数据结构 第4章串17 在字节编址方式和非紧缩格式的字编址中，顺序串可用高级语言的字符数组来实现：#define STRMAX 64 /*每个字符串的最大长度*/char sSTRMAX;/*用字符数组s存储串中所有字符*/在实际编程时，可在串

10、的结尾放置一个特定的、不会出现在串中的字符作为串的终止符，以表示串的结束。数据结构 第4章串18例如，C语言中以0作为串的终止符。若不设置终止符，可用一个整数slen表示字符串的实际长度，slen-1表示串中最后一个字符的存储位置。顺序串的类型定义与顺序表类似，可定义为：#define STRMAX 64typedef struct node char dataSTRMAX;int slen;seqstring;/*seqstring为顺序串的类型*/数据结构 第4章串194.2.2 4.2.2 串的链接存储结构串的链接存储结构 1一般的链接存储方法采用链接存储结构的串称为链串链串。把线性表的

11、链接存储方式应用到字符串的存储上就得到串的链接存储结构。链串与链表的差异仅在于其结点的数据域为字符类型。图4.4就是一个字符串链接存储结构的示意图。数据结构 第4章串20图图4.4 4.4 字符串的链接存储结构示意图字符串的链接存储结构示意图 数据结构 第4章串21便于字符的插入和删除运算。串的链接存储结构的缺点串的链接存储结构的缺点：由于每个字符都需要一个结点来存放，使得链表中的结点数相当多，存储空间的利用率很低。此外，访问链串的子串比访问顺序串的子串效率要低，它需要从头沿着链表依次扫描到希望的子串的开始元素，然后进一步沿着指针获得子串的后继元素。数据结构 第4章串22 2改进的链接存储方法

12、改进的链接存储方法是：让链表中每个结点存放多个字符。通常，将链表中每个结点数据域存储的字符个数称为结点的大小。假设每个结点存放m个字符，当结点大小m1（例如m=4）时，串的长度不一定正好是结点大小m的整数倍，链串最后一个结点的各个数据域不一定总能全被m个字符占满。此时，应在每个串的末尾还没有被占用的数据域里加上一个不属于字符集的特殊符号作为串的结束标志（例如0或），以表示串的结束，见图4.4（b）中最后一个结点。数据结构 第4章串23 例如，图4.4（a）所示是结点大小为1的链串，图4.4（b）所示则是结点大小为4的链串。【例4.4】假设字符串s1=“program”，s2=“data str

13、uctures”，若用结点大小为1的链串表示s1，用结点大小为4的链串表示s2，请分别给出s1和s2的链接存储结构。【解】图4.4所示是字符串s1和s2的链接存储结构示意图。图4.4（a）是链串s1，其结点大小m=1。若指针占用4个字节，字符数据域占用1个字节，则链串s1的存储密度为20%。图4.4（b）所示是结点大小m=4的链串s2，其存储密度达到了50%。数据结构 第4章串24显然，改进的串的链接存储方法是顺序存储和链接存储方法的折中方案。链串结点大小的选择与顺序串的格式选择类似。结点大小越大，存储密度越大。虽然提高结点的大小会使其存储密度增大，但是，进行插入和删除运算时，可能会引起大量的

14、字符移动，给运算带来不便，因此，它适用于串基本不变的情况下使用。例如，在图4.4（b）所示的字符串s2的第6个字符之后插入一个字符串“xxy”时，从s2第6个字符开始依次向后移动9个字符，其结果如图4.4（c）所示。结点大小越小（如结点大小为1时），运算处理方便，但其存储密度下降。为简单起见，我们常常把链串结点的大小规定为1。数据结构 第4章串25链串和单链表的差异仅在于其结点的数据域为字符类型。链串中每个结点有两个域：数据域data存放一个字符或一个字符串（对于结点大小不为1的链串），指针域next存放指向下一个结点的指针。一个链串则由头指针head惟一确定。数据结构 第4章串26对于结点大

15、小为1的链串，其类型定义如下：/*链串结点大小为1的结点类型*/typedef struct strnode char data;/*data为结点的数据域*/struct strnode *next;/*next为指针域*/linkstring;/*linkstring为链串类型*/linkstring *head;/*head是链串的头指针*/数据结构 第4章串27对于结点大小不为1的链串，其类型定义为：/*NODESIZE为链串结点的大小，由用户自定义*/#define NODESIZE 4typedef struct strnodem char dataNODESIZE;/*data为

16、结点数据域*/struct strnodem*next;/*next为指针域*/linkstringnode;/*linkstringnode是结点大小为m的链串类型*/数据结构 第4章串28数据结构 第4章串294.3.1 串的基本运算 假设假设s1=“a1a2an”，s2=“b1b2bm”，其中其中1mn。（1）串赋值strassign(s,t)：将一个串常量或串变量t赋给串变量s。（2）求串长strlen(s)：求s串的长度，即统计串中字符个数，函数返回一个整数。（3）串连接strcat(s1,s2)：将两个串首尾连接在一起形成一个新串，例如，s=strcat(s1,s2)，则s=“a1

17、a2anb1b2bm”。数据结构 第4章串30（4）串比较strcmp(s1,s2)：比较两个字符串的大小。若s1s2，则函数返回一个负数或1；若s1s2，则函数返回一个正数或1；若s1=s2，则函数返回0。（5）串插入串插入insert(s1,i,s2)：在串s1第i个字符位置之后插入字符串s2，例如，执行insert(s2,3,“THIS”)后，s2=“b1b2b3THISb4bm”。（6）串删除串删除delete(s,i,j)：从串s第i个字符开始，连续删除j个字符。若不足j个字符，则删除到s的最后一个字符。例如，s=“good lucky to you!”，执行delete(s,6,6

18、)后，s=“good to you！”。数据结构 第4章串31（7）串替换replace(s1,i,j,s2)：用串s2替换串s1中从第i个字符开始的连续j个字符，例如，执行replace(s1,2,3,“abc”)后，则串s1=“a1abca5a6an”。（8）串复制strcpy(s1,s2)：将s2的串值复制到串s1中。（9）取子串substr(s1,i,j,s2)：从串s1第i个字符开始，取连续j个字符构成一个新串s2，其中，1istrlen(s1)，1jstrlen(s1)i+1。例如，s=“abcdefgh”，则substr(s,3,4)=“cdef”。（10）子串定位index(s

19、1,s2,i)：其功能是求子串在主串中的位置。在主串中查找是否有与子串匹配的序列，若有，则给出子串在主串中首次出现的位置；若无，则返回0。数据结构 第4章串324.3.2 4.3.2 顺序串上基本运算的实现顺序串上基本运算的实现（1）顺序串的赋值函数S_strassign(s)：将从键盘输入的一串字符变量赋给串变量s。/*顺序串建立函数，从键盘输入字符串赋给顺序串变量s*/void S_strassign(s)seqstring*s;char c;int j=1;printf(nntt请输入一个字符串，以#作为结束:);scanf(%c,&c);while(c!=#&jdataj=c;j+;s

20、canf(%c,&c);s-dataj=0;s-slen=j-1;/*S_STRASSIGN*/数据结构 第4章串33（2）求顺序串的长度函数S_strlen(s)：求顺序串s的长度。/*求顺序串长度函数*/int S_strlen(s)seqstring*s;printf(nt顺序串长度length=%dn,s-slen);return(s-slen);/*返回顺序串的长度*/*S_STRLEN*/数据结构 第4章串34（3）顺序串的比较函数S_strcmp(s1,s2)：比较两个顺序串的大小。若s1=s2，则函数返回0；若s1s2，则函数返回正数；若s1s2，则函数返回负数。/*两个顺序串

21、比较函数，函数返回值为0、正数或负数*/int S_strcmp(s1,s2)seqstring*s1,*s2;int i=0,flag=1,m=0,n1,n2;n1=S_strlen(s1);n2=S_strlen(s2);while(flag=1)&(i=n1)&(idatai!=s2-datai)flag=0;if(flag=1)&(in1)&(in2)m=0;else m=s1-datai-s2-datai;return(m);/*S_STRCMP*/数据结构 第4章串35（4）顺序串的连接函数）顺序串的连接函数S_strcat(s1,s2)：将顺序串将顺序串s2连到连到s1之后形成一

22、个新串。之后形成一个新串。/*顺序串连接函数，将顺序串s2与s1连成一个新串*/int S_strcat(s1,s2)seqstring*s1,*s2;int i,j,k;i=S_strlen(s1);j=S_strlen(s2);if(i+j)MAX)return(1);for(k=1;kdatai+k=s2-datak;s1-datai+j+1=0;s1-slen=i+j;printf(nt两个顺序串连接后的新串长度length=%dn,s1-slen);return(0);/*S_STRCAT*/数据结构 第4章串36（5）顺序串的插入函数）顺序串的插入函数S_strinsert(s,i

23、,t)：将字符串将字符串t常量插到常量插到s串中，从串中，从s串第串第i个字符位置开始插入。个字符位置开始插入。/*顺序串的插入函数，从s串第i个位置开始插入t串*/int S_strinsert(s,i,t)seqstring*s,*t;int i;int ns,nt,k,j;ns=s-slen;nt=t-slen;if(ins+1|ns+ntMAX)return(1);k=ns+nt+1;for(j=ns+1;j=i;k-,j-)s-datak=s-dataj;for(k=1;kdata!=0;k+)s-datai+k-1=t-datak;s-slen=ns+nt;return(0);/*

24、S_STRINSERT*/数据结构 第4章串37（6）顺序串的删除函数）顺序串的删除函数S_strdelete(s,t)：从顺序从顺序串串s中删除与串中删除与串t相同的子串。相同的子串。/*顺序串删除函数，从顺序串s中删除与t串相同的子串*/int S_strdelete(s,t)seqstring*s,*t;int ns,nt,k=0,ks=0,kt=0,j,flag;ns=s-slen;nt=t-slen;if(ntns|ns0|nt0)return(1);while(k=ns)&(ktdataks+=t-datakt+)if(s-dataks!=t-datakt)flag=0;/*whi

25、le*/数据结构 第4章串38/*顺序串删除函数，从顺序串s中删除与t串相同的子串*/if(ktnt)&(k=ns)for(j=k;jdataj=s-dataj+nt;s-slen=ns-nt;s-datas-slen+1=0;return(0);/*IF*/*删除成功，函数返回成功信息0*/else return(1);/*删除失败，返回错误信息1*/*S_STRDELETE*/数据结构 第4章串39（7）求顺序串的子串函数）求顺序串的子串函数S_substr(s,i,k,t)：从顺从顺序串序串s中第中第i个字符开始连续取个字符开始连续取k个字符存放到顺序存个字符存放到顺序存储的子串储的子串

26、t中。中。/*从顺序串s第i个字符开始取k个子符放到顺序串t中*/int S_substr(s,i,k,t)seqstring*s,*t;int i,k;int m=s-slen;if(im)return(1);if(km+1)return(1);for(m=1;mdatam=s-datai+m-1;t-datam=0;t-slen=k;return(0);/*S_SUBSTR*/数据结构 第4章串404.3.3 4.3.3 链串上基本运算的实现链串上基本运算的实现（1）链串赋值函数L_strassign（s,t）：将一个字符串常量t赋给链串s，函数返回指向链串s的头指针。/*将一个串常量t赋

27、给链串s，返回链串s头指针*/linkstring*L_strassign(s,t)linkstring *s;char t;int k=0;linkstring *r,*p;s=(linkstring*)malloc(LEN);s-data=#;r=s;/*r为指向队尾指针*/while(tk!=0)/*将字符串常量t依次赋给链串s*/p=(linkstring*)malloc(LEN);p-data=tk+;r-next=p;r=p;r-next=NULL;return(s);/*L_STRASSIGN*/数据结构 第4章串41（2）求链串长度函数L_strlen(head)：求带头结点链

28、串head的长度。/*求带头结点链串head的长度函数*/int L_strlen(head)linkstring*head;linkstring*p;int i;p=head-next;/*指向链串head的首结点*/for(i=1;p!=NULL;i+)/*统计链串中结点的个数*/p=p-next;printf(nt该串的长度为%2d,i);return(i);/*函数返回带头结点链串head长度*/*L_STRLEN*/数据结构 第4章串42（3）链串比较函数L_strcmp(head1,head2)：将两个带头结点链串进行比较。若两串相等，则函数返回0；若前串大于后串，则函数返回1；若

29、前串小于后串，则返回1。/*将两个链串进行比较，函数返回1、0、或1-1*/int L_strcmp(head1,head2)linkstring*head1,*head2;linkstring*p1,*p2;int k=0;/*k为链串是否相等的标志*/p1=head1;/*指向head1的首结点*/p2=head2;/*指向head2的首结点*/while(p1!=NULL)&(p2!=NULL)&(k=0)p1=p1-next;p2=p2-next;数据结构 第4章串43/*将两个链串进行比较，函数返回-1、0、或1-2*/if(p1-data=p2-data)k=0;/*两串相等，k=

30、0*/if(p1-datap2-data)k=1;/*前串大于后串，k=1*/if(p1-datadata)k=-1;/*后串大于前串，k=-1*/if(p1=NULL&p2=NULL&k=0)k=0;/*两个链串相等，函数返回0*/if(p1-datap2-data)k=1;/*前串大于后串，函数返回1*/if(p1-datadata)k=-1;/*前串小于后串，函数返回-1*/return(k);/*L_STRCMP*/数据结构 第4章串44（4）两个链串的连接函数L_strcat(heads,headt)：利用原链串空间，将两个带头结点链串进行连接。要求将链串t连接到链串s后面，函数返回

31、连接后的新链串头指针。/*连接两个带头结点链串返回新链串头结点*/linkstring*L_strcat(heads,headt)linkstring*heads,*headt;linkstring*head,*sp;head=heads;if(heads=NULL)head=headt;else sp=head;while(sp-next!=NULL)sp=sp-next;sp-next=headt-next;return(head);/*L_STRCAT*/数据结构 第4章串45（5）链串的插入函数）链串的插入函数L_strinsert(head,i,s)：在在链串给定位置链串给定位置i处

32、插入字符串处插入字符串s。/*在链串head给定位置i处插入字符串s s5-1*/linkstring*L_strinsert(head,i,s)linkstring*head;int i;char s;linkstring*p,*r,*qr;int m=0,j=0;m=L_strlen(head)-i;if(head=NULL)|(mnext;数据结构 第4章串46/*在链串head给定位置i处插入字符串s5-2*/while(qr!=NULL&mnext;for(j=0;sj!=#;j+)p=(linkstring*)malloc(LEN);p-data=sj;r-next=p;r=p;r

33、-next=qr;return(head);/*返回插入后的新链串头指针*/*L_STRINSERT*/数据结构 第4章串47（6）链串的删除函数L_strdelete(head,i,n)：从链串给定位置i开始连续删n个字符。/*从链串给定位置i连续删除n个字符6-1*/linkstring *L_strdelete(head,i,n)linkstring *head;int i,n;linkstring*q,*r;int m=0;m=L_strlen(head)-i-n+1;if(head=NULL)|(mnext;数据结构 第4章串48 /*从链串给定位置i连续删除n个字符6-2*/m=1

34、;while(q!=NULL&mnext;/*q为r的后继结点*/m=0;r=q;/*r是指向第i个结点的指针*/while(q!=NULL&mnext;/*将q指针后移一个字符*r-next=q-next;/*q指针要删除的字符*/return(head);/*L_STRDELETE*/数据结构 第4章串49（7）求链串的子串函数）求链串的子串函数L_substr(s,i,j,t)：从从链串链串s中第中第i个字符开始，取连续个字符开始，取连续j个子符存放到链个子符存放到链串串t中。中。/*从链串s第i个字符开始取j个字符存到子串t中7-1*/int L_substr(s,i,j,t)link

35、string *s,*t;int i,j;linkstring*p,*q,*r;int m;if(i(m=L_strlen(s)return(1);if(jm+1)return(1);t=(linkstring*)malloc(LEN);t-data=#;t-next=NULL;p=s-next;/*从链串中查找子串的开始位置i*/数据结构 第4章串50/*从链串s第i个字符开始取j个字符存到子串t中7-2*/for(m=1;mnext;/*循环结束，p指向取子串始结点*/r=t;m=1;/*r指向子串的尾结点，m统计字符个数*/while(mdata=p-data;r-next=q;/*将子

36、串新结点连接到链串结尾处*/r=q;/*r指向子串新的尾结点*/p=p-next;/*将主串结点的指针向后移*/m+;/*WHILE*/r-next=NULL;return(0);/*L_SUBSTR*/数据结构 第4章串51数据结构 第4章串524.4 串的模式匹配运算 子 串 定 位 运 算子 串 定 位 运 算 称 为 串 的 模 式 匹 配模 式 匹 配（Pattern Matching）或串匹配串匹配（String Matching）运算，是串处理中最重要的运算之一，应用非常广泛。例如，在文本编辑程序中，我们经常要查找某个特定单词在文本中出现的位置。显然，解决该问题的有效算法能极大地

37、提高文本编辑程序的响应性能。数据结构 第4章串53假设有两个串s和t，且 s=“s0s1s2sn1”t=“t0t1t2tm1”式中，0mn（通常有mn）。子串定位就是要在主串s中找出一个与子串t相同的子串。通常，我们把主串s称为目标串目标串，把子串t称为模模式串式串，把从目标串s中查找t子串的定位过程称为串的“模式匹配模式匹配”。模式匹配有两种结果：若从主串s中找到模式为t的子串，则返回t子串在s中的起始位置。当s中有多个模式为t的子串时，通常只找出第一个子串的起始位置，这种情况称为匹配成功匹配成功，否则称为匹配失败匹配失败。数据结构 第4章串54模式匹配运算可用一个函数来实现，前面介绍的求子

38、串序号就是一个实现模式匹配运算的函数。串的匹配运算是一个比较复杂的串运算，许多人对此提出了多个效率各不相同的模式匹配算法。这里仅介绍BF模式匹配算法及基于BF算法的两种改进算法BM模式匹配算法和KMP模式匹配算法。数据结构 第4章串554.4.1 BF模式匹配算法1BF算法的基本思想一种最简单的模式匹配算法是布鲁特-福斯（Brute-Froce）算法，简称为朴素的朴素的模式匹配算法模式匹配算法或BF算法算法。数据结构 第4章串56：用模式串t=“t0t1t2tm1”中的字符依次与目标串s=“s0s1s2sn1”中的字符进行比较。从目标串s的第一个字符开始与模式串t的第一个字符进行比较，若相等，

39、则逐个比较后续字符；否则，从目标串s第二个字符开始重新与模式串t的第一个字符进行比较。其余类推，若模式串t的每个字符依次与目标串s中一个连续的字符序列相等，则称匹配成功匹配成功，函数返回模式串t中第一个字符在目标串s的位置；若将s的所有字符都检测完了，还找不到与t相同的子串，则称匹配失败匹配失败，函数返回0。数据结构 第4章串57【例4.5】假设目标串s=“abbaba”，模式串t=“aba”。若用指针I 指示目标串s当前待比较的字符位置，用指针j 指示模式串t当前待比较的字符位置，请给出BF算法的模式匹配过程。【解】图4.5是采用BF算法进行模式匹配的过程示意图。数据结构 第4章串58图图4

40、.5 4.5 BFBF算法的模式匹配过程示意图算法的模式匹配过程示意图 数据结构 第4章串59根据BF算法的匹配过程，我们可以推知以下两点。若前k1趟比较中未匹配成功，则第k（k1）趟匹配是从s中第k个字符sk1开始与t中第一个字符t0进行比较的。假设某一趟匹配有sitj，其中0in1，0jm1，ji，则应有si1=tj1，sij+1=t1，sij=t0。再由可知，下一趟比较是从目标串s的第sij+1个字符和模式串t的第一个字符t0开始进行比较的。数据结构 第4章串60因此，BF算法中某一次比较状态和下一次比较位置的一般性过程如图4.6所示。图图4.6 BF模式匹配的一般过程示意图模式匹配的一

41、般过程示意图 数据结构 第4章串612顺序串的BF模式匹配算法实现/*顺序串模式匹配运算求模式t在目标串s首次出现位置*/int S_bfindex(s,t)seqstring *s,*t;int i=0,j=0;/*模式t和目标串s初始位置为0*/int n=s-slen,m=t-slen;while(in)&(jdatai=t-dataj)/*两个字符相等 i+;j+;else /*匹配失败，指针i回溯，进行下趟匹配*/i=i-j+1;j=0;/*从模式t第一个字符开始进行下一趟匹配*/if(j=m)return(i-m);else return(-1);/*S_BFINDEX*/数据结构

42、 第4章串62 上述算法中，s-slen和t-slen分别表示串s和t的长度。当匹配成功时j=m，i值也相应地对应于tm1的后一个位置，故返回的序号是im而不是im+1。【算法分析算法分析】在最好的情况下，】在最好的情况下，每趟不成功的匹配都是在模式t的第一个字符与串s中相应的字符比较时就不相等。数据结构 第4章串63 假设s从第i个位置开始与t串匹配成功，那么在前面i1趟匹配中字符比较次数总共是i1次，第i趟匹配成功时，字符的比较次数为m次，因此，总的比较次数是i1+m。由于匹配成功时，s的开始位置只能是1nm+1。若对这nm+1个开始位置，匹配成功的概率为Pi且都是相等的，则在最好的情况下

43、，匹配成功的平均比较次数Cmin为：11min111(1)(1)12n mn miiinmCimimnm 故最好的情况下算法的平均时间复杂度是O(n+m)。数据结构 第4章串64在最坏的情况下，每趟匹配失败时都是在模式串t的最后一个字符与s中相应的字符比较后才不相等，新的一趟匹配开始前，指针i要回溯到im+2的位置上。在这种情况下，若第i趟匹配成功，在前面i1趟不成功的匹配中，每一趟匹配失败时都要比较m次，因此，字符比较次数总共是(i1)m次，第i趟匹配成功时也比较了m次，所以总共要比较mi次。数据结构 第4章串65若对这nm+1个开始位置，匹配成功的概率为Pi且都是相等的，则在最坏的情况下，

44、匹配成功的平均比较次数Cmax 为：若nm，则在最坏的情况下该算法的时间复杂度是O(mn)，即等于两串长度乘积的数量级。11max11(2)()12n mn miiimm nmCiminm数据结构 第4章串66例如，两个字符串例如，两个字符串s和和t分别为：分别为：s=“gggggggga”（n=9）t=“gggb”（m=4）由于t的前3个字符可在s中找到匹配，而t的第4个字符在s中找不到匹配，因此，每一趟匹配失败时都要比较m=4次，然后再将指针i移到s的第2个字符，结果是t的前3个字符在s中找到匹配，而第4个字符在s中找不到匹配。继续比较，比较的总趟数为nm+1=94+1=6，而每一趟都要比

45、较4次（m=4），因此，总的比较次数为4(94+1)=24。数据结构 第4章串673链串的BF模式匹配算法实现/*在链串上求模式串t在目标串s中首次出现的位置1*/linkstring linkstring *L_bfindex(s,t)L_bfindex(s,t)linkstring linkstring *s,s,*t;t;/*s,t s,t是带头结点的链串是带头结点的链串 */linkstring linkstring *first,first,*sp,sp,*tp;tp;if(s=NULL)|(t=NULL)if(s=NULL)|(t=NULL)return(NULL);return(

46、NULL);/*主串或模式为空，匹配失败返回主串或模式为空，匹配失败返回0 0*/first=s-next;first=s-next;/*first first是指向串是指向串s s起始位置的指针起始位置的指针 */sp=s-next;sp=s-next;tp=t-next;tp=t-next;/*串串s s和串和串t t从第一个结点开始进行比较从第一个结点开始进行比较*/数据结构 第4章串68/*在链串上求模式串t在目标串s中首次出现的位置1*/while(sp!=NULL)&(tp!=NULL)if(sp-data=tp-data)/*若两个结点的字符相等，则继续比较*/sp=sp-nex

47、t;tp=tp-next;else /*匹配失败，串s回溯，与串t从头开始比较*/first=first-next;sp=first;tp=t-next;if(tp=NULL)return(first);/*匹配成功，返回first所指子串开始位置*/else return(NULL);/*匹配失败，返回空指针NULL*/*L_BFINDEX*/【算法分析】该算法的时间复杂度是O(mn)，它与顺序串上BF算法的时间复杂度相同。数据结构 第4章串694.4.2 BM模式匹配算法 该算法对BF算法的匹配过程做了两点改进：其一是首先检查模式串t的首尾两个字符与主串s中对应的字符是否匹配，若这两对字符

48、匹配了再检查中间的字符；其二是在下一轮比较中，当主串s中余下的字符个数已经小于模式串t的长度时即停止运算，因为，在这种情况下匹配不可能成功。改进的BM算法利用主串中字符在模式串中出现的位置和长度等信息，减少每一趟的比较次数，从而大大提高算法的效率。数据结构 第4章串70 下面通过一个实例说明BM算法的匹配过程。【例例4.6】假设目标串AA=“dttabase”，模式串BB=“taba”。若利用BM算法进行模式匹配，请给出该算法在链接存储结构上进行模式匹配的过程示意图。【解解】图4.7是采用BM算法进行模式匹配时，其中某一趟模式匹配过程的示意图。在图4.7中，AA为目标串，BB为模式串。pAA和

49、pBB分别指向AA和BB中当前正在进行比较的字符，而qAA和qBB分别指向目标串AA和模式串BB的最后一个字符，k是指向目标串AA进行新一轮字符比较的起始位置指针。数据结构 第4章串71图图4.7 BM算法的模式匹配过程示意图算法的模式匹配过程示意图 数据结构 第4章串72 在第1趟匹配过程中，由于BB的第1个字符t与AA的第1个字符d不同，则停止检验，k和qAA分别向后移动一个结点，且使得pAA=k；在第2趟匹配中，因为BB的最后一个字符a与AA的第5个字符b不同（b是此趟匹配中AA的最后一个字符），则停止检验，k和qAA再分别后移一个结点，且使得pAA=k；在第3趟匹配中，这次BB的第1个

50、字符t与AA的第3个字符t相同，BB的最后一个字符a与AA的第6个字符a也相同，因此pBB和pAA分别逐结点后移检查其他字符是否匹配，这一趟各个字符均能匹配，故匹配成功，此时，k值指向AA的第3个结点。数据结构 第4章串73图4.7就是在第3趟匹配过程中，当pAA和pBB分别指向BB的第2个结点和AA的第4个结点时，二者字符进行比较的情况。显然，改进的模式匹配算法比BF算法运算速度要快。【算法分析】可以证明，改进的BM算法就平均情况来说会加快处理速度，但在输入数据最不利的情况下，其时间复杂度仍然是O(mn)。数据结构 第4章串74/*在链串上求模式BB在目标串AA中首次出现的位置-1*/lin