第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点.

Presentation on theme: "第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点."— Presentation transcript:

1 第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点

2 4.1 串 1、串的基本概念 串名 1)串(又称字符串)是由n(n≥0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）
记为： s =“s0,s1, ……,sn-1” (n≥0 ) 串名 串值（用“ ”括起来）

3 ２)串长　 串中字符的个数（n≥0）。 ３)空串 串中字符的个数为0 时称为空串  。 ４)空白串　由一个或多个空格符组成的串。 ５)子串　 串S中任意个连续的字符序列叫S的子串; S叫主 串。 ６)子串位置　子串的第一个字符在主串中的序号。 ７)字符位置　字符在串中的序号。 ８)串相等　 串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）

4 问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串. 注：串与字符的区别 　　“a” 串，长度为１的串。（它不仅要存储字符‘a’，还要存储该串的长度数据１） 　　‘a’　字符a。(只存储字符‘a’)

5 2、串的抽象数据类型 数据集合：串的数据集合可以表示为字符序列 s0,s1, ……,sn-1，每个数据元素的数据类型为字符类型。 操作集合：
(1)初始化串　Initiate(S) (2)赋值　 Assign(S,T) (3)求串长度　Length(S)

6 (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)

7 3、串和线性表的比较 相同之处：都是线性结构 不如之处： （1）线性表的数据元素类型为任意类型；而串的数据元素类型为字符类型
（2）线性表的插入和删除操作都是只对一个数据元素；而串的插入和删除操作都是对一个子串进行的 （3）串还有一些不同于线性表的其他操作 因此，专门设计串为一个专门的数据结构。 现有的所有高级程序设计语言，如C++，Java等，都提供了专门的串操作函数或串类。

8 3、C语言的串函数 注：用C语言处理字符串时，要调用标准库函数 #include<string.h>
串长度：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); ……

9 例:名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。 算法思想：因为C语言自动在串末尾添加结束标记‘\0‘,所以实现方法是:首先把把原姓名串name的空格改写为‘\0‘(注意此时‘\0‘后边，即指针p+1指示的是原字符串name的姓部分；此时的name表示的是原name的名部分)，再把原name的姓、逗号和名逐步添加到newName中，最后再恢复name为开始时的状态。 设计函数如下：

10 void ReverseName(char *name, char *newName)
{ char *p; p = strchr(name, ' '); //p指在空格' '位置 *p = NULL; //把空格换为NULL，因此name的长度只包括名 strcpy(newName, p+1); //newName等于name的姓 strcat(newName, ","); //newName等于姓加逗号 strcat(newName, name); // newName等于姓加逗号加名 *p =' '; //恢复name为开始时的状态 }

11 4.2 串的存储结构 1、串的顺序存储结构 串的顺序存储结构就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种：
一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程 另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。

12 (1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。
而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种： (1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。 其类成员变量包括： typedef struct { char str[MaxSize]; int length; } String;

13 (2)动态数组结构：用动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。
typedef struct { char *str; int maxLength; int length; } DString; 其中，str指向动态数组的首地址， maxLength表示动态数组的最大个数， length表示串的当前长度，必须满足length ≤ maxLength

14 2、串的链式存储结构 它分为单字符结点和块链两种。 (1)单字符结点链 typedef struct Node { char str;
struct Node *next; } SCharNode;

15 (2)块链 typedef struct Node
{ char str[Number]; struct Node *next; } NCharNode;

16 3．实际应用中串存储结构的选择 在实际应用中，串基本上采用动态数组存储结构： （1）静态数组存储结构下，串的长度参数很难灵活改变。 （2）在应用软件中，串类型的变量是一种介于常量和变量之间的一种变量，既不会像数值变量那样频繁改变，也不会像常量那样一成不变。 （3）链式存储结构中，单字符结点链的空间利用效率太低，块链的操作实现太麻烦。 （4）由于其他三种串的存储结构都存在这样或那样的问题，而动态数组存储结构不仅空间利用效率高，而且可以方便地定义串变量的长度和改变串变量的长度，所以，在实际应用中，串基本上采用动态数组存储结构。

17 4.3 串操作的实现 串的动态数组结构体定义为： typedef struct { char *str; int maxLength;
int length; } DString;

18 （1）初始化操作 void Initiate(DString *S, int max, char *string) { int i, m;
S->length = strlen(string); if(S->length > max) m = S->length; else m = max; S->maxLength = m; S->str = (char *)malloc(sizeof(char)*m); for(i = 0; i < S->length; i++) S->str[i] = string[i]; }

19 方法二： typedef struct { char *str; int length; } DString;
void Initiate(DString *S, char *string) { int i; S->length = strlen(string); S->str = (char *)malloc(sizeof(char)* S->length); for(i = 0; i < S->length; i++) S->str[i] = string[i]; }

20 （2）插入子串操作 { int i; char *p; if(pos < 0) { printf("参数pos出错！");
int Insert(DString *S, int pos, DString T) { int i; char *p; if(pos < 0) { printf("参数pos出错！"); return 0; } else { if(S->length + T.length > S->maxLength) p = (char *)realloc(S->str, (S->length+T.length)*sizeof(char)); for(i = S->length-1; i >= pos; i--) S->str[i+T.length] = S->str[i]; for(i = 0; i < T.length; i++) S->str[pos+i] = T.str[i]; S->length = S->length + T.length; return 1;

21 （3）删除子串操作 int Delete(DString *S, int pos, int len) { int i;
if(S->length <= 0) { printf("数组中未存放字符无元素可删! \n"); return 0; } else if(pos < 0 || len < 0 || pos+len > S->length) { printf(“参数pos和len不合法”); return 0; } else { for(i = pos+len; i <= S->length-1; i++) S->str[i-len] = S->str[i]; S->length = S->length - len; return 1; }

22 （4）取子串操作 int SubString(DString *S, int pos, int len, DString *T)
{ int i;   if(pos < 0 || len < 0 || pos+len > S->length) { printf("参数pos和len出错！"); return 0; } else { for(i = 0; i < len; i++) T->str[i] = S->str[pos+i];   T->length = len; return 1;

23 （5）撤消操作 void Destroy(DString *S) { free(S->str);
S->maxLength = 0; S->length = 0; }

24 例4-3 编写一个程序测试上述动态数组存储结构下串操作函数的正确性。
#include <stdio.h> #include <malloc.h> #include <string.h> #include"DString.h"   void main(void) { DString myString1, myString2, myString3; int i, max1 = 1, max2 = 1, max3 = 1; /*测试初始化函数*/ Initiate(&myString1, max1, "Data "); Initiate(&myString2, max2, "Structure"); Initiate(&myString3, max3, ""); 

25 /*测试插入函数*/ Insert(&myString2, 0, myString1); for(i = 0; i < myString2.length; i++) printf("%c", myString2.str[i]); printf("\n");   /*测试删除函数*/ Delete(&myString2, 0, 5); Destroy(&myString1); Destroy(&myString2); Destroy(&myString3); } 

26 （1）max1、max2 、max3 都很小，但程序初始化时能根据当前需要的字符串长度申请空间
程序运行输出为： Data Structure Structure 注意： （1）max1、max2 、max3 都很小，但程序初始化时能根据当前需要的字符串长度申请空间 （2）插入子串时，原先长度不够，程序可以根据实际需要的字符个数重新申请内存空间

27 4.3 串的模式匹配算法 串的查找操作也称做串的模式匹配操作，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。

28 1、 Brute-Force算法 将主串S的第一个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符；
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 –1。

29 (2) Brute-Force算法的实现 int BFIndex(DString S, int start, DString T) {
int i = start, j = 0, v; while(i < S.length && j < T.length) if(S.str[i] == T.str[j]) i++; j++; } else i = i-j+1; j = 0; if(j == T.length) v = i-T.length; else v = -1; return v;

30 (3)BF算法的时间复杂度 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m) 最好的情况是：一配就中！主串的前m个字符刚好等于模式串的 m个字符，只比较了m次，时间复杂度为O(m)。 最恶劣情况是：模式串的前m-1个字符序列与主串的相应字符序列比较总是相等，但模式串的第m个字符和主串的相应字符比较总是不等，此时模式串的m个字符序列必须和主串的相应字符序列块一共比较n-m+1，所以总次数为:m*(n-m+1),因此其时间复杂度为O(n×m)。

31 2、KMP算法 KMP算法是在BruteForce算法的基础上的模式匹配的改进算法。KMP算法的特点主要是消除了Brute-Force算法的如下缺点： 主串下标i在若干个字符序列比较相等后，只要有一个字符比较不相等便需要把下标i的值回退。分两种情况分析Brute-Force算法的匹配过程： 第一种情况是模式串中无真子串， 如下图的主串s=“cddcdc”、模式串t=“cdc”的模式匹配过程。当s0=t0，s1=t1，s2≠t2时，算法中取i=1,j=0，使主串下标i值回退，然后比较s1和t0。但是因t1≠t0，所以一定有s1≠t0，实际上接下来就可直接比较s2和t0。

32 第一次匹配 s＝ t＝ c d i＝2 j＝2 失败 第二次匹配 i＝１ j＝０ 第三次匹配 第四次匹配 i＝5 成功

33 第二种情况是模式串中有真子串。设主串s=“abacabab”、模式串t=“abab”。 第一次匹配过程如下图所示。此时, 因t0≠t1，s1=t1，必有s1≠t0；又因t0=t2，s2=t2，必有s2=t2， 因此接下来可直接比较s3和t1。 s＝ t＝ a b c i＝3 j＝3 失败

34 总结以上两种情况可以发现，一旦si和tj比较不相等，主串的si（或si+1）可直接与模式串的tk（0≤k<j）比较，k的确定与主串s并无关系，而只与模式串t本身的构成有关，即从模式串本身就可求出k的值。 一般情况下，设s="s0s1...sn-1"，t="t0t1...tm-1"，当si≠tj（0≤i<n,0≤j<m）时，存在 "si-jsi-j+1…si-1" = "t0t1…tj-1“ 此时若模式串中存在可相互重叠的真子串，满足 "t0t1...tk-1" = "tj-ktj-k+1…tj-1" （0<k<j）

35 则说明模式串中的子串“t0t1…tk-1”已和主串“si-ksi-k+1…si-1”匹配。下一次可直接比较si和tk；
此时若模式串中不存在可相互重叠的真子串，则说明在模式串t0t1…tj-1”中不存在任何以t0为首字符的字符串与“si-jsi-j+1…si-1”中以si-1为末字符的字符串匹配，下一次可直接比较si和t0。 关于模式串中的真子串问题。我们把模式串中从第一个字符开始到任一个字符为止的模式串中的真子串定义为next［j］函数，则next［j］函数定义为

36 next[ j ]＝ 当j＝0时 max { k | 0<k<j 且‘t0 t1 …tk-1’=‘tj-k tj-k+1…tj-1’ } 其他情况 当模式串t中的tj与主串s的si比较不相等时，模式串t中需重新与主串s的si比较的字符下标为k，即下一次开始比较si和tk； 若模式串t中不存在如上所说的真子串，有next［j］=0，则下一次开始比较si和t0；当j=0时令next［j］=-1。

37 KMP算法的思想: 设s为主串，t为模式串，设i为主串s当前比较字符的下标，j为模式串t当前比较字符的下标，令i和j的初值为０。当si = tj时，i和j分别增1再继续比较；否则i不变，j改变为next[j]值（即模式串右滑）后再继续比较。依次类推，直到出现下列两种情况之一：一是 j退回到某个j=next[j]值时有si = tj ，则i和j分别增1后再继续比较；二是j退回到j=-1时，令主串和子串的下标各增1，随后比较si+1和t0 。这样的循环过程一直进行到变量i大于等于size或变量j大于等于size时为止。

38 3、BF与KMP算法的运行效率比较 回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)*m＝O(n*m)
而此时KMP的情况是：由于主串比较位置i无须回退，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法。

39 作业 1)习题4-1，4-2 ，4-4 ，4-7 习题4-12，4-15