第3章字符串数组特殊矩阵.pptVIP

第3章字符串数组特殊矩阵第1页，共34页，星期日，2025年，2月5日*/35数据结构引言第一章概论第二章线性表第三章广义表、字符串、数组和特殊矩阵第四章递归技术第五章树和二叉树第六章图第七章检索第八章内排序第九章外排序第十章动态存储管理第2页，共34页，星期日，2025年，2月5日*/35字符串概念及数据结构、实际存储方式、应用字符串的模式匹配朴素的模式匹配算法快速模式匹配算法(KMP算法)数组特殊的矩阵对称阵、三角阵、带状矩阵(X对角阵)稀疏矩阵广义表第三章字符串、数组、广义表、特殊矩阵第3页，共34页，星期日，2025年，2月5日*/351.字符串概念及数据结构定义：由零个或多个字符构成的有限序列，一般可表示成如下形式：c1c2c3….cn，(n≥0)。当n=0时表示空串。ADTstring{

数据对象D：由零个或多个字符构成的有限集合；

数据关系R：{ai,ai+1|其中ai,ai+1?D,i=1,2,……n-1}

字符串的基本操作如下：

}ADTstring1）Strcreate(S)

2）Strassign(S,T)

3）Strlength(S)

4）Strempty(S)

5）Strclear(S)

6）Strcompare(S1，S2)

7）Strconcat(S1，S2)8）Substring(S,i,len)

9）Index(P,T)

10）Strinsert(S,i,T)

11）Strdelete(S,i,len)

12）Replace(S,T1,T2)

13）Strdestroy(S)第4页，共34页，星期日，2025年，2月5日*/351.字符串字符串的实际存储方式静态存储结构：即顺序存储结构；堆存储结构：顺序存储+动态分配；——即总空间足够大，且顺序(地址连续)，执行时在此空间动态分配/释放字符串。链式存储结构串名的存储映象：即建立串名和串值之间的对应关系的一个符号表。对C中的字符串，若从输入设备读取，最好定义为字符数组，而非字符指针。二者在空间分配方面有很大不同。第5页，共34页，星期日，2025年，2月5日*/351.字符串相关知识串的表示、字符的表示、空串及其表示、主串、子串、子串在主串中的位置、串的相等（一一对应）基本运算：插入、删除、求子串、串的连接应用举例已知S=(xyz)+*，T=(x+z)*y。试利用连接(||)，求子串(substr(s,i,j))和置换(replace(s1,i,j,s2))等基本操作，将S转化为T.已知三个字符串分别为S=ab…abcaabcbca…a，S1=caab，S2=bcb，利用所学字符串基本运算函数得到结果串为：S3=caabcbca…aca…a1、s1=substr(s,1,5)//s1=(xyz)s2=substr(s,3,1)//s2=ys3=substr(s,6,1)//s3=+s4=substr(s,7,1)//s4=*replace(s1,3,1,s3)//s1=(x+z)s=s1||s4||s2//s=(x+z)*y2、a=index(S,S1,1)==定位caab的起始位置b=index(S,S2,1)+3==定位ca…a的起始位置，3是S2的长度x=substring(s,a,strlength(s)-a+1);y=substring(s,b,strlength(s)-b+1);S3=concat(x,y)第6页，共34页，星期日，2025年，2月5日*/351.字符串的模式匹配模式匹配的含义给定文本串t和模式串p，编制算法寻找模式p在文本串t中首次出现的起始位置。|t|≥|p|,|x|表示字符串x的长度。——即判断p是否为t的一部分，若是，返回首次出现位置。朴素的模式匹配算法注意探测每一位置是否能匹配成功。能否优化？simpleMatch(t,p){for(i=0;i|t|;i++)ifsuccess(t,p,i)returni;return0}success(t,p,i){for(j=0;j|p|;j++)if(t[i+j]!=p[j])return0;return1}第7