串数据结构电子教案.ppt

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

2、置 将子串在主串中首次出现时，该子串首字符对应的主串序列中的序号定义为子串在主串中的位置。,串的比较 当且仅当两个串的长度相等，并且各个对应位置的字符也都相同，称两个串相等； 当两个串不相等时，可按“字典顺序”区分大小(在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可为串变量、串常量或经过适当运算所得到的串值。 串复制Strcpy(s,t)

4、：由串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,pos,len)：从串s中位置pos开始

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

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

7、的当前长度*/ SeqString; /*SeqString是顺序串类型*/ 在这种方式中，字符串的串值由ch0开始存放。当然，也可以将串的实际长度存储在0号单元中，实际串值从1号单元处开始存放。实际应用中究竟采用哪种结构，需要根据情况进行权衡。在C语言中是采用字符0作为串的终结符的方式。,顺序串的基本操作的实现 下面讨论串的部分基本操作的实现算法。 串的数据类型说明如下： #define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SeqString;,求串长Strlen(s) ：返回串s的元素个数。 int St

8、rlen(SeqString s) return(s.length); 串复制Strcpy(s,t)：将串s复制到串t中。 SeqString *Strcpy(SeqString s，SeqString *t) int i; for(i=0;is.length;i+) tchi=s.i; tlength=s.length; /*置串t的长度*/ return(t); ,串联接Strcat(s,t)：将串t联接到串s的末尾形成新串s。若t完全联接到s的末尾，表示联接成功则返回1，否则不成功返回0。 int Strcat(SeqString s, SeqString t) int i; if(s.

9、length+t.length=MaxStrSize) /*判断串s和t的长度之和是否超过串的最大长度*/ for(i=0;it.length;i+) s.chi+s.length=t.chi; s.length=s.length+t.length; /*置串s的实际长度*/ return(1); Else for(i=0;iMaxStrSize-t.length;i+) s.chi+s.length=t.chi; s.length=MaxStrSize /*置串s的实际长度*/ return(0); ,求子串Substr(s,pos,len,sub)：从串s中的第pos个字符开始取长度为le

10、n的子串sub，并返回串sub。 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的长度*/ return(sub); ,串删除StrDelete(s,pos,len)：

11、从串s中位置pos开始，删除len个字符，并返回串s。 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;islength;i+) schi-len=schi; slength=slength-len; /*重置串s的实际长度*/ return(s); ,串的顺序存储表示下，串操作的实现主要是进行“字符序列的复制”，操作的

12、时间复杂度基于复制的字符序列的长度。在这种存储方式下，涉及串长的操作速度快，但也存在不足之处：一是需事先预定义串的最大长度，这在程序运行前是很难估计的；二是由于定义了串的最大长度，串值空间的大小在编译时刻就已确定，是静态的，使得串的某些操作受限，如串的联接、插入等操作受到串值空间大小的制约。这种串的定长顺序表示不够灵活，适应范围有一定局限。,串的堆存储结构 堆存储结构的特点是：仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但该存储空间的大小不是预定义，而是在程序执行过程中动态分配的。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。这种方式可以

13、灵活地申请适当数目的存储空间，从而提高存储资源的利用率。 在C语言中，由动态分配函数malloc( )分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。由函数free( )释放串不再需要的空间。,串的堆存储结构类型定义如下： typedef struct char *ch; /*ch指向串起始地址*/ int length; /*串的实际长度*/ Hstring； 在这种存储方式中，指向字符串存储空间的是字符指针而非数组。若串为空串，则ch为NULL。另外在使用分配函数后需要检查函数的返回值（若分配失败，则返回NULL），避免出现对空指针进行操作。,堆串的

14、基本操作的实现 串的堆存储结构中，串中的字符也是顺序存放的，串操作的实现也是基于“字符序列的复制”方式。只是由于串长是可变的，所以在实施“插入”、“联结”等可能使串长发生变化的操作时，除了要修改串的实际长度，还要为串按新的长度重新分配空间。,串联接Strcat(s,t)：将串t联接到串s的末尾形成新串,返回新串。若无法生成新串，则返回空。 Hstring *Strcat(Hstring s, Hstring t) Hstring *new; int i; if(!new= (Hstring *)malloc(sizeof(Hstring) return(0); if(!new-ch= (cha

15、r *)malloc(s.length+t.length) return(0); /*分配空间失败*/ 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); ,串插入StrInsert(s,pos,t)：将串t插入在串s的位置pos上，并返回串s。 Hstring *StrInsert(Hstring *s, int pos, Hstring *t) c

16、har *p; int i; if(poss-length) /*插入位置不合法*/ printf(parameter 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-) s-chi+t-length=s-chi; /*向后移动字符，腾出位置*/ for(i=0;ilength;i+) s-chpos

17、+i-1=t-chi; /*插入串t*/ s-length=s-length+t-length; /*更新串s的长度*/ retrun(s); ,串删除StrDelete(s,pos,len)：从串s中位置pos开始，删除len个字符。 int StrDelete(Hstring *s, int pos,int len) char *p; int i; if(poss-length) /*参数不合法*/ printf(parameter error!); return(0); p=s-ch+pos-1; for(i=0;ilength=s-length-n; /*更改串s的长度*/ retur

18、n(1); ,4. 串的块链存储结构 串的链式存储结构类型定义如下： typedef struct char ch; struct cnode *next; cnode,*LinkString; LinkString head; /*head是链串的头指针*/ 串的链式存储结构简称链串。,链串结构便于进行插入和删除运算，但每个结点的指针域所占空间比字符域所占空间要大得多，存储空间利用率较低。为了有效利用存储空间，可以在链串的每个结点中存放多个字符，称这样的结点为块，每个结点中所容纳的字符个数为块的大小，称这样的串存储结构为块链结构。 块链结构中，当结点大小大于1时，串的长度不一定正好是结点大小

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

20、k; typedef struct /*定义块链存储结构*/ Chunk *head,*tail; /*链表头指针和尾指针*/ int strlen; /*串的实际长度*/ Lstring; 为了便于串进行操作如串联结，在链表中设置尾指针指示最后一个结点，同时设置一个分量表示串的实际长度。,4.3 串的模式匹配算法,子串定位操作又称为串的模式匹配(Pattern Matching)或串匹配，该操作是各种串处理系统中的重要操作之一 。 子串定位操作是要在主串中找出一个与子串相同的子串。一般将主串称为目标串，子串称之为模式串。 设S为目标串，T为模式串，把从目标串S中查找模式串T的过程成为“模式匹

21、配”。匹配的结果有两种：如果S中有模式为T的子串，则返回该子串在S中的位置，若S中有多个模式为T的子串时，则返回的是模式串T在S中第一次出现的位置，这种情况称匹配成功；否则，称为匹配失败。,基本的模式匹配算法,设有两个串S和T，其中： S=s1s2s3sn T=t1t2t3tm（1mn，通常有mn） 模式匹配算法的基本思想是：用T中字符依次与S中字符比较：从S中的第一个字符(i=1)和T中第一个字符(j=1)开始比较，如果s1t1，则i和j各加1，继续比较后续字符，若s1t1，s2t2，smtm，返回1；否则，一定存在某个整数j(1jm)使得sitj，即第一趟匹配失败，一旦出现这种情况，立即中

22、断后面比较，将模式串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的子串，那么匹配失败。,模式匹配基本算法 int Index(SeqString s , SeqString t) /* 在目标串s中找模式串t首次出现的位置，若不存在返回0。采用定长顺序存储结构第二种方式存放串S和串T

23、*/ int i,j; for(i=1,j=1;it.length) return(i-t.length+1); /*匹配成功*/ else return(0); /*匹配不成功*/ ,算法分析 该算法的基础是基于字符串的比较，匹配过程简单，易于理解，但算法效率不高。在某趟匹配过程中，若出现字符比较不等，则指向主串的指针需要回溯，需要从模式串的第一个字符重新开始比较。 设主串和模式串的长度分别为n、m，在最坏情况下（即第i趟匹配成功，前面 i-1趟不成功），每趟比较了m次，第i趟也比较了m次，那么上述算法所执行的字符比较的总次数为m(n-m+1)。算法的时间复杂度为O(m(n-m)，若nm，则

24、时间复杂度为O(mn) 。,模式匹配的改进算法KMP算法 KMP算法的基本思想：每当一趟匹配过程中出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。该算法可以在O(m+n)的数量级上完成串的模式匹配。,在匹配改进算法，需要解决的关键问题：当匹配过程中某次比较不成功时，模式串向右滑动的距离是多少，以及下次比较时j指针的值，即主串中第i个字符应该与模式串中哪个字符再比较？ 令nextj = k，则nextj表示当模式串中第j个字符与主串第i个字符不等时，模式串中需要重新与主串字符si进行比较的位置。 模式串的next函数的定义： 0 当j=1时 nextj= Maxk | 1kj且t1t