第六讲 KMP算法,栈

第六讲第六讲 KMP KMP算法算法,栈栈Hu JunfengHu JunfengPeking UniversityPeking University助教负责安排：助教负责安排：王磊：00511027-00611065彭跃辉：00711003-00711049邓昌明：00711051-00711076马秀娟：00711078-00711114刘亮：0071111500724079Email:负责助教;上机：前三组，4号机房。后两组5号机房。2Hu JunfengHu JunfengPeking UniversityPeking University内容：内容：作业补充题讲解KMP算法栈及其应用3Hu JunfengHu JunfengPeking UniversityPeking University循环链表排序（冒泡法）循环链表排序（冒泡法）4Hu JunfengHu JunfengPeking UniversityPeking University5Hu JunfengHu JunfengPeking UniversityPeking University循环链表排序循环链表排序6Hu JunfengHu JunfengPeking UniversityPeking University关于程序的白盒调试关于程序的白盒调试明确算法思路分步分层隔离考察边界点7Hu JunfengHu JunfengPeking UniversityPeking University无回溯的模式匹配方法无回溯的模式匹配方法(KMP算法算法)基本思想无回溯的模式匹配算法匹配算法的时间效率分析Next数组计算8Hu JunfengHu JunfengPeking UniversityPeking University基本思想基本思想-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值也不同。9Hu JunfengHu JunfengPeking UniversityPeking UniversityKMP算法算法特征子串与特征子串与next数组数组S0S1Sj-iSj-1SjSj+1P0P1Pi-1PiPi+1next0next1next2nexti-1nextiXk (1)求p0pi-1中最大相同的前缀和后缀的长度k;(2)nexti=k;作为特殊情况，当i=0时，令nexti=-1;显然，对于任意i(0im)，有nexti i;nexti的值越小，意味着在Sj不回溯的情况下，模式串P向右移动的越多。10Hu JunfengHu JunfengPeking UniversityPeking University基本思想基本思想-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)继续下去。11Hu JunfengHu JunfengPeking UniversityPeking UniversityKMP算法：算法：12Hu JunfengHu JunfengPeking UniversityPeking University模式串的特征数与特征向量模式串的特征数与特征向量模式串P开头的任意个字符，把它称为前缀子串。p0p1p2pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1.pi-2 pi-1 pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征特征数数ni特征数组成的向量称为该模式串的特征向量特征向量。13Hu JunfengHu JunfengPeking UniversityPeking UniversityNext数组（特征向量）的计算数组（特征向量）的计算下面证明对于任意的模式串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 p0 pi-1 tj p0 pi-1 pi14Hu JunfengHu JunfengPeking UniversityPeking University然后把然后把p右移若干位，右移若干位，tj以前的比较工作相当于用以前的比较工作相当于用p0pi-1的的一个前缀与它的一个长度相同的后缀进行比较，显然比较一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由的结果由p本身决定。本身决定。t0 tj-i-1 p0pi-k pi-1 tjp0 pk-1 pk?前缀前缀后缀后缀15Hu JunfengHu JunfengPeking UniversityPeking University 通过上面分析，得到了初步的通过上面分析，得到了初步的next计算方法：计算方法：(1)求求p0pi-1中最大相同的前缀和后缀的长度中最大相同的前缀和后缀的长度k;(2)nexti=k;作为特殊情况，作为特殊情况，当当i=0时，令时，令nexti=-1;显然，显然，对于任意对于任意i(0im)，有，有nexti 0的ni，假定已知前一位置的特征数ni-1k；如果pi pk，则ni k1；当pi pk 且k0时，则令k n k-1;让循环直到条件不满足；当qi qk 且k 0时，则ni 0;19Hu JunfengHu JunfengPeking UniversityPeking UniversityKMP算法算法 计算next数组初始k为前方字串的最大长度；然后循环计算。20Hu JunfengHu JunfengPeking UniversityPeking University栈：栈：栈的概念与抽象数据类型定义栈的存储结构与实现数制转换与递归表达式计算21Hu JunfengHu JunfengPeking UniversityPeking University栈的基本概念栈的基本概念栈是一种操作受限的线性表插入、删除操作都只能对栈顶（元素）进行其它元素对外不提供直接访问操作top=-1表示空栈topMAXNUM溢出出栈pop进栈push!OLLEHtop22Hu JunfengHu JunfengPeking UniversityPeking University栈的抽象数据类型定义栈的抽象数据类型定义ADTStackisOperations：StackcreateEmptyStack(void)/创建一个空栈。intisEmptyStack(Stackst)/判断栈st是否为空栈。voidpush(Stackst,DataTypex)/（栈顶）插入一个值为x的元素。voidpop(Stackst)/（栈顶）删除一个元素。DataTypetop(Stackst)/求栈顶元素的值。endADTStack23Hu JunfengHu JunfengPeking UniversityPeking University顺序结构栈的类型定义顺序结构栈的类型定义#defineMAXNUM100/*栈的最大容量*/typedefintDataType;/*栈元素的数据类型*/structSeqStack/*顺序栈类型定义*/DataTypeelementMAXNUM;inttop;/*栈顶指针*/；typedefstructSeqStack*PSeqStack;PSeqStackpastack;/*指向顺序栈的指针变量*/24Hu JunfengHu JunfengPeking UniversityPeking University顺序结构栈的类型定义（续）顺序结构栈的类型定义（续）25Hu JunfengHu JunfengPeking UniversityPeking University顺序结构栈的实现顺序结构栈的实现26Hu JunfengHu JunfengPeking UniversityPeking University顺序结构栈的操作实现（续）顺序结构栈的操作实现（续）27Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈链接结构栈:ki+2ki+1kik0 plstacktopinfolink28Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈的类型定义链接结构栈的类型定义#defineMAXNUM100/*栈的最大容量*/structNodeDataTypeinfo;Node*next;/*pointertothepreviousnode*/;typedefNode*PNode;StructLinkStackpNodetop;typedefstructLinkStack*PLinkStack;/*指向链接栈的指针*/PLinkStackpastack;/*指向链接栈的指针变量*/29Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈的链接结构栈的ADT?ADTStackisOperations：StackcreateEmptyStack(void)/创建一个空栈。intisEmptyStack(Stackst)/判断栈st是否为空栈。voidpush(Stackst,DataTypex)/（栈顶）插入一个值为x的元素。voidpop(Stackst)/（栈顶）删除一个元素。DataTypetop(Stackst)/求栈顶元素的值。endADTStack30Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈的链接结构栈的类型定义类型定义31Hu JunfengHu JunfengPeking UniversityPeking University压入和弹出元素压入和弹出元素压入元素：在top与栈顶之间插入（s-link=top,top=s)弹出元素：弹出栈顶元素(q=top;top=q-link;free(q);)plstackinfolinktopCB弹出弹出32Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈的链接结构栈的ADT的实现的实现33Hu JunfengHu JunfengPeking UniversityPeking University链接结构栈的操作链接结构栈的操作34Hu JunfengHu JunfengPeking UniversityPeking University栈的应用栈的应用数制转换与递归数制转换与递归问题：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。算法：N=(Ndivd)*d+Nmodd512=(514/8)*8+514mod82(64/8)*8+64mod80(8/8)*8+8mod80(1/8)*8+1mod81while(n!=0)/in stackpush(S,n%8);n=n/8;generatein stack35Hu JunfengHu JunfengPeking UniversityPeking University栈的应用栈的应用数制转换与递归（续）数制转换与递归（续）36Hu JunfengHu JunfengPeking UniversityPeking University递归算法与数制转换递归算法与数制转换37Hu JunfengHu JunfengPeking UniversityPeking University栈的应用栈的应用函数调用机制函数调用机制38Hu JunfengHu JunfengPeking UniversityPeking University栈的应用栈的应用表达式求值表达式求值二元运算符的表达式定义:表达式 :=(算子)+(算符)+(算子)算子 :=操作数|表达式 操作数 :=标识符|无符号整数 操作数、算符、界符+优先级 39Hu JunfengHu JunfengPeking UniversityPeking University栈的应用栈的应用表达式求值（续）表达式求值（续）表达式的三种标识方法:Exp =ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+中缀式丢失了括弧信息，致使运算的次序不确定。40Hu JunfengHu JunfengPeking UniversityPeking University后缀式的运算后缀式的运算后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。例：31*(5 22)+7031 5 22 -*70 +-22531*22-173141Hu JunfengHu JunfengPeking UniversityPeking University作业：作业：P115算法题：按照教材上的栈的ADT定义方式，完成：3（创建一个空栈）4（isEmpty()函数)5pop()函数push()函数6利用写好的栈（ADT）实现一个函数revers()，把字符串反转打印。例如：“a345”543a要求：高位字符先依次入栈，然后依次pop出来，打印字符。42Hu JunfengHu JunfengPeking UniversityPeking University43Hu JunfengHu JunfengPeking UniversityPeking University关于链表结构的文件存储关于链表结构的文件存储地址信息能否存储？关系能否存储？顺序与逆序44结束语结束语谢谢大家聆听！谢谢大家聆听！45