数据结构(严蔚敏)第四章(精品·公开课件).ppt

第 四 章 串 第 四 章 串 本章学习另一种特殊的线性表，它特殊在：1 ．数据元素都是来自字符集！2 ．由于数据元素特殊，它的操作有些不同与 一般线性表， 例如：操作的对象一般是对子串（即一组数据元素）,而不是单个数据元素! §4.1 串的逻辑结构及定义一 串的逻辑结构 1 、串（String）：简单说，它是有限字符集中的零个或多个字符组成的有限序列。 按数据结构来定义：它是一种特殊的线性表（数据元素之间的关系是线性关系），特殊在其数据元素来自于字符集这个数据对象。定义为： §4.1 串的逻辑结构及定义一 串的逻辑结构 一个串一般记作：S = ‘c1c2…cn’ 2 、串结构的特点：数据元索都是字符，它的操作的对象一般不再是单个数据元素，而是一组数据元索。 3 、串的一些术语： §4.1 串的逻辑结构及定义一 串的逻辑结构 字符在串中的位置：字符在串中的序号（即第几个数据元素）; 子串在串中的位置：子串的第一个字符在主串中的位置； 串相等：两个串的长度相等，且各对应位置处的字符都相等； 例如:a,b,c,d 四个字符串为 a=‘BEI’ , b=‘JING’ c=‘BEIJING’ , d=‘BEI JING’ 它们的长度分别为 3,4,7,8 a和b都是c和d的子串 a在c和d中的位置都是1 b在c中的位置是4,而b在d中的位置是5 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 §4.1 串的逻辑结构及定义 一 串的逻辑结构 3）判空操作 StrEmpty(S) 功能：若为空串，则返回TRUE，否则返回FALSE 4） 串比较操作 StrCompare( S, T) 功能:若ST，则返回值0；若S=T，则返回值=0； 若ST，则返回值0 5）串置空操作 ClearString( S) 功能：将S清为空串 §4.1 串的逻辑结构及定义 一 串的逻辑结构 9） 求子串位置操作Index( S, T, pos ) 功能：返回S中第pos个字符之后与T相同的子串的位置，若不存在返回0 10) 串插入操作 StrInsert( S, pos , T) 功能：将串T插入到串S的第pos字符之前 11）串删除操作 StrDelete( S, pos , len) 功能：从串S中删除第pos个字符起长度len 为子串 §4.1 串的逻辑结构及定义 二 串的ADT描述 §4.1 串的逻辑结构及定义 二 串的ADT应用举例 上述11种基本操作中,下面5种操作构成最小操作子集: 串赋值 StrAssign; 串比较 StrCompare; 求串长 StrLength; 串联结 Concat; 求子串 Substring; 其它操作可以用其实现 §4.1 串的逻辑结构及定义 二 串的ADT应用举例 例1:利用判断串相等,求串长度,求子串操作实现定位操作. §4.1 串的逻辑结构及定义 二 串的ADT应用举例 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 一、串的顺序存储结构（串的静态存储结构） 1 、存储方式：同一般线性表的顺序存储结构完全相同。用一组地址连续的存储单元存储串的字符序列，据预定义的大小，为每个定义的串变量分配一个固定长度的存储区． §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 3 虚拟实现 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 此外，还可以用另一种方式表示串长，即以‘\0 ’字符作为串的结束标志．串长隐含其中（C 语言的字符串是以这种方式实现）. 实际的串值存放在下标为O--MAXSTRLEN -1 的单元中，而下标为MAXSTRLEN 的单元存放‘\ O ’字符． §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 4 串的连接操作Concat(T,S1,S2)的算法示意图 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 5 取子串 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 6 、子串定位 模式匹配：在一个主串中，查找子串是否存在，存在返回子串的位置；不存在返回O 。子串称为模式。 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 §4.2串的表示及实现 §4.2.1串的顺序存储结构及操作虚拟实现 int Ind