数据结构课件第四章串.ppt

《数据结构课件第四章串.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