文档介绍：该【41串类型的定义42串的表示和实现43串的模式匹配算法课件 】是由【wwlgqnh】上传分享，文档一共【40】页，该文档可以免费在线阅读，需要了解更多关于【41串类型的定义42串的表示和实现43串的模式匹配算法课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。重点:(1)ADT串的设计、实现方法和基本操作;(2)串的简单模式匹配算法,KMP算法。
难点:串的模式匹配算法中的KMP算法。
本章重点难点
重点:(1)ADT串的设计、实现方法和基本操作;(2)串的
第4章串
串是由零个或多个字符组成的有限序列。
记为:s=”a1a2…an”(n≥0)
其中,s是串的名,用双引号括起来的字符序列是串
的值。
(1)串的长度:串中字符的数目n。
(2)空串(Nullstring):长度为零的串。
(3)子串:串中任意个连续的字符组成的子序列。
串的有关术语
串(String)的定义
(4)主串
包含子串的串相应地称为主串。
(5)串相等
只有当两个串的长度相等,并且各个对应位置的字符都相等,称两串相等。
(6)空格串(空白串)(blankstring)
由一个或多个空格组成的串。要和“空串”区别,空格串有长度就是空格的个数。
串的有关术语
(4)主串串的有关术
(1)串数据对象约束为字符集。
(2)基本操作的对象不同,线性表以“单个元素”为操作对象;串以“串的整体”为操作对象,操作的一般都是子串。
串与一般线性表的区别
(1)串数据对象约
ADTString{
数据对象:
数据关系:
基本操作:
}ADTString
串的ADT定义
见下页
D={ai|ai∈CharacterSet,i=1,2,...,n,n≥0}
R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
ADTString{串的ADT定义见下页D={ai
基本操作:
StrAssign(&T,chars)//根据串常量chars生成串T
StrCopy(&T,S)//把串S中内容拷贝到T串
DestroyString(&S)//销毁串S
StrEmpty(S)//判断串是否空
StrCompare(S,T)//比较串S和T
StrLength(S)//求串长
Concat(&T,S1,S2)//连接串
基本操作:StrAssign(&T,chars)
基本操作:
SubString(&Sub,S,pos,len)//求子串
Index(S,T,pos)//子串定位
ClearString(&S)//清空串S
StrDelete(&S,pos,len)//删除子串
Replace(&S,T,V)//把串S中符合T的子串替换
StrInsert(&S,pos,T)//插入子串
基本操作:SubString(&Sub,S,pos
、定长顺序存储表示
、堆分配存储表示
、串的块链存储表示
、定长顺序存储表示
#defineMAXSTRLEN255
//用户可在255以内定义最大串长
typedefunsignedcharSstring[MAXSTRLEN+1];
//0号单元存放串的长度
SstringS;
串的顺序存储C语言实现
#defineMAXST