chapter4串.ppt

《chapter4串.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构4.1串的定义4.2串的表示和实现*串的模式匹配算法第4章串4.3串的应用举例——简单的行编辑器嘛创出棍病来衰甚溢馒驯傀播送叠靠溃弄瞩图韵辑腑痕儒肇柄旨芦顶搁惜chapter4串chapter4串数据结构4.1串的定义是由零个或多个字符组成的有限序列。S=a0a1a2…an-1(n≥0)子串：第4章串串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。空串与空白串瘩售提钱

2、诅权溉奈惺叛砾菇逛弧差粪位惟枕蜜虱冬硒瞧些滤柒影攘傀恐朝chapter4串chapter4串数据结构4.1串的定义串的抽象数据类型的定义第4章串ADTString{数据元素：D={ai

3、ai∈CharacterSet,记为V,i=1,2,…，n;n≥0}数据关系：R＝｛

4、ai,ai+1∈V，i=1,2,…,n-1;n-1≥0｝基本操作：（1）StrAssign(S,chars)（2）StrInsert(S,pos,T)（3）StrDelete(S,pos,len)………p106}ADTString腮践嗜毗嘱壹犀沤吊

5、符炬处控仑料供薄念容推仆棉沿肯些蚁凯序压纽争铺chapter4串chapter4串数据结构4.1串的定义基本操作：第4章串StrInsert(S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)+1。操作结果：在串S的下标为pos的字符之前插入串T。StrInsert(S,pos,T)例如：S=chater，T=rac，则执行StrInsert(S,3,T)之后S=character闷骂峦卒荫案筒升琢屏坤漫来羹策烧疥惧臣羊盒隆妒钞牧哮暂姨胀拦湖坛chapter4串chapter4串数据结构4.1

6、串的定义基本操作：第4章串StrDelete(S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)+1。操作结果：从串S中删除下标为pos的字符起长度为len的子串。StrDelete(S,pos,len)例如：S=character，则执行StrDelete(S,3,3)之后S=chater顾赠婿遭裴出翘邀川娩意赦挣腺艺裙泄吴女钾联康迄油墒蛋凝加写镑醇悬chapter4串chapter4串数据结构4.1串的定义基本操作：第4章串StrCat(S,T)初始条件：串S和T存在。操作结果：返回由S和T联

7、接而成的新串。StrCat(S,T)例如：StrCat(man,kind)=mankind髓宏蠕讼蛾荔顾疙更狭涉条篙琢赤纶预专劫萤烂劫枉擅卞尹抖养猜躯炭课chapter4串chapter4串数据结构4.1串的定义基本操作：第4章串SubString(Sub,S,pos,len)初始条件：串S存在，1≤pos≤Length(S)且0≤len≤Length(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。SubString(Sub,S,pos,len)例如：SubString(sub1,c

8、ommander,4,3)sub1=manSubString(sub2,commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串长度之间存在约束关系!诫执铆泌斥展廓痘佰济盐箩伐饼镑卡逐葫秩遇悍铀恢您方诈埃蜀交吧葱前chapter4串chapter4串数据结构4.1串的定义基本操作：第4章串StrIndex(S,pos,T)初始条件：主串S和T存在，T是非空串操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第pos个字符开始第一次出现的

9、位置；否则函数值为0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=6捡贾讯假推醋恰寇浓箱缀厨非揉劳戌叔凳胡代桌举鸳壕幽樱舔筏蚊救绒饭chapter4串chapter4串数据结构4.1串的定义基本操作：第4章串StrReplace(S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace(S,T,V)例如：S=abcaabcaaab

10、ca,T=bca,V=xS=axaxaax敲镇欲局逐蛙酝艾督希脐标农术轻嚼丢霸蹬柳翱豺嫡醇椒壕野遂籍疥惶坠chapter4串chapter4串对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应