数据结构(严蔚敏)课件第4章.ppt

《数据结构(严蔚敏)课件第4章.ppt》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)课件第4章.ppt（90页珍藏版）》请在装配图网上搜索。

1、 第四章 串 【 课前思考 】 1. 串就是线性表 的结论是否正确？ 从数据结构的观点来说，串是一种特殊的 线性表 ;但就数据类型而言，串不是线性表。 2. 串和线性表的主要差别是什么？ 希望你带着这个问题开始这一章的学习， 并能在学完这一章的内容之后能得出正确 的结论。 【 学习目标 】 1. 理解“串”类型定义中各基本操作的特 点，并能正确利用它们进行串的其它操作。 2. 理解串类型的各种存储表示方法。 3. 理解串匹配的各种算法。 【 重点和难点 】 相对于其它各个知识点而言，本章非整个课程 的重点，鉴于串已是多数高级语言中已经实现的数 据类型，因此本章重点仅在于了解串类型定义中各 基本

2、操作的定义以及串的实现方法，并学会利用这 些基本操作来实现串的其它操作。本章的 难点 是理 解实现 串匹配的 KMP算法 的思想，但它不属本章学 习的基本要求，更不是重点学习内容。 【 知识点 】 串的类型定义、串的存储表示、串匹配、 KMP算法 【 学习指南 】 虽然目前各常用的高级语言中都已经实 现了串类型，但由于它是通过软件实现的， 因此作为一个软件工作者还是应该了解串的 实现方法。本章没有必须完成的算法设计题， 如果有兴趣可以试试以下几个题 :4.10， 4.11， 4.13， 4.17， 4.18， 4.23， 4.28,4.30。其中前 6个是练习串的基本操作的应用，后 2个是和

3、KMP算法相关的练习。 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.1串的类型定义 一、 基本概念 1 串的定义 串 ( string) 是由零个或多个字符组成的有限序列 ， 记作 s=a1a2 an， 其中 s为串的名字 ， 用成对的单引号括起 来的字符序列为串的值 ， 但两边的引号不算串值 ， 不包 含在串中 。 ai(1in)可以是字母 、 数字或其它字符 。 n为串中字符的个数 ， 称为串的长度 。 2 空串 不含任何字符的串称为空串，它的长度 n=0，记为 s=。 3 空格串 含有一个或多个空格的串 ， 称为空格串 ， 它的长度 n为 空格的个数 ，

4、一般用符号 “ ” 表示空串 。 串是有限长的字符序 列，由一对单引号相 括，如 : a string 4 子串 、 主串 通常将字符在串中的序号称为该字符在串中的位置 。 子串在主串中的位置则以子串的第一个字符在主串中的 位置来表示 。 若一个串是另一个串中连续的一段 ， 则这个串称为另一 个串的子串 ， 而另一个串相对于该串称为主串 。 例如 ,串 s1=“ abcdefg” ， s2=“ fabcdefghxyz” ， 则 s1为 s2的子串 ， s2相对于 s1为主串 。 另外 ， 空串是任意串的子串 ， 任意串是自身的子串 。 若一个串的长度为 n， 则它的子串数目为 +1， 真子串

5、 个数为 (除串本身以外的子串都称为真子串 )。 当且仅当两个串的值相等时 ,称这两个串是相等的，即 只有当两个串的长度相等 , 并且每个对应位置的字符都相 等时才相等。 2 )1( nn 2 )1( nn 二、串的抽象数据类型的定义如下： ADT String 数据对象 ： D ai |ai CharacterSet, i=1,2,.,n, n0 数据关系 ： R1 | ai-1, ai D, i=2,.,n 基本操作 ： StrAssign ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); i

6、f (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与 T相等的子串 / Index 又如串的置换函数 ： Replace( / 0号单元存放串的长度 或： typedef struct /* 串结构定 义 */ char chMAXLEN ; int len; SString; 按这种串的表示方法实现的串的 运算时，其基本操作为 “ 字符序列 的复制”。 串 的实际长度可在这个予定义长 度的范围内随意设定，超过予定义 长度的串值则被舍去，称之为 “截断” 。 特点 : Status Con

7、cat(SString S1, SString S2, SString / Concat 例如： 串的联接算法中需分三种情况处理： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断 else if (S10 MAXSTRSIZE) / 截断 else / 截断 (仅取 S1) T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLEN S10; T0 = MAXSTRLEN; uncut = FAL

8、SE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; (1) 串插入函数 。 StrInsert(s, pos, t) /*在串 s中序号为 pos的字符之前插入串 t */ SString *s, t; int pos; int i; if (poss-len) return(0); /* 插入位置不合法 */ if (s-len + t.lenlen + t.len-1;i=t.len + pos;i-) s-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch

9、i ; s-len=s-len+t.len; 定长顺序存储的操作实施： 【 算法 串插入函数 】 a b x y z c d e f x y z a b c d e f x y z T 串 S 串 T 串 S 串 ( a ) 插入前 图 4 1 顺序串的插入 ( b ) 插入后 ( i = 3 ) else if (pos+t.lenMAXLEN, 但串 t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i-) s-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch i ; s-len=MAXLEN; els

10、e /* 串 t的部分字符序列要舍弃 */ for (i=0;ich i+pos =t.ch i ; s-len=MAXSTRLEN; return(1); (2) StrDelete(s, pos, len) /* 在串 s中删除从序号 pos起 len个字符 */ SString *s; int pos, len; int i; if (pos(s-len-len) return(0); for (i=pos+len;ilen;i+) s-ch i-len =s-ch i ; s-len=s-len - len; return(1); 【 算法 串删除函数 】 a b c i j k a

11、b c d e f g h i j k ( a ) 删除前 图 4 - 2 顺序串的删除 ( i = 4 , j = 5 ) ( b ) 删除后 (3) StrCopy(s, t) /* 将串 t的值复制到串 s中 */ SString *s, t; int i; for (i=0;ich i =t.ch i ; s-len=t.len; 【 算法 串复制函数 】 (4) StrEmpty(s) /* 若串 s为空 (即串长为 0), 则返回 1, 否则返回 0 */ SString s; if (s.len=0) return(1); else return(0); 【 算法 判空函数 】

12、(5) 串比较函数 。 StrCompare(s, t) /* 若串 s和 t相等 , 则返回 0；若 st， 则返回 1；若 st， 则 返 回 -1 */ SString s, t; int i; for (i=0;is.len return(1); 【 算法 清空函数 】 (8) 连接函数。 Concat(s, t) /* 将串 t连接在串 s的后面 */ SString *s, t; int i, flag; if (s-len + t.lenlen; ilen + t.len; i+) s-ch i =t.ch i-s-len ; s-len+=t.len;flag=1; else

13、if (s-lenlen;ich i =t.ch i-s-len ; s-len=MAXSTRLEN;flag=0; else flag=0;/* 串 s的长度等于 MAXLEN, 串 t不被连接 */ return(flag); 【 算法 连接函数 】 (9) 求子串函数。 SubString(sub, s, pos, len) /* 将串 s中序号 pos起 len个字符复制到 sub中 */ SString *sub, s; int pos, len; int i; if (poss.len | lens.len-pos) sub-len=0;return(0); else for (i

14、=0;ich i =s.ch i+pos ; sub-len=len;return(1); 【 算法 求子串函数 】 (10) 定位函数 。 StrIndex(s, pos, t) /* 求串 t在串 s中的位置 */ SString s, t; int pos; int i, j; if (t.len=0) return(0); i=pos;j=0; while (is.len else return(0); 【 算法 定位函数 】 typedef struct char *ch; / 若是非空串，则按串长分配存储区 ， / 否则 ch为 NULL int length; / 串长度 HSt

15、ring; 二、串的堆分配存储表示 特点：仍用一组地址连续的存储单元 存储串的字符序列，但其存储空间是 在程序执行过程中动态分配而得。 通常， C语言中提供的串类型就是以这种 存储方式实现的。系统利用函数 malloc( )和 free( )进行串值空间的动态管理，为每一个新 产生的串分配一个存储区，称串值共享的存 储空间为 “堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。 这类串操作 实现的算法 为： 先为新生成的串分配一个存储空间，然后 进行串值的复制。 Status Concat(HString / 释放旧空间 if (!(T.ch = (char *) malloc(S

16、1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat Status SubString(HString if (Sub.ch) free (Sub.ch); / 释放旧空间 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 el

17、se / 完整子串 return OK; / SubString Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; 三、串的块链存储表示 也可用链表来存储串值，由于串的数据 元素是一个字符，它只有 8 位二进制数， 因此用链表存储时，通常一个结点中存 放的不是一个字符，而是一个子串。 存储密度 = 数据元素所占存储位 实际分配的存储位 #define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点结构

18、char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的 头和尾指针 int curlen; / 串的 当前长度 LString; 例如 : 在编辑系统中，整个文本编辑区 可以看成是一个串，每一行是一个子串， 构成一个结点。即 : 同一行的串用定长结构 (80个字符 ), 行和行之间用指针相联接。 实际应用时，可以根据问题所需来 设置结点的大小。 这是串的一种重要操作，很多 软件，若有 “编辑” 菜单项的话， 则其中必有 “查找” 子菜单项。 4.3 串的模式匹配算

19、法 子串的定位操作通常称为串的 模式匹 配 ，是各种串处理系统中最重要的操作 之一。 初始条件： 串 S和 T存在 ， T是非空串 ， 1posStrLength(S)。 操作结果： 若主串 S中存在和串 T值相 同的子串返回它在主串 S中 第 pos个字符之后第一次出 现的位置；否则函数值为 0。 首先，回忆一下 串匹配 (查找 )的定义 : INDEX (S, T, pos) 下面讨论以定长顺序结构 表示串时的几种算法。 一、简单算法 二、 首尾匹配算法 三、 KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 一、简单算法 Brute-Force算法 例如

20、,设目标串 s=“ cddcdc” ,模式串 t=“ cdc” 。 s 的长度为 n(n=6),t的长度为 m(m=3)。用指针 i指示目 标串 s的当前比较字符位置 ,用指针 j指示模式串 t的当 前比较字符位置。 BF模式匹配过程如下所示。 第 1 次匹配 s = c d d c d c i = 2 t = c d c j = 2 失败 第 2 次匹配 s = c d d c d c i = 1 t = c d c j = 0 失败 第 3 次匹配 s = c d d c d c i = 2 t = c d c j = 0 失败 第 4 次匹配 s = c d d c d c i = 5

21、t = c d c j = 2 成功 这个算法简单 ,易于理解 ,但效率不高 ,主要原因是 : 主串指针 i在若干个字符序列比较相等后 ,若有一个字 符比较不相等 ,仍需回溯 (即 i=i-j+1)。该算法在最好情 况下的时间复杂度为 O(m),即主串的前 m个字符正好 等于模式串的 m个字符。在最坏情况下的时间复杂度 为 O(n*m)。 int index(SqString s,SqString t) int i=0,j=0,k; while (is.len /*返回匹配的第一个字符的下标 */ else k=-1; /*模式匹配不成功 */ return k; 先 比较模式串的第一个字符，

22、 再 比较模式串的最后一个字符， 最后 比较模式串中从第二个到 第 n-1个字符。 二、 首尾匹配算法 int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹

23、配 else return 0; / 检查中间字符的匹配情况 k = 1; j = 2; while ( j tLength +j; if ( j = tLength ) return i; else +i; / 重新开始下一次的匹配检测 三、模式匹配的改进算法 （ KMP算法） 此方法由克努特 (D.E.Knuth)莫里斯 (J.H.Morris)普拉特 (V.R.Pratt)同时发现。 1.基本思想： 每当一趟匹配过程中出现字符不等时，不 需回溯 i指针，而是利用已得到的部分匹配结果，将模 式串向右滑动尽可能远的一段距离后继续进行比较。 避免多余的、不必要的比较，从而提高算法性能。算法 总

24、在 0(n+m)的时间数量级上完成匹配操作。 a b a b c a b c a c b a b ab c ( a ) 第一趟匹配 s 3 t 3 ( b ) 第二趟匹配 s 7 t 5 ( c ) 第三趟匹配成功 图 K M P 模式匹配过程 a b a b c a b c a c b a b ab cac a b a b c a b c a c b a b a b cac 2.KMP算法匹配实例： (1)模式串 t中没有真子串 真子串 是指模式串 t存在某个 k(0 k j),使得 “ t0t1 tk” =“ tj-ktj-k+1 tj” 成立 。 例如 t=cdc就是这样的模式串 。 在

25、图 4.6中的第一 次回溯 ,当 s0=t0,s1=t1,s2t2时 ,算法中取 i=1,j=0,使主串指 针回溯一个位置 ,比较 s1和 t0。 因 t0t1,所以一定有 s1t0。 另外 ,因有 t0=t2,s0=t0,s2t2,则一定可推出 s2t0,所以也不 必取 i=2,j=0去比较 s2和 t0。 可直接在第二次比较时取 i=3,j=0,比较 s3和 t0。 这样 ,模式匹配过程主串指针 i就可 不必回溯 。 (2)模式串中存在真子串 例如 t=“ abab” ,由于“ t0t1” =“ t2t3” (这里 k=1,j=3),则存在真子串。设 s=“ abacabab” ,t=“

26、abab” ,第一次匹配过程如下所 示。 第 1 次匹配 s = a ba c a ba b i= 3 t = a ba b j= 3 失败 此时不必从 i=1(i=i-j+1=1),j=0重新开始第二次匹 配。因 t0t1,s1=t1,必有 s1t0,又因 t0 =t2,s2=t2,所以必有 s2=t0。因此 ,第二次匹配可直接从 i=3,j=1开始。 现在我们讨论一般情况。 设 s=s0s1s n-1,t=t0t1t m-1,当 sitj (0in-m,0j m)时 ,存在 : t0t1 tj-1=si-jsi-j+1 si-1 (4.1) 若模式串中存在的真子串满足 : t0t1 tk=

27、tj-ktj-k+1 tj (0 k j) (4.2) 由 (4.1)式说明模式串中的子串 t0t1 tk-1已和主串 si-ksi-k+1 si-1匹配 ,下一次可直接比较 si和 tk,若不存在 (4.2) 式 ,则结合 (4.1)式说明在 t0t1 tj-1中不存在任何以 t0为首 字符子串与 si-j+1si-j+2 si-1中以 si-1为末字符的匹配子串 , 下一次可直接比较 si和 t0。 为此 ,定义 nextj函数如下 : maxk|0kj,且 “ t0t1 tk-1” =“ tj-ktj-k+1 tj-1” 当此集合非空时 -1 当 j=0时 0 其他情况 nextj= j

28、 0 1 2 3 tj a b a b nextj -1 0 0 1 t=“ abab” 对应的 next数组如下 : 由模式串 t求出 next值的算法如下 : void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.len-1) if (k=-1 | t.chj=t.chk) /*k为 -1或比较的字符相等时 */ j+;k+; nextj=k; else k=nextk; int KMPIndex(SqString s,SqString t) /*KMP算法 */ int nextMaxSize,i=

29、0,j=0,v; GetNext(t,next); while (is.len /*返回匹配模式串的首字符下标 */ else v=-1; /*返回不匹配标志 */ return v; 设主串 s的长度为 n,子串 t长度为 m,在 KMP算法 中求 next数组的时间复杂度为 O(m),在后面的匹配 中因主串 s的下标不减即不回溯 ,比较次数可记为 n, 所以 KMP算法总的时间复杂度为 O(n+m)。 例如 ,设目标串 s=“ aaabaaaab” ,模式串 t=“ aaaab” 。 s的长度为 n(n=9),t的长度为 m(m=5)。 用指针 i指示目标串 s的当前比较字符位置 ,用指针

30、 j指 示模式串 t的当前比较字符位置。 KMP模式匹配过 程如下所示。 第 1 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 3 , j = n e x t 3 = 2 失败 第 2 次匹配 s = a a a b a aaab i = 3 t = aaaab j = 2 , j = n e x t 2 = 1 失败 第 3 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 1 , j = n e x t 1 = 0 失败 第 4 次匹配 s = a a a b a a a a b i = 3 t = a

31、aaab j = 0 , j = n e x t 0 = - 1 失败 第 5 次匹配 s = a a a b a a a a b i = 9 t = aaaab j = 4 ,返回 9 - 5 = 4 成功 j 0 1 2 3 4 tj a a a a b nextj -1 0 1 2 3 上述定义的 next在某些情况下尚有缺陷。例如 , 模式“ aaaab” 在和主串“ aaabaaaab” 匹配时 ,当 i=3,j=3时 ,s.ch3t.ch3,由 nextj的指示还需进行 i=3、 j=2,i=3、 j=1,i=3、 j=0等三次比较。实际上 ,因为模式 中的第 1、 2、 3个字符

32、和第 4个字符都相等 ,因此 ,不需 要再和主串中第 4个字符相比较 ,而可以将模式一次向 右滑动 4个字符的位置直接进行 i=4,j=0时的字符比较。 KMP算法的改进： 这就是说 ,若按上述定义得到 nextj=k,而模式 中 pj=pk,则为主串中字符 si和 pj比较不等时 ,不需要 再和 pk进行比较 ,而直接和 pnextk进行比较 ,换句话 说 ,此时的 nextj应和 nextk相同。为此将 nextj 修正为 nextvalj。 由模式串 t求出 nextval值 : void GetNextval(SqString t,int nextval) int j=0,k=-1;

33、nextval0=-1; while (jnext，再设一 个对尾指针 q-rear指向链队列尾部。 队列的链式存储结构可定义如下： typedef struct node typedef struct char data; slnode *h; struct node *next; slnode ; slnode *rear;lqtype; 四、思考题 1、 比较链队列与链栈的相同点与不同点。 2、在链队列中， q-rear指针能否省 去 ？若能，怎样才能找到队尾？ 实验六 串的模式匹配 一、实验目的 熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。 二、实验内容 由用户随意输入两个串：主串 S和模式串 T，设 S= s1s2s n ， T= t1t2t m ，且 0m=n。用简单和 KMP模式匹配算法判断模式串 T是否在主 串 S中，若在，则输出模式串在主串的第一匹配位置，否则，匹配失败，返回零 值。 三、实验要点及说明 简单模式匹配算法和 KMP模式匹配算法的主要区别在于后者将有效利用已有的 匹配结果，省去不必要的匹配过程，提高匹配性能。 利用串的顺序存储结构实现实验内容。 四、思考题 能否用串的块链存储结构实现 KMP算法？ 重庆工商大学 计算 机与信息工程学院