• / 30
  • 下载费用:10 金币  

4第四章 串.ppt

关 键 词:
4第四章 串.ppt
资源描述:
第四章 串 (String),重点:串的基本运算、串的匹配算法; 难点:KMP算法。 知识点:串的基本概念串所支持的9种基本运算表示串的数据结构串的匹配算法。,字符串 (String),字符串是 n (  0 ) 个字符的有限序列,记作 S : “c1c2c3…cn”其中,S 是串名字“c1c2c3…cn”是串值ci 是串中字符n 是串的长度。 例如, S = “Tsinghua University”,4.1 串类型的定义,一、定义 (1)串(或字符串)(String)是由零个或多个字符组成的有限序列。一般记作s=“ c1c2c3…cn” (n≥0) (2)n称为串的长度。n=0的串称为空串(Null string)。 (3)子串:串中任意个连续字符组成的字序列。 (4)主串:包含子串的串。 (5)子串在串中的位置:子串的第一个字符在主串中的序号。(从1开始) (6)称两个串是相等的:当且仅当这两个串每个字符对应相等。,4.1 串类型的定义,例:a,b,c,d四个字符串为:a=‘BEI’, b=‘JING’, c=‘BEIJING’, d=‘BEI JING’它们的长度分别为3,4,7,8;a和b都是c和d的子串;a在c中的位置是1,b在c中的位置是4,而b在d中的位置是5。,4.1 串类型的定义,二、串的抽象数据类型—数据对象为字符集的线性表 ADT String{数据对象:D={ ai| ai∈ElemSet,i=1,2, …,n, n≥1}数据关系:R={| ai-1,ai∈D, i=1,2, …,n}基本操作: StrAssign (&T, chars) 初始条件:chars 是串常量。 操作结果:赋于串T的值为 chars。 StrCopy (&T, S) 初始条件:串 S 存在。 操作结果:由串 S 复制得串 T。 DestroyString (&S) 初始条件:串 S 存在。 操作结果:串 S 被销毁。,串的抽象数据类型的定义(续),基本操作: StrEmpty (S) 初始条件:串 S 存在。 操作结果:若 S 为空串,则返回 TRUE,否则返回 FALSE。 StrCompare (S, T) 初始条件:串 S 和 T 存在。 操作结果:若ST,则返回值0;若S=T,则返回值=0;若ST,则返回值0。 StrLength (S) 初始条件:串 S 存在。 操作结果:返回串 S 序列中的字符个数,即串的长度。 ClearString (&S) 初始条件:串 S 存在。 操作结果:将 S 清为空串。,串的抽象数据类型的定义(续),基本操作: Concat (&T, S1, S2) 初始条件:串 S1 和 S2 存在。 操作结果:用 T 返回由 S1 和 S2 联接而成的新串。 SubString (&Sub, S, pos, len) 初始条件:串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 操作结果:用 Sub 返回串S的第 pos 个字符起长度为 len 的子串。 Index (S, T, pos) 初始条件:串S和T存在,T 是非空串,1≤pos≤StrLength(S)。 操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,串的抽象数据类型的定义(续),基本操作: Replace (&S, T, V) 初始条件:串 S,T 和 V 存在,T 是非空串。 操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert (&S, pos, T) 初始条件:串 S 和 T 存在,1≤pos≤StrLength(S)+1。 操作结果:在串 S 的第 pos 个字符之前插入串 T。 StrDelete (&S, pos, len) 初始条件:串 S 存在,1≤pos≤StrLength(S)-len+1。 操作结果:从串 S 中删除第 pos 个字符起长度为 len 的子串。 } ADT String,4.1 串类型的定义,上述13种基本操作中,下面5种操作构成最小操作子集:串赋值 StrAssign求串长 StrLength串比较 StrCompare串联结 Concat求子串 SubString 其他操作可以用其实现。,4.1 串类型的定义,例如定位函数Index(S,T,pos)的算法如下: int Index (String S, String T, int pos) { // T为非空串。若主串S中第 pos 个字符之后存在与T相等的子串, // 则返回第一个这样的子串在S中的位置,否则返回0。 if (pos 0) { n = StrLength(S); m = StrLength(T); // 求得串长 i = pos; while ( i = n-m+1) { SubString (sub, S, i, m); // 取得从第 i 个字符起长度为 m 的子串 if (StrCompare(sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } // while } // if return 0; // S 中不存在满足条件的子串 } // Index,4.2 串的表示和实现4.2.1定长顺序存储表示用一组连续的存储单元存储串值得字符序列。在C语言中,用字符“\0”表示串的终结,“\0”不计入串长。另一种方法是定长数组表示一个串#define MAXSTRLEN 255 //串的长度最大为255typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度,其最大值刚好是255当串超出255个字符时,串的多余内容被舍去,叫做“截断”。下面用串联结合求子串为例讨论之。,串联接Concat Status Concat( SString } } // Concat,求子串SubString( } // SubString,4.2 串的表示和实现4.2.2堆分配存储表示也是用一组连续的存储单元存储串值得字符序列,但存储空间是在程序执行过程中动态分配得到的。在C语言中,用字符“\0”表示串的终结,“\0”不计入串长。typedef struct{char *ch;int length;}HString;,串插入StrInsert( } // StrInsert,4.2 串的表示和实现 4.2.3串的块链存储表示采用链表方式存储串值。存在一个“结点大小”的问题。即每个结点可以存放一个字符,也可以存放多个字符。串长不一定是结点大小的整数倍,所以链表中的最后一个结点不一定是全被串值占满,通常补上非串值字符,如“#”。,结点大小为4的链表,4.2 串的表示和实现 串的块链存储表示,#define CHUNKSIZE 80 typedef struct Chunk{char ch[CHUANSIZE];struct Chunk *next; }Chunk;,typedef struct{Chunk *head,*tail;int curlen; //串的当前长度 }//LString;,注: (1) 串值不必建立双向链表。(2) 联结时需处理第一个串尾的无效字符。,串值的存储密度:,4.3 串的模式匹配,定义 在串中寻找子串(第一个字符)在串中的位置 在模式匹配中,子串称为模式,主串称为目标。 示例 目标 T : “Beijing”模式 P : “jin”匹配结果 = 4,4.3 串的模式匹配,采用定长顺序存储结构,不依赖其他串操作的匹配算法: int Index(SString S, SString T, int pos) { // 返回子串T在主串S中第pos个字符之后的位置。//若不存在,则函数值为0。// 其中,T非空,1≤pos≤StrLength(S)。i = pos; j = 1;while (i T[0]) return i-T[0];else return 0; } // Index,第1趟 S a b a b c a b c a c b a b (i=3)T a b c (j=3)第2趟 S a b a b c a b c a c b a b (i=2)T a (j=1)第3趟 S a b a b c a b c a c b a b (i=7)T a b c a c (j=5)第4趟 S a b a b c a b c a c b a b (i=4)T a (j=1)第5趟 S a b a b c a b c a c b a b (i=5)T a (j=1)第4趟 S a b a b c a b c a c b a b (i=11)T a b c a c (j=6) 成功,简单匹配算法的匹配过程示例: T=“abcac”; S=“ababcabcacbab”,简单匹配算法的复杂度分析:,设 n=StrLength(S); m=StrLength(T); 最好情况的复杂度为O(n+m) 如:T=‘STING’;S=‘ASTRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT’最坏情况的复杂度为O(n*m) 如:T=‘0000001’;S=‘0000000000000000000000000000000000000000001’,模式匹配的一种改进算法(KMP算法),KMP算法的改进在于:每一趟匹配过程中,当发生两个串中字符比较不等时指针 i 不需要回溯,只要利用已经“部分匹配”结果,调整j指针。即将模式 串向右滑动尽可能远的一段距离,来提高算法效率。,模式匹配的一种改进算法(KMP算法),例:T=‘abcac’; S=‘ababcabcacbab’;第1趟 S a b a b c a b c a c b a b (i=3)T a b c (j=3)第2趟 S a b a b c a b c a c b a b (i=37)T a b c a c (j=15)第3趟 S a b a b c a b c a c b a b (i=711)T (a)b c a c (j=26) 成功 显然算法的复杂度为O(n+m),KMP算法的匹配过程的另一个例子,例:另一个模式串,j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2,第1趟 S a c a b a a b a a b c a c a a b c (i=2)T a b (j=2,next[2]=1)第2趟 S a c a b a a b a a b c a c a a b c (i=2)T a (j=1,next[1]=0)第3趟 S a c a b a a b a a b c a c a a b c (i=8)T a b a a b c (j=6,next[6]=3)第4趟 S a c a b a a b a a b c a c a a b c (i=14)T (a b) a a b c a c (j=9)成功,KMP算法的基本思想,next函数定义,例:T=‘abcac’;,j 1 2 3 4 5 模式串 a b c a c next[j] 0 1 1 1 2,KMP算法,int Index_KMP(SString S, SString T, int pos) {// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的// KMP算法。其中,T非空,1≤pos≤StrLength(S)。i = pos; j = 1;while (i T[0]) return i-T[0]; // 匹配成功else return 0; } // Index_KMP,求模式串的next值的算法思想,求模式串next值的算法,void get_next(SString T, int next[]) {//求模式串T的next函数值并存入数组next。 i=1; next[1]=0; j=0;while (iT[0]) {if(j==0 || T[i]== T[j]) { ++i; ++j; next[i] = j; }else j= next[j];} } //get_next,作业,P27—28 4.3 4.4 4.5 (不必上交)P28—29 4.7 (只需求next函数值) 4.17 (上交作业),
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:4第四章 串.ppt
链接地址:https://www.weizhuannet.com/p-9796883.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开