数据结构ppt课件.ppt

《数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串1【课前思考】1."串就是线性表"的结论是否正确？从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。2.串和线性表的主要差别是什么？希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。2【学习目标】1.理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。3.理解串匹配的各种算法。3【重点和难点】相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串

2、类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。【知识点】串的类型定义、串的存储表示、串匹配、KMP算法4【学习指南】虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题，如果有兴趣可以试试以下几个题:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6个是练习串

3、的基本操作的应用，后2个是和KMP算法相关的练习。54.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法64.1串的类型定义一、基本概念1．串的定义串(string)是由零个或多个字符组成的有限序列，记作s='a1a2…an'，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的引号不算串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2．空串不含任何字符的串称为空串，它的长度n=0，记为s=''。3．空格串含有一个或多个空格的串，称为空格串，它的长度

4、n为空格的个数，一般用符号“ø”表示空串。串是有限长的字符序列，由一对单引号相括，如:astring74．子串、主串通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为+1，真子串个数为

5、(除串本身以外的子串都称为真子串)。当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。8二、串的抽象数据类型的定义如下：ADTString{数据对象：D＝{ai

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

7、ai-1,ai∈D,i=2,...,n}9基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)S

8、trLength(S)Concat(&T,S1,S2)10SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTString11StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。12StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。13DestroyString(&S)初始条

9、件：串S存在。操作结果：串S被销毁。14StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。表示空串，空串的长度为零。15StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>016StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。17Co

10、ncat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：Concate(T,man,kind)求得T=mankind18SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤