第六讲 KMP算法,栈

1、KMP算法、栈及其应用 2009/03/102助教负责安排：助教负责安排：王磊 ： 00511027 - 00611065彭跃辉： 00711003 - 00711049 邓昌明： 00711051 - 00711076马秀娟： 00711078 - 00711114 刘 亮： 00711115 00724079 Email: 负责助教 ; 上机：前三组，4号机房。后两组5号机房。3内容：内容： 作业补充题讲解 KMP算法 栈及其应用4循环链表排序（冒泡法）循环链表排序（冒泡法）56循环链表排序循环链表排序7关于程序的白盒调试关于程序的白盒调试 明确算法思路 分步 分层 隔离 考察边界点8无回

2、溯的模式匹配方法无回溯的模式匹配方法(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，显然有 ki，并且对于不同的i，k值也不同。 10KMP算法算法 特征子串与特征子串与next数组数组S0 S1 Sj-iSj-1Sj Sj

3、+1 P0 P1 Pi-1Pi Pi+1 next0 next1 next2 nexti-1nexti Xk (1) 求p0pi-1中最大相同的前缀和后缀的长度k; (2) nexti = k; 作为特殊情况，当i=0时，令nexti = -1; 显然，对于任意i(0im)，有nexti i; nexti的值越小，意味着在Sj不回溯的情况下，模式串P向右移动的越多。11基本思想基本思想-2 第i个位置的特征值k 仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用nexti表示与i对应的k值。其意义在于： 若nexti0，表示一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标

4、的字符与tj进行比较。 若nexti = -1，则表示p中任何字符都不必在与tj进行比较，下次比较从tj+1与p0开始。 对于任意模式p，只要我们能够确定 nexti (i=0, 1, , m-1)的值，就可以加速匹配过程，避免回溯问题。当tj pi时，直接右移i-nexti个字符，并从tj(或tj+1)继续下去。12KMP算法：算法：13模式串的特征数与特征向量模式串的特征数与特征向量 模式串P开头的任意个字符，把它称为前缀子串。p0p1p2pm-1 在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1. pi-2 pi-1 pi 求出最长的（最大的k）使得前缀子串与左子串相

5、匹配称为，在第i位的最长前缀串。 第i位的最长前缀串的长度k就是模板串P在位置i上的特征特征数数ni 特征数组成的向量称为该模式串的特征向量特征向量。14Next数组（特征向量）的计算数组（特征向量）的计算 下面证明对于任意的模式串p=p0p1pm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next，并给出next数组的计算方法。 在p与任意的目标串t匹配时，若发现tjpi，则意味着p0、p1、pi-1已经与t中对应的字符进行过比较，而且是相等的，否则轮不到tj与pi的比较，因此下面两个图是等价的。t0tj-i tj-i+1 tj-1 tj p0 pi-1 pit0tj-i-1

6、p0 pi-1 tj p0 pi-1 pi15然后把然后把p右移若干位，右移若干位，tj以前的比较工作相当于用以前的比较工作相当于用p0pi-1的的一个前缀与它的一个长度相同的后缀进行比较，显然比较一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由的结果由p本身决定。本身决定。t0 tj-i-1 p0pi-k pi-1 tjp0 pk-1 pk?前缀前缀后缀后缀16 通过上面分析，得到了初步的通过上面分析，得到了初步的next计算方法：计算方法： (1) 求求p0pi-1中最大相同的前缀和后缀的长度中最大相同的前缀和后缀的长度k; (2) nexti = k; 作为特殊情况，作为特殊情

7、况，当当i=0时，令时，令nexti = -1; 显然，显然，对于任意对于任意i(0im)，有，有nexti 0的ni ，假定已知前一位置的特征数 ni-1 k ； 如果pi pk ，则ni k1 ； 当pi pk 且k0时，则令k n k -1 ; 让循环直到条件不满足； 当qi qk 且k 0时，则ni 0;20KMP算法算法 计算next数组初始k为前方字串的最大长度；然后循环计算。21栈：栈： 栈的概念与抽象数据类型定义 栈的存储结构与实现 数制转换与递归 表达式计算22栈的基本概念栈的基本概念栈是一种操作受限的线性表插入、删除操作都只能对栈顶（元素）进行其它元素对外不提供直接访问操作

8、 top = -1 表示空栈 top MAXNUM 溢出出栈 pop进栈 push!OLLEHtop23栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack isOperations： Stack createEmptyStack ( void ) /创建一个空栈。 int isEmptyStack ( Stack st ) /判断栈st是否为空栈。 void push ( Stack st, DataType x ) /（栈顶）插入一个值为x的元素。 void pop ( Stack st ) /（栈顶）删除一个元素。 DataType top ( Stack st ) / 求栈顶元素

9、的值。end ADT Stack 24顺序结构栈的类型定义顺序结构栈的类型定义 #define MAXNUM 100 /* 栈的最大容量*/ typedef int DataType; /* 栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ DataType elementMAXNUM; int top; /*栈顶指针*/ ；typedef struct SeqStack *PSeqStack;PSeqStack pastack; /*指向顺序栈的指针变量*/25顺序结构栈的类型定义（续）顺序结构栈的类型定义（续）26顺序结构栈的实现顺序结构栈的实现27顺序结

10、构栈的操作实现（续）顺序结构栈的操作实现（续）28链接结构栈链接结构栈: ki+2 ki+1 ki k0 plstacktopinfolink29链接结构栈的类型定义链接结构栈的类型定义 #define MAXNUM 100 /* 栈的最大容量*/ struct Node DataType info; Node * next; /* pointer to the previous node* /; typedef Node* PNode; Struct LinkStackpNode top; ;typedef struct LinkStack *PLinkStack; /* 指向链接栈的指针

11、*/PLinkStack pastack; /*指向链接栈的指针变量*/30链接结构栈的链接结构栈的ADT?ADT Stack isOperations： Stack createEmptyStack ( void ) /创建一个空栈。 int isEmptyStack ( Stack st ) /判断栈st是否为空栈。 void push ( Stack st, DataType x ) /（栈顶）插入一个值为x的元素。 void pop ( Stack st ) /（栈顶）删除一个元素。 DataType top ( Stack st ) / 求栈顶元素的值。end ADT Stack 3

12、1链接结构栈的链接结构栈的类型定义类型定义32 压入和弹出元素压入和弹出元素压入元素：在top与栈顶之间插入（s-link = top, top = s)弹出元素： 弹出栈顶元素 ( q = top; top= q-link; free(q); )plstackinfolinktopCB弹出弹出33链接结构栈的链接结构栈的ADT的实现的实现34链接结构栈的操作链接结构栈的操作35栈的应用栈的应用 数制转换与递归数制转换与递归问题：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 算法：N = (N div d) * d + N mod d 512 = (514 / 8) * 8

13、+ 514 mod 8 2 (64 / 8) * 8 + 64 mod 8 0 (8 / 8) * 8 + 8 mod 8 0 (1 / 8) * 8 + 1 mod 8 1 while(n != 0) /in stackpush(S,n%8);n=n/8;generatein stack36栈的应用栈的应用 数制转换与递归（续）数制转换与递归（续）37递归算法与数制转换递归算法与数制转换38栈的应用栈的应用 函数调用机制函数调用机制39栈的应用栈的应用 表达式求值表达式求值 二元运算符的表达式定义: 表达式 := (算子) + (算符) + (算子) 算子 := 操作数 | 表达式 操作数

14、:= 标识符 | 无符号整数 操作数、算符、界符 + 优先级 40栈的应用栈的应用 表达式求值（续）表达式求值（续） 表达式的三种标识方法: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +中缀式丢失了括弧信息，致使运算的次序不确定。41后缀式的运算后缀式的运算 后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。例：31 * ( 5 22 ) + 7031 5 22 - * 70 + -22531*2