第四章 串,【課前思考】,從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來(lái)說(shuō)，串是一種特殊的線性表;但就數(shù)據(jù)類型而言，串不是線性表。,希望你帶著這個(gè)問(wèn)題開(kāi)始這一章的學(xué)習(xí)，并能在學(xué)完這一章的內(nèi)容之后能得出正確的結(jié)論。,【學(xué)習(xí)目標(biāo)】,1. 理解“串”類型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作。 2. 理解串類型的各種存儲(chǔ)表示方法。 3. 理解串匹配的各種算法。,【重點(diǎn)和難點(diǎn)】,相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作。本章的難點(diǎn)是理解實(shí)現(xiàn)串匹配的KMP算法的思想，但它不屬本章學(xué)習(xí)的基本要求，更不是重點(diǎn)學(xué)習(xí)內(nèi)容。,【知識(shí)點(diǎn)】,串的類型定義、串的存儲(chǔ)表示、串匹配、KMP算法,【學(xué)習(xí)指南】,雖然目前各常用的高級(jí)語(yǔ)言中都已經(jīng)實(shí)現(xiàn)了串類型，但由于它是通過(guò)軟件實(shí)現(xiàn)的，因此作為一個(gè)軟件工作者還是應(yīng)該了解串的實(shí)現(xiàn)方法。本章沒(méi)有必須完成的算法設(shè)計(jì)題，如果有興趣可以試試以下幾個(gè)題:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6個(gè)是練習(xí)串的基本操作的應(yīng)用，后2個(gè)是和KMP算法相關(guān)的練習(xí)。,4.1 串類型的定義,4.2 串的表示和實(shí)現(xiàn),4.3 串的模式匹配算法,4.1串的類型定義,一、 基本概念,1串的定義 串( string) 是由零個(gè)或多個(gè)字符組成的有限序列，記作s='a1a2an'，其中s為串的名字，用成對(duì)的單引號(hào)括起來(lái)的字符序列為串的值，但兩邊的引號(hào)不算串值，不包含在串中。ai(1in)可以是字母、數(shù)字或其它字符。 n為串中字符的個(gè)數(shù)，稱為串的長(zhǎng)度。,2空串 不含任何字符的串稱為空串，它的長(zhǎng)度n=0，記為s=''。,3空格串 含有一個(gè)或多個(gè)空格的串，稱為空格串，它的長(zhǎng)度n為空格的個(gè)數(shù)，一般用符號(hào)“ ø”表示空串。,串是有限長(zhǎng)的字符序列，由一對(duì)單引號(hào)相括，如: a string,4子串、主串 通常將字符在串中的序號(hào)稱為該字符在串中的位置。子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示。 若一個(gè)串是另一個(gè)串中連續(xù)的一段，則這個(gè)串稱為另一個(gè)串的子串，而另一個(gè)串相對(duì)于該串稱為主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，則s1為s2的子串，s2相對(duì)于s1為主串。,另外，空串是任意串的子串，任意串是自身的子串。若一個(gè)串的長(zhǎng)度為n，則它的子串?dāng)?shù)目為 +1，真子串個(gè)數(shù)為 (除串本身以外的子串都稱為真子串)。 當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等, 并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。,二、串的抽象數(shù)據(jù)類型的定義如下：,ADT String ,數(shù)據(jù)對(duì)象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,數(shù)據(jù)關(guān)系：,R1 | ai-1, ai D, i=2,.,n ,基本操作：,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos, len),ClearString (&S), ADT String,StrAssign (&T, chars) 初始條件：chars 是字符串常量。 操作結(jié)果：把 chars 賦為 T 的值。,StrCopy (&T, S) 初始條件：串 S 存在。 操作結(jié)果：由串 S 復(fù)制得串 T。,DestroyString (&S) 初始條件：串 S 存在。 操作結(jié)果：串 S 被銷毀。,StrEmpty(S) 初始條件：串S存在。 操作結(jié)果：若 S 為空串，則返回TRUE， 否則返回 FALSE。, 表示空串，空串的長(zhǎng)度為零。,StrCompare(S,T) 初始條件：串 S 和 T 存在。 操作結(jié)果：若S T，則返回值 0； 若S T，則返回值 0； 若S T，則返回值 0。,例如：StrCompare(data, state) 0,StrLength(S) 初始條件：串 S 存在。 操作結(jié)果：返回 S 的元素個(gè)數(shù)， 稱為串的長(zhǎng)度。,Concat(&T,S1,S2) 初始條件：串 S1 和 S2 存在。 操作結(jié)果：用 T 返回由 S1 和 S2 聯(lián)接而成的新串。,例如： Concate( T, man, kind) 求得 T = mankind,SubString (&Sub, S, pos, len) 初始條件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作結(jié)果： 用 Sub 返回串 S 的第 pos 個(gè)字符起 長(zhǎng)度為 len 的子串。,例如： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9) 求得 sub = commander； SubString( sub, commander, 9, 1) 求得 sub = r；,子串為“串” 中的一個(gè)字符子序列,SubString(sub, commander, 4, 7) sub = ?,SubString(sub, beijing, 7, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串長(zhǎng)度之間存在約束關(guān)系,長(zhǎng)度為 0 的子串為“合法”串,Index(S,T,pos) 初始條件：串S和T存在，T是非空串， 1posStrLength(S)。 操作結(jié)果： 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。,假設(shè) S = abcaabcaaabc, T = bca,Index(S, T, 1) = 2；,Index(S, T, 2) = 6；,Index(S, T, 8) = 0；,“子串在主串中的位置”意指子串 中的第一個(gè)字符在主串中的位序。,Replace(&S,T,V) 初始條件：串S, T和 V 均已存在， 且 T 是非空串。 操作結(jié)果：用V替換主串S中出現(xiàn) 的所有與（模式串）T 相等的不重疊的子串。,例如：,假設(shè) S = abcaabcaaabca，T = bca,若 V = x， 則經(jīng)置換后得到 S = axaxaax,若 V = bc， 則經(jīng)置換后得到 S = abcabcaabc,StrInsert (&S, pos, T) 初始條件：串S和T存在， 1posStrLength(S)1。 操作結(jié)果：在串S的第pos個(gè)字符之前 插入串T。,例如：S = chater，T = rac， 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character,StrDelete (&S, pos, len) 初始條件：串S存在 1posStrLength(S)-len+1。 操作結(jié)果：從串S中刪除第pos個(gè)字符 起長(zhǎng)度為len的子串。,ClearString(&S) 初始條件：串S存在。 操作結(jié)果：將S清為空串。,對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。,gets(str) 輸入一個(gè)串； puts(str) 輸出一個(gè)串； strcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復(fù)制函數(shù)； strcmp(str1, str2) 串比較函數(shù)； strlen(str) 求串長(zhǎng)函數(shù)；,例如：C語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù)：,在上述抽象數(shù)據(jù)類型定義的13種操作中， 串賦值StrAssign、串復(fù)制Strcopy、 串比較StrCompare、求串長(zhǎng)StrLength、 串聯(lián)接Concat以及求子串SubString 等六種操作構(gòu)成串類型的最小操作子集。 即：這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn)， 反之，其他串操作（除串清除ClearString和串 銷毀DestroyString外）可在這個(gè)最小操作子 集上實(shí)現(xiàn)。,例如，可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。,StrCompare(SubString(S, i, StrLength(T),T ) ? 0,S 串,T 串,T 串,i,pos,n-m+1,算法的基本思想為：,int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個(gè)字符之后存在與 T相等的子串，則返回第一個(gè) 這樣的子串在S中的位置，否則返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在與T相等的子串 / Index,又如串的置換函數(shù)： Replace(&S,T,V),S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,sub,串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別 僅在于串的數(shù)據(jù)對(duì)象約束為字符集。,串的基本操作和線性表有很大差別。,在線性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象； 在串的基本操作中，通常以“串的整體”作為操作對(duì)象。,在程序設(shè)計(jì)語(yǔ)言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。,4.2 串的表示和實(shí)現(xiàn),一、串的定長(zhǎng)順序存儲(chǔ)表示,二、串的堆分配存儲(chǔ)表示,三、串的塊鏈存儲(chǔ)表示,一、串的定長(zhǎng)順序存儲(chǔ)表示,與前面所講的線性表的順序存儲(chǔ)結(jié)構(gòu)類似, 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列。常常將定長(zhǎng)順序串設(shè)計(jì)成一種結(jié)構(gòu)類型, 串的存儲(chǔ)分配是在編譯時(shí)完成的。,#define MAXSTRLEN 255 / 用戶可在255以內(nèi)定義最大串長(zhǎng) typedef unsigned char Sstring MAXSTRLEN + 1; / 0號(hào)單元存放串的長(zhǎng)度,或： typedef struct /* 串結(jié)構(gòu)定義 */ char chMAXLEN; int len; SString;,按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列的復(fù)制”。,串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱之為 “截?cái)唷?。,特點(diǎn):,Status Concat(SString S1, SString S2, SString / Concat,例如：串的聯(lián)接算法中需分三種情況處理：,T1S10 = S11S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截?cái)?else if (S10 MAXSTRSIZE) / 截?cái)?else / 截?cái)?僅取S1),T1S10 = S11S10; TS10+1MAXSTRLEN = S21MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T0MAXSTRLEN = S10MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,(1) 串插入函數(shù)。 StrInsert(s, pos, t) /*在串s中序號(hào)為pos的字符之前插入串t */ SString *s, t; int pos; int i; if (poss-len) return(0); /* 插入位置不合法 */ if (s-len + t.lenlen + t.len-1;i=t.len + pos;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos=t.chi; s-len=s-len+t.len; ,定長(zhǎng)順序存儲(chǔ)的操作實(shí)施：,【算法 串插入函數(shù)】,else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos=t.chi; s-len=MAXLEN; else /* 串t的部分字符序列要舍棄 */ for (i=0;ichi+pos=t.chi; s-len=MAXSTRLEN; return(1); ,(2) 串刪除函數(shù)。 StrDelete(s, pos, len) /* 在串s中刪除從序號(hào)pos起len個(gè)字符 */ SString *s; int pos, len; int i; if (pos(s-len-len) return(0); for (i=pos+len;ilen;i+) s-chi-len=s-chi; s-len=s-len - len; return(1); ,【算法 串刪除函數(shù)】,(3) 串復(fù)制函數(shù)。 StrCopy(s, t) /* 將串t的值復(fù)制到串s中 */ SString *s, t; int i; for (i=0;ichi=t.chi; s-len=t.len; ,【算法 串復(fù)制函數(shù)】,(4) 判空函數(shù)。 StrEmpty(s) /* 若串s為空(即串長(zhǎng)為0), 則返回1, 否則返回0 */ SString s; if (s.len=0) return(1); else return(0); ,【算法 判空函數(shù)】,(5) 串比較函數(shù)。 StrCompare(s, t) /* 若串s和t相等, 則返回0；若st，則返回1；若st，則返 回-1 */ SString s, t; int i; for (i=0;is.len ,【算法 串比較函數(shù)】,(6) 求串長(zhǎng)函數(shù)。 StrLength(s)/* 返回串s的長(zhǎng)度 */ SString s; return(s.len); ,【算法 求串長(zhǎng)函數(shù)】,(7) 清空函數(shù)。 StrClear(s) /* 將串s置為空串 */ SString *s; s-len=0; return(1); ,【算法 清空函數(shù)】,(8) 連接函數(shù)。 Concat(s, t) /* 將串t連接在串s的后面 */ SString *s, t; int i, flag; if (s-len + t.lenlen; ilen + t.len; i+) s-chi=t.chi-s-len; s-len+=t.len;flag=1; ,else if (s-lenlen;ichi=t.chi-s-len; s-len=MAXSTRLEN;flag=0; else flag=0;/* 串s的長(zhǎng)度等于MAXLEN, 串t不被連接 */ return(flag); ,【算法 連接函數(shù)】,(9) 求子串函數(shù)。 SubString(sub, s, pos, len) /* 將串s中序號(hào)pos起len個(gè)字符復(fù)制到sub中 */ SString *sub, s; int pos, len; int i; if (poss.len | lens.len-pos) sub-len=0;return(0); else for (i=0;ichi=s.chi+pos; sub-len=len;return(1); ,【算法 求子串函數(shù)】,(10) 定位函數(shù)。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */ SString s, t; int pos; int i, j; if (t.len=0) return(0); i=pos;j=0; while (i=t.len) return(i-t.len); else return(0); ,【算法 定位函數(shù)】,typedef struct char *ch; / 若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)， / 否則ch為NULL int length; / 串長(zhǎng)度 HString;,二、串的堆分配存儲(chǔ)表示,特點(diǎn)：仍用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列，但其存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。,通常，C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。 C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符， 串長(zhǎng)是一個(gè)隱含值。,這類串操作實(shí)現(xiàn)的算法為： 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制。,Status Concat(HString / Concat,Status SubString(HString / SubString, ,Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0len-1 = Spos-1pos+len-2; Sub.length = len;,三、串的塊鏈存儲(chǔ)表示,也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有 8 位二進(jìn)制數(shù)，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串。,存儲(chǔ)密度 =,數(shù)據(jù)元素所占存儲(chǔ)位,實(shí)際分配的存儲(chǔ)位,#define CHUNKSIZE 80 / 可由用戶定義的塊大小 typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LString;,例如: 在編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即: 同一行的串用定長(zhǎng)結(jié)構(gòu)(80個(gè)字符), 行和行之間用指針相聯(lián)接。,實(shí)際應(yīng)用時(shí)，可以根據(jù)問(wèn)題所需來(lái)設(shè)置結(jié)點(diǎn)的大小。,這是串的一種重要操作，很多 軟件，若有“編輯”菜單項(xiàng)的話， 則其中必有“查找”子菜單項(xiàng)。,4.3 串的模式匹配算法,子串的定位操作通常稱為串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。,初始條件：串S和T存在，T是非空串， 1posStrLength(S)。 操作結(jié)果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos個(gè)字符之后第一次出 現(xiàn)的位置；否則函數(shù)值為0。,首先，回憶一下串匹配(查找)的定義:,INDEX (S, T, pos),下面討論以定長(zhǎng)順序結(jié)構(gòu) 表示串時(shí)的幾種算法。,一、簡(jiǎn)單算法,二、首尾匹配算法,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,一、簡(jiǎn)單算法Brute-Force算法,例如,設(shè)目標(biāo)串s=“cddcdc”,模式串t=“cdc”。s的長(zhǎng)度為n(n=6),t的長(zhǎng)度為m(m=3)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。BF模式匹配過(guò)程如下所示。,這個(gè)算法簡(jiǎn)單,易于理解,但效率不高,主要原因是:主串指針i在若干個(gè)字符序列比較相等后,若有一個(gè)字符比較不相等,仍需回溯(即i=i-j+1)。該算法在最好情況下的時(shí)間復(fù)雜度為O(m),即主串的前m個(gè)字符正好等于模式串的m個(gè)字符。在最壞情況下的時(shí)間復(fù)雜度為O(n*m)。,int index(SqString s,SqString t) int i=0,j=0,k; while (i=t.len) k=i-t.len; /*返回匹配的第一個(gè)字符的下標(biāo)*/ else k=-1; /*模式匹配不成功*/ return k; ,先比較模式串的第一個(gè)字符， 再比較模式串的最后一個(gè)字符， 最后比較模式串中從第二個(gè)到 第n-1個(gè)字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始點(diǎn) else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; ,/ 檢查中間字符的匹配情況,k = 1; j = 2; while ( j tLength / 重新開(kāi)始下一次的匹配檢測(cè),三、模式匹配的改進(jìn)算法（KMP算法）,此方法由克努特(D.E.Knuth)莫里斯(J.H.Morris)普拉特(V.R.Pratt)同時(shí)發(fā)現(xiàn)。,1.基本思想：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符不等時(shí)，不需回溯i指針，而是利用已得到的部分匹配結(jié)果，將模式串向右滑動(dòng)盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較。 避免多余的、不必要的比較，從而提高算法性能。算法總在0(n+m)的時(shí)間數(shù)量級(jí)上完成匹配操作。,2.KMP算法匹配實(shí)例：,(1)模式串t中沒(méi)有真子串 真子串是指模式串t存在某個(gè)k(0kj),使得“t0t1tk”=“tj-ktj-k+1tj”成立。 例如t=“cdc“就是這樣的模式串。在圖4.6中的第一次回溯,當(dāng)s0=t0,s1=t1,s2t2時(shí),算法中取i=1,j=0,使主串指針回溯一個(gè)位置,比較s1和t0。因t0t1,所以一定有s1t0。另外,因有t0=t2,s0=t0,s2t2,則一定可推出s2t0,所以也不必取i=2,j=0去比較s2和t0?？芍苯釉诘诙伪容^時(shí)取i=3,j=0,比較s3和t0。這樣,模式匹配過(guò)程主串指針i就可不必回溯。,(2)模式串中存在真子串 例如t=“abab”,由于“t0t1”=“t2t3”(這里k=1,j=3),則存在真子串。設(shè)s=“abacabab”,t=“abab”,第一次匹配過(guò)程如下所示。,此時(shí)不必從i=1(i=i-j+1=1),j=0重新開(kāi)始第二次匹配。因t0t1,s1=t1,必有s1t0,又因t0 =t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接從i=3,j=1開(kāi)始。,現(xiàn)在我們討論一般情況。 設(shè)s=“s0s1sn-1“,t=“t0t1tm-1“,當(dāng)sitj (0in-m,0jm)時(shí),存在: “t0t1tj-1“=“si-jsi-j+1si-1“ (4.1) 若模式串中存在的真子串滿足: “t0t1tk“=“tj-ktj-k+1tj“ (0kj) (4.2) 由(4.1)式說(shuō)明模式串中的子串“t0t1tk-1“已和主串“si-ksi-k+1si-1“匹配,下一次可直接比較si和tk,若不存在(4.2)式,則結(jié)合(4.1)式說(shuō)明在“t0t1tj-1“中不存在任何以t0為首字符子串與“si-j+1si-j+2si-1“中以si-1為末字符的匹配子串,下一次可直接比較si和t0。,為此,定義nextj函數(shù)如下: maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng)此集合非空時(shí) -1 當(dāng)j=0時(shí) 0 其他情況,nextj=,t=“abab”對(duì)應(yīng)的next數(shù)組如下:,由模式串t求出next值的算法如下: void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.len-1) if (k=-1 | t.chj=t.chk) /*k為-1或比較的字符相等時(shí)*/ j+;k+; nextj=k; else k=nextk; ,int KMPIndex(SqString s,SqString t) /*KMP算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (i=t.len) v=i-t.len; /*返回匹配模式串的首字符下標(biāo)*/ else v=-1; /*返回不匹配標(biāo)志*/ return v; ,設(shè)主串s的長(zhǎng)度為n,子串t長(zhǎng)度為m,在KMP算法中求next數(shù)組的時(shí)間復(fù)雜度為O(m),在后面的匹配中因主串s的下標(biāo)不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時(shí)間復(fù)雜度為O(n+m)。,例如,設(shè)目標(biāo)串s=“aaabaaaab”,模式串t=“aaaab”。s的長(zhǎng)度為n(n=9),t的長(zhǎng)度為m(m=5)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。KMP模式匹配過(guò)程如下所示。,上述定義的next在某些情況下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配時(shí),當(dāng)i=3,j=3時(shí),s.ch3t.ch3,由nextj的指示還需進(jìn)行i=3、j=2,i=3、j=1,i=3、j=0等三次比較。實(shí)際上,因?yàn)槟Ｊ街械牡?、2、3個(gè)字符和第4個(gè)字符都相等,因此,不需要再和主串中第4個(gè)字符相比較,而可以將模式一次向右滑動(dòng)4個(gè)字符的位置直接進(jìn)行i=4,j=0時(shí)的字符比較。,KMP算法的改進(jìn)：,這就是說(shuō),若按上述定義得到nextj=k,而模式中pj=pk,則為主串中字符si和pj比較不等時(shí),不需要再和pk進(jìn)行比較,而直接和pnextk進(jìn)行比較,換句話說(shuō),此時(shí)的nextj應(yīng)和nextk相同。為此將nextj修正為nextvalj。,由模式串t求出nextval值: void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (jt.len) if (k=-1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; ,【本章小結(jié)】,在這一章介紹了串類型的定義及其實(shí)現(xiàn)方法，并重點(diǎn)討論了串操作中最常用的“串定位操作（又稱模式匹配）“的兩個(gè)算法。 串的兩個(gè)顯著特點(diǎn)是，其一、它的數(shù)據(jù)元素都是字符，因此它的存儲(chǔ)結(jié)構(gòu)和線性表有很大不同，例如多數(shù)情況下，實(shí)現(xiàn)串類型采用的是“堆分配“的存儲(chǔ)結(jié)構(gòu)，而當(dāng)用鏈表存儲(chǔ)串值時(shí)，結(jié)點(diǎn)中數(shù)據(jù)域的類型不是“字符“，而是“串“，這種塊鏈結(jié)構(gòu)通常只在應(yīng)用程序中使用；其二、串的基本操作通常以“串的整體“作為操作對(duì)象，而不像線性表是以“數(shù)據(jù)元素“作為操作對(duì)象,“串匹配”的簡(jiǎn)單算法,其算法思想直截了當(dāng)，簡(jiǎn)單易懂，適用于在一般的文檔編輯中應(yīng)用，但在某些特殊情況，例如只有0和1兩種字符構(gòu)成的文本串中應(yīng)用時(shí)效率就很低。KMP算法是它的一種改進(jìn)方法，其特點(diǎn)是利用匹配過(guò)程中已經(jīng)得到的主串和模式串對(duì)應(yīng)字符之間“等與不等“的信息以及T串本身具有的特性來(lái)決定之后進(jìn)行的匹配過(guò)程，從而減少了簡(jiǎn)單算法中進(jìn)行的“本不必要再進(jìn)行的“字符比較。 此外應(yīng)學(xué)會(huì)善于利用高級(jí)語(yǔ)言中提供的串操作（如C語(yǔ)言中的串函數(shù)庫(kù)和C+語(yǔ)言中的串類）進(jìn)行編程，只是在應(yīng)用前必須詳細(xì)閱讀語(yǔ)言所提供的使用手冊(cè)。,一、基礎(chǔ)知識(shí)題 二、算法設(shè)計(jì)題 4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30,作業(yè),實(shí)驗(yàn)五 鏈隊(duì)列的建立及入隊(duì)出隊(duì)操作,一、實(shí)驗(yàn)?zāi)康?了解鏈隊(duì)列的結(jié)構(gòu)特點(diǎn)和有關(guān)概念，掌握鏈隊(duì)列的建立及入隊(duì)出隊(duì)操作算法。 二、實(shí)驗(yàn)內(nèi)容 建立鏈隊(duì)列，并實(shí)現(xiàn)元素的入隊(duì)出隊(duì)的基本操作。 三、實(shí)驗(yàn)要點(diǎn)及說(shuō)明 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，符合先進(jìn)先出的原則。與鏈表一樣，鏈隊(duì)列大多采用帶頭結(jié)點(diǎn)的鏈對(duì)，設(shè)頭指針為h，則對(duì)頭結(jié)點(diǎn)為h-next，再設(shè)一個(gè)對(duì)尾指針q-rear指向鏈隊(duì)列尾部。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可定義如下： typedef struct node typedef struct char data; slnode *h; struct node *next; slnode ; slnode *rear;lqtype; 四、思考題 1、 比較鏈隊(duì)列與鏈棧的相同點(diǎn)與不同點(diǎn)。 2、在鏈隊(duì)列中， q-rear指針能否省去？若能，怎樣才能找到隊(duì)尾？,實(shí)驗(yàn)六 串的模式匹配,一、實(shí)驗(yàn)?zāi)康?熟悉串的有關(guān)概念，掌握串的存儲(chǔ)結(jié)構(gòu)及串的模式匹配算法。 二、實(shí)驗(yàn)內(nèi)容 由用戶隨意輸入兩個(gè)串：主串S和模式串T，設(shè)S=s1s2sn，T=t1t2tm，且0m=n。用簡(jiǎn)單和KMP模式匹配算法判斷模式串T是否在主串S中，若在，則輸出模式串在主串的第一匹配位置，否則，匹配失敗，返回零值。 三、實(shí)驗(yàn)要點(diǎn)及說(shuō)明 簡(jiǎn)單模式匹配算法和KMP模式匹配算法的主要區(qū)別在于后者將有效利用已有的匹配結(jié)果，省去不必要的匹配過(guò)程，提高匹配性能。 利用串的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。 四、思考題 能否用串的塊鏈存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)KMP算法？,