欢迎来到天天文库
浏览记录
ID:52237245
大小:769.50 KB
页数:59页
时间:2020-04-03
《数据结构课件第四章串.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1第四章串2021/8/122开始学习本讲前要知道:从数据结构角度看,串也属于线性结构,具有线性结构的共同特征;学习本章时,要注意到串所具有的线性结构的共性,更要掌握其个性;串的特殊性主要是:串的元素是字符;本讲具体内容见本章目录。2021/8/123本章目录4.1串类型的定义4.2串的表示和实现4.2.1串的顺序存储结构4.2.2串的链式存储结构4.3串的模式匹配4.3.1朴素的模式匹配算法4.3.2KMP算法4.4串的应用举例4.5算法设计举例2021/8/124知识点和难点重点知识点基本概念串操作模式匹配难点重点根
2、据给定操作,编写其它操作的算法(如,根据前5个基本操作,编写index,replace操作KMP算法模式串的next和nextval函数值手工模拟KMP算法的执行过程串的其它算法。54.1串的基本概念及其操作4.1.1串的基本概念串是由n(n≥0)个字符组成的有限序列。表示为s=“a0a1a2…an-1”长度为零的串称为空串由一个或多个空格组成的串称为空格串。由串中任意连续字符组成的子序列称为子串,而包含子串的串称为该子串的主串。单个字符在字符串中的序号称为该字符在串中的位置,而子串的第一个字符在主串中的位置称为子串的位
3、置。若两个串的长度相等且对应位置上的字符也相等,则称两个串相等。64.1.1串的基本概念例如,四个字符串S1=φS2=“”S3=“DataStructure”S4=“Struct”与线性表相比串有其特殊性:串的数据元素只能是字符类型;串以子串为操作单位。2021/8/127自测题1下面关于串的的叙述中,哪一个是不正确的?A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存储2021/8/128自测题2串是一种特殊的线性表,下面哪个叙述体现了这种特殊性?A.
4、数据元素是一个字符B.可以顺序存储C.数据元素可以是多个字符D.可以链接存储2021/8/129自测题3串的长度是指()【北京工商大学2001一.6(3分)】A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数2021/8/1210自测题4设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为()。【中科院计算所1997】A.2n-1B.n2C.(n2/2)+(n/2)D.(n2/2)+(n/2)-1E.(n2/2)-(n/
5、2)-1F.其他情况114.1.2串的抽象数据类型ADTString数据元素集合:字符的一个有限序列。基本操作:初始化串(InitString):初始化串求串长(StrLen):求取字符串中字符的个数取子串(SubStr):获取字符串中的一个连续字符序列定位串(Index):查找是否存在子串串连接(Concat):连接两个字符串形成一个新串串比较(StrCmp):比较两个串的大小判空串(StrEmpty):判断所给字符串是否为空串串替换(StrReplace):替换字符串中指定的所有子串串赋值(StrAssign):给串
6、赋值串插入(StrInsert):在串的指定位置处插入新串串删除(StrDelete):删除串中指定位置开始的数个字符124.2串的顺序存储结构4.2.1串的定长顺序存储表示采用静态内存分配方式,分配一组地址连续的存储单元,用来存放串的字符序列。串的定长顺序存储表示用C语言描述:#defineSTRSIZE100typedefstruct{charch[STRSIZE];intlength;}SqString;134.2.1串的定长顺序存储表示(1)初始化串intInitString(SqStringS,charstr)
7、{inti,len=0;charc=str;while(c!=' '){len++;c++;}/求str的长度/S->length=len;/置串的当前长度值/for(i=0;ilength;i++)/赋值串值/S->ch[i]=str[i];return1;}144.2.1串的定长顺序存储表示(2)串插入操作步骤:判断指定的插入位置是否合法。根据串长决定是否作截断处理:若插入后的串长小于STRSIZE,则正常插入;若插入后的串长大于STRSIZE,且串T可以全部插入,则主串S被部分截断;否则串T和串S都要被部
8、分截断。插入位置后的所有字符依次后移子串的长度。插入子串。修改串长域。154.2.1串的定长顺序存储表示intStrInsert(SqStringS,intpos,SqStringT){inti;if(pos<0pos>S->length){printf("插入位置不合法,其取值范围应该是[0,length]");r
此文档下载收益归作者所有