数据结构-第四章串

《数据结构-第四章串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串4.1串的定义4.2抽象数据类型串的实现4.2.1定长顺序串4.2.2堆串4.2.3块链串4.3串的应用举例：文本编辑4.1串的定义串(String)是零个或多个字符组成的有限序列。一般记为：S=‘a1a2…an’(n≥0)子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。其中S为串名，用单引号括起来的为串值，n为串的长度。通常将字符在串中的序号称为该字符在串中的位置。空格串：由一个或多个称为空格的特殊字符组成的串。空串：n=0时的串为空串4.1串的定义串(String)是零个或多个字符组成的有限序列。一般记为：S=‘a1a2…an

2、’(n≥0)子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。其中S为串名，用单引号括起来的为串值，n为串的长度。通常将字符在串中的序号称为该字符在串中的位置。空格串：由一个或多个称为空格的特殊字符组成的串。空串：n=0时的串为空串串的抽象数据类型定义：ADTString{数据对象:D={ai

3、ai∈CharacterSet,i=1,2,…,n;n≥0}数据关系:R={

4、ai-1,ai∈D,i=2,…,n;n≥0}基本操作：（1）StrAsign(S,chars)初始条件:chars是字符串常量操作结果:生成一个值等于ch

5、ars的串S（2）StrInsert(S,pos,T)初始条件:串S和T存在,1≤pos≤StrLength(S)+1操作结果:在串S的第pos个字符之前插入串T（3）StrDelete(S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)-len+1操作结果:从串S中删除第pos个字符起长度为len的子串（4）StrCopy(S,T)初始条件:串S存在操作结果:由串T复制得串S（5）StrEmpty(S)初始条件:串S存在操作结果:若串S为空串,则返回TRUE,否则返回FALSE（6）StrCompare(S,T)初始条件:串S和T存在操作结果:若S>

6、T,则返回值>0;若S=T,则返回值=0;若S

7、:串S和T存在,T是非空串,1≤pos≤StrLength(S)操作结果:若串S中存在与串T相同的子串,则返回它在串S中第pos个字符之后第一次出现的位置;否则返回0（12）StrReplace(S,T,V)初始条件:串S,T和V存在,且T是非空串操作结果:用V替换串S中出现的所有与T相等的不重叠子串（13）StrDestroy(S)初始条件:串S存在操作结果:销毁串S4.2抽象数据类型串的实现4.2.1定长顺序串定长顺序串是将串设计成一种结构类型,串的存储分配是在编译时完成的。串的定长顺序存储表示#defineMAXLEN20typedefstruct{/*串结构定义*/ch

8、arch[MAXLEN];intlen;}SString;定长顺序串基本操作的实现算法（1）串插入函数见P86例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=character（2）串删除函数StrDelete(s,pos,len)/*在串s中删除从序号pos起len个字符*/SString*s;intpos,len;{inti;if(pos<0

9、

10、pos>(s->len-len))return(0);for(i=pos+len;ilen;i++)s->ch[i-len]=s->ch[i];s->len=s->len-l

11、en;return(1);}（3）串复制函数StrCopy(s,t)/*将串t的值复制到串s中*/SString*s,t;{inti;for(i=0;ich[i]=t.ch[i];s->len=t.len;}（4）判空函数StrEmpty(s)/*若串s为空(即串长为0),则返回1,否则返回0*/SStrings;{if(s.len==0)return(1);elsereturn(0);}（5）串比较函数StrCompare(s,t)/*若串s和t相等,则返回0,