[课件]数据结构第四章串

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

1、4.1串类型的定义串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作s=〃a1a2…an〃(n≥0)其中：s为串名，用双引号括起来的字符序列是串的值；ai(0≤i≤n)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；串中字符的数目n称为串的长度。空串——零个字符的串，通常以两个相邻的双引号来表示空串（Nullstring），如：s=〃〃，它的长度为零；空格串——仅由空格组成的的串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’mastudent〃的长度为13。第四章串的基本概念串的抽象数据定义：P71对于

2、串的基本操作集可以有不同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。定位算法（P72）——Index（S，T，pos）4.2串的表示和实现对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。串的3种机内表示方式：定长顺序存储表示堆分配存储表示串的块链存储表示4.2.1定长顺序存储表示实现：用一组地址连续的存储单元存储串值的字符序列。存储表示#defineMAXSTRLEN255Typedef

3、unsignedcharString[MAXSTRLEN+1]截断——超过与定义长度的串值被舍去。串长的两种表示：下标为0的分量存放串的实际长度，如：pascal在串尾加一个不计入串长的结束标记符。如：C中的‘’串连接算法Concat（&T，S1，S2）StatusConcat(SString&T,SStringS1,SStringS2){//用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。S[0]//保存串的长度,有三种情况(1)S1[0]+S2[0]<=MAXSTRLEN;(2)S1[0]MA

4、XSTRLEN;(3)S1[0]=MAXSTRLENIf(S1[0]+S2[0]<=MAXSTRLEN{//未截断T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]

5、AXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}求子串算法SubString（&Sub，S，pos，len）串操作特点：原操作为——字符序列的复制操作的时间复杂度基于复制序列的长度截断处理StatusSubString(SString&Sub,SStringS,intpos,intlen){//用Sub返回串的第pos个字符起长度为len的子串，其中//1<=pos<=StrLength(s)&&0<=len<=StrLength(s)-pos+1if(pos<1

6、

7、pos>S[0]

8、

9、len<0

10、

11、len>S[0]-pos

12、+1returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}串的动态存储结构串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。串的动态存储方式采用堆存储结构和链式存储结构两种形式：4.2.2堆存储结构特点仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如

13、果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。存储结构：typedefstruct{char*ch;//若是非空串，按串长分配空间，否则ch为NULLintlength;//串长}HString;基本算法（P76-77）举例：串插入操作StatusStrAssign(HString&T,char*chars);//生成一个值等于串常量chars的串TIntStrLength(HStringS);//返回串S的元素个数，称为串的