數(shù)據(jù)結(jié)構(gòu)與算法 課件 第3、4章 棧和隊列、串

3.1棧

3.2隊列3.1棧3.1.1棧的定義及基本運算棧(Stack)是限定僅在表的一端進行插入或刪除操作的線性表。插入、刪除的一端稱為棧頂(Top)，另一端稱為棧底(Bottom)。不含任何元素的空表稱為空棧。對于非空棧S?=?(a1,a2,…,an)，a1是棧底元素，an是棧頂元素。如圖3.1所示，進棧的順序是a1,a2,…,an，出棧的順序正好相反。因此，棧是一種后進先出的(LastInFirstOut)的線性表。棧的常用基本運算有以下六種：(1)?InitStack(&S)棧初始化：操作結(jié)果是構(gòu)造一個空棧S。(2)?SetNull(S)置空棧：棧S已存在，將棧S清為空棧。(3)?Empty(S)判斷?？眨喝魲為空則返回“真”值；否則返回“假”值。(4)?Push(S,x)進棧：若棧S不滿，將數(shù)據(jù)元素x插入棧頂，并返回入棧是否成功的狀態(tài)信息。入棧操作會改變棧的內(nèi)容。(5)?Pop(S,&x)出棧：若棧S非空，刪除棧頂數(shù)據(jù)元素，通過參數(shù)x帶回棧頂元素，并返回出棧是否成功的狀態(tài)信息。出棧操作會使棧的內(nèi)容發(fā)生變化。(6)?GetTop(S,&x)取棧頂元素：若棧S非空，通過參數(shù)x帶回棧頂元素，并返回取棧頂元素是否成功的狀態(tài)信息。該操作完成后，棧的內(nèi)容不變。3.1.2棧的順序存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．棧的順序存儲結(jié)構(gòu)——順序棧棧的順序存儲結(jié)構(gòu)簡稱順序棧(SequentialStack)。順序棧采用一維數(shù)組來存儲，并且用一個整型量Top指示當前棧頂?shù)奈恢?，我們不妨把Top稱為棧頂指針。順序棧的類型定義如下：其中，maxsize是數(shù)組空間的長度；datatype是棧中元素的類型。設S是指向SeqStack結(jié)構(gòu)體類型數(shù)據(jù)的指針。順序棧本質(zhì)上是順序表的簡化，我們需要確定用數(shù)組的哪一端作為棧底。通常把數(shù)組中下標為0的一端作為棧底，那么S->data[0]是棧底元素，S->data[S->Top]是棧頂元素。當S->Top?=?-1時為空棧，滿棧時S->Top=maxsize-1。對于順序棧，入棧時要先判斷棧是否已滿，棧滿簡稱為“上溢”；出棧時需判斷棧是否為空，?？蘸喎Q為“下溢”。入棧操作S->Top加1，出棧操作S->Top減1。圖3.2說明了棧中元素和棧頂指針之間的關(guān)系。2．順序?；具\算的實現(xiàn)1)棧初始化算法3.1建立空順序棧。2)置空棧算法3.2順序棧置空。3)判斷棧空算法3.3判順序棧S是否為空棧。4)入棧算法3.4順序棧入棧。5)出棧算法3.5順序棧棧頂元素出棧。6)取棧頂元素算法3.6取順序棧的棧頂元素。3．多個順序棧共享連續(xù)空間在同時使用兩個或多個順序棧時，為了避免某個棧發(fā)生上溢，而其余棧還有很多未用空間的情況出現(xiàn)，可讓這些棧共享同一個一維數(shù)組空間，相互之間調(diào)劑余缺，既節(jié)約了存儲空間，又降低了發(fā)生上溢的概率。下面以兩個順序棧共享同一個數(shù)組空間的情況進行討論。兩個棧共享一個數(shù)組空間的結(jié)構(gòu)類型定義如下：將兩個棧的棧底分別固定在一維數(shù)組空間的兩端，棧頂向中間延伸，空閑區(qū)域在數(shù)組的中部，如圖3.3所示。只有當兩個棧占滿整個數(shù)組空間時(S->Top1+1等于S->Top2)，才會發(fā)生上溢。設i表示整型數(shù)值，它只取1或者2，分別表示對1號?；蛘?號棧進行操作。這里我們只給出兩個棧共享空間的入棧和出棧操作。進棧操作的算法如下所示：當存儲棧的數(shù)組中沒有空閑單元時為棧滿。此時1號棧的棧頂與2號棧的棧頂處于相鄰的位置，即Top1+1?=?Top2(或Top1?=?Top2-1)。另外，對于2號棧的入棧，Top2應當是減1而不是加1。出棧操作的算法如下所示：當Top1=-1時，1號棧為空；當Top2=maxsize時，2號棧為空。另外，對于2號棧的出棧，Top2應當是加1而不是減1。3.1.3棧的鏈式存儲結(jié)構(gòu)和基本運算的實現(xiàn)1.棧的鏈接存儲結(jié)構(gòu)——鏈棧棧的鏈接存儲結(jié)構(gòu)簡稱鏈棧(LinkedStack)，通常用單鏈表表示。鏈棧的結(jié)點結(jié)構(gòu)類型定義如下：由于鏈棧是動態(tài)分配元素存儲空間的，因此在對棧進行操作時不存在上溢的問題。我們將單鏈表的表頭定義為棧頂。由于只能在棧頂進行入棧和出棧操作，因此只能在表頭插入和刪除，可以說鏈棧是操作受限的單鏈表。既然只能在表頭進行操作，所以也就沒有必要設置頭結(jié)點了。如圖3.5所示，S是LinkStack類型的指針，指向鏈棧，可以看作是棧的接口。Top是棧頂指針，指向棧頂結(jié)點。當Top等于NULL時為空棧。2．鏈棧基本運算的實現(xiàn)鏈棧基本運算的實現(xiàn)實質(zhì)上是單鏈表基本運算的簡化。由于對棧的操作都是在棧頂(單鏈表的表頭)進行的，因此算法的時間復雜度均為O(1)。1)棧初始化算法3.7建立空鏈棧。2)置空棧算法3.8鏈棧置空。3)入棧算法3.9鏈棧入棧。4)出棧算法3.10鏈棧棧頂元素出棧。5)取棧頂元素算法3.11取鏈棧的棧頂元素。3.1.4順序棧和鏈棧的比較從時間特性方面來看，實現(xiàn)順序棧和鏈棧的所有基本運算的算法，其時間復雜度都是O(1)，因此唯一可以比較的是空間特性。棧初始化時，順序棧必須確定一個固定的長度作為棧的容量，所以有存儲元素個數(shù)的限制和空間浪費的問題。鏈棧沒有棧滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)不能入棧的情況，但是每個元素都需要一個指針域，從而又產(chǎn)生了結(jié)構(gòu)性的開銷。所以當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的；反之，應該采用順序棧。3.2隊列3.2.1隊列的定義及基本運算隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，該端稱為隊尾(Rear)；在表的另一端進行刪除，該端稱為隊頭(Front)。當隊列中沒有元素時稱為空隊列。隊列亦稱作先進先出(FirstInFirstOut)的線性表，簡稱為FIFO表。設隊列中的元素為a1,a2,…,an，a1是隊頭元素，an是隊尾元素。隊列中的元素都是按照a1,a2,…,an的順序依次入隊和出隊的。圖3.6是隊列的示意圖。隊列的主要基本運算如下：(1)?InitQueue(&Q)隊列初始化：構(gòu)造一個空隊列Q。(2)?SetNull(Q)置空隊：將隊列Q清空。(3)?Length(Q)求隊列長度：返回隊列中元素的個數(shù)。(4)?Empty(Q)判空隊：若隊列Q為空隊列，返回“真”值；否則返回“假”值。(5)?EnQueue(Q,x)入隊：若隊列Q非滿，將元素x插入Q的隊尾。(6)?DeQueue(Q)出隊：若隊列Q非空，刪除隊頭元素，返回Q的隊頭元素。(7)?GetFront(Q)取隊頭元素：若隊列Q非空，返回Q的隊頭元素；Q中元素保持不變。3.2.2隊列的順序存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．隊列的順序存儲結(jié)構(gòu)——順序隊列隊列的順序存儲結(jié)構(gòu)稱為順序隊列，采用數(shù)組存儲隊列中的元素。本書約定，在非空隊列中隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素的位置。如果是空隊，隊頭、隊尾指針相等。隊尾指針減去隊頭指針就是隊列的長度。當然也可以約定隊頭指針front指向隊頭元素的位置，隊尾指針rear指向隊尾元素的后一個位置。順序隊列的結(jié)構(gòu)類型定義如下：順序隊列中出隊、入隊操作的情況如圖3.7所示。順序隊列中可能出現(xiàn)“上溢”和“下溢”現(xiàn)象，并且還存在“假上溢”現(xiàn)象。也就是說，盡管隊列的數(shù)組空間雖然未被占滿，但尾指針已達到數(shù)組的上界而不能進行入隊操作。例如在圖3.7(c)或(d)的情況下，再進行入隊操作，則會出現(xiàn)“假上溢”。采用循環(huán)隊列(CircularQueue)的方法可以較好地解決“假上溢”問題，即將數(shù)組看作一個首尾相接的圓環(huán)，如圖3.8所示。在循環(huán)隊中通過取模運算修改隊尾指針和隊頭指針，具體描述為：在循環(huán)隊列中，入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針。由圖3.9可以看出，在隊空和隊滿時都有sq->front等于sq->rear，無法區(qū)分空隊和滿隊。通常采用少用一個元素空間的方法來解決這個問題，如圖3.10所示。判斷空隊和滿隊的條件分別是：2．循環(huán)隊列基本運算的實現(xiàn)我們用前面所述方法來實現(xiàn)循環(huán)隊列上的基本運算。1)隊列初始化算法3.12生成空循環(huán)隊列。對于循環(huán)隊列來說，只要隊頭和隊尾指針相等即為空隊，所以這里置為0～maxsize-1之間的任何一個值都可以，但一般置為0。2)置空隊算法3.13循環(huán)隊列置空。3)求隊列長度算法3.14求循環(huán)隊列長度。4)入隊算法3.15循環(huán)隊列入隊。5)出隊算法3.16循環(huán)隊列出隊。6)取隊頭元素算法3.17取循環(huán)隊列的隊頭元素。3.2.3隊列的鏈式存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．隊列的鏈式存儲結(jié)構(gòu)——鏈隊列隊列的鏈式存儲結(jié)構(gòu)簡稱鏈隊列，它是僅限在表頭刪除和表尾插入的單鏈表。為了便于在表尾做插入操作，需要增加一個尾指針，指向單鏈表中的最后一個結(jié)點。我們將鏈隊列的頭指針和尾指針封裝在一起作為一個結(jié)構(gòu)體。下面是其類型定義：為了運算方便，鏈隊列中通常也帶有頭結(jié)點。圖3.11給出了鏈隊列的示意圖，圖中q為LinkQueue類型的指針。鏈隊列不會出現(xiàn)隊滿的情況。2．鏈隊列基本運算的實現(xiàn)1)隊列初始化算法3.18生成空鏈隊列。2)置空隊算法3.19鏈隊列置空。3)判隊空算法3.20鏈隊列判空隊。4)入隊算法3.21鏈隊列入隊。鏈隊列不會出現(xiàn)“上溢”的情況，不需要判斷隊滿。5)出隊算法3.22鏈隊列出隊。6)取隊頭元素算法3.23取鏈隊列的隊頭元素。4.1串的概念及基本運算

4.2串的順序存儲結(jié)構(gòu)及基本運算的實現(xiàn)

4.3串的鏈式存儲結(jié)構(gòu)

4.4串的模式匹配算法4.1串的概念及基本運算4.1.1串的定義串(String)是由多個或零個字符組成的有限序列，記作S?=?"c1c2c3…cn"(n≥0)。其中，S是串名，由雙引號括起來的字符序列稱為串值，但雙引號本身不屬于串；ci(1≤i≤n)是串中的字符，i是字符在串中的位置序號；n是串的長度，表示串中字符的個數(shù)。不包含任何字符的串稱為空串，例如""是長度為0的空串。串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應地稱為主串。子串在主串中的序號定義為子串在主串中首次出現(xiàn)的位置序號。例如，設S1和S2分別為，S1?=?"Thisisastring"?和S2?=?"is"，則S2是S1的子串，S1是S2的主串。S2在S1中出現(xiàn)了兩次，首次出現(xiàn)在主串的第3個位置上，因此S2在S1中的序號是3。特別需要一提的是，空串是任意串的子串，任意串是其自身的子串。通常串可以分為串變量和串常量。正如我們所知道的，在程序中常量只能被引用但不能改變其值，而變量的值可以改變。在C語言中，串變量可以用字符型數(shù)組來表示，串常量可以用雙引號括起來的字符序列直接表示或者用符號常量來表示。4.1.2串的基本運算串的基本運算和線性表有很大的差別。線性表的插入、刪除等運算都以“單個元素”作為操作對象；而串的運算通常是對串的整體或一部分進行操作，如串的復制、串的比較、插入和刪除子串等。下面介紹串的部分基本運算。(1)?StrLength(S)求串長：計算并返回串的長度。(2)?StrCopy(S1,S2)串賦值：將S2賦給S1。S1是串變量，S2是串常量或者是串變量。(3)?StrCat(S1,S2)串連接：將S2連接在S1的后面。S1是串變量，S2是串常量或者是串變量。(4)?StrCmp(S1,S2)串比較：若S1?=?S2，則運算結(jié)果為0；若S1?>?S2，則運算結(jié)果大于0；若S1?<?S2，則運算結(jié)果小于0。兩個串的比較，實際上比較的是字符的ASCII碼值。從第一個位置上的字符開始逐個字符進行比較，當?shù)谝淮纬霈F(xiàn)字符不等的情況時，即可得到比較的結(jié)果。(5)?StrIndex(S,T)子串定位：若串T是串S的子串，則運算結(jié)果為T在S中首次出現(xiàn)的位置，否則運算結(jié)果為0。(6)?SubStr(Sub,S,i,len)求子串：串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運算結(jié)果是得到S串從第i個字符開始的長度為len的子串，并將其賦給T。如果len為0，則賦給Sub的是空串。(7)?StrInsert(S,i,T)串插入：串S和T均為非空串，且1≤i≤StrLength(S)+1。結(jié)果是將串T插入到串S的第i個字符位置上，串S的值被改變。(8)?Strdelete(S,i,len)串刪除：串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運算結(jié)果是刪除S串中從第i個字符開始的長度為len的子串，串S的值被改變。(9)?StrRep(S,T,R)串替換：串S、T、R均非空，運算結(jié)果是用串R替換串S中所有子串T，串S的值被改變。以上是串的基本運算，其中前5個運算是最基本的，其余的串運算一般可以由這些最基本的串運算組合而成。4.2串的順序存儲結(jié)構(gòu)及基本運算的實現(xiàn)4.2.1串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)又稱為順序串。與線性表的順序存儲結(jié)構(gòu)類似，順序串用一組地址連續(xù)的存儲單元存儲串值的字符序列，其中每個結(jié)點是單個字符。串的定長順序存儲表示也稱為靜態(tài)存儲分配的順序串。定長順序存儲結(jié)構(gòu)是指直接使用定長的字符數(shù)組來定義，數(shù)組的上界預先給出。串的長度一般有三種表示方法：(1)用一個整型變量來表示串的長度，如圖4.1所示。此時順序串的類型定義和順序表類似，定義如下：在這種存儲方式下，可以直接得到順序串的長度為s->length。(2)在串的末尾設置串結(jié)束符。在有些編程語言中，采用特定的終結(jié)符表示串的結(jié)束，例如C語言用轉(zhuǎn)義字符?'\0'?作為串結(jié)束符，如圖4.2所示。?這種方式不能直接得到串的長度，而是通過判斷當前字符是否為?'\0'?來確定串是否結(jié)束，從而求得串的長度。此時，順序串的定義如下：這就是為什么在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個字符的原因，因為必須留一個字節(jié)來存放?'\0'?字符作為串結(jié)束符。(3)設置順序串存儲空間：chars[maxsize+1];?，用s[0]存放串的實際長度，而串值存放在s[1]～s[maxsize]中，如圖4.3所示。這樣可以使得字符的序號與存儲位置的下標一致。在下面關(guān)于順序串的討論中，為了和C語言的字符串運算保持一致，順序串采用第2種存儲方式，即從數(shù)組下標0開始存放字符，并且在串尾存儲串結(jié)束符?'\0'。4.2.2順序串基本運算的實現(xiàn)1．順序串的基本運算1)求串長算法4.1求順序串的長度，即統(tǒng)計串中字符的個數(shù)。2)串賦值(串復制)算法4.2將串s2復制給串s1。3)串比較算法4.3比較兩個串s1和s2的大小。若s1>s2，返回值大于0；若s1=s2，返回值等于0；若s1<s2，返回值小于0。4)串連接算法4.4將s1和s2兩個串首尾連接成一個新的串s1。2．使用C語言的字符串運算庫函數(shù)使用C語言的字符串運算庫函數(shù)，需要包含頭文件string.h，庫函數(shù)名均為小寫。我們先定義使用的幾個相關(guān)變量：說明：字符串從字符數(shù)組下標為0的元素開始存放。(1)?strlen(S)求串長度：返回字符串長度。(2)?strcpy(&T,S)復制串：將源串復制給目標串。(3)?strcmp(S1,S2)比較串：比較兩個串的大小，返回整型值。(4)?strcat(&T,S)串連接：將串S連接到串T的末尾，返回指向串T的指針。(5)?strstr(S,Sub)子串定位：查找串Sub在串S中第一次出現(xiàn)的位置。若查找到，則返回該位置信息，否則返回NULL。(6)?strchr(S,C)字符定位：查找字符C在串S中第一次出現(xiàn)的位置。若查找到，則返回該位置信息，否則返回NULL。在串的順序存儲結(jié)構(gòu)中，串操作的時間復雜度基于串的長度n，即時間復雜度為O(n)。上述操作的另一個特點是，當在操作中出現(xiàn)串值序列的長度超過上界maxsize時，約定用截尾法處理，這種情況不僅在連接串時可能發(fā)生，在串的插入等其他操作也可能發(fā)生。這個弊病可以采用動態(tài)分配串的存儲空間的方式來克服。4.3串的鏈式存儲結(jié)構(gòu)和順序表類似，在順序串上進行插入、刪除操作不方便，需要移動大量的元素。采用鏈表存儲串值可以提高插入、刪除的效率。串的鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串便于進行插入和刪除運算，但存儲空間利用率太低。由于串中的每個元素是一個字符，因此用鏈表存儲串值時存在結(jié)點大小的問題。也就是說，在每個結(jié)點存放一個字符還是存放多個字符。圖4.4(a)和(b)中每個結(jié)點分別可以存放1個字符和4個字符。如果每個結(jié)點放多個字符，當串長不是結(jié)點大小的整數(shù)倍時，鏈表中的最后一個結(jié)點不一定被串值完全占滿，可以用特殊的字符(例如?'\0'或?'#'?)來填充。為了方便串的操作，當以鏈表存儲串值時，除頭指針外，還可以附設一個尾指針指向鏈表中的最后一個結(jié)點，并給出當前串的長度。這樣定義的優(yōu)點是便于進行連接操作，并且對于涉及串長的操作時速度較快。圖4.4(b)是結(jié)點大小為4的鏈串示意圖，其類型定義如下：在該存儲方式下，結(jié)點大小的選擇非常重要，它會影響處理的效率。定義串的存儲密度為串值的存儲位與實際分配存儲位的比值。當存儲密度小時，運算處理方便，但是占用的存儲空間大；而當存儲密度大時，占用的空間小，但是運算量大。若鏈串中的每個結(jié)點存放一個字符，結(jié)點的指針域占4個字節(jié)，那么鏈串的存儲密度只有20%；如果每個結(jié)點存放多個字符，例如4個字符，則存儲密度可以達到50%，有效地提高了存儲空間的利用率。在大多數(shù)情況下，對串進行操作時，只需要像單鏈表一樣按從頭到尾的順序掃描即可。對于結(jié)點大小大于1的情況，需要注意串尾的無效字符。4.4串的模式匹配算法子串定位又稱為串的模式匹配(PatternMatching)，是串運算中最重要的操作之一。將主串稱為目標串(TargetString)，子串稱為模式串(PatternString)，所謂模式匹配，就是在目標串中查找模式串的出現(xiàn)位置，例如在文本中查找是否存在給定的單詞及出現(xiàn)的位置。串的模式匹配算法分為簡單的模式匹配算法和改進的模式匹配算法兩種。4.4.1簡單的模式匹配算法簡單的模式匹配算法又稱為窮舉的模式匹配算法或是樸素的模式匹配算法，也稱為Brute-Force算法，簡稱BF算法。假設T為目標串(主串)，P為模式串(子串)，則有其中，0＜m≤n。在實際應用中，模式串長度m通常遠遠小于目標串長度n，即m<<n。下面給出采用順序串結(jié)構(gòu)時，不依賴其他串運算的簡單的模式匹配算法。算法4.5順序串簡單的模式匹配。分別利用計數(shù)指針i和j指示目標串T和模式串P中當前比較的字符位序。算法的基本思想是：從目標串T的第pos個字符開始與模式串P的第一個字符進行比較，若相等，則繼續(xù)比較后面的字符；否則從目標串的下一個字符開始與模式串的第一個字符進行下一趟比較。重復此過程，直至模式串中的每個字符依次與目標串中的一個連續(xù)的字符序列相等，則匹配成功，函數(shù)值為與模式串中第一個字符相等的字符在目標串中的位序；如果各趟比較均不相等，則匹配不成功，函數(shù)返回值為0。如果在匹配過程中出現(xiàn)ti?≠?pj的情況，即本趟匹配失敗，那么下一趟匹配應該使指針j等于1(即指向p1)，而指針i則等于i-j+2(即指向ti-j+2)。這樣，指針i必須由當前位置i回溯到i-j+2的位置上。圖4.6給出了模式串P?=?"abc"?與目標串T?=?"abbabca"?的簡單的模式匹配過程(pos=1)。下面我們再來討論以結(jié)點大小為1的單鏈表存儲串實現(xiàn)簡單的模式匹配算法。在算法中使用指針shift指向每一趟在目標串中比較的起始位置，若一趟比較中出現(xiàn)不相等的字符，則指針shift右移指向下一個結(jié)點，繼續(xù)下一趟的比較。匹配成功，返回shift所指向的結(jié)點地址；匹配不成功，返回空地址值。具體算法如下：算法4.6鏈串簡單的模式匹配。簡單的模式匹配算法雖然簡單，但效率較低，這是因為在一趟匹配中，目標串內(nèi)可能存在多個和模式串“部分匹配”的子串，而引起計數(shù)指針的多次回溯。特別地，在某些情況下，該算法的效率很低。在最壞情況下，每一趟不成功的匹配都發(fā)生在模式串P的最后一個字符與主串T中相應字符的比較時，則在主串T中新一趟比較的起始位置為i-m+1。若第i趟匹配成功，則前i-1趟不成功的匹配中每趟都比較了m次，而第i趟成功的匹配也比較了m次。所不同的是，前i-1趟均是在第m次比較時不匹配，而第i趟的m次比較都成功匹配。所以，第i趟成功匹配共進行了i?×?m次比較。因此，在最壞情況下，匹配成功的比較次數(shù)為其中，qi為匹配成功的等概率。由于n>>m，故最壞情況下BF算法的時間復雜度為O(n?×?m)。4.4.2改進的模式匹配算法BF算法雖然簡單，但由于帶有回溯而效率低。KMP算法是一種改進的模式匹配算法，由D.E.Knuth、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)，因此人們稱它為克努特-莫里斯-普拉特操作，簡稱KMP算法。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)，以達到快速匹配的目的。1．KMP算法的基本思想BF算法的目標串存在回溯，目標串T與模式串P逐個比較字符，若T[i]?≠?P[j](0≤i＜n，0≤j＜m)，則下趟匹配目標串從T[i]退回到T[i-j+1]開始與模式串P[0]比較。實際上，這種丟棄前面匹配信息的方法極大地降低了匹配效率。目標串的回溯是不必要的，T[i-j+1]與