ppt课件-数据结构讲义(严蔚敏版)第四章 串.pptVIP

4.2.3 串的块链存储表示 特点：以一组存储单元（在程序执行过程中动态分配）存放串值字符序列-串的链表表示。 A B C D E F G H I # # # ^ head A B C I ^ head …… 结点大小为4的链表 结点大小为1的链表 * C语言描述串的块链存储表示 #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; //串的头和尾指针，便于联结操作 int curlen; // 串的当前长度 } LString; 4.2.3 串的块链存储表示 * 串的块链存储表示小结 串的块链存储结构-串的链表表示。 除了某些特定操作如联接有一定方便之处，总的来说不如另外两种存储结构灵活 结点大小为1 优点:操作方便； 缺点:存储密度较低，占用存储量大。所谓存储密度为： 结点大小为4 优点：存储密度高； 缺点：插入、删除字符时，可能会引起结点之间字符的移动，算法实现比较复杂。 存储密度＝ 串值所占存储位 实际分配存储位 * 4.3 串的模式匹配算法 模式匹配：子串T在主串Ｓ中的定位操作。 目标：主串S 模式：子串T(模式串) 匹配有两种结果： 匹配成功:S中有模式为T的子串，返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可 匹配失败:若S中无模式为T的子串，返回值为零 方法 BF(Brute-Force)算法：经典的、朴素的、穷举的 首尾匹配算法 KMP算法：速度快 * KMP算法的思想 D.E.Knuth,J.H.Morris 和V.R.Pratt发现。简称KMP算法。 KMP算法的思想 i指针不回溯，效率高，速度快． 将主串与模式串的匹配转化成模式串自身的匹配 当模式串第j个字符与主串中对应字符失配时,模式串应向右滑动尽量远的距离，以减少匹配的次数。到底滑动多远? 当j=1时 其他情况 当此集合不空 * 产生失配（si ?pj）时 设si应与模式串的第k（kj）个字符比较，则有： 　　　　　　 部分匹配结果： 于是： 主串与模式串匹配转化成模式串自身匹配 s1s2s3……si-k+1si-k+2…si-1 si p1p2…pj-k+1 pj-k+2 …pj-1 pj i j i p1 p2 … pk-1 pk…pj-1pj s1s2s3……si-k+1si-k+2…si-1　 si j j ‘p1p2…pk-1’ = ‘si-k+1si-k+2…si-1’ (4-2) ‘pj-k+1pj-k+2…pj-1’ = ’si-k+1si-k+2…si-1’　　　(4-3) ‘p1p2…pk-1’ =‘pj-k+1pj-k+2…pj-1’ 　　　(4-4) * 模式串的next函数值(1) 令next[j] = k, 表明当模式中第j个字符与主串中相应字符“失配”时，在模式串中需重新和主串中该字符进行比较的字符位置为k。next函数的定义： next[j+1]＝？有两种情况： （1）若pk=pj, 则表明在模式串中有： ‘p1p2…pk-1pk’ = ‘pj-k+1pj-k+2…pj-1pj’ 　　　则 （2）若pk ? pj，则表明在模式串中有 ‘p1p2…pk-1pk’ ? ‘pj-k+1pj-k+2…pj-1pj’ 但：‘p1p2…pk-1’ =‘pj-k+1pj-k+2…pj-1’ next[j+1]=next[j]+1 = k+1 当j=0时 其他情况 当此集合不空 * 结论：将模式向右滑动至模式中的第next[k]个字符和主串中第j个字符相比较。设next[k]=k’，有： ①如果pk‘=pj，则说明在主串第j+1个字符之前存在一个长度为k‘（即next[k]）的最长子串，和模式串中从首字符起长度为k‘的子串相等。即 ‘p1p2…pk’’ = ‘pj-k’+1pj-k’+2…pj’ 于是有next[j+1]=next[k]+1=k’+1 ②若pj?pk’，则将模式继续向右滑动至模式中第next[k’]个字符与pj对齐。依次类推，直至pj和模式串中某个字符匹配成功或者不存在任何k’（0k’j)满足如下等式： ‘p1p2…pk’” = “pj-k’+1pj-k’+2…pj’ 此时有： next[j+1] = 1