算法与数据结构 第3章 字符串.ppt

1、第三章 字符串,首先介绍字符串的相关概念，引入字符串的抽象数据类型， 然后具体给出两种字符串的表示方法：顺序表示和链接表示，分别给出它们的存储结构和主要操作的实现算法。 本章的重点在第3节，详细讨论了无回溯的模式匹配算法。,目录,3.1字符串及其抽象数据类型 3.1.1基本概念 3.1.2抽象数据类型 3.2字符串的实现 3.2.1顺序表示 3.2.2链接表示 3.3模式匹配 3.3.1朴素的模式匹配 3.3.2无回溯的模式匹配,3.1 字符串及其抽象数据类型,3.1.1 基本概念 字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。 一个串可以记作s=s0s1sn-1

2、（n 0），其中s是串的名字，双引号括起来的字符序列s0s1sn-是串的值。 例如： A = 123B = ABBABBCC = BBD = BB E = ,一个串中包括的字符个数称作这个串的长度。长度为零的串称为空串，它不包括任何字符，写作s=“”。空字符也是一个字符，由一个或多个空字符构成的字符串“ ”不是空串。 字符串s1中任意个连续的字符组成的子序列s2被称为是s1的子串，而称s1是s2的主串。 特别地，空串是任意串的子串。任意串s都是s本身的子串。 除s本身之外，s的其它子串称为s的真子串。 子串在主串中的位置指的是该子串的第一个字符在主串中的位置。,3.1.2 抽象数据类型,ADT

3、 String is operations String createNullStr (void) 创建一个空串。 int IsNullStr ( String s ) 判断串s是否为空串，若为空串，则返回1，否则返回0。 int length ( String s ) 返回串s的长度。,String concat (String s1, Sting s2 ) 返回将串s1和s2拼接在一起构成的一个新串。 String subStr (String s, int i, int j ) 在串s中，求从串的第i个字符开始连续j个字符所构成的子串。 int index (String s1, Str

4、ing s2 ) 如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。 end ADT String,3.2 字符串的实现,顺序表示 链接表示,3.2.1 顺序表示,字符串的顺序表示，就是把串中的字符，顺序地存储在一 组地址连续的存储单元中。其类型定义为： struct SeqString /* 顺序串的类型 */ int MAXNUM; /* 串允许的最大字符个数 */ int n;/* 串的长度，nMAXNUM */ char *c; ; typedef struct SeqString *PSeqString;,例如：串s = “abcdef”，用顺序表示方式，假设s是str

5、uct SeqString类型的变量，那么它的元素在数组中的存放方式如下图所示：,字符串运算1： 创建空顺序串 创建空串的方法与创建空顺序表类似， 可有如下程序实现： PSeqString createNullStr_seq( int m ),字符串运算2： 求顺序表示的串的子串 PSeqString subStr_seq(PSeqString s,int i,int j) 求从s所指的顺序串中第i(i0)个字符开始连续取j个字符所构成的子串。 首先要创建一个空串，给子串分配空间（这由算法3.1实现）。然后判断所给参数i ，j的值是否合理，i ，j的取值应满足1 i s-n，j0。但可能会出现

6、这种情况：j的值太大，从i开始在s中取不到j个字符，这时可根据串的长度算出串s中从i开始到串尾的字符个数，并修改j的值，从而将串s中从i开始到串尾的j个字符都拷到子串中。 程序实现,3.2.2 链接表示,在串的链接表示中，每个结点包含两个字段：字符和指针，分别用于存放字符和指向下一个结点的指针。这样一个串就可 用一个单链表来表示，其类型定义为： struct StrNode;/* 链串的结点 */ typedef struct StrNode *PStrNode;/* 结点指针类型 */ struct StrNode /* 链串的结点结构 */ char c; PStrNode link; ;

7、 typedef struct StrNode *LinkString; /* 链串的类型 */,例如：串s = abcdef，按单链表存储时，假设s是LinkString类型的变量，那么它的存储结构如图3.2(a)所示。同样为了方便处理，可在第一个结点之前增加一个头结点，如图3.2(b)所示。也可以采用循环表的形式存储串，具体形式请看图3.2(c)。,字符串运算1：创建带头结点的空链串 创建空串的方法与创建空链表类似 ， 可有如下程序实现： LinkString createNullStr_link( void ),字符串运算2：求单链表示的串的子串 LinkString subStr_li

8、nk(LinkString s,int i,int j) 求从s所指的带头结点的链串中第i(i0)个字符 开始连续取j个字符所构成的子串。 这里首先要为链串结构和头结点申请空间，创建一个 空链表，这由算法3.3实现。然后判断所给参数i ，j的值是 否合理，i ，j的取值应为i0，j0。接着从s-head开始找第 i个结点，找到后，就从该结点开始，为子串中的结点申请 空间，并将元素值拷过去。 程序实现,3.3 模式匹配,设有两个串t和p：t = t0t1tn-1p = p0p1pm-1 其中1mn（通常有m n）。我们的任务是要在t中找出一个与p相同的子串。 通常把t称为目标，把p称为模式。从目

9、标t中查找与模式p完全相同的子串的过程叫作模式匹配。 匹配结果有两种：如果t中存在等于p的子串，就指出该子串在t中的位置，称为匹配成功；否则称为匹配失败。,3.31 朴素的模式匹配,基本思想是：用p中的字符依次与t中的字符比较（见图3.3-(a)），如果t0 = p0，t1 = p1，tm-1 = pm-1，则匹配成功，返回第一次出现的位置是从第一个字符t0开始。否则必有某个i（0im-1），使得ti pi，这时可将p右移一个字符，用p中字符从头p0开始与t中字符t1依次比较（见图3.3-b），如此反复执行，直到下面两种情况之一：或者到达某步时，ti = p0，ti+1 = p1，ti+m-1

10、 = pm-1，匹配成功，返回第一次出现的位置是从t中第i+1个字符ti开始，即是找到的（第一个）与模式p相同的子串；或者一直将p移到无法与t继续比较为止，则匹配失败。 程序实现,设目标串以tabbaba和paba为例，s的长度为n（n=6），t的长度为m（m=3）,该算法简单，易于理解，但效率不高，一旦比较不等， 就将p所指的串右移一个字符，并从p0（算法中用p- c0表示）开始比较。在最坏的情况下，每趟比较 都在最后出现不等，最多比较nm1趟，总比较次 数为m*(nm1)，由于在一般情况下mn，所以 算法运行时间为O(m*n)。,3.3.2 无回溯的模式匹配,为要找到一个无回溯的匹配算法，

11、关键在于当匹配过程中，一旦pi和tj比较不等，即： subStr(p,1,i-1)subStr(t,j-i+1,i-1)， pitj要能立即确定右移的位数和继续（无回溯的）比较的字符.,把这个字符记为pk，显然有ki，并且对不同的i，k值也不相同。Knuth等人发现这个k值仅依赖于模式p本身前i个字符的组成，而与目标t无关。 下面用nexti表示与pi对应的k值，其意义在于：一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符p nexti与tj进行比较。 特别地，如果p中任何字符都不必再与tj进行比较（这个nexti下面用-1表示），可以直接从tj+1和p0开始比较。,对任何模

12、式p，只要我们能确定nexti（i0，1，m-1）的值，就可以如下加速匹配的过程：当pitj时，直接右移inexti个字符，如果nexti大于等于0，则从tj与p nexti继续比较，否则从tj1与p0继续比较下去。 在已知next数组的前提下，无回溯的匹配算法可以实现为： int pMatch(PSeqString t,PSeqString p, int *next),仔细分析执行过程，j的值在循环中只增不减。由于j的初值为0，循环过程中保持jn（第7行），所以循环体中（第9行）j+的语句最多执行n次，从而与它相邻的（第9行）i+语句最多也不超过n次；另外i的初值（第6行）为0，循环中唯一能

13、使i减少的语句是（第11行）i=nexti（每次执行至少减1），由于一旦执行i=nexti,而使i=-1,那么下步必定会执行（第9行）i+; j+，所以循环中，执行（第11行）inexti的次数，不会超过i+的执行次数加1。 根据上面分析可知：算法3.6的时间代价为O()。,例子,taabcbabcaabcaababcn18， p“abcaababc”, m9。,next数组的存在性,在p与任意的目标t匹配时，若发现pitj，则意味着p0，p1，pi-1已与t中对应的字符进行过比较，而且是相等的（见图3.5(a)），否则便轮不到pi与tj比较。因此，图3.5(a)与3.5(b)相同。 然后，把

14、p右移k位，希望用p与tj继续比较，这意味着，tj以前的比较工作（相当于用p0pi-1的一个前缀（p0pk-1）与它的一个长度相同的后缀（pi-kpi-1）进行比较）,都已经全部相等（图3.6）。,图3.5 发现pitj时的状态,图3.6 p0p-1的前缀与后缀比较,因此，我们可以在p0pi-1中，求出其相同的而且是最大的前缀与后缀的长度，设它是k（0ki1）。显然这个值不但存在，而且仅仅依赖于本身，与任何无关。 当右移量为ik时，相同的前后缀恰好对齐，pk与tj对齐。我们用不着去比较这一对前后缀，因为已经知道它们是相等的。当右移量小于ik时，也用不着比较，因为根据k的意义，此时用长度大于k的

15、前后缀对齐，比较结果必定不相等。当右移量大于ik时，又可能错过目前匹配成功的机会。由此可见，若在匹配时发现pitj，即可直接地把p右移ik位，并且只从pk与tj开始向右比较。这样做，不但实现了没有回溯，同时并没有丢失任何匹配成功的机会。,通过上述分析，可以知道求nexti的关键，就是求出p0pi-1中最大相同的前缀与后缀的长度。而求出p0pi-1中最大相同的前缀与后缀的问题，也就是需要判断：p0pi-2 是否等于p1pi-1 如果不等，继续判断p0pi-3 是否等于p2pi-1等等。,作为一种特殊情况，对于任何而言，当i0时，都可以令next-1。因为如果p0与tj比较不等，只能用p0与tj+

16、1去比较，也就是说不存在一个pnext0可以再与tj比较。 另外根据前面的讨论，可以知道：对于任意的i（0im）有nextii；同时，如果p0pi-1中最大相同的前缀与后缀的长度k，那么p0pi中最大相同的前缀与后缀的长度为k+1。加上有next-1作为基础，就可以依次计算出next， next，等值。在计算nexti+1时，充分利用已经求出的next0，next1，nexti的值，结果使得计算nexti+1的过程，有点类似于前面无回溯的模式匹配。 程序实现,算法改进 按上述方法求出的next数组，已可用于无回溯的匹配，但是还可以进一步改善。试想，按上面算法求出k后，若pkpi，则当发现pit

17、j时，用pk与tj比较，也必然不相等。应该再右移，用pnextk与tj比较。既然预先就知道这种结局，理应预先避免走这个弯路。这只要把第7行修改为： if (pk!= pi) nextik ; else nextinextk ; 这种改进是为了使nexti的值尽可能变得更小些，以便在匹配时更多地右移。 程序实现,以上算法从形式上来看，这是一个二重循环，每重循环最多执行m次，最大运行时间可能达到O(m2)。但是仔细分析一下，因为每执行一次外层（第4行）循环，i严格增1（第6行），所以外层循环正好执行m1次；另外k的值从（第2行）-1开始，k+恰好执行（第6行）m1次，并且只有在这一语句中k被增值。而在内层循环（第5行）中，语句knextk至少使k减少1，所以整个算法中，这个语句的执行次数累计起来不可能超过m1次（否则，k将小于-1，这是不可能的），所以内层循环总的执行次数最大为m1。因此算法的执行时间为O(m)。与算法3.6的执行