数据结构串ppt课件.ppt

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

1、4.1串的抽象数据类型定义4.2串的表示和实现4.3串的匹配算法第四章串串的基本概念串是由零个或多个任意字符组成的字符序列。一般记作：s=‘a1a2…an’。其中s是串名；在本书中，用单引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1<=i<=n)是一个任意字符，可以是字母、数字或其它字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。注意：空串和空白串（通常将仅由一个或多个空格组成的串称为空白串(BlankStri

2、ng))。串中任意个连续字符组成的子序列称为该串的子串；包含子串的串相应地称为主串；通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的位置。例如，设A和B分别为A=‘Thisisastring’B=‘is’则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。特别地，空串是任意串的子串，任意串是其自身的子串。串的类型定义串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量或数的常量混淆而已。如x=‘123’；表明x是一个串变

3、量名，赋予它的值是字符序列123，而x=123，则表明x是一个整型变量，赋予它的值为整数123。　　同样在aString=‘aString’;中，左边的aString是一个串变量名，而右边的字符序列‘aString’是赋给它的值。串的类型定义通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。串的类型定义ADTString｛

4、数据对象：D=｛ai

5、aiCharacterSet，i=1，2，…，n，n0｝数据关系：R=｛

6、ai-1，aiD，i=2，…，n｝基本操作：1.｛结构初始化｝StrAssign(&T,chars)初始条件：chars是串常量。　　　操作结果：生成一个其值等于chars的串T。串的抽象数据类型定义串的抽象数据类型定义StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。2.｛销毁结构｝DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。串的抽象数据类型定义3.｛引用型操作｝

7、StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S

8、s个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在,T是非空串，1≤pos≤StrLength(S)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。串的抽象数据类型定义4.｛加工型操作｝ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。Replace(&S,T,V)初始条件：串S，T和V存在，T是非空串。操作结果

9、：用V替换主串S中出现的所有与T相等的不重叠的子串。串的抽象数据类型定义StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。｝ADTString串的抽象数据类型定义在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLe

10、ngth、串联接Concat以及求子串SubString等5种操作构成串类型的最小操作子集。即这些操作不可能利用其它操作来实现，而其它操作均可在这个最小操作子集上实现。例如，可利用判等、求串长和求子串等操作实现串的定位函