数据结构ppt课件.ppt

第四章串*1."串就是线性表"的结论是否正确?从数据结构的观点来说,串是一种特殊的线性表;但就数据类型而言,串不是线性表。?希望你带着这个问题开始这一章的学****并能在学完这一章的内容之后能得出正确的结论。*“串”类型定义中各基本操作的特点,并能正确利用它们进行串的其它操作。。。*相对于其它各个知识点而言,本章非整个课程的重点,鉴于串已是多数高级语言中已经实现的数据类型,因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法,并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想,但它不属本章学****的基本要求,更不是重点学****内容。【知识点】串的类型定义、串的存储表示、串匹配、KMP算法*虽然目前各常用的高级语言中都已经实现了串类型,但由于它是通过软件实现的,因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题,如果有兴趣可以试试以下几个题:,,,,,,,。其中前6个是练****串的基本操作的应用,后2个是和KMP算法相关的练****串的模式匹配算法*、(string)是由零个或多个字符组成的有限序列,记作s='a1a2…an',其中s为串的名字,用成对的单引号括起来的字符序列为串的值,但两边的引号不算串值,不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数,称为串的长度。,它的长度n=0,记为s=''。,称为空格串,它的长度n为空格的个数,一般用符号“ø”表示空串。串是有限长的字符序列,由一对单引号相括,如:astring*、主串通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。若一个串是另一个串中连续的一段,则这个串称为另一个串的子串,而另一个串相对于该串称为主串。例如,串s1=“abcdefg”,s2=“fabcdefghxyz”,则s1为s2的子串,s2相对于s1为主串。另外,空串是任意串的子串,任意串是自身的子串。若一个串的长度为n,则它的子串数目为+1,真子串个数为(除串本身以外的子串都称为真子串)。当且仅当两个串的值相等时,称这两个串是相等的,即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。*二、串的抽象数据类型的定义如下:ADTString{数据对象:D={ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}*基本操作:StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)pare(S,T)StrLength(S)Concat(&T,S1,S2)*