數(shù)據(jù)結(jié)構(gòu)_字符串操作原理

1、CH4 串串q4.1 串類型的定義串類型的定義q4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)q4.3 串的模式匹配算法串的模式匹配算法n教學(xué)目標(biāo)教學(xué)目標(biāo)n熟悉串的有關(guān)概念，串和線性表的關(guān)系。熟悉串的有關(guān)概念，串和線性表的關(guān)系。n掌握串的各種存儲結(jié)構(gòu)，比較它們的優(yōu)、缺點(diǎn)，從而學(xué)會(huì)掌握串的各種存儲結(jié)構(gòu)，比較它們的優(yōu)、缺點(diǎn)，從而學(xué)會(huì)在何時(shí)選用何種存儲結(jié)構(gòu)為宜。在何時(shí)選用何種存儲結(jié)構(gòu)為宜。n熟練掌握串的七種基本運(yùn)算，并能利用這些基本運(yùn)算實(shí)現(xiàn)熟練掌握串的七種基本運(yùn)算，并能利用這些基本運(yùn)算實(shí)現(xiàn)串的其它各種運(yùn)算。串的其它各種運(yùn)算。n教學(xué)難點(diǎn)教學(xué)難點(diǎn)n串運(yùn)算的實(shí)現(xiàn)，特別是順序串上子串定位的運(yùn)算（又稱串串運(yùn)算的實(shí)現(xiàn)，特

2、別是順序串上子串定位的運(yùn)算（又稱串的模式匹配或串匹配）。的模式匹配或串匹配）。4.1 串類型的定義串類型的定義n一、串的基本概念一、串的基本概念n串串(String)的定義的定義 s“a1a2an”n其中：其中：ns為串的名字，為串的名字，n串的值串的值nai(1in)一般是字母、數(shù)學(xué)、標(biāo)點(diǎn)符號等可屏幕顯一般是字母、數(shù)學(xué)、標(biāo)點(diǎn)符號等可屏幕顯示的字符。示的字符。n串的長度串的長度n。4.1 串類型的定義串類型的定義n字符串與一般的線性表的區(qū)別：字符串與一般的線性表的區(qū)別：n串的數(shù)據(jù)元素約束為字符集；串的數(shù)據(jù)元素約束為字符集；n串的基本操作通常針對串的基本操作通常針對串的整體或串的一個(gè)部分串的整體

3、或串的一個(gè)部分進(jìn)行。進(jìn)行。n問題：為何要單獨(dú)討論問題：為何要單獨(dú)討論“串串”類型？類型？n字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）n程序設(shè)計(jì)中，處理對象很多都是串類型。程序設(shè)計(jì)中，處理對象很多都是串類型。4.1 串類型的定義串類型的定義n空串和空白串：空串和空白串：n長度為零的串稱為長度為零的串稱為空串空串(Empty String)，它不包含任何字符。它不包含任何字符。n空格（白）串空格（白）串:僅由一個(gè)或多個(gè)空格組成的串稱為僅由一個(gè)或多個(gè)空格組成的串稱為空白串空白串(Blank String)n子串和主串子串和主串neg: A“T

4、his is a string” B“is”n特別地：特別地：n空串是任意串的子串，任意串是其自身的子串?？沾侨我獯淖哟我獯瞧渥陨淼淖哟?。n串的相等串的相等二、串的抽象數(shù)據(jù)類型定義二、串的抽象數(shù)據(jù)類型定義ADT String數(shù)據(jù)對象：數(shù)據(jù)對象：Dai|aiCharacterSet,i1,2,n;n0數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：S| ai-1， ai D, i 2,n基本操作：基本操作：StrAssign(&T,chars) StrLength(S)SubString(&Sub,S,pos,len)StrCopy(&T,S) Index(S,T,pos)StrEmpty

5、(S) Replace(&S,T,V)StrCompare(S,T) StrInsert(&S,pos,T)Concat(&T,S1,S2) StrDelete(&S,pos,len) ADT String三、三、C語言的串函數(shù)語言的串函數(shù)n用用C處理字符串時(shí)，要調(diào)用標(biāo)準(zhǔn)庫函數(shù)處理字符串時(shí)，要調(diào)用標(biāo)準(zhǔn)庫函數(shù) #includen串長度：串長度：int strlen(char *s);n串比較：串比較：int strcmp(char *str1,char *str2); n串拷貝：串拷貝：char * strcpy(char *str1,char *str2);n串

6、連接：串連接：char * strcat(char *str1,char *str2); n子串子串T定位：定位：char *strchr(char *str,char ch); n子串查找子串查找 ： char *strstr(char *s1,char *s2); n 4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)n串的機(jī)內(nèi)表示方法：串的機(jī)內(nèi)表示方法：定長順序存儲表示（靜態(tài)數(shù)組結(jié)構(gòu)）定長順序存儲表示（靜態(tài)數(shù)組結(jié)構(gòu)）堆分配存儲表示（動(dòng)態(tài)數(shù)組結(jié)構(gòu)）堆分配存儲表示（動(dòng)態(tài)數(shù)組結(jié)構(gòu)）串的塊鏈存儲表示串的塊鏈存儲表示順序存儲：順序存儲：鏈?zhǔn)酱鎯Γ烘準(zhǔn)酱鎯Γ?.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)n 4.2.1 定長

7、順序存儲表示定長順序存儲表示n用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配靜態(tài)存儲分配。n存儲表示一：存儲表示一：#define MAXSTRLEN 255typedef char SStringMAXSTRLEN +1;SString s; n串的結(jié)束標(biāo)志的設(shè)置串的結(jié)束標(biāo)志的設(shè)置n（1）一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符在串值的尾部來）一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符在串值的尾部來表示串的結(jié)束。表示串的結(jié)束。 例如：例如：C語言中以字符語言中以

8、字符0表示串值的終結(jié)。表示串值的終結(jié)。n（2）可以不設(shè)終結(jié)符）可以不設(shè)終結(jié)符 typedef struct char chMAXSTRLEN; int length; SString; n（3）還可以用數(shù)組的）還可以用數(shù)組的0號單元存儲串的長度號單元存儲串的長度。算法算法4.2（串的連接算法）（串的連接算法）Status Concat(SString &T,SString S1,SString S2)if (S10+S20=MAXSTRLEN) T1 S10=S11 S10; TS10+1 S10+S20=S21 S20; T0=S10+S20; uncut=TRUE;else if

9、(S10MAXSTRLEN) T1 S10=S11 S10; TS10+1 MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN;uncut=FALSE; else T0.MAXSTRLEN=S10MAXSTRLEN; uncut=FALSE;return OK;算法算法4.3（取子串）（取子串）Status SubString(SString &Sub,SString S,int pos,int len) if (posS0 |lenS0-pos+1) return ERROR; Sub1 len=Spos pos+len-1 Sub0=len; retu

10、rn OK;/SubString小結(jié)：小結(jié)：n1.串的定長順序存儲結(jié)構(gòu)又稱為串的靜態(tài)存儲結(jié)構(gòu)，即用串的定長順序存儲結(jié)構(gòu)又稱為串的靜態(tài)存儲結(jié)構(gòu)，即用一段連續(xù)的存儲單元來存儲串的字符序列。一段連續(xù)的存儲單元來存儲串的字符序列。n2.串的存儲結(jié)構(gòu)必須預(yù)先定義允許存放串的最大字符個(gè)數(shù)，串的存儲結(jié)構(gòu)必須預(yù)先定義允許存放串的最大字符個(gè)數(shù)，容易造成系統(tǒng)空間浪費(fèi)或運(yùn)行出錯(cuò)。容易造成系統(tǒng)空間浪費(fèi)或運(yùn)行出錯(cuò)。n3.串的某些操作（如：串的連接、串的替換等）受到限制。串的某些操作（如：串的連接、串的替換等）受到限制。4.2.2 堆分配存儲表示堆分配存儲表示n特點(diǎn)：特點(diǎn)：n仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在

11、程序仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中執(zhí)行過程中動(dòng)態(tài)分配動(dòng)態(tài)分配而得。而得。n思路：思路：n利用利用malloc函數(shù)合理預(yù)設(shè)串長空間。函數(shù)合理預(yù)設(shè)串長空間。n串的動(dòng)態(tài)數(shù)組結(jié)構(gòu)體定義如下：串的動(dòng)態(tài)數(shù)組結(jié)構(gòu)體定義如下： typedef struct char *ch; int length; HString; 串的賦值算法串的賦值算法 Status StrAssign(HString &T,char *chars) if (T.ch) free (T.ch); for (i=0,c=chars;c;+i,+c); if (!i) T.ch=NULL; T.leng

12、th=0; else T.ch=(char*)malloc(i*sizeof(char); if (!T.ch) exit OVERFLOW; T.ch0i-1=chars0i-1; T.length=i; return OK;n串的比較算法串的比較算法 int StrCompare(HString S,HString T) for (i=0;iS.length& iT.length;+i) if (S.chi!=T.chi ) return S.chi-T.chi; return S.length-T.length; n串的連接算法串的連接算法Status Concat(HStrin

13、g &T,HString S1,HString S2)if (T.ch) free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char) if (T.ch) exit OVERFLOW;T.ch0S1.length-1=S1.ch0S1.length-1;T.length=S1.length+S2.length;T.chS1.lengthT.length1=S2.ch0S2.length-1;return OK; n取子串算法取子串算法SubString(HString &Sub,HString S,int pos

14、,int len) if (posS.length|lenS.length-pos+1) return ERROR; if (Sub.ch) free(Sub.ch); if (!len) Sub.ch=NULL;Sub.length=0; else Sub.ch=(char*)malloc(len*sizeof(char); Sub.ch0len-1=Spos-1pos+len-2; Sub.length=len; return OK;4.2.3 串的鏈?zhǔn)酱鎯Y(jié)構(gòu)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)n(1)單字符結(jié)點(diǎn)鏈單字符結(jié)點(diǎn)鏈 typedef struct node char data; struct no

15、de *next; *LString; A B C I headn特點(diǎn)：特點(diǎn)：n一個(gè)鏈串由頭指針唯一確定。一個(gè)鏈串由頭指針唯一確定。n這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲空間利用率太這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲空間利用率太低。低。n（2）串的塊鏈結(jié)構(gòu)）串的塊鏈結(jié)構(gòu)n引入目的：提高存儲密度引入目的：提高存儲密度headA B C D E F G H I # # # NULLn存儲表示的定義：存儲表示的定義：#define CHUNKSIZE 80typedef struct node char dataCHUNKSIZE; struct node *next; *LString;4.

16、3 串的模式匹配算法串的模式匹配算法n一、基本概念一、基本概念n模式匹配（子串定位）模式匹配（子串定位）n設(shè)有主串設(shè)有主串S和子串和子串T（將（將S稱為目標(biāo)串，將稱為目標(biāo)串，將T稱為模式串），在主串稱為模式串），在主串S中，從位置中，從位置start開始查找，如若在主串開始查找，如若在主串S中找到一個(gè)與子串中找到一個(gè)與子串T相等相等的子串，則返回的子串，則返回T的第一個(gè)字符在主串中的位置，否則返回的第一個(gè)字符在主串中的位置，否則返回-1。n算法目的算法目的n確定主串中所含子串第一次出現(xiàn)的位置（定位）確定主串中所含子串第一次出現(xiàn)的位置（定位） n算法種類算法種類nBF算法算法 （又稱古典的、經(jīng)典

17、的、樸素的、窮舉的）（又稱古典的、經(jīng)典的、樸素的、窮舉的）nKMP算法算法n二、二、Brute-Force算法算法n1.算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：將主串將主串S的第一個(gè)字符和模式的第一個(gè)字符和模式T的第的第1個(gè)字符比較，個(gè)字符比較，n若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若相等，繼續(xù)逐個(gè)比較后續(xù)字符；n若不等，從主串若不等，從主串S的下一字符起，重新與的下一字符起，重新與T第一個(gè)字第一個(gè)字符比較。符比較。 n直到直到:n主串主串S的一個(gè)連續(xù)子串字符序列與模式的一個(gè)連續(xù)子串字符序列與模式T相等。返回相等。返回值為值為S中與中與T匹配的子序列第一個(gè)字符的序號，即匹匹配的子序列第一個(gè)字符的序號，即匹配

18、成功。配成功。n否則，匹配失敗，返回值否則，匹配失敗，返回值 1。n2.下面以定長的順序串類型作為存儲結(jié)構(gòu)，給出具體的串下面以定長的順序串類型作為存儲結(jié)構(gòu)，給出具體的串匹配算法。匹配算法。int index(SString S,SString T,int pos) i=pos; j=1; while (i=S0 &jT0) return i T0; else return 0;n顯然，該算法在最壞情況下的時(shí)間復(fù)雜度為顯然，該算法在最壞情況下的時(shí)間復(fù)雜度為O(n-m)m)。n3.BF算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度n若若n為主串長度，為主串長度，m為子串長度，為子串長度，n最好情況：最好

19、情況：n一配就中！一配就中！ 只比較了只比較了m次。次。n最壞情況：最壞情況：n則串的則串的BF匹配算法最壞的情況下需要比較字符的總次匹配算法最壞的情況下需要比較字符的總次數(shù)為數(shù)為(nm1)m。n4.BF（Brute-Force）算法的特點(diǎn)：算法的特點(diǎn)：n 簡單，易于理解，效率較高簡單，易于理解，效率較高；n 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度O(n m)m) 。(其中其中n,m分別為主串分別為主串和模式串的長度）和模式串的長度）n 實(shí)際運(yùn)行中，時(shí)間近似于實(shí)際運(yùn)行中，時(shí)間近似于 O（nm)。n注意：注意：n當(dāng)遇到一次當(dāng)遇到一次sitj,主串要回退到主串要回退到ij+2的位置，而模式串要的位置，而

20、模式串要回到第一個(gè)位置（即回到第一個(gè)位置（即j1的位置的位置)；n但當(dāng)一次比較出現(xiàn)但當(dāng)一次比較出現(xiàn)sitj時(shí)，則應(yīng)該有：時(shí)，則應(yīng)該有： si-j+1si-j+2si-1=t1t2 tj-2tj-1 n改進(jìn)：改進(jìn)：n每當(dāng)一趟匹配過程出現(xiàn)每當(dāng)一趟匹配過程出現(xiàn)sitj時(shí)，主串指示器時(shí)，主串指示器i不用回溯，而不用回溯，而是利用已經(jīng)得到的是利用已經(jīng)得到的“部分匹配部分匹配”結(jié)果，將模式串向右結(jié)果，將模式串向右“滑滑動(dòng)動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。4.3.2 模式匹配的改進(jìn)算法模式匹配的改進(jìn)算法 （KMP算法）算法）n一、分析與示例一、分析與示例 1趟趟ab

21、abcabcacbababc2趟趟ababcabcacbababcac3趟趟ababcabcacbababcac二、討論一般情況二、討論一般情況n設(shè)設(shè): 主串主串 S= s1s2sisn ， 模式串模式串T = p1p2pjpmn問：問：n當(dāng)某趟比較發(fā)生當(dāng)某趟比較發(fā)生“失配失配”（即（即sipj）時(shí)，模式串應(yīng)該向時(shí)，模式串應(yīng)該向“右右”滑動(dòng)的可行距離為多長？滑動(dòng)的可行距離為多長？n解：解：n設(shè)某趟匹配發(fā)生設(shè)某趟匹配發(fā)生sipj時(shí)，時(shí)， si應(yīng)該與應(yīng)該與pk（kj）繼續(xù)比較。繼續(xù)比較。 根據(jù)根據(jù) ：p1p2pk-1 si-k+1si-k+2si-1 pj-k+1pj-k+2pj-1 si-k+1

22、si-k+2si-1 可以推出可以推出：“p1p2pk-1” “pj-k+1pj-k+2pj-1”n示意圖如下：示意圖如下：主串主串Si ik kj j模式串模式串T令令next(j)knext(j) 0 當(dāng)當(dāng) j=1Maxk|1kj 且且“p1p2pk-1” “pj-k+1pj-k+2pj-1” 當(dāng)此集合非空當(dāng)此集合非空 1 其他情況其他情況j12345Pjabcacnext(j)01112例例1：計(jì)算如下模式串的：計(jì)算如下模式串的next函數(shù)值。函數(shù)值。n例例2：n計(jì)算如下模式串的計(jì)算如下模式串的next函數(shù)值。函數(shù)值。j12345678Pjabaabcacnext(j)01122312K

23、MP算法（算法算法（算法4.6）int Index_KMP(SString S,SString T,int pos) i=pos;j=1; while (i=S0&jT0) return i -T0; else return 0;/ Index_KMP三、模式串的三、模式串的next函數(shù)值的求解函數(shù)值的求解n由定義知：由定義知：next1=0，n設(shè)設(shè)nextj=kn表明：表明： p1p2pk-1= pj-k+1pj-k+2pj-1 （其中其中1kj, 且不存在且不存在k(kk)滿足上式）滿足上式）n問：問：next j+1= k=? 解：解：情況情況1：若若pK = Pj,即即 p1p

24、2 pk-1 pk= pj-k+1pj-k+2 pj-1 pj 則則nextj+1=nextj+1=k+1；情況情況2：若若pK Pj,即即p1p2 pk-1 pk pj-k+1pj-k+2 pj-1 pj,但但 p1p2 pk-1 pj-k+1pj-k+2 pj-1 ,則應(yīng)將模式向右滑動(dòng)至模式中的則應(yīng)將模式向右滑動(dòng)至模式中的nextk=k個(gè)字符比較，重復(fù)上述過程直個(gè)字符比較，重復(fù)上述過程直至至Pj 和模式中的某個(gè)字符匹配成功或不存在任何和模式中的某個(gè)字符匹配成功或不存在任何k(1kj)滿足滿足 ，則令則令nextj+1=1。n算法算法4.7void get_next(SString T,in

25、t &next ) i=1;next1=0;j=0; while (iT0) if (j=0&Ti=Tj) +i;+j;nextI=j; else j=nextj; / get_nextn 4.4 串的應(yīng)用舉例串的應(yīng)用舉例n文本編輯文本編輯n文本編輯程序是一個(gè)面向用戶的系統(tǒng)服務(wù)程序，廣泛應(yīng)用文本編輯程序是一個(gè)面向用戶的系統(tǒng)服務(wù)程序，廣泛應(yīng)用于文件的起草、錄入、修改、存儲、打印。于文件的起草、錄入、修改、存儲、打印。n在文本編輯器中，處理的對象主要是針對字符串的，所以在文本編輯器中，處理的對象主要是針對字符串的，所以文本編輯器的基本操作，一般包括串的插入、刪除、查找、文本編輯器的基本操作，一般包括串的插入、刪除、查找、替換、存儲及打印等功能。替換、存儲及打印等功能。n建立詞索引表（信息檢索）建立詞索引表（信息檢索）第第4章小結(jié)章小結(jié)s =“a1a2 .an”定長順序存儲結(jié)構(gòu)定長順序存儲結(jié)構(gòu)塊鏈存儲結(jié)構(gòu)塊鏈存儲結(jié)構(gòu)堆存儲結(jié)構(gòu)堆存儲結(jié)構(gòu)串串邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)操作操作(或運(yùn)算或運(yùn)算)本章結(jié)束本章結(jié)束模式匹配算法模式匹配算法若干函數(shù)的實(shí)現(xiàn)若干函數(shù)的實(shí)現(xiàn)BF算法算法古典古典KMP算法算法