数据结构第4章_串

《数据结构第4章_串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例4.1串类型的定义1.串的概念由零个或多个字符组成的有限序列，记作s=‘a1a2…an’其中：s为串的名字；用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中；ai(1≤i≤n)可以是字母、数字或其它字符；n为串中字符的个数，称为串的长度。空串：不含任何字符的串。长度n=0，记为s=‘’；空格串：含有空格的串，长度n>0，记为s=‘’。子串、主串:串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串

2、。通常将子串在主串中首次出现时，该子串的首字符对应的主串中的序号称为子串在主串中的位置。例：A和B分别为A=‘Thisisastring’B=‘is’空串是任意串的子串，任意串是其自身的子串。串的比较大小：‘a’<‘ab’，‘abc’<‘abd’两串相等：当且仅当这两个串的值相等（长度相等,对应位置上的字符也相等）时。2.串的抽象类型定义ADTString数据对象：D＝{ai

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

4、ai-1,ai∈D,i=2,…,n}基本操作：}ADTSt

5、ring串的常用操作(1)StrAssign(&T,chars)条件：chars是字符串常量；结果：把chars赋为T的值(2)StrCopy(&T,S)条件：串S存在；结果：将串S的值复制到串T(3)DestroyString(&S)条件：串S存在；结果：串S被销毁(4)StrEmpty(S)条件：串S存在；结果：若S为空串，返回真，否则假(5)StrCompare(S,T)条件：串S和T存在；结果：若S>T，则返回值>0；若S=T，则返回值=0若S

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

7、ring(&S)条件：串S存在；结果：将S清为空串(11)Replace(&S,T,V)条件：串S,T和V存在，T是非空串且是S的子串结果：用V替换S中所有与T相等的不重叠的子串(12)StrInsert(&S,p,T)条件：串S和T存在，1≤p≤StrLength(S)＋1结果：在串S的第p个字符之前插入串T(13)StrDelete(&S,p,len)条件：串S存在，1≤p≤StrLength(S)-len+1结果：从串S中删除第p个字符起长度为len的子串设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER

8、’。求：例：StrLength(s)＝StrLength(t)＝SubString(s,8,7)＝SubString(t,2,1)＝Index(s,‘A’)＝Index(s,t)＝Replace(s,‘STUDENT’,q)＝144‘STUDENT’‘O’30（s中没有t！）’IAMAWORKER’考虑：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？注意事项：对串的基本操作集可以有不同的定义方法，读者在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。串类型的最

9、小操作子集包括：串赋值StrAssign、求串长StrLength、串比较StrCompare、求子串SubString、串联接Concat等操作。例：利用判等、求串长和求子串等操作实现定位函数Index(S,T,p)。算法的基本思想：在主串S中取从第i(i的初值为p)个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1，直至串S中不存在和串T相等的子串为止。intIndex(StringS,StringT,intp){//T为非空串。若主串S中第p个字符之后存在与T相等的子串，//则返回第一个这样的子

10、串在S中的位置，否则返回0if(p>0){n=StrLength(S);m=StrLength(T);i=p;while(i<=n-m+1){SubString(&sub,S,i,m);if(StrCompare(sub,T)!=0)++i;els