数据结构c语言版(串)ppt课件.ppt

《数据结构c语言版(串)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例4.1串类型的定义1基本概念1．串的定义串(string)是由零个或多个字符组成的有限序列，记作s=“a1a2…an”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2．空串不含任何字符的串称为空串，它的长度n=0，记为s=“”。3．空白（空格）串含有一个或多个空格的串，称为空白串，它的长度n为空格的个数。4．子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串

2、的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“Thisisastring”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此称B在A中的序号（或位置）为3特别的，空串是任意串的子串，任意串是自身的子串。通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只

3、能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。串变量和其它类型的变量一样，其取值是可以改变的。2串类型的定义如下：ADTString{数据对象：D＝{ai

4、ai∈CharacterSet,i=1,2,...,n,n≥0}n称为串的长度数据关系：R1＝{

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

6、(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTStringStrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋给T。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串

7、，则返回TRUE，否则返回FALSE。表示空串，空串的长度为零。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>0StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例

8、如：Concat(T,man,kind)求得T=mankindSubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”中的一个字符子序列例如：SubString(sub,commander,4,3)求得sub=man；SubString(sub,commander,1,9)求得sub=commander；SubString(sub,commander,9,1)求得sub=r；

9、SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现