数据结构与算法 教学课件 作者 王曙燕 chapter4 串.ppt

《数据结构与算法 教学课件 作者 王曙燕 chapter4 串.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、4.2串及其运算4.3串的存储结构及实现第4章串4.4串的模式匹配4.1应用实例4.5实例分析与实现4.6算法总结4.1应用实例应用实例：文本编辑软件文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作，甚至用于报刊和书籍的编辑排版。常用的简单文本编辑程序Edit，和文字处理软件WPS、Word等，究其实质，都是修改字符数据的形式或格式。可用于文本编辑的程序很多，功能不同且强弱差别很大，但基本操作是一样的，一般都包含串的查找、插入和删除等基本操作。4.2串及其运算是由零个或多个字符组成的有限序列。S=a0a1a2…an

2、-1(n≥0)子串：第4章串串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。空串与空白串串的抽象数据类型的定义第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,p

5、os,T)（3）StrDelete(S,pos,len)………p106}ADTString4.2串及其运算基本操作：第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4.2串及其运算基本操作：第4章串StrDelete(S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)+1。

6、操作结果：从串S中删除下标为pos的字符起长度为len的子串。StrDelete(S,pos,len)例如：S=character，则执行StrDelete(S,3,3)之后S=chater4.2串及其运算基本操作：第4章串StrCat(S,T)初始条件：串S和T存在。操作结果：返回由S和T联接而成的新串。StrCat(S,T)例如：StrCat(man,kind)=mankind4.2串及其运算基本操作：第4章串SubString(Sub,S,pos,len)初始条件：串S存在，1≤pos≤Length(S)且0≤len≤Lengt

7、h(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。SubString(Sub,S,pos,len)例如：SubString(sub1,commander,4,3)sub1=manSubString(sub2,commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串长度之间存在约束关系!4.2串及其运算基本操作：第4章串StrIndex(S,pos,T)初始条件：主串S和T存在，T是非空串操作结果：若主串S中存在和串T值相同的子串,则返回它

8、在主串S中从第pos个字符开始第一次出现的位置；否则函数值为0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=64.2串及其运算基本操作：第4章串StrReplace(S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace(S,T,V)例如：S=abcaabcaaabca,T=bca,V=xS=axaxaax给出一个由小写字母组成的串s和一个

9、不超过s的长度的正整数l，求s所有长度不小于l的子串在s中不重叠地重复出现次数最多的子串。4.2串及其运算对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。基本操作第4章串4.2串及其运算①定长顺序串4.3串的存储及实现常用的实现方法：第4章串②堆串③块链串①定长顺序串常用的实现方法：第4章串存储表示：静态数组结构#defineMAXLEN40typedefstruct{charstr[MAXLEN];intlength;}SString;4.3串的存储及实现①定长顺序串常用的实现方法：第4章串基本操作：

10、插入、删除、复制、判空、比较、求串长、清空、连接、求子串。参见P7