严蔚敏数据结构(串).ppt

第4章 串（String） 练1：串是由 字符组成的序列，一般记为 。 串的抽象数据类型定义（参见教材P71） 例： 设 s =’I AM A STUDENT’, t =’GOOD’, q=’WORKER’。求： 4.2 串的表示和实现 定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例：用顺序存储方式实现求子串函数SubString(Sub, S, pos, len) 堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。 例：用“堆”实现串插入操作(教材P75) 附：堆分配存储表示(教材P76) 链式存储特点 ：用链表存储串值，易插入和删除。 4.3 串的模式匹配算法 算法种类： ② BF算法的实现—即Index（）操作的实现 （见教材P79） KMP算法（特点：速度快） ① KMP算法设计思想 ② KMP算法的推导过程 ③ KMP算法的实现 （关键技术:计算next[j]） ④ KMP算法的时间复杂度 ① KMP算法设计思想： (参见教材P80-84） ② KMP算法的推导过程：（见教材P81） ② KMP算法的推导过程(续）： ③ KMP算法的实现—即Index( )操作的实现 （见教材P82） 第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来； 第二步：执行定位函数index_kmp （与BF算法模块非常相似） 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？ 例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 next[j] : 实际上是有个诀窍的,说白了很简单就以a b a b a?a?b a b0 1?1 2 3?4?2 3 4?为例?next[j] 里面 开头的红色01?没什么好说的,固定格式.我就以兰色的4?来说明下为什么是4.?与4有关的, 是4所对应的兰色a之前的所有的字符,即紫色的?a b a b a?这个字符串中所有符合匹配条件的字符串如下a b a b a a b a b aa aa b a a b a 最长的匹配字符串(a b a b a本身除外)在这里 ,长度为3, 再加上1,就是4了注意next[ j ]中4?的位置! 至于为什么要加1?,大家自己去思考吧, 明白了为什么要加1,KMP算法也就自然明白了next[ j ]中其他位置的数值也可以用同样的方法得出 讨论两个有关next [ j ]的问题： ① 怎样计算next[j]？ 可用递推法编程实现！ ④ KMP算法的时间复杂度 因为计算next[j]的时间为O(m); 且Index_KMP函数（没有回溯）的匹配时间为O(n); 所以KMP算法的总时间耗费为： O(n+m) 注意：由于BF算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。 * 4.2 串的表示和实现 4.3 串的模式匹配算法 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 4.1 串类型的定义 记为： s =‘ a1 a2 …….. an’ (n≥0 ) 串名 串值（用‘ ’ 括起来） 串中字符个数（n≥0）. n=0 时称为空串 ? 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 4.1 串类型的定义 若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等： 隐含结束符‘\0’ ，即ASCII码NULL 练2：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 a是c和d的子串，在c和d中的位置都是1 练3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串.