数据结构课件(串).ppt

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

1、数据结构第四章串7/21/2021第四章串串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。4.1串的定义是由零个或多个字符组成的有限序列，一般记为s=“a1a2…an”(n0)其中，

2、s是串名，用单引号（也可以是用双引号括起来的）括起来的字符序列是串的值。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。注意区分空串与空格串的区别。4.1串的定义串的逻辑结构和线性表的区别:1.串的数据对象约束为字符集。2.线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的

3、整体”作为操作对象。对于串可以定义以下运算：1.置串为一个空串；2.判断一个串是否为空串3.求一个串的长度；4.将两个串拼接在一起构成一个新串；5.在一个串中，求从串的第i个字符开始连续j个字符所构成的子串；6.如果串S2是S1的子串，则可求串S2在串S1中第一次出现的位置。4.1串的定义串的抽象数据类型的定义ADTString{数据对象：D＝{ai

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

5、ai-1,ai∈D,i=2,...,n}基本操作：StrAssi

6、gn(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。4.1串的定义串的抽象数据类型的定义StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S

7、。StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串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的子串。4.1串的定义串的抽象数据类型的定义Index(S,T,pos)初始条件：串S和T存在，T是非空串，

8、1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。Replace(&S,T,V)初始条件：串S,T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。4.1串的定义串的抽象数据类型的定义StrDelete(&S,pos,len)初始条件

9、：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。}ADTString4.1串的定义对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等

10、六种操作构成串类型的最小操作子集。例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为：在主串S中取从第i(i的初值为pos)个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。4.1串的定义intIndex(StringS,StringT,intp