第六讲 KMP算法,栈

1,KMP算法、栈及其应用,2009/03/10,2,助教负责安排：,王磊：wanglei00511027-00611065彭跃辉：pengyuehui00711003-00711049邓昌明：triday.d00711051-00711076马秀娟：maxj0700711078-00711114刘亮：fanxing07010071111500724079Email:负责助教;teacherhu上机：前三组，4号机房。后两组5号机房。,3,内容：,作业补充题讲解KMP算法栈及其应用,4,循环链表排序（冒泡法）,5,6,循环链表排序,7,关于程序的白盒调试,明确算法思路分步分层隔离考察边界点,8,无回溯的模式匹配方法(KMP算法),基本思想无回溯的模式匹配算法匹配算法的时间效率分析Next数组计算,9,基本思想-1,要找到一个无回溯的模式匹配算法，关键在于当匹配过程中，一旦pi与tj比较不等，即：SubStr_Seq(p,1,i-1)=SubStr_Seq(t,j-i+1,i-1)pitj要能立即确定p右移的位数和继续（无回溯）比较的字符，也就是说应该用p中的哪个字符和tj进行比较？把这个字符记为pk，显然有ki，并且对于不同的i，k值也不同。,10,KMP算法特征子串与next数组,X,k,(1)求p0pi-1中最大相同的前缀和后缀的长度k;(2)nexti=k;作为特殊情况，当i=0时，令nexti=-1;显然，对于任意i(0im)，有nextii;nexti的值越小，意味着在Sj不回溯的情况下，模式串P向右移动的越多。,11,基本思想-2,第i个位置的特征值k仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用nexti表示与i对应的k值。其意义在于：若nexti0，表示一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符与tj进行比较。若nexti=-1，则表示p中任何字符都不必在与tj进行比较，下次比较从tj+1与p0开始。对于任意模式p，只要我们能够确定nexti(i=0,1,m-1)的值，就可以加速匹配过程，避免回溯问题。当tjpi时，直接右移i-nexti个字符，并从tj(或tj+1)继续下去。,12,KMP算法：,13,模式串的特征数与特征向量,模式串P开头的任意个字符，把它称为前缀子串。p0p1p2pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1.pi-2pi-1pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数ni特征数组成的向量称为该模式串的特征向量。,14,Next数组（特征向量）的计算,下面证明对于任意的模式串p=p0p1pm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next，并给出next数组的计算方法。在p与任意的目标串t匹配时，若发现tjpi，则意味着p0、p1、pi-1已经与t中对应的字符进行过比较，而且是相等的，否则轮不到tj与pi的比较，因此下面两个图是等价的。,t0tj-itj-i+1tj-1tj,p0pi-1pi,t0tj-i-1p0pi-1tj,p0pi-1pi,15,然后把p右移若干位，tj以前的比较工作相当于用p0pi-1的一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由p本身决定。,16,通过上面分析，得到了初步的next计算方法：(1)求p0pi-1中最大相同的前缀和后缀的长度k;(2)nexti=k;作为特殊情况，当i=0时，令nexti=-1;显然，对于任意i(0iMAXNUM溢出,出栈pop,进栈push,top,23,栈的抽象数据类型定义,ADTStackisOperations：StackcreateEmptyStack(void)/创建一个空栈。intisEmptyStack(Stackst)/判断栈st是否为空栈。voidpush(Stackst,DataTypex)/（栈顶）插入一个值为x的元素。voidpop(Stackst)/（栈顶）删除一个元素。DataTypetop(Stackst)/求栈顶元素的值。endADTStack,24,顺序结构栈的类型定义,#defineMAXNUM100/*栈的最大容量*/typedefintDataType;/*栈元素的数据类型*/structSeqStack/*顺序栈类型定义*/DataTypeelementMAXNUM;inttop;/*栈顶指针*/；typedefstructSeqStack*PSeqStack;PSeqStackpastack;/*指向顺序栈的指针变量*/,25,顺序结构栈的类型定义（续）,26,顺序结构栈的实现,27,顺序结构栈的操作实现（续）,28,链接结构栈:,29,链接结构栈的类型定义,#defineMAXNUM100/*栈的最大容量*/structNodeDataTypeinfo;Node*next;/*pointertothepreviousnode*/;typedefNode*PNode;StructLinkStackpNodetop;typedefstructLinkStack*PLinkStack;/*指向链接栈的指针*/PLinkStackpastack;/*指向链接栈的指针变量*/,30,链接结构栈的ADT?,ADTStackisOperations：StackcreateEmptyStack(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的实现,34,链接结构栈的操作,35,栈的应用数制转换与递归,问题：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。算法：N=(Ndivd)*d+Nmodd512=(514/8)*8+514mod82(64/8)*8+64mod80(8/8)*8+8mod80(1/8)*8+1mod81,while(n!=0)/instackpush(S,n%8);n=n/8;,generate,instack,36,栈的应用数制转换与递归（续）,37,递归算法与数制转换,38,栈的应用函数调用机制,39,栈的应用表达式求值,二元运算符的表达式定义:表达式:=(算子)+(算符)+(算子)算子:=操作数|表达式操作数:=标识符|无符号整数操作数、算符、界符+优先级,40,栈的应用表达式求值（续）,表达式的三种标识方法:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+中缀式丢失了括弧信息，致使运算的次序不确定。,41,后缀式的运算,后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。,例：31*(522)+7031522-*70+,42,作业：,P115算法题：按照教材上的栈的AD