数据结构4知识讲解.ppt

《数据结构4知识讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构4串长：串中字符个数（n≥0）.n=0时称为空串，记。空格串：由一个或多个空格符组成的串。子串:串S中任意个连续的字符序列叫S的子串;S叫主串。子串位置：子串的第一个字符在主串中的序号。串相等：串长度相等，且对应位置上字符也相等。术语：1.空串和空格串有无区别？有区别。空串(NullString)是指长度为零的串；而空格串(BlankString)是指包含一个或多个空格的字符串.2.现有以下4个字符串：a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’问：①他们各自的长度？②b是哪个串的子串？它在主串中的位置是多少？例：10/2/2021ADTS

2、tring{Data:零个或多个字符组成的字符序列Operation:String();//构造函数intLength();//求串长intCompare(StringS);//两个串比较，若大于，返回值大于0，若小于，返回值小于0，若等于，返回值等于0二、串的抽象数据类型定义10/2/2021二、串的抽象数据类型定义boolConcat(StringS1,StringS2);//串联接StringSubstring(intpos,intlen);//求子串intIndex(StringT,intstart);//返回子串在开始位置之后的匹配位置boolReplace(Strin

3、gT,StringV);用子串V替换子串TboolAssign(char*s);//串赋值，将字符数组s中的字符复制到串中}//ADTStringintIndex(StringT，intstart){//T为非空串。若主串中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0if(start>0)(n=Length(S);m=Length(T);i=start;while(i<=n-m+1){stringsub=SubString(i,m);if(sub.Compare(T)!=0)++i;elsereturni;//返回子串在主串中的位置}//w

4、hile}//ifreturn0;//S中不存在与T相等的子串}//Index串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。4.2串的存储结构顺序存储结构——用一组地址连续的存储单元存储串值的字符序列堆分配存储表示——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示——链式方式存储串有三种表示方法：顺序存储链式存储#defineMAXSTRLEN255classSStrin

5、g{charstr[MAXSTRLEN+1];//存放字符串的数组，最后一个字节存放结束符intsize;//有效字符个数public:SString(){size=0;}//构造函数intLength();intCompare(SStringS);boolConcat(SStringS1,SStringS2);SStringSubstring(intpos,intlen);intIndex(SStringT,intstart);一、定长顺序存储算法描述boolReplace(SStringT,SStringV);boolAssign(char*s);};//SString串连接

6、Concat(S1,S2)boolSString::Concat(SStrings1,SStrings2){if(s1.size+s2.size

7、ze..MAXSTRLEN-1]=s2.str[0..MAXSTRLEN-s1.size-1];size=MAXSTRLEN;str[size]='';returnfalse;//被截断}else{str[0..MAXSTRLEN-1]=s1.str[0..MAXSTRLEN-1];size=MAXSTRLEN;str[size]='';returnfalse;//被截断}}//Concat求子串SStringSString::Substring(intpos,intle