课前导学4.1 串类型的定义4.2 串的表示和实现 4.3 串的模式.ppt

《课前导学4.1 串类型的定义4.2 串的表示和实现 4.3 串的模式.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第四章串课前导学4.1串类型的定义4.2串的表示和实现*4.3串的模式匹配算法4.4串操作应用举例【学习目标】1.理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。3.理解串匹配的各种算法。【重点和难点】了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。【知识点】串的类型定义、串的存储表示、串匹配【课前思考】从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。区别1、它的数据元素都是字符，它的存储结构和线性

2、表有很大不同;区别2、串的基本操作通常以"串的整体"作为操作对象，而不像线性表是以"数据元素"作为操作对象。“串就是线性表”的结论是否正确？二者之间有何区别?4.1串类型的定义1.基本概念串（string）：由0个或多个字符组成的有限序列，也称字符串。记为：s=’a1a2a3……an’(n≥0)式中s是串的名，a1a2a3……an是串的值，ai（1≤i≤n）可以是字母、数字或其它字符。串长度：串中字符的数目n。空串：不含任何字符的串，串长度=0空格串：仅由一个或多个空格组成的串子串：由串中任意个连续的字符组成的子序列主串：包含

3、子串的串。串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。注意：（1）串值必须用一对单引号括起来（2）串值大小是按词典次序进行比较的StrCompare(‘data’,’Stru’)<0StrCompare(‘cat’,’case’)>0显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。2.串的抽象数据类型的定义ADTString{数据对象：D＝{ai

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

5、ai-1,ai∈D,i=2,...,

6、n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S

7、初始条件：串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的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子

8、串,则返回它在主串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。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。Clea

9、rString(&S)初始条件：串S存在。操作结果：将S清为空串。}ADTString在以上操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现。例：假设S="abcacabcaca"，T="abca"和V="x"，则置换之后的S="xcxca"。注意定义中"不重叠"三个字，若上例中的V="ab"时，则置换后的结果应该是S="abcabca"，而不是"abbca"。思考：串的

10、基本操作和线性表一样，无非也就是查找、插入和删除等，那么它们能否用线性表的操作来替代呢？串的基本操作和线性表有很大的区别，同样是查找、插入和删除，但对线性表而言操作对象是“数据元素”，而对串言，是以整个串作为操作对象。由此可见，串类型不能和线性表类型混为一谈。4．2串的表示和