数据结构——用C语言描述（第二版）第4章串.ppt

1、4.1 串的基本概念 4.2 串的存储实现 4.3 串的模式匹配算法 4.4 汉字串,第4章 串,串又称字符串，是一种特殊的线性表，是数据元素类型为字符的线性表，其应用非常广泛，是许多软件系统（如字符编辑、情报检索、词法分析、符号处里、自然语言翻译等系统）的操作对象。 本章介绍串的概念和各种存储结构，并讨论串的联接、求子串、串的插入、删除和置换以及串的模式匹配等运算。,第4章 串,串是由n个(n 0 )字符组成的有限序列，一般记作： S=“a1a2an” 其中，S是串名，用成对的双引号括起来的字符序列是串的值，ai可以是字母，数字或其它字符；n为串中字符的个数，称为串的长度，长度为零的串称为空

2、串。需要注意的是，成对的双引号本身仅作为标记，不属于串。 例如，串“Beijing”和“Bei jing”的长度分别是7和8。空串和空格串是两个不同的情况，例如，S1=“”即为空串，它的长度为0，空串内无任何字符，而S2=“ ”为空格串，即由一个或多个空格组成，其长度为串中空格的个数，空格符可以出现在字符序列的任意部位。 串中任意个连续的字符组成的子序列称为子串，一个串可以包含若干个子串，相应地，包含子串的串称为主串。字符在串中的序号称作该字符在串中的位置。当两个串长度相等且对应字符都相同时相等。,4.1 串的基本概念,串的逻辑结构与线性表的区别仅在于串的数据对象约束为字符集。 串结构的形式化

3、定义为： String=(D，R) 其中，D= aiaicharacter，i=1，2n，n0，R=a i-1，aiD，i=1，2，n 串的基本运算有： （1）初始化ClearString（s）：初始化串s。 （2）StrAssign（s，ch）：串赋值。 （3）StrCopy(s，t)：串复制。 （4）StrConcat（t，s1，s2）：串联接。 （5）求串长StrLen（s）：返回s串的元素个数，即s串的长度。 （6）串比较StrCom（s，t） （7）求子串SubStr（t，s，pos，len）：返回s串的第pos个字符起始的长度为len的子串。 （8）插入运算StrInsert（s，

4、pos，t）：把串t的值插入到串s的第pos个字符之后。 （9）删除运算StrDel（s，pos，len）：将串s中从第pos字符起始的长度为len的子串删除。,（10）子串定位StrIndex（s，t，pos）：从主串s的第pos个字符起定位串s中是否存在和串t值相等的子串，若存在，则返回子串t在主串s中第一次出现的位置，否则，返回函数值0。 例如， StrIndex（“Beijing”，“jin”，1）=4； StrIndex（“Beijing”，“jng”，2）=0 （11）置换运算StrReplace（s，pos，len,t）：用t串置换s串中第pos字符开始的连续的len个字符。 例

5、如，s=“Thatisabag！”，则 StrReplace（s，3，2，“is”）“Thisisabag！” 有时用另一种置换运算StrReplace（s，t，v）表示用v串置换所有在s串中出现的与t串相等的子串。 例如，s=“if（jn） j；”，t=“j”，v=“i”，则 StrReplace（s，t，v）=“if（in） i；” 以上介绍的是有关串的一些基本运算，利用它们可以处理关于串的各种操作，在使用高级程序设计语言中的串类型时，对于串的基本运算可以有不同的定义方法。,4.2.1 串的定长顺序存储及运算实现 1.串的定长顺序存储 串的顺序存储结构简称顺序串，是把串中的字符依次存放在一

6、组地址连续的存储单元中。 有时将为字符串分配一个固定长度的一组地址连续的存储单元的存储分配方法称之为定长顺序存储分配。定长顺序存储分配的实现，要结合具体的计算机编址方式进行，通常有三种实现方式： （1）紧缩方式 紧缩方式将串长显式地直接存储，字符依次顺序放在连续的几个单元中，这种存储方式的优点是充分地利用了空间，然而运算不太方便。 假定计算机按字编址，若串S为“DataStructure”， 表示空格字符，则S串有14个字符，存储S串的长度14和每个字符，一共需占用4个存储单元，如图4.1所示。,4.2 串的存储实现,（2）非紧缩方式 非紧缩方式是每个单元只存放一个字符，串的长度不显式存储，由

7、串中字符占存储单元的数目来隐式确定。如图4.2给出了上述串的非紧缩存储。显然，非紧缩存储方式对于串运算比较方便，但存储空间没有得到有效的利用。 （3）单字节存储方式 计算机按字节编址，每个字节存放一个字符，这时的串长度由串占用的字节数隐式确定，如图4.3所示。这种存储方式既不浪费空间，又使串中每个字符与唯一的地址对应，方便了运算，对于按字节编址的计算机而言是非常合适的。,在C语言中，按字节寻址。C语言中的串有字符串常量和字符串变量两种。用双引号括起来的字符序列为字符串常量，可以用宏定义#define来定义字符串常量的标识符。 例如， #define CITY Beijing 对字符串变量而言，

8、C语言将其类型说明为字符型一维数组。 例如，char ch100； 其中，数组ch是一个一维数组，这里的字符串的最大长度是由其变量说明时决定并且固定不变。通常，在字符串的最后一个字符的后面存放一个结束标志0。 为了更好地讨论字符串的运算，可将顺序串类型定义如下： #define MAXLEN 81 typedef struct string char chMAXLEN； int len； SeqString；,2.定长顺序串的基本运算实现 （1）求串长 int StrLen (SeqString *s) return(*s).len); （2）串的联接 两个串的联接就是将一个串紧接着存放在另一

9、个串的后面而得到一个新串。,void StrConcat (SeqString *t ， SeqString *s1， SeqString *s2) int i，j; if (*s1).len+(*s2).len=MAXLEN) for(i=0；i (*s1).len ；i+) (*t).chi=(*s1).chi; for(j=0；j (*s2).len ；j+) (*t).ch(*s1).len +j=(*s2).chj; (*t).len=(*s1).len+(*s2).len; else if (*s1).len MAXLEN) for(i=0；i (*s1).len ；i+) (*t

10、).chi=(*s1).chi; for(j=0；j MAXLEN- (*s1).len；j+) (*t).ch(*s1).len +j=(*s2).chj; (*t).len= MAXLEN； else printf (“overflow！n”); ,（3）求子串 void SubString（t，s，pos，len）/* 用t返回主串s中第pos个字符起，长度为len的子串 */ SeqString *t，*s； int pos，len； int i； if (pos(*s).len) | (len(*s).len-pos+1) printf(“pos或len超界n”); else for

11、(i=0；i len；i+) (*t).chi=(*s).chpos-1+i (*t).len=len; ,（4）子串的插入 void StrInsert (SeqString *s， int pos， SeqString *t) /* 在串s中的pos位置插入子串t */ int i； if (pos (*s).len+1) printf(“Insertion position incorrect!n”)； else if (*s).len+(*t).len=pos；i-) (*s).chi+(*t).len=(*s).chi; for (i=0；i(*t).len；i+) (*s).chi

12、+pos=(*t).chi; (*s).len=(*s).len+(*t).len； else printf(“overflow！”)； ,（5）子串的删除 void StrDel (s，pos，len) /*从串s中删除第pos字符起始的长度为len的子串*/ SeqString *s； int pos，len; int i，j，k； char *p，*q； if (pos (*s).len) printf(“Deleted position incorrect!n”)； else if (pos= =len) (*s).len=0；/*删除整个串*/ else,if (pos+len-10

13、）/*将被删除位置后的字符向前移动*/ *q=*p； +p； +q； k-； *q=*p; (*s).len=(*s).len-len； else printf(“no characteds deleted!n”)；/*没有len个字符可删除*/ ,（6）串的置换 void StrReplace (s，t，v) /*用v串替代s串中所有的t子串*/ SeqString *s，*t，*v； int start，pos，m，n，q； n=(*s).len；m=(*t).len；q=(*v).len； pos=1； do start=StrIndex(s，t，pos)；/*定位函数*/ if (st

14、art!=0) StrDel (s，start，m)； StrInsert(s，v，start)； pos= start+q； (*s).len=(*s).len+q-m； n=(*s).len； while (pos=n-m+1) /*串在堆中的开始位置*/ int length; /*串长度*/ HeapString；,在堆式动态存储分配下的串的几种常见运算的实现。 （1）串赋值StrAssign(t，chars) int StrAssign(HeapString *t，char *chars) int len，i=0; /*为统计字符串常量中的字符个数初始化*/ if (t-st !=N

15、ULL) free(t-st)；/*释放t空间*/ while(charsi!= 0) /*统计chars中字符个数*/ i+; len=i; if(！len) printf(“串常量为空串n”)； t-st =NULL; t-length=0; else if (!(t-st=(char *)malloc(i*sizeof(char) return (0); for(i=0；isti=charsi; t-length=len; return (1); /*StrAssign*/,（2）串联接StrConcat(t，s1，s2) StrConcat(HeapString *t，HeapStri

16、ng *s1，HeapString *s2) if (t-st !=NULL) free(t-st)；/*释放t原空间*/ if (!(t-st=(char *)malloc(（s1-length+s2-length）*sizeof(char) return(0); for(i=0；ilength；i+) /*逐字符赋值*/ t-sti= s1-sti; for(i=0；ilength；i+) /*逐字符赋值*/ t-sts1-length+i= s2-sti； t-length=s1-length+ s2-length； return (1); /*StrConcat */,（3）求子串Su

17、bString(t, s, pos, len) SubString(HeapString * t， HeapString * s， int i， int len) if(poss-length)| (lens-length-pos+1) printf(“子串位置或长度有错误n”); return (0); if (t-st !=NULL) free(t-st)；/*释放t原空间*/ if(len= =0) /*空子串*/ t-st =NULL; t-length=0; else t-st=(char *)malloc(len*sizeof(char); for(i=0；isti= s-stpo

18、s-1+i; t-length=len; return (1); /*SubString*/,（4）插入函数StrInsert(s, pos, t) StrInsert(HeapString *s，int pos，HeapString *t) int i; char *temp; if (poss-length | s-length= =0) return(0); temp=(char *)malloc(s-length + t-length)*sizeof(char); if (temp= =NULL) return(0); for (i=0；isti; for (i=0；ilength；i

19、+) tempi+pos=t-sti; for (i=pos；ilength；i+) tempi + t-length=s-sti; s-length+=t-length; free(s-st); s-st=temp; return (1); /*StrInsert*/,（5）删除函数StrDelete (s, pos, t) StrDelete(HeapString *s，int pos，int len) int i; char *temp; if (pos(s-length- len) return(0); temp=(char *)malloc(s-length- len)*sizeof

20、(char); if (temp= =NULL) return(0); for (i=0;isti; for (i=pos；ilength- len；i+) tempi=s-sti+len; s-length=s-length-len; free(s-st); s-st=temp; return (1); /*StrDelete*/,4.2.3串的块链存储表示 顺序串上的插入和删除操作运算需要移动大量的字符。因此，可以采用单链表方式来存储串值，串的这种链式存储结构简称为链串。但在利用链表存储串值时，每个结点既可以存放一个字符，也可以存放多个字符，即存在一个“结点大小”的问题。结点的大小是指结点

21、的数据域可存放字符的个数。如图4.6中所示的链表，其结点大小分别为4和1。,一般的，为了提高存储密度，可使每个结点存放多个字符。显然，当结点大小大于 1时，由于串长不一定是结点大小的整数倍，最后一个结点的数据域不一定刚好全被串值填满，此时就需要以特殊的字符如或其它的非串值字符填充。通常，将这种结构中的结点称为块，相应的链表称为块链结构。块链结构的类型可定义如下： #define BLOCKSIZE 8 /*块大小定义*/ typedef struct Blocknode /*块类型定义*/ char dataBLOCKSIZE； struct Blocknode *next ； BLOCK；

22、typedef struct /*块链类型定义*/ BLOCK *head,*tail； int length； BLString； BLString *s，*p，*head； /*s，p，head为块链指针类型*/,4.3 串的模式匹配算法,4.3.1 串的简单模式匹配算法 设有两个串s和t，在串s中查找值等于t的子串的过程称为模式匹配，其中，s串称为主串或目标串，t串称为模式串。若在主串s中存在模式为t的子串，则称匹配成功，否则称为匹配失败。串的简单模式匹配实际上是子串的定位运算，是一种带回溯的模式匹配。 例如，图4.7给出了s=“ababcabcacbab”，t=“abcac”的简单模式

23、匹配过程。,其模式匹配过程可描述为：设在某一趟匹配时，s串中的第i个字符与t串中的第j个字符比较，若sitj，则应有si-1=tj-1，si-2=tj-2，si-j+1=t1，如图4.8所示。因此，当si与tj匹配失败时，新的一趟匹配开始应该是t1与si-j+2继续进行比较，i指针从当前位置回溯到新位置。 其基本思想是：首先从主串s的第 start（1startStrLen(s)）个字符起和模式串t的第一个字符进行比较，若相等，则继续比较后续字符，否则，从主串s的下一个字符起再重新和模式t的第一个字符比较，依此类推，直至模式t的每一个字符依次和主串s中的一个连续的字符序列相等时为止，此时称匹配

24、成功，函数值为与模式t中第一个字符相等的字符在主串s中的位置；否则称匹配不成功，函数值返回0。,算法描述如下：int StrIndex（SeqString *s ， SeqString * t， int start） /*在目标串s中定位模式串t的位置*/ int i，j; if (start(*s).len)|(*t).len= =0) return (0)； else i=start；j=1； while(i(*s).len)&(j(*t).len) if（(*s).chi= =(*t).chj） i+ +； j+ +； else i=i-j+2； j=1； if (j= =(*t).le

25、n) return (i-(*t).len)； else return (0)； 在上面算法中可以引入起始查找位置指针start，即从s串的start位置起始查找第一个与t串相同的子串，使函数更为通用。,该算法匹配过程由于存在回溯，算法的效率不高。在最好情况下，算法的时间复杂度为O(n+m)。在最坏情况下的时间复杂度为O(nm)。最坏的情况是在每一趟匹配失败时，都是模式t的最后一个字符与s中相应的字符比较时才不相等。 例如，当模式串为“00000001”，而目标串为“00000000000000000000000000000000000000000000000000001”时，整个匹配过程中指

26、针i需回溯45次，在算法中while循环了468（indexm）次，算法的效率很低。有时，我们也将该算法称为朴素的模式匹配。在下一节中，我们将介绍另一种较好的KMP模式匹配算法。,4.3.2 一种改进的模式匹配算法 D.E.Knuth与V.R.Pratt和J.H.Morris同时发现通过对上一节的简单模式匹配算法进行一些改进，就可以消除算法中主串s指针的回溯，完成串的模式匹配，而且算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。人们把该改进算法称它为克努特莫里斯普拉特算法(简称为KMP算法)，如图4.9模式匹配过程。可以看出，其改进之处在于整个匹配过程对主串而言无需回溯，每当某一趟匹

27、配过程中出现字符比较不等即匹配失败时，目标串i指针不需要回溯，而是利用已得到的“部分匹配”的结果将模式向右移动尽可能远的一段距离后，继续进行比较，从而消除回溯。,一般的情况讨论如下： 假设主串s为“s1s2sn”，模式串t为“t1t2.tm”，要设计一个无回溯的匹配算法，关键在于确定在匹配过程中，当主串中si与tj比较不等（即“失配”）时，模式串t中的哪一个字符应与si继续进行比较？ 假设将这个字符记做tk，显然，有k0时，表示一旦匹配过程中出现si与tj不相等时，可用t中的nextj位置的字符继续与si比较；若nextj=0，则表示t中任何字符都不与si比较，需重新比较t1与s i+1。 可

28、见，对于任何的模式串t而言，只要能确定nextj（j=1，2，m）的值，就可以用来加速匹配过程。模式串的next函数的定义为：,next函数的意义是：若模式串t中存在满足等式“t1t2t k-1”=“t j-k+1 t j-k+2t j-1”的两个子串，则当匹配过程中主串中第i个字符与模式中第j个字符比较不等时，仅需将模式向右移动至模式中的第k个字符和主串中的第i个字符对齐，匹配仅需从模式中的第k个字符与主串中的第i个字符继续比较即可，如图4.10所示。另外，若在“t1t2. tj-1”中不存在首尾相等的子串，则k=1，表示一旦有si与tj不相等时，则用t1与si继续进行比较。特别地，若j=1

29、，当t1与si比较不相等时，此时不能继续右移，只要将t1与s i+1继续比较即可进行新一趟的匹配，所以在next定义中，nextj=0。,同时，为使模式串t的右移不丢失任何匹配成功的可能，对于同时存在多个满足以上性质条件的k值应取最大值，以使得移动的位数i-k最小。 例如，图4.11中，s=“aaaabbb”，t=“aaab”，当s4与t4比较不相等时，k可取1，2和3，但只有k取3时才可保证不丢失成功的可能匹配。,在求得模式的next函数之后，匹配过程如下：若在匹配过程中有si=tj成立，则i和j分别增加1，否则，i不变，即主串指针不回溯，而j退到nextj的位置再比较，即用tnextj与s

30、i继续比较，若此时相等，则指针各自增加1，否则j再退到下一个nextnextj值的位置，依此类推，直至出现下列两种可能的情况：一是j退到某个next值（nextnext.nextj）时，主串和模式串中的字符进行比较，若相等，则指针各自增1继续进行匹配；另一种情况是j退到值为0（即模式的第一个字符“失配”），此时需将模式继续向右移动一个位置，即从主串的下一个字符si+1起和模式重新开始匹配。 例如，对于模式串t=“abaabcac”： （1）j=1，next1=0； （2）j=2，没有首尾相等的子串，next2=1； （3）j=3，同样，也没有首尾相等的子串，next3=1； （4）j=4，存在

31、首尾相等的子串“a”，所以next4=2； .其余类推，从而可求得t所对应的next函数，如图4.12（a）所示。匹配过程如图4.12（b）所示。,KMP算法描述如下： int KMP(SeqString *s， SeqString * t， int start) if (start (*s).len+1)|(*t).len= =0) return (0)； else i= start；j=1； while (ichi= =t- chj ) +i； +j； else j=nextj； if (j(*t).len) return( i-(*t).len)； else return (0)； /*

32、 KMP*/,下面介绍模式串的next函数值的求解算法。由于模式串的next函数值仅取决于模式串本身而和主串无关，可以从分析其定义出发用递推的方法求得next的函数值。 由定义可得： next1=0 现假设nextj=k，这表明在模式串中存在下列关系： “t1t2tk-1”=“tj-k+1tj-k+2tj-1” 其中，k为满足1k满足上式。显然，若能求得nextj+1与nextj的关系，就可以求得next函数。 （1）若tk= tj ，则有：nextj+1=k+1，从而 nextj+1= nextj+1,（2）若tktj ，此时可把求next函数的问题看成是一个模式匹配的问题，整个模式串既是主

33、串又是模式串。 在当前匹配的过程中，当tjtk时，应该将模式向右移动至用模式中的第nextk个字符和主串中的第j个字符相比较。此时， 若nextk=k且 tj= tk，1kkj，则 ：nextj+1=k+1，从而可得： nextj+1= nextk+1 同理，若tjt k，则将模式继续向右移动直至将模式中第nextk个字符和tj对齐，.，依次类推，直至tj和模式中某个字符匹配成功或者不存在任何k(1kj)满足上述等式，则：nextj+1=1 例如，对于图4.12（a）中的模式串t，已求得前6个字符的next函数值，现要求next7的值。因为next6=3，且t6t3，由next3=1可知，需要

34、比较t6和t1，这相当于将模式串向右移动，由于t6t1而且next1=0，所以可得next7=1；同样，t7=t1，得next8=2。,求next函数的算法如下： void GetNext(SeqString *t，int &next ) /*求模式串t的next函数值并存入数组next中 */ int i=1，j=0； next1=0； while (i(*t).len) if (j= =0)|(*t).chi =(*t).chj)） +i； +j； nexti=j； else j=nextj； /*GetNext*/ 该算法的时间复杂度为O（m）。,需要注意的是： （1）KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比算法StrIndex效率高一些，KMP算法的最大特点是在整个匹配过程中，指示主串的指针无需回溯，对主串仅需从头至尾扫描一遍，这对于处理诸