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