第六講 KMP算法,棧

1、KMP算法、棧及其應(yīng)用 2009/03/102助教負責(zé)安排：助教負責(zé)安排：王磊 ： 00511027 - 00611065彭躍輝： 00711003 - 00711049 鄧昌明： 00711051 - 00711076馬秀娟： 00711078 - 00711114 劉 亮： 00711115 00724079 Email: 負責(zé)助教 ; 上機：前三組，4號機房。后兩組5號機房。3內(nèi)容：內(nèi)容： 作業(yè)補充題講解 KMP算法 棧及其應(yīng)用4循環(huán)鏈表排序（冒泡法）循環(huán)鏈表排序（冒泡法）56循環(huán)鏈表排序循環(huán)鏈表排序7關(guān)于程序的白盒調(diào)試關(guān)于程序的白盒調(diào)試 明確算法思路 分步 分層 隔離 考察邊界點8無回

2、溯的模式匹配方法無回溯的模式匹配方法(KMP算法算法) 基本思想 無回溯的模式匹配算法 匹配算法的時間效率分析 Next數(shù)組計算9基本思想基本思想-1要找到一個無回溯的模式匹配算法，關(guān)鍵在于當(dāng)匹配過程中，一旦pi 與tj比較不等，即：SubStr_Seq(p, 1, i-1) = SubStr_Seq(t, j-i+1, i-1) pi tj要能立即確定p右移的位數(shù)和繼續(xù)（無回溯）比較的字符，也就是說應(yīng)該用p中的哪個字符和tj進行比較？把這個字符記為pk，顯然有 ki，并且對于不同的i，k值也不同。 10KMP算法算法 特征子串與特征子串與next數(shù)組數(shù)組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; 作為特殊情況，當(dāng)i=0時，令nexti = -1; 顯然，對于任意i(0im)，有nexti i; nexti的值越小，意味著在Sj不回溯的情況下，模式串P向右移動的越多。11基本思想基本思想-2 第i個位置的特征值k 僅依賴于模式p本身前i個字符的組成，而與目標t無關(guān)，一般可用nexti表示與i對應(yīng)的k值。其意義在于： 若nexti0，表示一旦匹配過程中pi與tj比較不等，可用p中以nexti為下標

4、的字符與tj進行比較。 若nexti = -1，則表示p中任何字符都不必在與tj進行比較，下次比較從tj+1與p0開始。 對于任意模式p，只要我們能夠確定 nexti (i=0, 1, , m-1)的值，就可以加速匹配過程，避免回溯問題。當(dāng)tj pi時，直接右移i-nexti個字符，并從tj(或tj+1)繼續(xù)下去。12KMP算法：算法：13模式串的特征數(shù)與特征向量模式串的特征數(shù)與特征向量 模式串P開頭的任意個字符，把它稱為前綴子串。p0p1p2pm-1 在P的第i位置的左邊，取出k個字符，稱為i位置的左子串。pi-k+1. pi-2 pi-1 pi 求出最長的（最大的k）使得前綴子串與左子串相

5、匹配稱為，在第i位的最長前綴串。 第i位的最長前綴串的長度k就是模板串P在位置i上的特征特征數(shù)數(shù)ni 特征數(shù)組成的向量稱為該模式串的特征向量特征向量。14Next數(shù)組（特征向量）的計算數(shù)組（特征向量）的計算 下面證明對于任意的模式串p=p0p1pm-1,確實存在一個由模式串本身唯一確定的與目標串無關(guān)的數(shù)組next，并給出next數(shù)組的計算方法。 在p與任意的目標串t匹配時，若發(fā)現(xiàn)tjpi，則意味著p0、p1、pi-1已經(jīng)與t中對應(yīng)的字符進行過比較，而且是相等的，否則輪不到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以前的比較工作相當(dāng)于用以前的比較工作相當(dāng)于用p0pi-1的的一個前綴與它的一個長度相同的后綴進行比較，顯然比較一個前綴與它的一個長度相同的后綴進行比較，顯然比較的結(jié)果由的結(jié)果由p本身決定。本身決定。t0 tj-i-1 p0pi-k pi-1 tjp0 pk-1 pk?前綴前綴后綴后綴16 通過上面分析，得到了初步的通過上面分析，得到了初步的next計算方法：計算方法： (1) 求求p0pi-1中最大相同的前綴和后綴的長度中最大相同的前綴和后綴的長度k; (2) nexti = k; 作為特殊情況，作為特殊情

7、況，當(dāng)當(dāng)i=0時，令時，令nexti = -1; 顯然，顯然，對于任意對于任意i(0im)，有，有nexti 0的ni ，假定已知前一位置的特征數(shù) ni-1 k ； 如果pi pk ，則ni k1 ； 當(dāng)pi pk 且k0時，則令k n k -1 ; 讓循環(huán)直到條件不滿足； 當(dāng)qi qk 且k 0時，則ni 0;20KMP算法算法 計算next數(shù)組初始k為前方字串的最大長度；然后循環(huán)計算。21棧：棧： 棧的概念與抽象數(shù)據(jù)類型定義 棧的存儲結(jié)構(gòu)與實現(xiàn) 數(shù)制轉(zhuǎn)換與遞歸 表達式計算22棧的基本概念棧的基本概念棧是一種操作受限的線性表插入、刪除操作都只能對棧頂（元素）進行其它元素對外不提供直接訪問操作

8、 top = -1 表示空棧 top MAXNUM 溢出出棧 pop進棧 push!OLLEHtop23棧的抽象數(shù)據(jù)類型定義棧的抽象數(shù)據(jù)類型定義ADT Stack isOperations： Stack createEmptyStack ( void ) /創(chuàng)建一個空棧。 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順序結(jié)構(gòu)棧的類型定義順序結(jié)構(gòu)棧的類型定義 #define MAXNUM 100 /* 棧的最大容量*/ typedef int DataType; /* 棧元素的數(shù)據(jù)類型* / struct SeqStack /* 順序棧類型定義 */ DataType elementMAXNUM; int top; /*棧頂指針*/ ；typedef struct SeqStack *PSeqStack;PSeqStack pastack; /*指向順序棧的指針變量*/25順序結(jié)構(gòu)棧的類型定義（續(xù)）順序結(jié)構(gòu)棧的類型定義（續(xù)）26順序結(jié)構(gòu)棧的實現(xiàn)順序結(jié)構(gòu)棧的實現(xiàn)27順序結(jié)

10、構(gòu)棧的操作實現(xiàn)（續(xù)）順序結(jié)構(gòu)棧的操作實現(xiàn)（續(xù)）28鏈接結(jié)構(gòu)棧鏈接結(jié)構(gòu)棧: ki+2 ki+1 ki k0 plstacktopinfolink29鏈接結(jié)構(gòu)棧的類型定義鏈接結(jié)構(gòu)棧的類型定義 #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鏈接結(jié)構(gòu)棧的鏈接結(jié)構(gòu)棧的ADT?ADT Stack isOperations： Stack createEmptyStack ( void ) /創(chuàng)建一個空棧。 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鏈接結(jié)構(gòu)棧的鏈接結(jié)構(gòu)棧的類型定義類型定義32 壓入和彈出元素壓入和彈出元素壓入元素：在top與棧頂之間插入（s-link = top, top = s)彈出元素： 彈出棧頂元素 ( q = top; top= q-link; free(q); )plstackinfolinktopCB彈出彈出33鏈接結(jié)構(gòu)棧的鏈接結(jié)構(gòu)棧的ADT的實現(xiàn)的實現(xiàn)34鏈接結(jié)構(gòu)棧的操作鏈接結(jié)構(gòu)棧的操作35棧的應(yīng)用棧的應(yīng)用 數(shù)制轉(zhuǎn)換與遞歸數(shù)制轉(zhuǎn)換與遞歸問題：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。 算法：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棧的應(yīng)用棧的應(yīng)用 數(shù)制轉(zhuǎn)換與遞歸（續(xù)）數(shù)制轉(zhuǎn)換與遞歸（續(xù)）37遞歸算法與數(shù)制轉(zhuǎn)換遞歸算法與數(shù)制轉(zhuǎn)換38棧的應(yīng)用棧的應(yīng)用 函數(shù)調(diào)用機制函數(shù)調(diào)用機制39棧的應(yīng)用棧的應(yīng)用 表達式求值表達式求值 二元運算符的表達式定義: 表達式 := (算子) + (算符) + (算子) 算子 := 操作數(shù) | 表達式 操作數(shù)

14、:= 標識符 | 無符號整數(shù) 操作數(shù)、算符、界符 + 優(yōu)先級 40棧的應(yīng)用棧的應(yīng)用 表達式求值（續(xù)）表達式求值（續(xù)） 表達式的三種標識方法: 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后綴式的運算后綴式的運算 后綴式的運算規(guī)則為: 運算符在式中出現(xiàn)的順序恰為 表達式的運算順序; 每個運算符和在它之前出現(xiàn)，且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式（算子）。例：31 * ( 5 22 ) + 7031 5 22 - * 70 + -22531*2