CH4串4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法教學目標熟悉串的有關概念，串和線性表的關系。掌握串的各種存儲結(jié)構，比較它們的優(yōu)、缺點，從而學會在何時選用何種存儲結(jié)構為宜。熟練掌握串的七種基本運算，并能利用這些基本運算實現(xiàn)串的其它各種運算。教學難點串運算的實現(xiàn)，特別是順序串上子串定位的運算（又稱串的模式匹配或串匹配）。4.1串類型的定義一、串的基本概念串(String)的定義

s＝“a1a2…an”其中：s為串的名字，串的值ai(1≤i≤n)一般是字母、數(shù)學、標點符號等可屏幕顯示的字符。串的長度n。4.1串類型的定義字符串與一般的線性表的區(qū)別：串的數(shù)據(jù)元素約束為字符集；串的基本操作通常針對串的整體或串的一個部分進行。問題：為何要單獨討論“串”類型？字符串操作比其他數(shù)據(jù)類型更復雜（如拷貝、連接操作）程序設計中，處理對象很多都是串類型。4.1串類型的定義空串和空白串：長度為零的串稱為空串(EmptyString)，它不包含任何字符。空格（白）串:僅由一個或多個空格組成的串稱為空白串(BlankString)子串和主串eg:

A＝“Thisisastring”

B＝“is”特別地：空串是任意串的子串，任意串是其自身的子串。串的相等二、串的抽象數(shù)據(jù)類型定義ADTString{數(shù)據(jù)對象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0}數(shù)據(jù)關系：S＝{<ai-1,ai>|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(S) Replace(&S,T,V)StrCompare(S,T) StrInsert(&S,pos,T)Concat(&T,S1,S2) StrDelete(&S,pos,len)}ADTString三、C語言的串函數(shù)用C處理字符串時，要調(diào)用標準庫函數(shù)#include<string.h>串長度：intstrlen(char*s);串比較：intstrcmp(char*str1,char*str2);串拷貝：char*strcpy(char*str1,char*str2);串連接：char*strcat(char*str1,char*str2);子串T定位：char*strchr(char*str,charch);子串查找：char*strstr(char*s1,char*s2);

……4.2串的表示和實現(xiàn)串的機內(nèi)表示方法：定長順序存儲表示（靜態(tài)數(shù)組結(jié)構）堆分配存儲表示（動態(tài)數(shù)組結(jié)構）串的塊鏈存儲表示順序存儲：鏈式存儲：4.2串的表示和實現(xiàn)4.2.1定長順序存儲表示用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預先給出，故稱為靜態(tài)存儲分配。存儲表示一：#defineMAXSTRLEN255typedefcharSString[MAXSTRLEN+1];SStrings;

串的結(jié)束標志的設置（1）一般可使用一個不會出現(xiàn)在串中的特殊字符在串值的尾部來表示串的結(jié)束。例如：C語言中以字符‘\0’表示串值的終結(jié)。（2）可以不設終結(jié)符

typedefstruct{charch[MAXSTRLEN];intlength;}SString;

（3）還可以用數(shù)組的0號單元存儲串的長度。 算法4.2（串的連接算法）StatusConcat(SString&T,SStringS1,SStringS2){if(S1[0]+S2[0]<=MAXSTRLEN){T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…S1[0]+S2[0]]=S2[1…S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…MAXSTRLEN]=S2[1…MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;} else{ T[0..MAXSTRLEN]=S1[0…MAXSTRLEN]; uncut=FALSE;}returnOK;}算法4.3（取子串）StatusSubString(SString&Sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1…len]=S[pos…pos+len-1]Sub[0]=len;returnOK;}//SubString小結(jié)：1.串的定長順序存儲結(jié)構又稱為串的靜態(tài)存儲結(jié)構，即用一段連續(xù)的存儲單元來存儲串的字符序列。2.串的存儲結(jié)構必須預先定義允許存放串的最大字符個數(shù)，容易造成系統(tǒng)空間浪費或運行出錯。3.串的某些操作（如：串的連接、串的替換等）受到限制。4.2.2堆分配存儲表示特點：仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。思路：利用malloc函數(shù)合理預設串長空間。串的動態(tài)數(shù)組結(jié)構體定義如下：

typedefstruct{char*ch;intlength;}HString;串的賦值算法

StatusStrAssign(HString&T,char*chars){if(T.ch)free(T.ch);for(i=0,c=chars;c;++i,++c);if(!i){T.ch=NULL;T.length=0;}else{T.ch=(char*)malloc(i*sizeof(char));if(!T.ch)exitOVERFLOW;T.ch[0…i-1]=chars[0…i-1];T.length=i;}returnOK;}串的比較算法

intStrCompare(HStringS,HStringT){for(i=0;i<S.length&&i<T.length;++i){if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}串的連接算法StatusConcat(HString&T,HStringS1,HStringS2){if(T.ch)free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char))if(T.ch)exitOVERFLOW;T.ch[0…S1.length-1]=S1.ch[0…S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length…T.length1]=S2.ch[0…S2.length-1];returnOK;}

取子串算法SubString(HString&Sub,HStringS,intpos,intlen){if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);if(!len){Sub.ch=NULL;Sub.length=0;}else{Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0…len-1]=S[pos-1…pos+len-2];Sub.length=len;}returnOK;}4.2.3串的鏈式存儲結(jié)構(1)單字符結(jié)點鏈

typedefstructnode{chardata;structnode*next;}*LString;

A

B

C

I

^head特點：一個鏈串由頭指針唯一確定。這種結(jié)構便于進行插入和刪除運算，但存儲空間利用率太低。（2）串的塊鏈結(jié)構引入目的：提高存儲密度headABCDEFGHI###NULL存儲表示的定義：#defineCHUNKSIZE80typedefstructnode{chardata[CHUNKSIZE];structnode*next;}*LString;4.3串的模式匹配算法一、基本概念模式匹配（子串定位）設有主串S和子串T（將S稱為目標串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個與子串T相等的子串，則返回T的第一個字符在主串中的位置，否則返回-1。算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）算法種類BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法二、Brute-Force算法1.算法的設計思想：將主串S的第一個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符起，重新與T第一個字符比較。直到:主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值–1。2.下面以定長的順序串類型作為存儲結(jié)構，給出具體的串匹配算法。intindex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0])if(s[i]==T[j]){++i;++j;}else{i=i－j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}顯然，該算法在最壞情況下的時間復雜度為O((n-m)×m)。3.BF算法的時間復雜度若n為主串長度，m為子串長度，最好情況：一配就中！只比較了m次。最壞情況：則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n－m＋1)×m。4.BF（Brute-Force）算法的特點：

簡單，易于理解，效率較高；算法的時間復雜度O((n－m)×m)。(其中n,m分別為主串和模式串的長度）

實際運行中，時間近似于O（n＋m)。注意：當遇到一次si≠tj,主串要回退到i－j+2的位置，而模式串要回到第一個位置（即j＝1的位置)；但當一次比較出現(xiàn)si≠tj時，則應該有：

"si-j+1si-j+2……si-1"="t1t2……tj-2tj-1"改進：每當一趟匹配過程出現(xiàn)si≠tj時，主串指示器i不用回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式串向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。4.3.2模式匹配的改進算法（KMP算法）一、分析與示例1趟ababcabcacbababc2趟ababcabcacbababcac3趟ababcabcacbababcac二、討論一般情況設:主串S="s1s2……si……sn"，

模式串T="p1p2…pj…pm"問：當某趟比較發(fā)生“失配”（即si≠pj）時，模式串應該向“右”滑動的可行距離為多長？解：設某趟匹配發(fā)生si≠pj時，

si應該與pk（k＜j）繼續(xù)比較。根據(jù)："p1p2…pk-1"＝"si-k+1si-k+2…si-1"

"pj-k+1pj-k+2…pj-1"＝"si-k+1si-k+2…si-1"可以推出：“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”示意圖如下：主串Sikj模式串T令next(j)＝knext(j)＝

0

當j=1Max{k|1＜k＜j且“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”}

當此集合非空

1

其他情況j12345Pjabcacnext(j)01112例1：計算如下模式串的next函數(shù)值。例2：計算如下模式串的next函數(shù)值。j12345678Pjabaabcacnext(j)01122312KMP算法（算法4.6）intIndex_KMP(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j=0||S[i]==T[j]){++i,;++j;}elsej=next[j];}if(j>T[0])returni-T[0];elsereturn0;}//Index_KMP三、模式串的next函數(shù)值的求解由定義知：next[1]=0，設next[j]=k表明："p1p2…pk-1"="pj-k+1pj-k+2…pj-1

" （其中1＜k＜j,且不存在k’(k’＞k)滿足上式）問：next[j+1]=k’=?

解：情況1：若pK=

Pj,即"p1p2…pk-1pk"="pj-k+1pj-k+2…pj-1pj"②則next[j+1]=next[j]+1=k+1；情況2：若pK≠Pj,即"p1p2…pk-1pk"≠"pj-k+1pj-k+2…pj-1pj",但"p1p2…pk-1"≠"pj-k+1pj-k+2…pj-1

",則應將模式向右滑動至模式中的next[k]=k’個字符比較，重復上述過程直至Pj

和模式中的某個字符匹配成功或不存在任何k’(1<k’<j)滿足②，則令next[j+1]=1。算法4.7voidget_next(SStringT,int&next[]){i=1;next[1]=0;j=0;while(i<T[0]){if(j==0&&T[i]==T[j]){++i;++j;next[I]=j;}elsej=next[j];}}//get_next

4.4串的應用舉例文本編輯文本編輯程序是一個面向用戶的系