• / 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相等的子串, // 则返回第一个这样
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

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

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

微传网博客

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

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

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

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

收起
展开