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

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

1、第4章串4.1串的定义4.2抽象数据类型串的实现4.3串的模式匹配算法4.4串的应用举例：文本编辑4.1串的定义串(String)是零个或多个字符组成的有限序列。一般记为：S=‘a1a2...an’(n≥0)其中S是串的名字，用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度，n=0时的串称为空串(NullString)。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串

2、的第一个字符在主串中的位置来表示。假如有串A=‘ChinaBeijing’，B=‘Beijing’，C=‘China’，则它们的长度分别为13、7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等。串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其它字符中间。由一个或多个空格组成的串‘’称为空格串（

3、blankstring，请注意此处不是空串）。它的长度为串中空格字符的个数。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的抽象数据类型定义如下:ADTString{数据对象:D={ai

4、ai∈CharacterSet,i=1,2,…,n;n≥0}数据关系:R={

5、ai-1,ai∈D,i=2,…,n;n≥0}基本操作:(1)StrAssign（&T,chars）初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串T。(2)Strcopy（&T,S）初始条件：串S存在。操

6、作结果：由串S复制得串T。(3)StrEmpty（S）初始条件：串S存在。操作结果：若S为空串，则返回TURE，否则返回FALSE(4)StrCompare（S，T）初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T,则返回值＝0；若S

7、1和S2联接而成的新串。(8)SubString(&Sub,S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。(9)Index（S，T，pos）初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。(10)Replace（&S,T,V）初始条件：串S，T和V存

8、在，T是非空串。操作结果：用V替换主串S的第pos个字符之前插入串T。(11)StrInsert（&S,pos,T）初始条件：串S和T存在，1≤pos≤StrLength(S)。操作结果:在串S的第pos个字符起长度为len的子串。(12)StrDelete（&S,pos,len）初始条件：串S存在，1≤pos≤StrLength(S)–len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。。(13)DestroyString（&S）初始条件：串S存在。操作结果：串S被销毁。对于串的基本操作集可以有不同的定义方法，

9、读者在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLengt、串联接Concat以及求子串SubString等五种操作构成的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）均可在这个最小操作子集上实现。例如：可利用判等、求串长和求子串等操作作为实现定位函数Index（S，T，pos）。算法的基本思想为：在主串S中取从第i（

10、i的初值为pos）个字符起、长度和T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。如算法4.1所示。intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第p