数据结构 第四章 串

数据结构 第四章 串

ID:43517001

大小:506.00 KB

页数:76页

时间:2019-10-09

数据结构 第四章 串_第1页
数据结构 第四章 串_第2页
数据结构 第四章 串_第3页
数据结构 第四章 串_第4页
数据结构 第四章 串_第5页
资源描述:

《数据结构 第四章 串》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第4章串4.1串的抽象数据类型定义4.2串的表示和实现4.3串的模式匹配算法1本章要点理解串匹配的KMP算法,熟悉NEXT函数的定义,学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。熟悉串的基本操作的定义,并能利用基本操作来实现串的其它各种操作的方法。掌握串的三种机内表示方法。2串(string):由零个或多个字符组成的有限序列。记为:s=a1a2a3……an(n≥0)串的长度:串中字符的数目n。空串:零个字符的串,它的长度为零。用Φ表示空串。空格串:由一个或多个空格组成的串。4.1串的抽象数据类型定义3子串:串中任意个连续的字符组成的子序列。主串:包含子串的串。

2、如:A=STUDYING,B=DYI,A为主串,B为子串。位置:字符在序列中的序号。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。串相等的条件:当两个串的长度相等且各个对应位置的字符都相等时才相等。4串的抽象数据类型的定义如下:ADTString{数据对象:D={ai

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

4、ai-1,ai∈D,i=2,...,n}串是有限长的字符序列,由一对单引号相括,如:astring5基本操作:StrAssign(&T,chars)StrCopy(&T,S)DestroySt

5、ring(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)6SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTString7StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个值等于chars的串T。8StrCopy(&T,S)初始条件:串S存在。操作结果:由串S复制得串T。9DestroyString(&

6、S)初始条件:串S存在。操作结果:串S被销毁。10StrEmpty(S)初始条件:串S存在。操作结果:若S为空串,则返回TRUE,否则返回FALSE。表示空串,空串的长度为零。11StrCompare(S,T)初始条件:串S和T存在。操作结果:若ST,则返回值0; 若ST,则返回值0;若ST,则返回值0。例如:StrCompare(data,state)<0StrCompare(cat,case)>012StrLength(S)初始条件:串S存在。操作结果:返回S的元素个数, 称为串的长度。13Concat(&T,S1,S2)初始条件:串S1和S2存

7、在。操作结果:用T返回由S1和S2联接而成的新串。例如:Concate(T,man,kind)求得T=mankind14SubString(&Sub,S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。15例如:SubString(sub,commander,4,3)求得sub=man;SubString(sub,commander,1,9)求得sub=commander;SubString(sub,command

8、er,9,1)求得sub=r;子串为“串”中的一个字符子序列16SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串17Index(S,T,pos)初始条件:串S和T存在,T是非空串,1≤pos≤StrLength(S)。操作结果:若主串S中存在和串T值相同 的子串,则返回它在主串S中第pos个 字符之后第一次出现的位置; 否则函数值为0。18假设S=abcaabcaaabc

9、,T=bcaIndex(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。19Replace(&S,T,V)初始条件:串S,T和V均已存在, 且T是非空串。操作结果:用V替换主串S中出现 的所有与(模式串)T相等的不重叠的子串。20例如:假设S=abcaabcaaabca,T=bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=

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

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

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