资源描述：
《算法与数据结构 第4 章串.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第4章串4.1串的定义4.2抽象数据类型串的实现4.3串的应用举例：文本编辑4.1串的定义串(String)是零个或多个字符组成的有限序列。一般记为：S=′a1a2...an′(n≥0)其中S是串的名字,用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。n是串中字符的个数,称为串的长度，n=0时的串称为空串(NullString)。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则
2、以子串的第一个字符在主串中的位置来表示。假如有串A=′ChinaBeijing′,B=′Beijing′,C=′China′,则它们的长度分别为13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。串的抽象数据类型定义如下:ADTString{数据对象:D={ai
3、ai∈CharacterSet,i=1,2,…,n;n≥0}数据关系:R={
4、ai-1,ai∈
5、D,i=2,…,n;n≥0}基本操作:(1)StrAsign(S,chars)初始条件:chars是字符串常量。操作结果:生成一个值等于chars的串S。(2)StrInsert(S,pos,T)初始条件:串S存在,1≤pos≤StrLength(S)-len+1。操作结果:在串S的第pos个字符之前插入串T。(3)StrDelete(S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)-len+1。操作结果:从串S中删除第pos个字符起长度为len的子串。(4)St
6、rCopy(S,T)初始条件:串S存在。操作结果:由串T复制得串S。(5)StrEmpty(S)初始条件:串S存在。操作结果:若串S为空串,则返回TRUE,否则返回FALSE。(6)StrCompare(S,T)初始条件:串S和T存在。操作结果:若S>T,则返回值>0;如S=T,则返回值=0;若S7、)StrCat(S,T)初始条件:串S和T存在。操作结果:将串T的值连接在串S的后面。(10)SubString(Sub,S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。(11)StrIndex(S,T,pos)初始条件:串S和T存在,T是非空串,1≤pos≤StrLength(S)。操作结果:若串S中存在与串T相同的子串,则返回它在串S中第pos个字符之后
8、第一次出现的位置，否则返回0。(12)StrReplace(S,T,V)初始条件:串S,T和V存在,且T是非空串。操作结果:用V替换串S中出现的所有与T相等的不重叠的子串。(13)StrDestroy(S)初始条件:串S存在。操作结果:销毁串S。4.2抽象数据类型串的实现4.2.1定长顺序串＃defineMAXLEN20typedefstruct{/*串结构定义*/charch［MAXLEN］;intlen;}SString;定长顺序串是将串设计成一种结构类型,串的存储分配是在编译时完成的。与
9、前面所讲的线性表的顺序存储结构类似,用一组地址连续的存储单元存储串的字符序列。在进行串的插入时，插入位置pos将串分为两部分（假设为A、B,长度为LA、LB）,及待插入部分（假设为C,长度为LC）,则串由插入前的AB变为ACB，可能有三种情况：（1）插入后串长(LA+LC+LB)≤MAXLEN，则将B后移LC个元素位置，再将C插入。（2）插入后串长>MAXLEN且pos+LCMAXLEN且pos+LC>MAXLEN，则B的全部字符被舍弃（
10、不需后移），并且C在插入时也有部分字符被舍弃。与上述类似，在进行串的连接时（假设原来串为A，长度为LA,待连接串为B，长度为LB），也可能有三种情况：（1）连接后串长≤MAXLEN，则直接将B加在A的后面。（2）连接后串长>MAXLEN且LAMAXLEN且LA=MAXLEN，则B的全部字符被舍弃（不需连接）。置换时的情况较为
