数据结构 第4章.ppt

1、第4章 串,4.1 串的定义 4.2 抽象数据类型串的实现 4.3 串的应用举例：文本编辑,4.1 串的定义,串(String)是零个或多个字符组成的有限序列。 一般记为： S=a1a2.an (n0) 其中S是串的名字, 用单引号括起来的字符序列是串的值，ai(1in)可以是字母、数字或其它字符。n是串中字符的个数, 称为串的长度，n=0时的串称为空串 (Null String)。,串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 假如有串A=China B

2、eijing, B=Beijing, C=China, 则它们的长度分别为13、7和5。B和C是A的子串, B在A中的位置是7, C在A中的位置是1。 当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等。,串的抽象数据类型定义如下: ADT String 数据对象: D=ai| ai CharacterSet, i=1, 2, , n; n0 数据关系: R=| ai-1, ai D, i=2, , n; n0 基本操作: (1) StrAsign(S, chars) 初始条件: chars是字符串常量。 操作结果: 生成一个值等于c

3、hars的串S。,(2) StrInsert(S, pos, T) 初始条件: 串S存在, 1posStrLength(S)+1。 操作结果: 在串S的第pos个字符之前插入串T。 (3) StrDelete(S, pos, len) 初始条件: 串S存在, 1posStrLength(S)-len+1。 操作结果: 从串S中删除第pos个字符起长度为len的子串。 (4) StrCopy(S, T) 初始条件: 串S存在。 操作结果: 由串T复制得串S。,(5) StrEmpty(S) 初始条件: 串S存在。 操作结果: 若串S为空串, 则返回TRUE, 否则返回FALSE。 (6) Str

4、Compare(S, T) 初始条件: 串S和T存在。 操作结果: 若ST, 则返回值0;如S=T, 则返回值=0;若ST, 则返回值0。 (7) StrLength(S) 初始条件: 串S存在。 操作结果: 返回串S的长度, 即串S中的元素个数。,(8) StrClear(S) 初始条件: 串S存在。 操作结果: 将S清为空串。 (9) StrCat(S, T) 初始条件: 串S和T存在。 操作结果: 将串T的值连接在串S的后面。 (10) SubString(Sub, S, pos, len) 初始条件: 串S存在, 1posStrLength(S)且 1lenStrLength(S)-p

5、os+1。 操作结果: 用Sub返回串S的第pos个字符起长度为len的子串。,(11) StrIndex(S, T, pos) 初始条件: 串S和T存在, T是非空串, 1posStrLength(S)。 操作结果: 若串S中存在与串T相同的子串, 则返回它在串S中第pos个字符之后第一次出现的位置， 否则返回0。 (12) StrReplace(S, T, V) 初始条件: 串S, T和V存在, 且T是非空串。 操作结果: 用V替换串S中出现的所有与T相等的不重叠的子串。 (13) StrDestroy(S) 初始条件: 串S存在。 操作结果: 销毁串S。,4.2 抽象数据类型串的实现,4

6、.2.1 定长顺序串,define MAXLEN 20 typedef struct /* 串结构定义 */ char chMAXLEN; int len; SString;,定长顺序串是将串设计成一种结构类型, 串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似, 用一组地址连续的存储单元存储串的字符序列。,在进行串的插入时，插入位置pos将串分为两部分（假设为A、 B, 长度为LA、 LB）, 及待插入部分（假设为C, 长度为LC）, 则串由插入前的AB变为ACB， 可能有三种情况： （1） 插入后串长(LA+LC+LB)MAXLEN，则将B后移LC个元素位置，再将C插入。

7、 （2） 插入后串长MAXLEN且pos+LCMAXLEN且pos+LCMAXLEN，则B的全部字符被舍弃（不需后移），并且C在插入时也有部分字符被舍弃。,与上述类似， 在进行串的连接时（假设原来串为A， 长度为LA, 待连接串为B， 长度为LB）， 也可能有三种情况： （1）连接后串长MAXLEN， 则直接将B加在A的后面。 （2）连接后串长MAXLEN且LAMAXLEN且LA=MAXLEN， 则B的全部字符被舍弃（不需连接）。,置换时的情况较为复杂，假设原串为A、长度为LA，被置换串为B、长度为LB, 置换串为C、 长度为LC，每次置换位置为pos，则每次置换有三种可能： （1） LB=L

8、C： 将C复制到A中pos起共LC个字符处。 （2） LBLC： 将A中B后的所有字符前移LB-LC个字符位置，然后将C复制到A中pos起共LC个字符。 （3） LBLC： 将A中B后的所有字符后移LC-LB个字符位置，然后将C复制到A中pos起共LC个字符，此时可能会出现串插入时的三种情况， 应按三种情况作相应处理。,(1) 串插入函数。 StrInsert(s, pos, t) /*在串s中序号为pos的字符之前插入串t */ SString *s, t; int pos; int i; if (poss-len+1) return(0); /* 插入位置不合法 */ if (s-len

9、+ t.lenlen + t.len-1;i=t.len + pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos-1=t.chi; s-len=s-len+t.len; ,else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXLEN-1;it.len+pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos-1=t.chi; s-len=MAXLEN; else /* 串t的部分字符序列要舍弃 */ for (i=0;ichi+pos-1=t.chi; s-len

10、=MAXLEN; return(1); ,【算法4.1 串插入函数】,(2) 串删除函数。 StrDelete(s, pos, len) /* 在串s中删除从序号pos起len个字符 */ SString *s; int pos, len; int i; if (pos(s-len-len+1) return(0); for (i=pos+len-1;ilen;i+) s-chi-len=s-chi; s-len=s-len - len; return(1); ,【算法4.2 串删除函数】,(3) 串复制函数。 StrCopy(s, t) /* 将串t的值复制到串s中 */ SString *

11、s, t; int i; for (i=0;ichi=t.chi; s-len=t.len; ,【算法4.3 串复制函数】,(4) 判空函数。 StrEmpty(s) /* 若串s为空(即串长为0), 则返回1, 否则返回0 */ SString s; if (s.len=0) return(1); else return(0); ,【算法4.4 判空函数】,(5) 串比较函数。 StrCompare(s, t) /* 若串s和t相等, 则返回0；若st，则返回0；若st， 则返回0 */ SString s, t; int i; for (i=0;is.len ,【算法4.5 串比较函数】,

12、(6) 求串长函数。 StrLength(s)/* 返回串s的长度 */ SString s; return(s.len); ,【算法4.6 求串长函数】,(7) 清空函数。 StrClear(s) /* 将串s置为空串 */ SString *s; s-len=0; return(1); ,【算法4.7 清空函数】,(8) 连接函数。 StrCat(s, t) /* 将串t连接在串s的后面 */ SString *s, t; int i, flag; if (s-len + t.lenlen; ilen + t.len; i+) s-chi=t.chi-s-len; s-len+=t.len

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

14、ens.len-pos+1) sub-len=0;return(0); else for (i=0;ichi=s.chi+pos-1; sub-len=len;return(1); ,【算法4.9 求子串函数】,(10) 定位函数。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */ SString s, t; int pos; int i, j; if (t.len=0) return(0); i=pos-1;j=0; while (i=t.len) return(i-j); else return(0); ,【算法4.10 定位函数】,4.2.2 堆串,假设以一维数组

15、heap MAXSIZE 表示可供字符串进行动态分配的存储空间，并设 int free 指向heap 中未分配区域的开始地址(初始化时free=0) 。在程序执行过程中，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。 此时，堆串可定义如下：,typedef struct int len； int start； HeapString；,其中len域指示串的长度，start域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映象。系统中所有串名的存储映象构成一个符号表。 图4.1是一个堆存储及

16、符号表，其中a=a program， b=string ， c=process,图4.1 堆串的存储映象示例,HeapMAXSIZE,Free=23,符号表,在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”实现堆串。此时，堆串可定义如下：,typedef struct char * ch； int len； HString；,(1) 串赋值函数。 StrAssign(s， tval) /* 将字符常量tval的值赋给串s */ HString *s; char *tval; int len， i=0

17、; if (s-ch! =NULL) free(s-ch); while (tvali! =0) i+; len=i; if (len) s-ch=(char *)malloc(len); if (s-ch=NULL) return(0); for (i=0;ichi=tvali; else s-ch=NULL; s-len=len; return(1); ,【算法4.11 串赋值函数】,(2) 串插入函数。,StrInsert(s， pos， t) /* 在串s中序号为pos的字符之前插入串t */ HString *s， t; int pos; int i; char *temp; if

18、(poss-len | s-len=0) return(0); temp=(char *)malloc(s-len + t.len); if (temp=NULL) return(0); for (i=0;ichi; for (i=0;ilen;i+) tempi + t.len=s-chi; s-len+=t.len; free(s-ch);s-ch=temp; return(1); ,【算法4.12 串插入函数】,(3) 串删除函数。 StrDelete(s， pos， len) /* 在串s中删除从序号pos起的len个字符 */ HString *s; int pos， len; in

19、t i; char *temp; if (pos(s-len - len) return(0); temp=(char *)malloc(s-len - len); if (temp=NULL) return(0); for (i=0;ichi; for (i=pos;ilen - len;i+) tempi=s-chi+len; s-len=s-len-len; free(s-ch);s-ch=temp; return(1); ,【算法4.13 串删除函数】,(4) 串复制函数。 StrCopy(s， t) /* 将串t的值复制到串s中 */ HString *s， t; int i; s-

20、ch=(char *)malloc(t.len); if (s-ch=NULL) return(0); for (i=0;ichi=t.chi; s-len=t.len; return(1); ,【算法4.14 串复制函数】,(5) 判空函数。 StrEmpty(s) /* 若串s为空(即串长为0)，则返回1，否则返回0 */ HString s; if (s.len=0) return(1); else return(0); ,【算法4.15 判空函数】,(6) 串比较函数。 StrCompare(s， t) /* 若串s和t相等， 则返回0； 若st， 则返回1； 若st， 则返回-1 *

21、/ HString s， t; int i; for (i=0;is.len ,【算法4.16 串比较函数】,(7) 求串长函数。 StrLength(s) /* 返回串s的长度 */ HString s; return(s.len); ,【算法4.17 求串长函数】,(8) 清空函数。 StrClear(s) /* 将串s置为空串 */ HString *s; if (s-ch! =NULL) free(s-ch); s-ch=NULL; s-len=0; return(1); ,【算法4.18 清空函数】,(9) 连接函数。 StrCat(s， t) /* 将串t连接在串s的后面 */ H

22、String *s， t; int i; char *temp; temp=(char *)malloc(s-len + t.len); if (temp=NULL) return(0); for (i=0;ilen;i+) tempi=s-chi; for (i=s-len;ilen + t.len;i+) tempi=t.chi-s-len; s-len+=t.len; free(s-ch);s-ch=temp; return(1); ,【算法4.19 连接函数】,(10) 求子串函数。 SubString(sub， s， pos， len) /* 将串s中序号pos起的len个字符复制到

23、sub中 */ HString *sub， s; int pos， len; int i; if (sub-ch!=NULL) free(sub-ch); if (poss.len | lens.len-pos) sub-ch=NULL;sub-len=0;return(0);,else sub-ch=(char *)malloc(len); if (sub-ch=NULL) return(0); for (i=0;ichi=s.chi+pos; sub-len=len; return(1); ,【算法4.20 求子串函数】,(11) 定位函数。 StrIndex(s， pos， t) /*

24、求串t在串s中的位置 */ HString s， t; int pos; int i， j; if (s.len=0 | t.len=0) return(0); i=pos;j=0; while (i=t.len) return(i-j); else return(0); ,【算法4.21 定位函数】,模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两 个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到 等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置 (或序号)，否则匹配失败，返回-1。t也称为模式。为了运算方便，设 字符串的长度存放在0号单

25、元，串值从1号单元存放，这样字符序号与存储位置一致。,补充：,简单的模式匹配算法,算法思想如下：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t.len，否则，匹配失败。,设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下图所示：,第一趟,第二趟

26、,第三趟,第四趟,第五趟,第六趟,简单模式匹配的匹配过程,依据这个思想，算法描述如下: int StrIndex_BF(char *s,char *t) /*从串s的第一个字符开始找首次与串t相等的子串*/ int i=1,j=1; while (it.len) return (i-t.len);/*匹配成功，返回存储位置*/ else return 1; ,该算法简称为BF算法。分析它的时间复杂度，设串s长度为n，串t长度为m。 匹配成功的情况下，考虑两种极端情况： 在最好情况下，每趟不成功的匹配都发生在第一对字符比较时： 例如：s=aaaaaaaaaabc t=bc 设匹配成功发生在si处

27、，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是： 即最好情况下的时间复杂度是O(n+m)。 在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符： 例如：s=aaaaaaaaaaab t=aaab 设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏好情况下平均比较的次数是：,即最坏情况下的时间复杂度是

28、O(n*m)。,上述算法中匹配是从s串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数pos：StrIndex(shar *s,int pos,char *t)，比较的初始位置定位在pos处。,改进后的模式匹配算法,BF算法简单但效率较低，一种对BF算法做了很大改进的模式匹配算法是克努特(Knuth)，莫里斯(Morris)和普拉特(Pratt)同时设计的，简称KMP算法。,（1）KMP算法的思想： 分析上面算法的执行过程, 造成BF算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于s串要回到本趟开始字符的下一个字符，t串要回到第一个字符。而这些回溯并不是

29、必要的。如上图所示的匹配过程，在第三趟匹配过程中，s3 s6和t1 t4是匹配成功的，s7t5匹配失败，因此有了第四趟，其实这一趟是不必要的：由图可看出，因为在第三趟中有s4=t2，而t 1t2，肯定有t1s4 。同理第五趟也是没有必要的，所以从第三趟之后可以直接到第六趟，进一步分析第六趟中的第一对字符s 6和t1的比较也是多余的，因为第三趟中已经比过了s6和t4，并且s6=t4，而t 1=t4，必有s 6=t1，因此第六趟的比较可以从第二对字符s7和t2开始进行，这就是说，第三趟匹配失败后，指针i不动，而是将模式串t向右“滑动”，用t2 “对准” s 7继续进行，依此类推。这样的处理方法指针

30、i是无回溯的。,综上所述，希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk 对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立： t1 t2 tk-1 =si-k+1 si-k+2 si-1 (1) (1)式左边是tk前面的k-1个字符，右边是si 前面的k-1个字符。 而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是： t1 t2 tj-1 =si-j+1 si-j+2 si-1

31、(2) 因为kj，所以有： tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (3) (3)式左边是 tj前面的k-1个字符，右边是si 前面的k-1个字符， 通过(4.1)和(4.3)得到关系： t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 (4) 结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。,（2）next函数 模式中的每一个tj都对应一个k值，由(4)式可知，这个k值仅依赖与模式t本

32、身字符序列的构成，而与主串s无关。我们用nextj表示tj对应的k值，根据以上分析，next函数有如下性质： nextj是一个整数，且0nextjj； 为了使t的右移不丢失任何匹配成功的可能，当存在多个满足(4)式的k 值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个； 如果在tj前不存在满足(4.4)式的子串，此时若t1tj，则k=1; 若t1=tj，则k=0; 这时“滑动”的最远，为j-1个字符即用t1 和sj+1继续比较。 因此，next函数定义如下 ：,设有模式串：t=abcaababc，则它的next函数值为：,(3) KMP算法,在求得模式的next函

33、数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中sitj，则i和j分别增，若sitj 匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增继续进行匹配; 另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增，表明从主串的下一个字符起和模式重新开始匹配。,设主串s=“acabaabaabcacaabc”，子串t=“abaabcac”，下图是一个利用next函数进行匹配的

34、过程示意图。,在假设已有next函数情况下，KMP算法如下： int StrIndex_KMP(char *s,char *t,int pos) /*从串s的第pos个字符开始找首次与串t相等的子串*/ int i=pos,j=1,slen,tlen; while (it.len) return i-t.len; /*匹配成功，返回存储位置*/ else return 1; ,(4)如何求next函数,由以上讨论知，next函数值仅取决于模式本身而和主串无关。 我们可以从分析next函数的定义出发用递推的方法求得next函数值。 由定义知： next1=0 (4.5) 设nextj=k，即有： t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 (4.6) nextj+1=?可能有两种情况： 第一种情况：若tk tj 则表明在模式串中 t1 t2 tk =tj-k+1 tj-k+2 tj (4.7) 这就是说nextj+1=k+1，即 nextj=nextj+1 (4.8) 第二种情况：若tk tj 则表明在模式串中 t1 t2 tk tj-k+1 tj-k+2 tj (4.9),此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是