第四章串的模式匹配ppt课件.ppt

《第四章串的模式匹配ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串第四章串1、熟悉串的概念、类型定义及其基本操作2、掌握串不同存储结构的定义及各种存储结构下基本操作的实现方法3、掌握串匹配的各种算法尤其是KMP算法1、串的相关概念串(String):零或多个字符组成的有限序列，实际就是元素限定为字符的特殊线性表,记作s=‘a1a2…an’，C程序中用””例:a=‘BEI’b=‘JING’c=‘BEIJING’D=‘BEIJING’概念:串的长度子串主串子串在主串中的位置(子串第一个字符的位序)串相等串比较空串空格串φ串是一个特殊的线性表，但一般线性表的基本操作常以“单个元素”作为处理单位，如插入/删除某元素;而串的操作中多以“

2、多个字符组成的串”为处理单位,如串的连接、求子串等,因此对串类型及其操作重新进行定义4.1串类型的定义Concate(T,man,kind)求得T=mankind2、串的ADT定义ADTString{数据对象：D={ai

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

4、ai-1,ai∈D,i=2,…n)基本操作：//字符串生成、销毁操作StrAssign(&T,chars)初始条件:chars是字符串常量操作结果:生成值等于chars的串TStrCopy(&T,S)初始条件:串S存在操作结果:由串S复制得串T

5、Concat(&T,S1,S2)初始条件:串S1和S2存在操作结果:由S1与S2连接构成新串TDestroyString(&S)初始条件:串S已存在操作结果:销毁串SConcate(T,man,kind)求得T=mankind串的ADT定义---加工型操作ClearString(&S)初始条件:串S已存在操作结果:将S清为空串StrInsert(&S,pos,T)初始条件:串S和T存在,1<=pos<=StrLength(S)+1操作结果:在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)初始条件:串S存在,1<=pos<=StrL

6、ength(S)-len+1操作结果:从S中删除第pos个字符开始长len的子串Replace(&S,T,V)初始条件:串S,T和V均已存在,且T是非空串。操作结果:用V替换主串S中出现的所有与T相等的不重叠子串S=chater，T=rac，则StrInsert(S,4,T)后S=characterS=abcbabcbaabcbcb,T=bcb若V=x则置换后得S=axaxaaxcb若V=bc则经置换后得S=abcabcaabccb串的ADT定义—引用型操作StrLength(S)初始条件:串S存在操作结果:返回S中元素的个数，即串长

7、StrEmpty(S)初始条件:串S已经存在操作结果:空串返回TRUE,否则返回FALSESubString(&Sub,S,pos,len)初始条件:S存在,1≤pos≤StrLength(S),0≤len≤StrLength(S)-pos+1操作结果:用Sub返回串S中第pos个字符起长度为len的子串StrCompare(S,T)初始条件:栈S已串S和T存在操作结果:S>T返回值>0,S=T返回0,S

8、等的子串则返回“该子串在主串s中的位置”(子串第一个字符的位序,pos后),否则返回0.StrCompare(date,data)>0StrCompare(cat,cate)<0相等返0,否则返第一个不同字符之“差”或长度差等SubString(sub,commander,4,3)求得sub=manSubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r；SubString(sub,student,5,0)求得sub=φ或S

9、ubString(sub,beijing,7,2)求得sub=?S=abcaabcaaabc,T=bcaIndex(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0串的基本操作集不同语言有不同的定义方法，应以相应语言的参考手册为准。如C语言如下：char*gets(char*str);//遇回车结束,函数值也为str,intputs(char*str);//将’’转为’’输出,函数值为‘’或EOFchar*strcat(char*destin,char*source)/