《数据结构》串》PPT课件.ppt

第4章 串,4.1 串及其操作 4.2 串的存储结构 4.3 串的基本运算实现 4.4 串的模式匹配运算 习题,在非数值处理的应用领域中，字符串的应用非常广泛。如编辑器(Edit、Word本质上是字符串处理)、信息检索(字符串比较)等。 实际上，编写数值计算程序的机会很有限。从发明计算机的思路来说，其目的是为了模拟人类的对信息的逻辑处理方法，而数值计算仅仅是一种逻辑思路的标准化。 现今我们使用的计算机的硬件结构主要反映数值计算的需要的，因此，在处理字符串数据时比处理整数和浮点数要复杂的多。而且，在不同类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据具体情况使用合适的存储结构。下面将讨论字符串的一些处理方法和字符串的几种不同的存储结构。,4.1 串及其操作,4.1.1 串的逻辑结构 定义：串(字符串)，是由零个或多个字符组成的有限序列。一般记作： s=a0a1an-2an-1 (n0) s是串的名。 双引号括起来是是串的值。 n为串的长度。 空串为零个字符，n=0。 子串为串中任意个连续的字符组成的子序列。 位置为字符在序列中的序号。为字符在串中的称作。 子串位置以子串的第一个字符在主串中的位置来表示。,举例：a=This is a string 串长=16 b=string串长=6 ，是a的子串，在a串的位置是10 c= 串长=2，的空格串，它不是a和b的子串。 串的集合定义： 设string=(D，R)是一个数据结构，其中 D=a0，a1，an-1 为字符元素的集合，i=0，n-1 ，并且n0。 R=|ai-1，aiD，i=1，2，n-1 R为上元素的关系集合 则称 string是一个字符串。字符串与线性表的区别是 它的数据对象为字符集。,4.1.2 串的基本运算 (1)赋值操作assign(s，t)。将t的值赋给s。 (2)串相等判断equal(s，t)函数。若s串与t串相等，则函数返回1，否则函数将返回0。 (3)串的联接操作concat(s，t)函数。将s串和t串联接成一个串，新生成的串是s串在前，而t串紧接s串的尾部。 例如，设a=data , b=structure,执行concat(a,b), 新生成的串是data structure。 串的联接不满足交换律:concat(s,t)!=concat(t,s) ; 串的联接满足结合律: concat(s1，concat(s2，s3)=concat(s1，s2，s3) 其运算结果是将这3个串的值依次首尾相接得到一个新串。 (4)求长度length(s)函数。其函数值为串s中字符的个数。,(5)求子串sub(s，start，len，t)。若 0startlength(s) 0lenlength(s)-start 则t中值为从串s中第start个字符起，长度为len的字符序列，并且函数返回值为1；否则函数返回值为0。 例如，s=data structure, sub(s，5，5，t), 则 t=struc。 (6)子串定位index(s,t)函数。若在主串s中存在和t相等的子串，则函数值为s中第一个这样的子串在主串s中的位置，否则函数值为-1。注意，在此t不能是个空串。例如，s=data structure， t=ru, 则index(s,t)=7。 (7)替换replace(s,t,v)。操作结果是以串v替换串s中出现的所有和非空子串t相同的不重叠子串。,4.2 串的存储结构,在程序执行的过程中，串的值可变。所以，与在程序出现的其他类型的变量一样，给要处理的串赋一个变量名，这样在对串进行操作时，可以通过变量名访其值。 串的存储结构有两种形式： 一种是将串设计成一种结构类型，串是字符型的数组，从串名可直接访问到串值，串值的存储分配是在编译时完成； 一种是串值的存储分配是在程序运行时完成，在串名和串值之间需要建立一个对照表，这个对照表称之为串名的存储映像。,4.2.1 顺序存储结构 用一组地址连续的存储单元存储串字符序列。唯一确定一个串，需要二个数据：串的起始地址，串的长度。在C语言中，对字符串处理两个要素是：数组名，结束标记符号，如图4.1所示,图4.1串的顺序存储结构,说明：ch是一个数组，存放串”data structure”，判断串的结束标志为字符0，在它前面的字符组成串。在这种表示方法中，访问子串方便，但插入、删除麻烦，需要大量移动字符。例如，要取子串 sub(s,5,4,t)，只要将数组ch5到ch8赋给t，便可实现求子串运算。,顺序存储结构又分为非紧缩格式和紧缩格式。 a.非紧缩格式 一个存储单元存放一个字符。若计算机的存储单元是按字编址，并且计算机字长大于八位二进制数，这样，在一个存储单元仅仅存放一个字符就浪费存储空间，但简化了对串的操作。例如，在一个字长为32位的计算机中，其一个存储单元为四个字节，但只存放一个字符(字符只占一个字节)，所以空间浪费，如图4.2所示。 b.紧缩格式 图4.3紧缩格式为了节省存储空间，也可以用紧缩方式，即在一个存储单元中存放多个字符，如图4.3所示，在一个存储单元中存放4个字符。显然，紧缩格式可以节省空间，但在对串值进行访问时需要花费较多时间分离同一存储单元中字符。,2.紧缩格式,图4 | 2 非紧缩格式,实际使用：如果计算机采用以字节为存储单元，一个字符占用一个存储单元(字节 )，此时既节省空间，处理又方便，C语言中字符串存储采用该方法，即图4.1所示，在后面讨论的串运算，都采用这种存储结构（字符数组）。,4.2.2 链式存储结构 用链表方式存储串值。由于串结构的特殊性，即结构中每一个数据元素是一个字符，用链表存储串值时，结点的大小需要讨论每个结点是存放一个字符，还是存放多个字符。例如，图4.4所示是结点大小分别为存放4个字符和1个字符。,(a)结点大小为4的链表,(b)结点大小为1的链表,图4.4结点大小不同的链表,4.2.3 堆存储结构 堆结构是一种动态存储结构。系统将一个容量很大的连续空间作为多个串值可共用的空间，每当建立一个新串时，若该串尚未赋值，它不占堆的存储空间；若要给该串赋值，首先，从未分配的堆空间中分配给该串值要求的空间，然后，将串值写入到分配的空间中；同样，当串的值无意义或串值被赋空串时，原串值所占用的空间要还给堆。所以，串的存储地址是动态分配的，一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名和串值之间要建立一个对照表。例如图4.5，所示为对照表和存放字符串的堆。,在图中假定，堆是一个字符数组，定义为： char storeMAX；/*存放串值的堆，MAX表示连续空间最大容量*/ int free；/* free为当前可分配空间起始地址的指针，起初值为0 */ 在堆中存放的三个串分别是： a=data b=structure c=book,4.3 串的基本运算实现,字符串是一种特殊的线性表，对它的操作不同于对线性表的处理，有自己独特的处理方法。在实际串的处理中，其存储结构为字符数组。下面讨论在这种存储方式下的串的运算。 定义： #define MAX 100 /* MAX为数组最大下标 */ char tMAX, sMAX; /* s,t为存放字符串的数组 */,(1) 算法4.1 求字符串长度函数length(s) 。 int length(char s) /* 求串s的长度 */ int i; for (i=0, si!=0；i+)； return(i)； ,(2)算法4.2求子串函数substr(s,start,len,t) int sub(char s,int start,int len,char t) /* 若0start=(n=length(s) return(0); if(lenn) return(0); for(i=0;ilen,i+) ti=sstart+i; sm+n= 0; /* 子串串结束标志 */ return(1); ,(3)算法4.3 两个字符串联接函数concat(s,t)。 int concat(char s,char t) /* 将t串联接在s串之后，成功函数返回1，否则函数返回值为0 */ int m,n,i; m=length(s); n=length(t); if(m+n=MAX) return(0); for(i=0;in;i+) sm+i=ti; ti=0; /* 联接得到串的结束标志 */ return(1); ,(4)算法4.4 串相等判断函数equal(s,t) int equal(char s,char t) /* 若s串与t串相等，则函数返回1，否则函数将返回0 */ int m,n,i; m=length(s); n=length(t); if(m!=n) return(0); for(i=0;im;i+) if(si!=ti) return(0); return(1); 另外，在C语言的库函数中已经包含了一些串操作函数，例如，赋值函数strcpy，判断函数strcmp，求长度函数strlen，求子串substr等，在程序设计中可以直接调用。,4.4 串的模式匹配运算,模式匹配：子串定位运算index(s,t,start)，即在主串s中寻找子串t的过程通常称作串的模式匹配(其中t称为模式)。 当匹配成功时: index(s,t,start)函数的值为t在s中的序号； 当匹配失败时， index(s,t,start)函数的返回值为-1。 为增加通用性，定义了一个start用来表示在s中开始匹配的字符位置。例如， s=abcdef，t=cde index(s，t，0)=2 s=abcdef，t=ab index(s，t，0)=0 s=abcdef，t=ad index(s，t，0)=-1,4.4.1 BF算法(Brute-Force) 算法的基本思想：在主串s中取从第i(i的初值为start)个字符起，并且长度和串t相等的子串和t比较，若相等，则求得函数值为i，否则i增1直至串s中不存在从i开始和t相等的子串为止，匹配失败，返回-1。 例如，主串s为ababcabcacbab 模式串t为abcac 匹配过程如图4.6所示,算法4.5 取子串进行比较的模式匹配算法。 int index(char s,char t,int start) int i,eq,m,n; char subchMAX; m=strlen(s); n=strlen(t); if(startm) return(-1); /*起始点+模式串长度主串长度 */ /*subch为在s中从i开始与t相同长度子串*/ i=start; eq=sub(s,i,n,subch) ； while(eq) if(strcmp(t,subch) break; /* i开始的子串与t相等 */ else i+; eq=sub(s,i,n,subch); /*从i开始的子串与t不相等*/ if(eq) return(i); else return(-1); ,有回溯的模式匹配算法：设置两个指针i和j分别指向主串s和模式串t中当前正待比较的字符位置。 算法的基本思想是： 初始 i=0；j=0; 做循环 若 si=tj 则 (继续逐个比较后续字符i+,j+) 否则,从主串的第二个字符起在重新和模式串比较(i返回到原位置加1，j返回0) . 直至模式串t的每一个字符依次和主串s的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。 该算法与前面所讨论的算法相同，只是前者是以每一个位置为始点，取出子串与t比较，而后是以每一个位置为出发点，与t比较，并且若匹配成功比较到t串结束，否则只需要比较到某一位置，即串s与串t的字符不相同。,例如主串s为ababcabcacbab，模式串t为abcac，匹配过程如图4.7所示,算法4.6 有回溯的模式匹配算法。 int index(char s,char t,int start) int i,j,m,n; m=length(s); n=length(t); if(startm) return(-1); i=start; j=0; while(itj，i回到原位置+1，j回到0 */ if(jn) return(i-n); else return(-1); ,上面所描述的算法中，若从某一个si开始与tj比较(j=0)，若si=tj，则i和j后移；若si!=tj，j回到原位置0，而i回到原位置加1。因为j已经从原来的位置向后移动了j次，所以i也向后移动了j次，故i的原位置为i-j，而原位置加1为i-j+1。同样，当匹配成功时，函数值返回i的原位置，这时j从0移动到串t的结束(j=n)，即j向后移动n次，同样，i也应向后移动了n次，所以，函数返回值是i-n。 这种有回溯的模式匹配算法在一些情况下，效率非常低，例如， s=aaaaaaab 串长为n t=aab 串长为m，并且nm 这样，每趟比较m次后匹配失败，i回到原位置加1，j返回到0，继续下一趟匹配,共计需要n-m趟。所以最坏情况下的时间复杂度为：O(n-m)*m)=O(n*m)，其原因是由每次匹配失败，i回溯到原位置加1造成，下面我们讨论无回溯的模式匹配算法。,4.4.2 无回溯的模式匹配算法(KMP算法) 算法的思想：是在每一趟匹配过程中，当出现si不等于tj时，i不需要回溯到原位置加1(i保持不变)，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。,例如，有回溯的匹配算法图4.7，在该算法的第三趟匹配中，当i=6和j=4字符不等时(si!=tj)，再次从i=3和j=0重新开始比较。但是，经仔细观察可以发现，在s3和t0，s4和t0以及s5和t0这三次比较都是不必进行的。,因为从第三趟部分匹配的结果就可得出，主串中第4、5和6个字符必然是b、c和a(即模式串中第2、3和4个字符)，而模式串的第一个字符是a，因此它无需再和这三个字符进行比较，仅需要将模式串指针j向右滑动到第二个字符的位置(i保持不变)继续进行i=6和j=1时的字符比较即可。,同理，在第一趟匹配中，从i=0和j=0开始进行比较，当比较到i=2和j=2字符不等时(si!=tj)，i=6保持不变，而j滑动到j=0的位置继续进行字符的比较。如图4.8所示，在整个匹配过程中,i指针没有回溯。,例如主串s为ababcabcacbab，模式串t为abcac，无回溯的匹配过程如图4.8所示。,现在讨论一般情况。每趟匹配失败，根据子串t的特性使i不回溯，这时j退到恰当的某个位置重新比较。 设主串为s0s1sn-1，模式串为t0t1tm-1，从主串s中某一个位置开始比较，当匹配过程中产生“失配”(即si!=tj)时，指针i应保持不变，如何设置j(si应与模式串中的哪个tj字符比较)? 此时应有： t0t1tj-1=si-jsi-j+1si-1 (4-1) 假设此时j应滑动到j=k(kk(即si和tk进行比较)，那么k具有以下性质： t0t1tk-1=si-ksj-k+1si-1 (4-2) 同时利用已经得到的“部分匹配”结果表达式(4-1)可知，这时应有： tj-ktj-k+1tj-1=si-ksj-k+1si-1 ” (4-3) 再从表达式(4-2)和(4-3)可得到，于是对k的要求是： t0t1tk-1=tj-ktj-k+1tj-1 (4-4),通俗说法是：当模式中tj与主串中si失配时，将si与tk比较，所取k的原则：模式串的前k个字符子串等于tj前的k个字符子串，并且是具有此性质的最大子串的串长。如图4.9所示。,图4.9 模式串的特征,反之，若模式串中存在满足(4-4)的两个子串，则当匹配过程中，主串中第i个字符与模式串中第j个字符比较不等时，仅需要将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐，此时，模式串中头k个字符的子串t0t1tk-1必定与主串中第i个字符之前长度为k的子串si-ksj-k+1si-1相等。,如在图4.8中，当第二趟匹配“失配”时，i=6不变，此时在模式串t0到tj-1(即t3)中，满足此性质的最大子串为a，所以k取1，即从i=6和j=1进行第三趟匹配。在模式串中，对于不同的tj有不同的tk，于是设一个数组nextj=k，用于存储各字符tj的对应tk的k值。具体求nextj的原则若下： (1)j=0时，nextj=-1。 (2)存在t0t1tk-1=tj-ktj-k+1tj-1(0kj)，则 取k的最大值。 (3)否则，nextj=0。,例4.1,例4.2,因为next数组只与模式串相关，所以可以预先求出。,假设next已经求得，则KMP的模式匹配算法用C语言描述下： 算法4.8 KMP的模式匹配算法。 int index_kmp(char s,char t,int next) /* 从主串s起始位置开始查找 */ int i=0, j=0, m, n; m=strlen(s); n=strlen(t); while(i=n) return(i-n); else return(-1); ,求next的算法又是如何实现的？ 由定义可知： next0=-1 设 nextj=k，这表明在模式串中 t0t1tk-1”=”tj-ktj-k+1tj-1 其中k为满足0k满足上式。此时nextj+1=?可能有两种情况： (1)若tk=tj，则表明在模式串中 t0t1tk-1tk=tj-ktj-k+1tj-1tj 并且，不可能存在kk满足上式，这就是说nextj+1=k+1，即 nextj+1=nextj+1 (2)若tk!=tj，则表明在模式串中 t0t1tk-1tk!= tj-ktj-k+1tj-1tj,此时可以把求next数组问题看成是一个模式匹配问题，整个模式串既是主串又是模式串，而当前在匹配过程中，已有t0=tj-k ，t1=tj-k+1，tk-1=tj-1，则当tk!=tj时应将模式串向右滑动以至于使模式串中第k=nextk个字符和主串中的第j个字符比较，若tk =tj ，则说明在主串中第j+1个字符前存在一个长度为k+1的最长子串，和模式串中头k+1个字符组成的子串相等，即 t0t1tk-1tk != tj-ktj-k+1tj-1tj 这就是说 nextj+1=k+1，即 nextj+1=nextk+1 同理，若tk!=tj，则将模式继续向右滑动直至将模式中第k=nextk个字符和tj对齐，依次类推，直至tj和模式中某个字符匹配成功或者不存在任何k(0kj)满足等式t0t1tk-1tk != tj-ktj-k+1tj-1tj，则 nextj+1=0,例如，模式串t=abaabcac，如图4.10所示，已求得前6个字符的next值，现在要求next6，因为next5=2，又t5!=t2，则需要比较t5和t1(因为next2=0),这相当于将子串模式向右滑动。由于t5!=t0，而且因next0=-1，所以next6=0；又由next6 =0，并且t6=t0，