《串的基本概念》PPT课件

《串的基本概念》PPT课件

ID:45130558

大小:379.50 KB

页数:26页

时间:2019-11-10

《串的基本概念》PPT课件_第1页
《串的基本概念》PPT课件_第2页
《串的基本概念》PPT课件_第3页
《串的基本概念》PPT课件_第4页
《串的基本概念》PPT课件_第5页
资源描述:

《《串的基本概念》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、4.1串类型的定义串(或字符串)(String)是由零个或多个字符组成的有限序列。一般记作s=〃a1a2…an〃(n≥0)其中:s为串名,用双引号括起来的字符序列是串的值;ai(0≤i≤n)可以是字母、数字或其它字符;双引号为串值的定界符,不是串的一部分;串中字符的数目n称为串的长度。空串——零个字符的串,通常以两个相邻的双引号来表示空串(Nullstring),如:s=〃〃,它的长度为零;空格串——仅由空格组成的的串,如:s=〃└┘〃;若串中含有空格,在计算串长时,空格应计入串的长度中,如:s=〃I

2、’mastudent〃的长度为13。第四章串的基本概念串的抽象数据定义:P71对于串的基本操作集可以有不同的定义方法,读者在使用高级语言中的串类型时,应该以语言的参考手册为准。定位算法(P72)——Index(S,T,pos)4.2串的表示和实现对串的存储方式取决于我们对串所进行的运算,如果在程序设计语言中,串的运算只是作为输入或输出的常量出现,则此时只需存储该串的字符序列,这就是串值的存储。此外,一个字符序列还可赋给一个串变量,操作运算时通过串变量名访问串值。串的3种机内表示方式:定长顺序存储表示堆

3、分配存储表示串的块链存储表示4.2.1定长顺序存储表示实现:用一组地址连续的存储单元存储串值的字符序列。存储表示#defineMAXSTRLEN255TypedefunsignedcharString[MAXSTRLEN+1]截断——超过与定义长度的串值被舍去。串长的两种表示:下标为0的分量存放串的实际长度,如:pascal在串尾加一个不计入串长的结束标记符。如:C中的‘’串连接算法Concat(&T,S1,S2)StatusConcat(SString&T,SStringS1,SStringS2

4、){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE,否则FALSE。S[0]//保存串的长度,有三种情况(1)S1[0]+S2[0]<=MAXSTRLEN;(2)S1[0]MAXSTRLEN;(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]+

5、S2[0];uncut=TRUE;}elseif(S1[0]

6、原操作为——字符序列的复制操作的时间复杂度基于复制序列的长度截断处理StatusSubString(SString&Sub,SStringS,intpos,intlen){//用Sub返回串的第pos个字符起长度为len的子串,其中//1<=pos<=StrLength(s)&&0<=len<=StrLength(s)-pos+1if(pos<1

7、

8、pos>S[0]

9、

10、len<0

11、

12、len>S[0]-pos+1returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。