数据结构-幻灯片(第四章)

《数据结构-幻灯片(第四章)》由会员分享，可在线阅读，更多相关《数据结构-幻灯片(第四章)（65页珍藏版）》请在金锄头文库上搜索。

1、第四章 串结构,本章学习另一种特殊的线性表，它特殊在： 数据元素都是来自字符集！由于数据元素特殊 它的操作有些不同于一般线性表，例如： 操作的对象一般是子串（即一组数据元素） 而不是单个数据元素！,有些高级语言已经把串ADT物理实现了，所 以，我们这里只是简单讨论一下串的逻辑特性、 存储结构及一些操作的实现。,4.1 串的逻辑结构及操作,一、串的逻辑结构,1、串(String): 简单说，它是有限字符集中的零个 或多个字符组成的有限序列。 按数据结构来定义：它是一种特殊的线性表 （数据元素之间的关系是线性关系），特殊在其 数据元素来自于字符集这个数据对象。定义为：,String=(D,R) D

2、=ci | ciD0 D0=CHARACTER i=1,2,.,n n=0 R= | ci-1,ci D0 i=2,3,.,n,4.1 串的逻辑结构及操作,一个串一般记作： S=,2、串结构的特点: 数据元素都是字符，它的操作的对象一般不再 是单个数据元素，而是一组数据元素。,3、串的一些术语:,空串：长度为零的字符串，n=0,空格串：数据元素都是空格的字符串；,一、串的逻辑结构,4.1 串的逻辑结构及操作,字符在串中的位置：字符在串中的序号（即第几个 数据元素）；,子串在串中的位置：子串的第一个字符在主串中的 位置；,串相等：两个串的长度相等，且各对应位置处的字 符都相等；,子串：串中连续的

3、任意个字符组成的子序列， 称为该串的子串；,主串：包含子串的串；,一、串的逻辑结构,4.1 串的逻辑结构及操作,串的常用操作包括:,串置空 SetNULL(s),串赋值(创建) Assign(s,t) Create(s,ss),判断串是否相等 Equal(s,t),求串长度 Length(s),串联结 Concat(s,t),取子串 Substr(s,start,len) Substr(s,start,end),定位 Index(s,t),二、串结构常定义的操作,4.1 串的逻辑结构及操作,串置换 Repacle(s,t,v),串插入 Insert(s,pos,t),串删除 Delete(s,

4、pos,len),可以看出：串的操作有一个特点，即对一组 数据元素进行操作！,判断是否空串 ISNULL(s),二、串结构常定义的操作,4.1 串的逻辑结构及操作,三、串的ADT描述,ADT String data structure: D=ci | ciD0 i=1,2, n=0 R= | ci-1,ci D0 D0=CHARACTER i=2,3,4,. operations: Setnull(S); Assign(s,t); Create(s,ss); Equal(s,t); Length(s); Concat(s,t); Substr(s,start,len) ; Index(s,t)

5、; Repacle(s,t,v); Insert(s,pos,t); Delete(s,pos,len); END,四、串的ADT应用举例,4.1 串的逻辑结构及操作,s,t,s2,s1,t,s1,s2,例1：将串 t 插入在串 s 中的第 i 个位置之后。,算法省略,4.1 串的逻辑结构及操作,例2：从串 s 中删除子串 t 。,s,t,s1,s2,算法自己写出,4.1 串的逻辑结构及操作,例3：利用判断串相等、求串长度、求子串等操作实现定位操作。,1 2 3 4 5 6 7,s,t,4.1 串的逻辑结构及操作,int Index(String S, String T, int pos) /

6、T为非空串，返回主串S中从第pos个字符开 /始的与T相同的子串的位置 if(pos0) n=Length(S); m=Length(T); i=pos; while(i=n-m+1) SubStr(sub,S,i,m); if(Equal(sub,T)!=0 +i; else return i return 0 ,算法如下：,一、串的顺序存储结构,1、存储方式：同一般线性表的顺序存储结构完全 相同。用一组地址连续的存储单元存储串的字符 序列，用curlen代替last指示串的长度。,2、特点：简单、方便，但空间效率低，插入、 删除要移动字符，时间效率低。,3、虚拟实现：,于是可用C+语言描述

7、为: const int maxsize=maxlen； typedef char elemtype; /定义数据元素类型为CHAR struct seqstring elemtype chmaxsize; /表示存放串值的连续空间 int curlen; /curlen当前串的长度 ；,1、串数据结构的特点,2、串ADT与高级语言的串类型是什么关系？,各个高级语言中的串类型（及运算函数）是否都一样？为什么？,特殊的线性数据结构，特殊在哪里？,数据元素是字符集，使得其操作的操作对象不再是 单个数据元素，而是一组元素子串。,串ADT就是串类型的原始模型，串类型是串ADT的 物理实现。,3、串的A

8、DT,ADT String data structure: D=ci | ciD0 i=1,2 n=0, D0=CHARACTER R=N N= | ci-1,ci D0 i=2,3,4,. operations: Setnull(S); Assign(s,t); Create(s,ss); Equal(s,t); Length(s); Concat(s,t); Substr(s,start,len) ; Index(s,t); Repacle(s,t,v); Insert(s,pos,t); Delete(s,pos,len); END,4、串的ADT基于顺序存储结构的虚拟实现,const

9、int maxsize=maxlen； typedef char elemtype; /定义数据元素类型为CHAR struct seqstring elemtype chmaxsize; /表示存放串值的连续空间 int curlen; /curlen当前串的长度 ；,需要注意的一个问题：紧缩与非紧缩,字符存储是存储的它的编码，我们知道编码的方式有 很多，但是它的值都是有限的，例如：0255。 如果采用的是字（一般包括几个字节）编址方式，一 个数组元素占用一个字单元，存放一个字符，显然，字 比较大时，空间是占不满的！ 例如：一般字符的编码在0255，则存放一个编码用 一个字节就够了，如果一个

10、字是4个字节，则存放一个字 符有3个字节没有使用！,非紧缩存储方式,紧缩 PACKED,二者比较：,紧缩方式：可以节省空间，但需花费时间去分 离一个单元中的字符；,非紧缩方式：操作方便，空间利用率低！,现在，计算机一般采用字节编址，所以字符存放 采用字节为单位，即一个字节存放一个字符！,二、串在顺序存储结构下各运算的虚拟实现,1、判断串相等,长度相等，逐个字符比较 算法略,2、串联结,分几种情况： s.curlen+t.curlenmaxlen) AND(s.curlenmaxlen): 没有正常联结 但联接了部分 s.curlen=maxlen: 没有正常联结,3、取子串,有两种取法：其一：

11、已知子串起点和长度； 其二：已知子串起点和终点；,模式匹配：在一个主串中，查找子串是否存在， 存在返回子串的位置；不存在返回0。 子串称为模式。,4、子串定位,实现它的方法也很多，如BF算法、KMP算法、 BM算法、KR算法等等。 我们只介绍两种： BF算法最简单的匹配算法； KMP算法效率较高的匹配算法；,BF算法的基本思想： 从主串的第i个位置开始，与子串的每个字 符逐个比较，若均相等，则找到；否则，即在 某个位置出现了不等，则说明从该起点开始的 子串不是模式串，换一个新起点，重新开始！,1 2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8,a a b a,a a c,a a

12、 c b b b,a a a c a a c b,每次： 主串回溯到上次起点的下一个位置； 模式串回到1,int INDEX ( seqstring s, seqstring t, int pos) /返回子串t在主串s中第pos个字符之后的位置， /若不存在返回0 i=pos; j=1; while ( it.curlen ) return (i-t.curlen); else return (0); /匹配失败 ,回溯 i:=i-j+1+1,算法效率：,设主串长度为 m ，模式串长度为 n ; 找到模式串（无回溯）： 最好：开始就是模式串, O(n) aaaaabbbbbb aaa 最坏：

13、最后是模式串， O(m) cbbbcbcbaaa aaa 找不到模式串（无回溯）: O(m) aaaaaaaaaaaa xyz,O(m),找到模式串（有回溯）： 最好：回溯很少，或没回溯 O(Index+n) O(m+n) abcabcabcaab aab 最坏：回溯很多，或每次都有回溯 O(Index*n) O(m*n) aaaaaaaaaaaa aaab 找不到模式串（有回溯）: O(m*n) aaaaaaaaaaaa aaac,O(m*n),BF算法的特点：,a、时间复杂性最坏为 O(m*n) ，但一般情况下为 O(m+n)，所以还是一个常用算法。 b、由于有回溯，所以主串输入后必须保存

14、。,下面介绍一种改进的模式匹配算法KMP算法 D.E.Knuth J.H.Morris V.R.Pratt,按照BF算法：当比较到某个位置，不匹配时，不管比 过的字符串是什么情况，都是进行回溯！那么，有没有可能 在比较过的串中存在部分匹配的信息呢？,假设主串为 s= s1s2s3.sn 模式串为 t= t1t2t3.tm mn 子串 sisi+1.sj titi+1.tj 分别用 sij 和 tij 表示 则模式匹配可描述为： 求最小的 i ， 0i n-m ，使得 t1m=si+1,.i+m,I、KMP算法的基本思想：,假设在 s 中从 si+1开始匹配，遇到一个不完全的匹配，即得到一个 q

15、 (1si+1i+q+1,如果能确定一个最小的整数 ii+1,i+2,.,i+q 使得 t1k=si+1.i+k，其中 k=i+q-i 那么，哪些测试和比较是多余的？,k,i+1,i+k,A、由上面可知：对于 任意 l ， isl+1l+k 从而可以肯定有 t1msl+1l+m （部分不匹配，整体肯定不匹配！） 即下一步匹配可以跳到 si+1,都不可能作为 匹配的起点！,ili,B、由于 t1k=si+1i+k 所以从 i 开始的比较 可以从 i+k+1 开始，即从 tk+1 与 si+k+1 比较 开始。,那么如何求 i 呢？,t1k=si+1i+k,si+1,si+q,t1,tq,x,si+q+1 si+k+1,tq+1,si+1,t1q=si+1i+q,t1q+1si+1i+q+1,t1k=si+1i+k,k,k,tk+1,假设 k=i+q-i，所以，确定 i 就等价与确定 k, 即在i+1,i+2,.i+q中找最小的整数 i使得 t1k=si+1.i+k