串类型的定义串的表示与实现串的模式匹配算法串操作应用举例ppt课件.ppt

《串类型的定义串的表示与实现串的模式匹配算法串操作应用举例ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、串类型的定义串的表示和实现串的模式匹配算法串操作应用举例第四章串1、了解串的概念；学习要点2、熟悉串的基本运算的定义及实现方法；3、掌握基本串匹配算法。在较早的程序设计语言中，字符串（简称串）是作为输入或输出的常量（是直接量，不参加运算）出现，而非数值处理的对象基本上是字符串数据。这就要求字符串也能以变量的形式出现，能进行一系列字符串操作（运算）。目前大多数程序设计语言都支持串这种数据类型。1、串2、串长：串中所包含的字符个数。3、空串：长度为零的串，它不包含任何字符。记作“Ø”4、子串：串中任意个连续的字符组成的子序列。5、主

2、串：包含子串的串。4.1串类型的定义基本概念：零个或多个字符组成的有限序列，即数据元素为字符的线性表。一般记为S=‘a1a2...an’，其中，S是串名，单引号括起的字符序列是串值。7、子串在主串中的位置：子串在主串中第一次出现时，子串的第一个字符在主串中的位置。6、字符在串中的位置：字符在序列中的序号。8、两个串相等：两个串的长度相等，并且各个对应位置的字符都相等时才相等。9、空格串：由一个或多个空格组成的串，其长度为串中空格字符的个数。它与空串Ø是不同的概念。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象为字符集。串的

3、基本操作和线性表有很大差别：在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。ADTString{数据对象：D＝{ai

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

5、ai-1,ai∈D,i=2,...,n}基本操作：……}ADTStringADT串的定义StrAssign(&T,chars)//串赋值初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)//串复制初始条件：串S存在

6、。操作结果：由串S复制得串T。DestroyString(&S)//串销毁初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)//串判空初始条件：串S存在。操作结果：若S为空串，则返TRUE，否则返回FALSE。StrCompare(S,T)//串比较例如：StrCompare(data,state)<0StrCompare(cat,case)>0初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0StrLength(S)//求串长初始条件：串S存

7、在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)//串联接例如：Concate(T,man,kind)求得T=mankind初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)//求子串初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”中的一个字符子序列。SubString(sub

8、,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r例如：SubString(sub,commander,4,3)求得sub=man;SubString(sub,student,5,0)得sub=关于参数len（子串长度）的说明：长度为0的子串为“合法”串—空串。事实上对任何串S和位置pos都有：SubString(sub,commander,4,7)得sub=manderSubString(sub,S,pos,

9、0)得sub=；有时对len放宽到len＞StrLength(S)-pos+1，此时规定SubString(sub,S,pos,len)的值取S的第pos个字符到S的最后一个字符作为子串（长为StrLength(S)-pos+1）。Index(S,T,pos)//(子)串(位置)定位初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设S=abcaabcaaabc,T=bcaIn

10、dex(S,T,1)=Index(S,T,3)=Index(S,T,8)=“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。2;6;0;Replace(&S,T,V)//串替换初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出