《数据结构》(C语言版).ppt

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

1、第四章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例1学习提要：1.熟悉串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆分配存储结构以及在其上实现串操作的基本方法。4.理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。重难点内容：串的存储结构，串的模式匹配算法2串（string）：由零个或多个字符组成的有限序列，也称字符串。记为：S=‘a1a2a3……an’(n≥0)

2、如：A=‘BEIJING’，B=‘JING’4.1串类型的定义3ADTString{数据对象：D＝{ai

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

4、ai-1,ai∈D,i=2,...,n}基本操作：}ADTString……串的抽象数据类型定义:4StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrCompare(S,T)StrLength(S)ClearString(&S)StrEmpty(S)5SubString(&Sub,S,pos,len)

5、Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)Concat(&T,S1,S2)6StrAssign(&T,chars)//串赋值初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)//串复制初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。7ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。StrEmpty(S)初始条件：串S存

6、在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。8StrLength(S)//求串长初始条件：串S存在。操作结果：返回S的元素个数。串的长度：串中字符的数目n。空串：不含任何字符的串，串长度为0，用“”或‘’表示。空格串：仅由一个或多个空格组成的串，长度为串中空格字符的个数。9初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S

7、trCompare(S,T)//串比较10Concat(&T,S1,S2)//串联接初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。Concat(&T,‘data’,‘structure’)T=‘datastructure’11SubString(&Sub,S,pos,len)//求子串子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A=‘BEIJING’B=‘JING’12SubString(&Sub,S,pos,len)//求子串初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLe

8、ngth(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。SubString(&sub,‘datastructure’,6,9)Sub=‘structure’13Index(S,T,pos)//串定位字符在串中的位置：字符在序列中的序号。子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。如：A=‘BEIJING’，B=‘JING’，B在A中的位置为4。14Index(S,T,pos)//串定位初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返

9、回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设：S=abcaabcaaabc,T=bcaIndex(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；15Replace(&S,T,V)//串替换初始条件：串S,T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。例如：S=‘abcaabc’,T=‘ab’,V=‘x’S=‘xcaxc’V=‘bc’S=‘bccabcc’16StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)

10、＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S＝‘g