资源描述：
《数据结构――串ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构串1串的初步认识串（字符串）:由零个或多个字符组成的有限序列。记为：s=‘a1a2…an’(n>=0)其中，s是串的名，也称为串变量。单引号内的字符序列为串值；ai(1≤i≤n)可以是字母、数字或其它字符。例如：a=‘Data’b=‘Structure’c=‘DataStructure’d=‘DataStructure’2基本术语长度串中所包含的字符个数n空串长度为0的串子串串中任意个连续的字符组成的子序列主串包含子串的串称为该子串的主串位置字符在序列中的序号子串的位置子串的第一个字符在主串中的位置例如a=‘Data’b=‘Structure’c=
2、‘DataStructure’d=‘DataStructure’长度分别为4、9、13和14；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是5，在d中的位置则是6。3主要的基本操作求子串substring(s,start,len)返回值为串s中第start个字符起，长度为len的字符序列插入insert(s,pos,t)在串s的第pos个字符之后插入串t删除delete(s,pos,len)从串s中删去第pos个字符起长度为len的子串定位position(s,t)若t在s中存在，则返回t在主串s中的位置，否则函数值为0替换rep
3、lace(s,t,v)操作结果是以串v替换所有在串s中出现的和非空串t相等的子串判相等equal(s,t)若s和t相等，则返回true否则返回false。求长度length(s)返回s中字符的个数两个串长度相等并且对应位置上的字符都相等4基本操作的实例s1=“Data”s2=“Structure”s3=“DataStructure”s4=“DataStructure”length(s3)返回值为13length(s4)返回值为14position(s4,s2)返回值为5substring(s3,4,3)返回一个字符串“Str”delete(s4,5,3)执
4、行后串s4的值为“Dataucture”replace(s4,s1,s2)执行后串s4的值为“StructureStructure”5串的抽象数据类型classStr{public:virtualintleng()=0;//求长度virtualintpos(char*t,intk=0)=0;//定位virtualchar*subs(intpos,intlen)=0;//求子串virtualStr&inst(intpos,char*t)=0;//插入virtualStr&dele(intpos,intlen)=0;//删除virtualStr&repl(ch
5、ar*t,char*r)=0;//替换};6串的存储结构顺序存储结构类型定义constmaxlen=允许的串最大长度;structTstr{intcurlen;charstr[maxlen];};串的存储结构顺序存储结构链式存储结构（一般不使用）堆式存储结构DATASTRUCTURESDATASTRUCTURES7堆式存储结构存储空间系统中设置一个容量很大、地址连续的存储空间作为串值的可利用空间，当建立一个新串时，系统就从这个空间中分配一个大小和串长相同的空间存储新串。映象空间同时建立一个串的描述符来指示串的地址及长度，系统中所有串的描述符构成了一张从串名
6、到串的映射表即构成了映象空间。BEIJINGfreeitemstartlena13b54c188在进行类定义时，可采用不同的存储方式与处理方式。对于串而言同样是采用顺序的存储方式，可以由开始位置与长度来确定一个串，也可以由开始位置与结束符’ ’来确定一个串。这两种处理方式分别对应本章中的Str1与Str2两个实现类。Str1的特点是：为适应串的变化，在分配串空间时留有一定的余地。在进行串操作时，若当前长度的变化在最大长度的范围之内，则无须重新分配存储空间，仅当超出了最大长度的范围之内才须重新分配。设置长度的顺序串类Str19顺序串的类定义classStr
7、1:publicStr{private:char*str;intcurlen;intmaxlen;public:Str1(intsz=81);Str1(char*s);Str1(Str1&s);~Str1(){delete[]str;};intleng(){returncurlen;};char*subs(intpos,intlen);intpos(char*t,intk=0);Str&inst(intpos,char*t);Str&dele(intpos,intlen);Str&repl(char*t,char*r);};10str1类的构造函数Str1
8、(intsz=81){curlen=0;maxlen=sz;str
