大学数据结构课件4.串

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,主要知识点,串的基本概念和C语言的串函数,串的存储结构,动态数组实现的顺序串,串的模式匹配算法BF算法,1,4.1,串的基本概念,1)串,(又称字符串)是由n(n,0)个,字符,组成的,有限序列,。（它是,数据元素为单个字符,的特殊线性表。）,记为： s = “c,0,c,1,c,n-1,” (n0 ),串名,串值（用”,”,括起来）,串举例：a=“speak English” b=“string”,c=“speak” d=“ing”,e=“ ” f=“”,1. 基本概念,2,)串长,串中字符的个数（n0）。,)空串,串中字符的个数为0 时称为空串,。,)空白串,由一个或多个空格符组成的串。,)子串,串S中任意个连续的字符序列叫S的子串; S叫主串。,)子串位置,子串的第一个字符在主串中的序号。,)字符位置,字符在串中的序号。,)串相等,串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）,串举例：a=“speak English” b=“string”,c=“speak” d=“ing” d1=“ing”,e=“ ” e1=“ ” f=“” d2=“nig”,3,问：空串和空白串有无区别？,答：有区别。,空串(Null String)是指长度为零的串；,而空白串(Blank String),是指包含一个或多个空白字符” ”(空格键)的字符串.,注：1.串与字符的区别,“a” 串，长度为的串。（它不仅要存储字符a，还要存储该串的长度数据）,a字符a。(只存储字符a),2.串常量与串变量的区别,串常量具有固定的值，而串变量的值是可以改变的。在C语言中串变量说明有两种：Char *变量名；或 Char 变量名下标数,串举例： d = “” e = “ ” e1= “ ”,4,2. 串的抽象数据类型,数据集合：,串的数据集合可以表示为字符序列 c,0,c,1,c,n-1,，每个数据元素的数据类型为字符类型。,操作集合：,(1) 初始化串Initiate(S),(2) 赋值 Assign(S,T),(3) 求串长度Length(S),(4) 比较 Compare(S,T) :有相等和不相等两种比较结果，还有大于、等于和小于三种比较结果,(5) 插入 Insert(S,pos,T),(6) 删除 Delete(S,pos,len),(7) 取子串 SubString(S,pos,len),(8) 查找子串Search(S,start,T),(9) 替换子串Replace(S,start,T,V),5,相同之处：都是线性结构,不如之处：,（1）线性表的数据元素类型为任意类型；而串的数据元素类型为字符类型；,（2）线性表的插入和删除操作都是只对一个单个元素；而串的插入和删除操作都是对一个子串进行的；,（3）串还有一些不同于线性表的其他操作；,因此，专门设计串为一个专门的数据结构。,现有的所有高级程序设计语言，如C/C+，Java等，都提供了专门的串操作函数或串类。,3. 串和线性表的比较,6,4. C语言的串函数,串长度：,int strlen(char *str);,串拷贝：,char *strcpy(char *str1,char *str2);,串比较：,int strcmp(char *str1,char *str2);,字符定位：,char *strchr(char *str,char ch);,子串查找:,char *strstr(char *s1,char *s2);,串连接：,char *strcat(char *str1,char *str2);,注：用C语言处理字符串时，要调用标准库函数 #include ,7,4.2 串的存储结构,4.2.1 串的顺序存储结构,串的顺序存储结构就是,用一个字符类型的,数组,存放串的所有字符，此时，表示串的长度的方法有两种：,一种方法是设置一个串的,长度参数,，此种方法的优点是便于在算法中用长度参数控制循环过程,另一种方法是在串值的末尾添加,结束标记,，此种方法的优点是便于系统自动实现。,而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种：,S T R I N G 0,typedef struct, char stringMAXSIZE;,int length;, Str;,8,用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长顺序存储结构。,其结构类型定义如下：,typedef struct, char strMAXSIZE;,int length;, String;,1.串的定长顺序存储(静态数组结构):,#define MAXSIZE 256,0length MAXSIZE,9,用动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。,在C语言中存在一个称之为“堆”的自由存储区，并由C的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际需要的存储空间，若分配成功则返回一个指针，指向串的起始地址。其存储结构如下：,2. 串的堆存储（动态数组结构）：,10,typedef struct, char *str;,int length;, Hstring;,其中，str 为指针变量，也是字符数组名，指向动态数组的首地址，若str为非空串，则按串长分配存储区，否则str为NULL；length 表示串的长度，Hstring为堆类型标识符。,堆分配存储结构的串既有顺序存储结构的特点，在操作中又没有串长的限制，显得很灵活，因此在串处理的应用程序中常被选用。,11,(1)单字符结点链,typedef struct Snode,char ch;,struct Snode *next;, SCharNode;,(2)块链,typedef struct Snode, char strNUMBER;,struct Snode *next;, NCharNode;,它分为单字符结点和块链两种。,4.2.2 串的链表存储结构,g,n,i,r,t,s,point,point,s t r i,n g,12,4.3,串的运算,4.3.1 串的运算简介,串定义后，还需要经常对其进行运算操作。下列介绍几种基本运算。我们尽可能用C语言中库函数表示，若没有库函数，则用自定义函数说明。,1、求字符串的长度 （字符个数，结束标记0不算）,unsign int strlen ( char *string ),2、字符串的联接 ( string1 = string1 string2 ）,char * strcat ( char *string1, char *string2 ),3、两个字符串的比较( 返回值：-1，0，1 ),int strcmp ( char *string1, char *string2 ),4、子串的查询（找出2在1中首次出现的位置并返回指针 ）,char * strstr( char *string1, char *string2 ),5、字符串的拷贝（将2复制到1中，并返指1的指针）,char * strcpy (char *string1, char *string2 ),13,6、字符串插入操作,void insert(char *string1, string2, int i ), int j, n=strlen(string1); m=strlen(string2);,if( in) printf(“No!”);,else for ( j=n-1; j=i-1; j-) string1j+m=string1j;,for ( j=i-1; jstrlen(str1) printf(“NO!”);,else k=pos-1;,while(str1k+len!=0) /*k+len strlen(sor) return 0;,point = 0;,while(sorstart-1!= &start=end), despoint=sorstart-1;,start+; point+;,despoint =; return 1; /*返回1表示成功, 0表示失败*/,4.3.1 串的运算简介,end,数组下标: 0 1 2 3 4 5 6 7,8,9 10,11,12 13 14 15,p,r,o,g,r,a,m,-,e,x,a,m,1,1,0,sor,序号: 1 2 3 4 5 6 7 8,9,10 11,12,13 14 15 16,start,e,x,a,m,des,0 1 2 3 4 5,16,4.3.2,串的模式匹配算法,假设t和p是两个给定的串, 在t中寻找与p相同的子串的过程称为模式匹配，称t为正文(text)，p为模式（pattern）,t的长度大于p的长度。如果在t中找到等于p的子串，则匹配成功，否则匹配失败。串的匹配运算可以用C语言的库函数strstr()来完成，这里主要介绍串匹配的实现过程。,设字符串t为t1.n, 字符串p为p1.m.实现模式匹配的算法有Brute-Force算法和KMP两种算法。,Brute-Force算法称为简单算法(简称BF算法)，KMP称为BF算法的改进算法。,17,4.3.2,串的模式匹配算法,1、,Brute-Force算法,(1)Brute-Force算法的设计思想：,将正文,t,的第一个字符和模式p的第一个字符比较，,若,相等,，继续逐个比较后续字符；,若,不等,，从正文,t,的下一字符起，重新与p第一个字符比较。,直到正文t的一个连续子串字符序列与模式p相等。返回值为t中与p匹配的子序列第一个字符的序号（数据下标+1），即匹配成功。,否则，匹配失败，返回值 0。,18,(2) Brute-Force算法的实现,int simp ( char *t, char *p ), int n=strlen(t), m=strlen(p); /*求 t 和 p 的长度*/,int j, i = 0, bool = 0; /*bool=1时表示匹配成功*/,while(i = n-m) & (bool = 0), j=0; /*模式p数组的下标*/,while(j=m-1),if(jm时，其时间复杂度为,O,(,n,m,)。,20,2、,KMP算法,KMP算法是在Brute-Force算法的基础上的模式匹配的改进算法。KMP算法的特点主要是消除了Brute-Force算法的如下缺点：,正文下标i在若干个字符序列比较相等后，只要有一个字符比较不相等便需要把下标i的值回退。,分两种情况分析Brute-Force算法的匹配过程：,21,第一种情况是模式串中无真子串,， 如下图的正文t=“cddcdc”、模式串p=“cdc”的模式匹配过程。当t,0,=p,0,，t,1,=p,1,，t,2,p,2,时，算法中取i=1,j=0，使正文下标i值回退，然后比较t,1,和p,0,。但是因p,1,p,0,，所以一定有t,1,p,0,，实际上接下来就可直接比较t,2,和p,0,。,22,第一次匹配,t,p,c,d,d,c,d,c,c,d,c,i2,j2,失败,第二次匹配,t,p,c,d,d,c,d,c,c,d,c,i,j,失败,第三次,匹配,t,p,c,d,d,c,d,c,c,d,c,i2,j,失败,第四次匹配,t,p,c,d,d,c,d,c,c,d,c,i5,j2,成功,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,0,1,2,3,4,5,0,1,2,0,1,2,0,1,2,3,4,5,23,第二种情况是模式串中有真子串。,设正文t=“abacabab”、模式串p=“abab”。 第一次匹配过程如下图所示。此时, 因p,0,p,1,，t,1,=p,1,，必有t,1,p,0,；又因p,2,=p,0,，p,2,=t,2,，必有t,2,=p,0,， 因此接下来可直接比较t,3,和p,1,。,i3,j3,失败,t,a,b,a,c,a,b,a,b,0 1 2,3,4 5 6 7,p,a,b,a,b,0 1 2,3,i3,j1,失败,t,a,b,a,c,a,b,a,b,0 1 2,3,4 5 6 7,p,a,b,a,b,0 1 2,3,24,总结以上两种情况可以发现，一旦,t,i,和,p,j,比较不相等，正文串的,t,i,（或,t,i,+1,）可直接与模式串的,p,k,（0,k,j,）比较，k的确定与正文串,t,并无关系，而只与模式串,p,本身的构成有关，即从模式串本身就可求出,k,的值。,一般情况下，设t=t,0,t,1,.t,n-1,，p=p,0,p,1,.p,m-1,，当t,i,p,j,（0in,0jm）时，存在,t,i-j,t,i-j+1,t,i-1, = p,0,p,1,p,j-1,”,此时,若模式串中存在可相互重叠的真子串,，满足,p,0,p,1,.p,k-,1, = p,j-k,p,j-k+1,p,j-1,（0kj）,25,则说明模式串中的子串,“p,0,p,1,p,k-1,”,已和正文串,“t,i-k,t,i-k+1,t,i-1,”,匹配。下一次可直接比较,t,i,和,p,k,；,此时,若模式串中不存在可相互重叠的真子串,，则说明在模式串,p,0,p,1,p,j-1,”,中不存在任何以p,0,为首字符的字符串与,“t,i-j,t,i-j+1,t,i-1,”中以,t,i-1,为末字符的字符串匹配，下一次可直接比较,t,i,和,p,0,。,关于模式串中的真子串问题。我们,把模式串中从第一个字符开始到任一个字符为止的模式串中的真子串定义为nextj函数,，则nextj函数定义为,26,next j ,-1 当,j,0 时,max,k,|,0 ,k,j,且,p,0,p,1,p,k,-1,=,p,j-k,p,j-k,+1,p,j,-1,0 其他情况,当模式串,p,中的,p,j,与,正文串,t,的,t,i,比较,不相等时,，模式串,p,中需重新与正文串,t,的,t,i,比较的字符下标为,k,，即,下一次开始比较,t,i,和,p,k,；,若,模式串,p,中不存在如上所说的真子串,，有,next,j,=0,，则,下一次开始比较,t,i,和,p,0,；当,j,=0,时令,next,j,=-1,。,27,KMP算法的思想:,设,t,为正文串，,p,为模式串，设,i,为正文串,t,当前比较字符的下标，,j,为模式串,p,当前比较字符的下标，令,i,和,j,的,初值为,。当,t,i,=,p,j,时,，,i,和,j,分别,增1,再,继续比较,；否则,i,不变，,j,改变为,next,j,值（即模式串右滑）后再继续比较。依次类推，直到出现下列两种情况之一：,一,是,j,退回到某个,j,=next,j,值时有,t,i,=,p,j,，则,i,和,j,分别增1后再继续比较；,二,是,j,退回到,j,=-1,时，令正文串和子串的下标各增1，随后比较,t,i,+1,和,p,0,。这样的循环过程一直进行到变量,i,大于等于size或变量j大于等于size时为止。,28,void failink(char *p), int j=2, k; flink1=0;,while(j=m), k=flinkj-1;,while(k!=0) ,flinkj=k+1; j+;,29,int kmpmatch(char *t, char *p, int *flink), int n=strlen(t), m=strlen(p);,int i=0, j=0, succ=false;,while(i=n)&(!succ), while(j!=0) ,if(j=m) succ=true; return(i-m+1); ,else i+; j+; ,if(!succ) return(0);,30,3、BF与KMP算法的运行效率比较,而此时KMP的情况是：,由于正文串比较位置,i,无须回退，比较次数仅为,n,即使加上计算,nextj,时所用的比较次数,m,，,比较总次数也仅为,n+m=O(nm),，,大大快于BF算法。,回顾BF的最恶劣情况：,t,与,p,之间存在大量的,部分匹配，,比较总次数为：,(n-m+1)*mO(n*m),31,