数据结构-C语言版：DS04-串

1、 基本概念 串的存储结构 串的基本操作 串的模式匹配第四章 串4.1 串的定义和基本操作串定义：是字符串的简称，是由零个或多个字符组成的有限序列。一般记为： S=a1a2an （n0） 其中：S是串名；用双引号（“”）括起的字符序列是串的值；ai（1in）可以是字母、数字或其它符； n是串中字符的个数, 称为串的长度。 空串与空格串 长度为零（n0）的串称为空串（Null String），它不包含任何字符。由空格字符组成的串，称为空格串（Blank String）。它的长度为串中空格字符的个数。 子串与主串 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。例如：串A

2、=“China Beijing”, B=“Beijing”, 则它们的长度分别为13、7。B在A中的位置是7。子串的位置 以子串的第一个字符在主串中的位置来表示。 串的比较 当且仅当两个串的长度相等，并且各个对应位置的字符也都相同，称两个串相等； 当两个串不相等时，可按“字典顺序”区分大小(在C语言中，按字符ASCII码的大小为准)。例如，有下列四个串s1，s2，s3，s4： s1= “pro”， s2= Program s3= program ，s4= program 以上四个串彼此互不相等，且s4s3s1s2。 串变量：其取值是可以改变的，它必须用名字来识别； 串常量：和整常数、实常数一样

3、，具有固定的值，在程序中只能被引用但不能改变其值，即只能读不能写。 串变量与串常量例如，在C语言中，有下列语句： char x=456; /*x是一个串变量名，它的值为字符序列456，而不是整数456*/ char string1=string; /*string1是一个串变量名，字符序列string是赋给它的值*/求串长Strlen(s) ：求串s的长度，Strlen(s)的值是一个非负整数。若s是一个空串，则Strlen(s)=0串赋值StringAssign(s,string_constant) ：给串s赋值。其中string_constant可为串变量、串常量或经过适当运算所得到的串值

4、。 串复制Strcpy(s,t)：由串s复制得到串t。串联接Strcat(s,t)：将串t联接到串s的末尾形成新串s。 串比较Strcmp(s,t)：比较s和t的大小，若st，则返回值小于0；若st，则返回值大于0；若s=t，则返回值为0 。 串的基本操作 求子串Substr(s,pos,len,sub)：从串s中的第pos个字符开始取长度为len的子串构成串sub。 子串的定位Index(s,t)：在串s中寻找串t第一次出现时，串t首字符在串s中的位置。若找到，则返回该位置，否则返回0。 串插入StrInsert(s,pos,t)：将串t插入在串s的位置pos上。串删除StrDelete(s

5、,pos,len)：从串s中位置pos开始，删除len个字符。子串替换操作Replace(s,t,v)：将串s中的子串t全部替换成串v。4.2 串的表示和实现 串的定长顺序存储 串的顺序存储结构，简称为顺序串。用一组地址连续的存储单元来依次存放串中的字符序列，串中相邻的字符顺序存放在相邻的存储单元中。所谓定长，指按照预先定义的大小为每一个串分配一个固定的存储区域。 通常有下列两种实现方式： 第一种使用定长的字符数组存放串，一般使用一个不会在串中出现的特殊字符（如0）放在串值的末尾（不记入串长）来表示串的结束。类型定义如下:#define MaxStrSize 256 /*串可能的最大长度*/

6、typedef char SeqStringMaxStrSize; /*SeqString是顺序串类型*/SeqString S; /*S是一个顺序串变量*/ 这种存储方法不能直接得到串的长度，而是判断字符是否为0来确定串是否结束，串长是隐含的。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。 第二种不使用终结符,用一个整数length来指示串的实际长度，length-1表示串中最后一个字符的存储位置。 类型定义如下： #define MaxStrSize 256 /*串可能的最大长度*/ typedef struct char chMaxStrSize;

7、int length; /*指示串的当前长度*/ SeqString; /*SeqString是顺序串类型*/ 在这种方式中,字符串的串值由ch0开始存放。当然，也可以将串的实际长度存储在0号单元中，实际串值从1号单元处开始存放。实际应用中究竟采用哪种结构，需要根据情况进行权衡。在C语言中是采用字符0作为串的终结符的方式。串的数据类型说明采用如下形式：#define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SeqString; /*使用时可不用0作为结束标志*/顺序串的基本操作的实现int Strlen(SeqS

8、tring s) /*s是结构体类型*/ return(s.length); 求串长Strlen(s) ：返回串s的元素个数。SeqString *Strcpy(SeqString s，SeqString *t) int i; for(i=0;is.length;i+) tchi=s.chi; tlength=s.length; /*置串t的长度*/ return(t); 串复制Strcpy(s,t)：将串s复制到串t中。将串t联接到串s的末尾形成新串s。若t完全联接到s的末尾，表示联接成功则返回1，否则不成功返回0。串联接Strcat(s,t)：int Strcat(SeqString s,

9、 SeqString t) int i; if(s.length+t.length=MaxStrSize) /*可不用0作为结束标志*/ /*判断串s和t的长度之和是否超过串的最大长度*/ for(i=0;it.length;i+) /*串t联接到串s之后*/ s.chi+s.length=t.chi; s.length=s.length+t.length; /*置串s的实际长度*/ return(1); else /*只把t串的前半部分联接到串s后，使s达到长度为MaxStrSize */ for(i=0;iMaxStrSize-s.length;i+) s.chi+s.length=t.c

10、hi; s.length=MaxStrSize /*置串s的实际长度,无0作为结束标志*/ return(0); SeqString *Substr(SeqString s,int pos,int len, SeqString *sub) int i; if(pos= s.length|len s.length-pos+1) /*判断pos和len的合法性*/ printf(parameter error!); return NULL; for(i=0;i len;i+) subchi=s.chpos+i-1; /*向子串sub复制字符*/ sublength=len; /*置串sub的长度*

11、/ return(sub); 求子串Substr(s,pos,len,sub)：从串s中的第pos个字符开始取长度为len的子串sub，并返回串sub。SeqString *StrDelete(SeqString *s, int pos, int len) int i; if(pos= slength|len= slength) /*判断pos和len的合法性*/ printf(parameter error!); return NULL; for(i=pos+len-1;ich= (char *)malloc(s.length+t.length) return(0); /*分配空间失败*/

12、for(i=0;ichi=s.chi; /*将串s复制到新串new中*/ for(i=0;ichs.length+i=t.chi; /*依次复制串t中字符到新串new中串s之后*/ new-length=s.length+t.length; /*新串new的实际长度*/ return(new); 两次申请空间 串插入：将串t插入在串s的位置pos处，并返回串sHstring *StrInsert(Hstring *s, int pos, Hstring *t) char *p; int i; if(poss-length) /*插入位置不合法，这位置是从1数起*/ printf(paramet

13、er error!); return NULL; if(t-length) /*串t非空,重新分配空间，插入串t*/ if(!p=(char*)realloc(s-ch,(s-length+t-length)*sizeof(char) return(0); /*重新分配空间失败*/ s-ch=p; for(i=s-length-1;i=pos-1;i-) /*因为数组下标从0起*/ s-chi+t-length=s-chi; /*向后移动字符，腾出位置*/ for(i=0;ilength;i+) /*插入串t*/ s-chpos+i-1=t-chi; s-length=s-length+t-l

14、ength; /*更新串s的长度*/retrun(s);串删除：从串s中位置pos开始，删除len个字符int StrDelete(Hstring *s, int pos,int len) char *p; int i; if(poslength-pos ch+pos-1; /*使指针p指向删除的开始位置*/ for(i=0;ilength-pos- len;i+) *(p+i)=*(p+len+i); /*删除字符,使后面的字符前移*/ s-length=s-length-len; /*更改串s的长度*/ return(1);串的块链存储结构 串的链式存储结构类型定义如下： typedef

15、struct char ch; /*单字符*/ struct cnode *next; cnode,*LinkString; LinkString head; /*head是链串的头指针*/ 串的链式存储结构简称链串。 ABCDEhead结点大小为1的链串表示 在这种存储结构下，结点数据域的类型是单字符，所以与前面讲的单链表的操作一样。 结点大小为1时，链串结构便于进行插入和删除运算，但每个结点的指针域所占空间比字符域所占空间要大得多，存储空间利用率低。存储密度较低。所谓存储密度为： 为了有效利用存储空间，可在链串的每个结点中存放多个字符，称这样的结点为块，每个结点中所容纳的字符个数为块的大小

16、，称这样的串存储结构为块链结构 块链结构中，结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符”#”来填充最后一个结点，以表示串的终结。 结点大小为1时，串的操作较方便，但是存储空间占用较大，空间利用率低；提高结点的大小使得存储空间利用率增大，但做插入、删除运算时，需要考虑结点的拆分与合并，可能会引起大量字符的移动，给运算带来不便。 在串的链式结构中，结点大小的选择很重要，直接影响到串的处理效率和内存空间利用率。#define CHUNKSIZE=4 /*定义块大小*/typedef struct Chunk /*定义块链结点结构*/ char strCHUNKSIZE;

17、 / *一块存储空间大小*/ struct Chunk *next; Chunk;typedef struct /*定义块链存储结构*/ Chunk *head,*tail; /*链表头指针和尾指针*/ int strlen; /*串的实际长度*/ Lstring; 为了便于串进行操作如串联结，在链表中设置尾指针指示最后一个结点，同时设置一个分量表示串的实际长度。串的块链存储结构类型定义如下：4.3 串的模式匹配算法 在一个文本中，我们经常要查找某一特定的单词，这也叫子串定位操作又称为串的模式匹配(Pattern Matching)或串匹配，它是串处理系统中的重要操作之一 。基本的模式匹配算法

18、 子串定位操作是要在主串中找出一个与子串相同的子串。一般将主串称为目标串，子串称之为模式串。 设S为目标串，T为模式串，把从目标串S中查找模式串T的过程成为“模式匹配”。匹配的结果有两种：如果S中有模式为T的子串，则返回该子串在S中的位置，若S中有多个模式为T的子串时，则返回的是模式串T在S中第一次出现的位置，这种情况称匹配成功；否则，称为匹配失败。设有两个串S（目标串）和T（模式串），其中： S=s1s2s3sn T=t1t2t3tm（1mn，通常有mn） 模式匹配算法的基本思想是：用T中字符依次与S中字符比较：从S中的第一个字符(i=1)和T中第一个字符(j=1)开始比较，如果s1t1，则

19、i和j各加1，继续比较后续字符，若s1t1，s2t2，smtm，返回1；否则，一定存在某个整数j(1jm)使得sitj，即第一趟匹配失败，立即中断本趟比较；将模式串T向右移动一个字符执行第二趟匹配，即用T中第一个字符(j=1)与S中的第2个字符(i=2)开始依次比较； 或者在某一趟匹配中出现t1si-m+1，t2si-m+2，tmsi，那么匹配成功，返回序号i-m+1（本趟匹配的开始位置）； 或者当执行了(n-m+1)趟匹配步骤之后，即一直将T向右移到无法继续与S比较为止，在S中没有找到等于T的子串，那么匹配失败。 反复执行匹配步骤，直到出现下面两种情况之一：S a c a c b a c b

20、 a b c aT a c b a bi =3j=3S a c a c b a c b a b c aT a c b a bi =2j =1S a c a c b a c b a b c aT a c b a bi=7j=5第一趟匹配S3T3第二趟匹配S2T1第三趟匹配S7T5(含n=10个字符)(含m=5个字符)S a c a c b a c b a b c aT a c b a b i =4j=1S a c a c b a c b a b c aT a c b a bi =5j =1S a c a c b a c b a b c aT a c b a bi=10j=5第五趟匹配S5T1第四

21、趟匹配S4T1第六趟匹配成功此匹配成功时，返回n-m+1(即10-5+1)int Index(SeqString s , SeqString t) /* 在目标串s中找模式串t首次出现的位置，若不存在返回0。采用定长顺序存储结构第二种方式存放串S和串T */int i,j;for(i=1,j=1;i=s.length&jt.length) return(i-t.length+1); /*匹配成功，返回模式在目的串中*/ else /*第1次出现的位置*/ return(0); /*匹配不成功*/ 模式匹配基本算法 算法分析 该算法的基础是基于字符串的比较，匹配过程简单，好理解，但算法效率不高。

22、在某趟匹配过程中，若出现字符比较不等，则指向主串的指针需要回溯，要从模式串的第一个字符重新开始比较。 设主串和模式串的长度分别为n、m，在最坏情况下（即第i趟匹配成功，前面 i-1趟不成功），每趟比较了m次，第i趟也比较了m次，那么上述算法所执行的字符比较的总次数(最多)为m(n-m+1)。算法的时间复杂度为O(m(n-m)，若nm，则时间复杂度为O(mn) 。 KMP(克努特、莫里斯、普拉特)算法的基本思想：每当一趟匹配过程中出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。模式匹配的改进算法KMP算法假设下一次主串中的第i

23、个字符就与模式串中的第k(kk，根据()和()可推出： t1t2t3 tk-1= tj-k+1tj-k+2tj-1 在模式串的前j-1个字符中应存在两个长度为k-1的相同的最大子串，两子串t1t2tk-1与tj-k+1tj-k+2tj-1 相等，即 t1= tj-k+1，t2= tj-k+2，tk-1=tj-1。 0 当j=1时 nextj= Maxk | 1kj且t1t2tk-1=tj-k+1tj-k+2tj-1 当此集合不空 1 其他情况 根据以上的讨论，我们得出：当模式串T中第j个字符与主串S中第i个字符失配时，模式串中要重新与主串中字符si进行比较的字符位置k的函数nextj=k 为：例：根据定义可推出下列模式串的next函数值： 位置j 1 2 3 4 5 6 7 8 9 10 11 12 模式串 b