《第六讲 KMP算法栈》由会员分享，可在线阅读，更多相关《第六讲 KMP算法栈（44页珍藏版）》请在金锄头文库上搜索。
1、1 KMP算法 栈及其应用 2009 03 10 2 助教负责安排 王磊 wanglei 00511027 00611065彭跃辉 pengyuehui 00711003 00711049邓昌明 triday d 00711051 00711076马秀娟 maxj07 00711078 00711114刘亮 fanxing0701 00711115 00724079Email 负责助教 teacherhu 上机 前三组 4号机房 后两组5号机房 3 内容 作业补充题讲解KMP算法栈及其应用 4 循环链表排序 冒泡法 5 6 循环链表排序 7 关于程序的白盒调试 明确算法思路分步分层隔离考察边界
2、点 8 无回溯的模式匹配方法 KMP算法 基本思想无回溯的模式匹配算法匹配算法的时间效率分析Next数组计算 9 基本思想 1 要找到一个无回溯的模式匹配算法 关键在于当匹配过程中 一旦pi与tj比较不等 即 SubStr Seq p 1 i 1 SubStr Seq t j i 1 i 1 pi tj要能立即确定p右移的位数和继续 无回溯 比较的字符 也就是说应该用p中的哪个字符和tj进行比较 把这个字符记为pk 显然有k i 并且对于不同的i k值也不同 10 KMP算法 特征子串与next数组 X k 1 求p0 pi 1中最大相同的前缀和后缀的长度k 2 next i k 作为特殊情况
3、 当i 0时 令next i 1 显然 对于任意i 0 i m 有next i i next i 的值越小 意味着在Sj不回溯的情况下 模式串P向右移动的越多 11 基本思想 2 第i个位置的特征值k仅依赖于模式p本身前i个字符的组成 而与目标t无关 一般可用next i 表示与i对应的k值 其意义在于 若next i 0 表示一旦匹配过程中pi与tj比较不等 可用p中以next i 为下标的字符与tj进行比较 若next i 1 则表示p中任何字符都不必在与tj进行比较 下次比较从tj 1与p0开始 对于任意模式p 只要我们能够确定next i i 0 1 m 1 的值 就可以加速匹配过程
4、避免回溯问题 当tj pi时 直接右移i next i 个字符 并从tj 或tj 1 继续下去 12 KMP算法 13 模式串的特征数与特征向量 模式串P开头的任意个字符 把它称为前缀子串 p0p1p2 pm 1在P的第i位置的左边 取出k个字符 称为i位置的左子串 pi k 1 pi 2pi 1pi求出最长的 最大的k 使得前缀子串与左子串相匹配称为 在第i位的最长前缀串 第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n i 特征数组成的向量称为该模式串的特征向量 14 Next数组 特征向量 的计算 下面证明对于任意的模式串p p0p1 pm 1 确实存在一个由模式串本身唯一确定
5、的与目标串无关的数组next 并给出next数组的计算方法 在p与任意的目标串t匹配时 若发现tj pi 则意味着p0 p1 pi 1已经与t中对应的字符进行过比较 而且是相等的 否则轮不到tj与pi的比较 因此下面两个图是等价的 t0 tj itj i 1 tj 1tj p0 pi 1pi t0 tj i 1p0 pi 1tj p0 pi 1pi 15 然后把p右移若干位 tj以前的比较工作相当于用p0 pi 1的一个前缀与它的一个长度相同的后缀进行比较 显然比较的结果由p本身决定 16 通过上面分析 得到了初步的next计算方法 1 求p0 pi 1中最大相同的前缀和后缀的长度k 2 ne
6、xt i k 作为特殊情况 当i 0时 令next i 1 显然 对于任意i 0 i m 有next i i 假定已经计算得到next i 那么next i 1 Next数组 特征向量 的计算 续 17 KMP算法 next数组的递推计算 p0 pi kpi k 1 pi 1pi p0p1 pk 1pkpk 1 Pi 1 第一种情况 对于next i k 有 p0 pk 1 pi k pi 1 1 如果pk pi 则有 p0 pk 1pk pi k pi 1pi则 next i 1 k 1 next i 1 18 KMP算法 next数组的递推计算 续 第二种情况 如果pk pi 则有 p0
7、pk 1pk pi k pi 1pi 模式串本身既是目标又是模式 与模式匹配的思路一样 应当将模式串往右滑动到模式串的第next k 个字符与pi进行尝试 如果成功 则next i 1 next k 1 否则 继续上述思路 p0 pi kpi k 1 pi 1pi Pi 1 p0p1 pk 1pk p0p1 pk 1pk pk 1pk 假定next k k 19 特征数的循环定义 特征数ni 1 ni i 是递归定义的 定义如下 n 0 1 对于i 0的n i 假定已知前一位置的特征数n i 1 k 如果pi pk 则n i k 1 当pi pk且k 0时 则令k n k 1 让 循环直到条件
8、不满足 当qi qk且k 0时 则ni 0 20 KMP算法 计算next数组 初始k为前方字串的最大长度 然后循环计算 21 栈 栈的概念与抽象数据类型定义栈的存储结构与实现数制转换与递归表达式计算 22 栈的基本概念 栈是一种操作受限的线性表插入 删除操作都只能对栈顶 元素 进行其它元素对外不提供直接访问操作top 1表示空栈top MAXNUM溢出 出栈pop 进栈push top 23 栈的抽象数据类型定义 ADTStackisOperations StackcreateEmptyStack void 创建一个空栈 intisEmptyStack Stackst 判断栈st是否为空栈
9、voidpush Stackst DataTypex 栈顶 插入一个值为x的元素 voidpop Stackst 栈顶 删除一个元素 DataTypetop Stackst 求栈顶元素的值 endADTStack 24 顺序结构栈的类型定义 defineMAXNUM100 栈的最大容量 typedefintDataType 栈元素的数据类型 structSeqStack 顺序栈类型定义 DataTypeelement MAXNUM inttop 栈顶指针 typedefstructSeqStack PSeqStack PSeqStackpastack 指向顺序栈的指针变量 25 顺序结构栈的类
10、型定义 续 26 顺序结构栈的实现 27 顺序结构栈的操作实现 续 28 链接结构栈 29 链接结构栈的类型定义 defineMAXNUM100 栈的最大容量 structNode DataTypeinfo Node next pointertothepreviousnode typedefNode PNode StructLinkStack pNodetop typedefstructLinkStack PLinkStack 指向链接栈的指针 PLinkStackpastack 指向链接栈的指针变量 30 链接结构栈的ADT ADTStackisOperations StackcreateE
11、mptyStack void 创建一个空栈 intisEmptyStack Stackst 判断栈st是否为空栈 voidpush Stackst DataTypex 栈顶 插入一个值为x的元素 voidpop Stackst 栈顶 删除一个元素 DataTypetop Stackst 求栈顶元素的值 endADTStack 31 链接结构栈的类型定义 32 压入和弹出元素 压入元素 在top与栈顶之间插入 s link top top s 弹出元素 弹出栈顶元素 q top top q link free q plstack info link top C B 弹出 33 链接结构栈的ADT
12、的实现 34 链接结构栈的操作 35 栈的应用 数制转换与递归 问题 对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 算法 N Ndivd d Nmodd512 514 8 8 514mod8 2 64 8 8 64mod8 0 8 8 8 8mod8 0 1 8 8 1mod8 1 while n 0 instack push S n 8 n n 8 generate instack 36 栈的应用 数制转换与递归 续 37 递归算法与数制转换 38 栈的应用 函数调用机制 39 栈的应用 表达式求值 二元运算符的表达式定义 表达式 算子 算符 算子 算子 操作数 表达式操作数
13、 标识符 无符号整数操作数 算符 界符 优先级 40 栈的应用 表达式求值 续 表达式的三种标识方法 Exp a b c d e f前缀式 ab c def中缀式 a b c d e f后缀式 ab cde f 中缀式丢失了括弧信息 致使运算的次序不确定 41 后缀式的运算 后缀式的运算规则为 运算符在式中出现的顺序恰为表达式的运算顺序 每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式 算子 例 31 5 22 7031522 70 42 作业 P115算法题 按照教材上的栈的ADT定义方式 完成 3 创建一个空栈 4 isEmpty 函数 5pop 函数push 函数6利用写好的栈 ADT 实现一个函数revers 把字符串反转打印 例如 a345 543a要求 高位字符先依次入栈 然后依次pop出来 打印字符 43 44 关于链表结构的文件存储 地址信息能否存储 关系能否存储 顺序与逆序
