《數(shù)據(jù)結(jié)構(gòu)》課件-第4章 串

數(shù)據(jù)構(gòu)C語(yǔ)言描述結(jié)第4章

串知識(shí)目標(biāo)：熟悉串的十種基本操作的定義，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的其它各種操作熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法理解串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法理解串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)理解串的樸素模式匹配算法（BF算法）技能目標(biāo)：能應(yīng)用串的各種基本操作和模式匹配算法解決實(shí)際問(wèn)題第4章串4.1串的邏輯結(jié)構(gòu)4.2串的存儲(chǔ)結(jié)構(gòu)4.3串的模式匹配4.0案例導(dǎo)引4.4案例實(shí)現(xiàn)——文本文件中單詞的檢索和計(jì)數(shù)4.0案例導(dǎo)引案例：文本文件單詞的檢索和計(jì)數(shù)編程建立一個(gè)文本文件，每個(gè)單詞都不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫(xiě)。要求統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)，檢索輸出某個(gè)單詞出現(xiàn)在文本中的行號(hào)、在該行中出現(xiàn)的次數(shù)以及位置。案例探析：本案例需要選擇合適的結(jié)構(gòu)完成字符串的建立，實(shí)現(xiàn)串的基本操作，利用樸素模式匹配算法實(shí)現(xiàn)對(duì)文本文件中單詞的檢索和計(jì)數(shù)。第4章串線性表——具有相同類型的數(shù)據(jù)元素的有限序列?！獌H在表的一端進(jìn)行插入和刪除操作隊(duì)列——在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作限制插入、刪除位置第4章串線性表——具有相同類型的數(shù)據(jù)元素的有限序列（多維）數(shù)組——線性表中的數(shù)據(jù)元素可以是線性表串——零個(gè)或多個(gè)字符組成的有限序列將元素類型擴(kuò)充為線性表將元素類型限制為字符4.1串的邏輯結(jié)構(gòu)串(string)：零個(gè)或多個(gè)字符組成的有限序列。串長(zhǎng)度：串中所包含的字符個(gè)數(shù)?？沾洪L(zhǎng)度為0的串，記為""。由一個(gè)或多個(gè)稱為空格的特殊字符組成的串，稱為空格串(Blank)，其長(zhǎng)度為串中空格字符的個(gè)數(shù)。非空串通常記為：

S="s1

s2……sn"串名定界符串值4.1串的邏輯結(jié)構(gòu)S1=“ab23kj” S2=“0012” S3=“” S4=“??”

——長(zhǎng)度為6的串；——長(zhǎng)度為4的串；——空串，長(zhǎng)度為0；——含兩個(gè)空格的空格串。4.1串的邏輯結(jié)構(gòu)子串：串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串。子串的位置：子串的第一個(gè)字符在主串中的序號(hào)。例如，假設(shè)A、B、C、D為如下的四個(gè)串：A=“SHANGHAI” B=“SHANGHAI”C=“SHANG” D=“HAI”串長(zhǎng)？子串的位置？4.1串的邏輯結(jié)構(gòu)串的數(shù)據(jù)對(duì)象約束為某個(gè)字符集。微機(jī)上常用的字符集是標(biāo)準(zhǔn)ASCII碼，由7位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示128個(gè)字符。擴(kuò)展ASCII碼由8位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示256個(gè)字符，足夠表示英語(yǔ)和一些特殊符號(hào)，但無(wú)法滿足國(guó)際需要。Unicode由16位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示216個(gè)字符，能夠表示世界上所有語(yǔ)言的所有字符，包括亞洲國(guó)家的表意字符。為了保持兼容性，Unicode字符集中的前256個(gè)字符與擴(kuò)展ASCII碼完全相同。串的抽象數(shù)據(jù)類型ADTString{

數(shù)據(jù)對(duì)象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3…,n}

基本操作：

StrAssign(＆s,chars)：將串chars的串值賦給串變量s

StrCopy(＆t,s)：由串s復(fù)制得到串t

StrEmpty(s)：判斷串s是否為空串，若是返回TRUE，否則返回FALSE

StrLength(s)：返回串s的長(zhǎng)度

StrCompare(s,t)：比較串s和t的大小。若s>t，返回正整數(shù)；若s==t，返回0；若s<t，則返回負(fù)整數(shù)串的抽象數(shù)據(jù)類型

ClearString(＆s)：將s清為空串

StrConcat(s1,s2,＆t)：由t返回將串s2連接在串s1的末尾組成的新串

SubStr(s,pos,len)：返回串s中從第pos個(gè)字符開(kāi)始長(zhǎng)度為len的子串

StrIndex(s,t,pos)：返回串t在串s的第pos個(gè)字符之后第一次出現(xiàn)的位置，若t不是s的子串，則返回0

StrReplace(＆s,t,v)：用串v替換串s中出現(xiàn)的所有與串t相等的不重疊子串

StrInsert(＆s,pos,t)：在串s的第pos個(gè)字符之前插入串t

StrDelete(＆s,pos,len)：刪除串s中從第pos個(gè)字符開(kāi)始長(zhǎng)度為len的子串

Destroystring(＆s)：銷毀串s}ADTString串的基本操作在線性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象，如：在線性表中查找某個(gè)元素、求取某個(gè)元素、在某個(gè)位置上插入一個(gè)元素和刪除一個(gè)元素等；而在串的基本操作中，通常以“串的整體”作為操作對(duì)象。串的基本操作如下：（1）串賦值：StrAssign(&s1,s2)操作條件：s1是一個(gè)串變量，s2或者是一個(gè)串常量，或者是一個(gè)串變量(通常s2是一個(gè)串常量時(shí)稱為串賦值，是一個(gè)串變量時(shí)稱為串拷貝)。操作結(jié)果：將s2的串值賦值給s1，s1原來(lái)的值被覆蓋掉。

例：StrAssign(s,“abcd”);例：t=“abcde”; StrAssign(s,t);串的基本操作（2）求串長(zhǎng)：StrLength(s)操作條件：串s存在。操作結(jié)果：求出串s的長(zhǎng)度。（3）聯(lián)接運(yùn)算：StrConcat(s1,s2,&s)或StrConcat(&s1,s2)操作條件：串s1，s2存在。操作結(jié)果：兩個(gè)串的聯(lián)接就是將一個(gè)串的串值緊接著放在另一個(gè)串的后面，聯(lián)接成一個(gè)串。前者是產(chǎn)生新串s，s1和s2不改變；后者是在s1的后面聯(lián)接s2的串值，s1改變，s2不改變。例：t="abcde“; StrLength(t);例：s1="bei"，s2="jing“; StrConcat(s1,s2,&s);

StrConcat(&s1,s2);s="beijing"，s1="bei"，s2="jing"s1="beijing"，s2="jing"

（5）串比較運(yùn)算：StrCompare(s1,s2)操作條件：串s1和s2存在。操作結(jié)果：

若s1==s2，操作返回值為0；

若s1<s2，返回值<0；

若s1>s2，返回值>0

(兩個(gè)字符串自左向右逐個(gè)字符按ASCII值大小相比較)。串的基本操作（4）求子串：SubStr(s,pos,len)操作條件：串s存在，1≤pos≤StrLength(s)，0≤len≤StrLength(s)-pos+1。操作結(jié)果：返回從串s的第pos個(gè)字符開(kāi)始的長(zhǎng)度為len的子串。len=0得到的是空串。例：SubStr("abcdefghi",3,4)=例：StrCompare("bei","bei") StrCompare("bei","dei") StrCompare("cat","case")"cdef"=0<0>0串的基本操作（6）串定位：StrIndex(s,t,pos)操作條件：串s和t存在。操作結(jié)果：若主串s中存在和串t值相同的子串,則返回t在主串s中第pos個(gè)字符之后第一次出現(xiàn)的位置，pos如果省略，默認(rèn)為1，否則返回值為-1。例：StrIndex("abebebda","be") StrIndex("abcdebda","ba")例：s="chater";t="rac";pos=4; StrInsert(s,pos,t);s="character"（7）串插入操作：StrInsert(&s,pos,t)操作條件：串s和t存在，且1≤pos≤StrLength(s)+1。操作結(jié)果：將串t插入到串s的第pos個(gè)字符位置之前，s的串值發(fā)生改變。=2=-1串的基本操作（8）串刪除操作：StrDelete(&s,pos,len)操作條件：串s存在，且1≤pos≤StrLength(s)，0≤len≤StrLength(s)-pos+1。操作結(jié)果：刪除串s中從第pos個(gè)字符開(kāi)始的長(zhǎng)度為len的子串，s的串值改變。（9）串替換操作：StrReplace(&s,t,r)操作條件：串s，t和r存在，且t不為空。操作結(jié)果：用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。例：s=“Microsoft”;pos=4;len=5; StrDelete(s,pos,len)例：s="abcacabcaca";t="abca";r="x";

StrReplace(&s,t,r);s="Mict"s="xcxca"串的基本操作（10）判相等操作：StrEqual(s,t)操作條件：串s和t存在。操作結(jié)果：若s與t的值相等則運(yùn)算結(jié)果為1，否則為0。通常將前5個(gè)基本操作稱為最小操作集，其他操作均可在最小操作子集上實(shí)現(xiàn)。例如：可利用判等、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)StrIndex(s,t,pos)。在主串s中取從第i（i的初值為pos）個(gè)字符起，長(zhǎng)度與串t相等的子串同串t比較，若相等，則函數(shù)返回值為i，否則i值增1，直至串s中從第i個(gè)字符起直到串尾的子串長(zhǎng)度小于串t的長(zhǎng)度為止。

例：s="ab";t="abzcd";r="ab";

StrEqual(s,t)=0

StrEqual(s,r)=1串的基本操作【算法4-1】利用最小操作子集實(shí)現(xiàn)定位函數(shù)#defineMaxLen<最大串長(zhǎng)>;typedefstruct{charstr[MaxLen];intcurlen;}SString;intStrIndex(SStrings,SStringt,intpos){if(pos>0){SStringsub;n=StrLength(s);m=StrLength(t);i=pos;while(i<=n-m+1){sub=SubStr(s,i,m);if(StrCompare(sub,t)!=0)++i;elsereturni;}}return-1;}

4.2串的存儲(chǔ)結(jié)構(gòu)串的順序存儲(chǔ)結(jié)構(gòu)被稱為順序串。串的順序存儲(chǔ)有兩種方法：在一個(gè)存儲(chǔ)單元中存放多個(gè)字符，稱為緊縮格式。一個(gè)存儲(chǔ)單元中只存放一個(gè)字符，即所需的存儲(chǔ)

單元個(gè)數(shù)就是串的長(zhǎng)度，稱為非緊縮格式。DATASYSTEM非緊縮格式DATA空閑SYSTEM所需的存儲(chǔ)單元個(gè)數(shù)就是串長(zhǎng)串的定長(zhǎng)順序存儲(chǔ)一個(gè)單元串的定長(zhǎng)順序存儲(chǔ)方案1：用一個(gè)變量來(lái)表示串的實(shí)際長(zhǎng)度。串的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)組來(lái)存儲(chǔ)串中的字符序列。那么如何表示串的長(zhǎng)度？0123456……MaxLen-1

abcdefg7空閑串的定長(zhǎng)順序存儲(chǔ)01234567……MaxLen-1

abcdefg\0空閑方案2：在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。方案1：用一個(gè)變量來(lái)表示串的實(shí)際長(zhǎng)度。串的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)組來(lái)存儲(chǔ)串中的字符序列。那么如何表示串的長(zhǎng)度？串的定長(zhǎng)順序存儲(chǔ)方案3：用數(shù)組的0號(hào)單元存放串的長(zhǎng)度，從1號(hào)單元開(kāi)始存放串值。01234567……MaxLen-1

7

abcdefg空閑方案2：在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。方案1：用一個(gè)變量來(lái)表示串的實(shí)際長(zhǎng)度。串的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)組來(lái)存儲(chǔ)串中的字符序列。那么如何表示串的長(zhǎng)度？7串的定長(zhǎng)順序存儲(chǔ)#defineMaxLen<最大串長(zhǎng)>

／*定義能處理的最大的串長(zhǎng)度*／typedefstruct{charstr[MaxLen];

／*定義可容納MaxLen個(gè)字符的字符數(shù)組*／intcurlen;／*定義當(dāng)前實(shí)際串長(zhǎng)度*／}SString;順序串的類型定義描述順序串的實(shí)現(xiàn)——判相等運(yùn)算StrEqual(s,t)intStrEqual(SStrings,SStringt)／*判串s和串t是否相等。相等，返回l；否則返回0*／{inti,j;if(s.curlen==t.curlen)／*首先判斷兩個(gè)串的長(zhǎng)度是否相等*／{for(i=0;i<s.curlen;i++)／*長(zhǎng)度相等則繼續(xù)比較對(duì)應(yīng)位置的每個(gè)字符是否相等*／

{if(s.str[i]==t.str[i])j=1;else{j=0;

break;}／*若對(duì)應(yīng)位置字符出現(xiàn)不等，終止比較*／}}elsej=0;／*長(zhǎng)度不相等則判定兩個(gè)串不相等，返回0*／returnj;}【算法4-2】順序串的實(shí)現(xiàn)——聯(lián)接運(yùn)算StrConcat(s,t,&ch)串的聯(lián)接運(yùn)算是將兩個(gè)串s和t的串值分別傳送到新串ch的相應(yīng)位置，超過(guò)MaxLen的部分截去。其運(yùn)算結(jié)果可能有3種情況：s.curlen+t.curlen≤MaxLen，得到的新串ch是正確的結(jié)果；s.curlen+t.curlen>MaxLen而s.curlen<MaxLen，則將t的一部分截去，得到的新串ch中包含s和t的一個(gè)子串；s.curlen>=MaxLen，則得到的新串ch中只含有s一個(gè)子串。voidStrConcat(SStrings,SStringt,SString&ch)

／*用ch返回由s和t聯(lián)接而成的新串*／{inti;

if(s.curlen+t.curlen<=MaxLen)／*未截?cái)?／

{ch.curlen=s.curlen+t.curlen;／*計(jì)算新串的串長(zhǎng)度*／for(i=0;i<s.curlen;i++) ch.str[i]=s.str[i];for(i=0;i<t.curlen;i++) ch.str[s.curlen+i]=t.str[i];

ch.str[ch.curlen]=’\0’;／*在新串的最后設(shè)置串的結(jié)束符*／

}【算法4-3】順序串的實(shí)現(xiàn)——聯(lián)接運(yùn)算StrConcat(s,t,&ch)

elseif(s.curlen<MaxLen)/*截?cái)?／

{ch.curlen=MaxLen;/*計(jì)算新串的串長(zhǎng)度*／for(i=0;i<s.curlen;i++) ch.str[i]=s.str[i];for(i=0;

i<MaxLen-s.curlen;i++) ch.str[s.curlen+i]=t.str[i];

ch.str[ch.curlen]=’\0’;/*在新串的最后設(shè)置串的結(jié)束符*／

}else/*截?cái)啵瑑H取s的一個(gè)子串*／

{ch.curlen=MaxLen;/*計(jì)算新串的串長(zhǎng)度*／

for(i=0;i<MaxLen;i++) ch.str[i]=s.str[i];

ch.str[ch.curlen]=’\0’;／*在新串的最后設(shè)置串的結(jié)束符*／

}}【算法4-3】順序串的實(shí)現(xiàn)——聯(lián)接運(yùn)算StrConcat(s,t,&ch)順序串的實(shí)現(xiàn)——求子串運(yùn)算SubStr(s,pos,len)SStringSubStr(SStrings,intpos,intlen){inti,j=0;SStringch;

if((pos>=1&&pos<=StrLength(s))&&(len>=0&&len<=StrLength(s)-pos+1)){for(i=pos-1;i<len+pos-1;i++)

ch.str[j++]=s.str[i];

ch.curlen=len;ch.str[ch.curlen]='\0';}elseprintf(“\nerror!\n”);／*參數(shù)不正確時(shí)返回錯(cuò)誤信息*／returnch;}【算法4-4】順序串的實(shí)現(xiàn)串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)適用于求串長(zhǎng)、求子串等運(yùn)算。但這種存儲(chǔ)結(jié)構(gòu)有兩個(gè)缺點(diǎn)：一是需要預(yù)先定義一個(gè)串允許的最大長(zhǎng)度，如果定義的空間過(guò)大，則會(huì)造成空間浪費(fèi)；二是由于限定了串的最大長(zhǎng)度，則會(huì)限制串的某些運(yùn)算，如聯(lián)接、置換運(yùn)算等。串的堆分配存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)方法：提供一個(gè)足夠大的連續(xù)存儲(chǔ)空間，作為串的可利用空間，來(lái)存儲(chǔ)各串的串值。每當(dāng)建立一個(gè)新串時(shí)，系統(tǒng)就從這個(gè)可利用空間中劃分出一個(gè)大小和新串長(zhǎng)度相等的空間給新串，若分配成功則返回一個(gè)指向起始地址的指針。可使用C語(yǔ)言中的malloc()和free()函數(shù)來(lái)管理可利用空間。雖然這種存儲(chǔ)表示仍以一組地址連續(xù)的存儲(chǔ)單元存放串值，但它屬于一種動(dòng)態(tài)分配方式，所以也可看做一種動(dòng)態(tài)存儲(chǔ)分配的順序表。typedefstruct{intlen;/*len存放串長(zhǎng)*/char*ch;/*ch存放串的首地址，若是空串，則ch的值為NULL*/}HString;串的堆分配存儲(chǔ)結(jié)構(gòu)串的堆分配存儲(chǔ)結(jié)構(gòu)圖4-1串的堆分配存儲(chǔ)結(jié)構(gòu)示例串的賦值運(yùn)算：StrAssign(&s1,s2)intStrAsssign(HString&t,char*chars)/*生成一個(gè)其值等于串常量chars的串t*/{inti,k;char*c;／*c為指向字符的指針變量*／

if(t.ch)free(t.ch);／*釋放t原有的空間*／

for(i=0,c=chars;c;++i,++c);

／*求chars的長(zhǎng)度*／if(!i)／*若chars的長(zhǎng)度為0，則生成空串t*／

{t.ch=NULL;t.len=0;}【算法4-5】串的賦值運(yùn)算：StrAssign(&s1,s2)else／*chars的長(zhǎng)度大于0*／

{if(!(t.ch=(char*)malloc(i*sizeof(char))))return0;／*空間申請(qǐng)失敗，返回失敗標(biāo)志*／

for(k=0;k<=i-1;k++)／*逐個(gè)復(fù)制元素*／

t.ch[k]=chars[k];t.len=i;／*保存串的長(zhǎng)度*／

return1;／*成功*／

}}【算法4-5】串的聯(lián)接運(yùn)算：StrConcat(s1,s2,&t)intStrConcat(HStrings1,HStrings2,Hstring＆t)／*用t返回由s1和s2聯(lián)接成的新串*／{intk，j=0;

if(t.ch)free(t.ch);

if(!(t.ch=(char*)malloc((s1.len+s2.len)*sizeof(char))))

return0;

for(k=0;k<=s1.len-1;k++)t.ch[k]=s1.ch[k];／*復(fù)制串s1到串t*／

t.len=s1.len+s2.len;／*串t的長(zhǎng)度等于串s1和串s2長(zhǎng)度之和*／

for(k=s1.len;k<=t.len-1;k++)／*復(fù)制串s2到t，s2接在s1之后*／

{t.ch[k]=s2.ch[j];

j++;

}return1;}【算法4-6】堆分配存儲(chǔ)結(jié)構(gòu)的串既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)（簡(jiǎn)單、處理方便），操作中對(duì)串長(zhǎng)又沒(méi)有任何限制，非常靈活，因此在串處理中經(jīng)常被采用。串的塊鏈存儲(chǔ)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)被稱為鏈串。使用鏈表存儲(chǔ)串值時(shí)，每個(gè)結(jié)點(diǎn)可以存放一個(gè)字符，也可以存放多個(gè)字符，結(jié)點(diǎn)中存放字符的個(gè)數(shù)稱為“結(jié)點(diǎn)大小”。串的塊鏈存儲(chǔ)#defineCHUNKSIZE80/*可由用戶定義的塊大小*/typedefstruct/*結(jié)點(diǎn)結(jié)構(gòu)*/{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct/*串的鏈表結(jié)構(gòu)*/{Chunk*head,*tail;/*串的頭和尾指針*/intcurlen;/*串的當(dāng)前長(zhǎng)度*/}LString;鏈串的類型定義描述鏈串的基本操作——求串長(zhǎng)度算法intStrLength(char*s){ char*p=s; intlen=0; while(*p!='\0') {len++; p++; } returnlen;}鏈串的基本操作——串連接算法intStrConcat1(s1,s2,s)chars1[],s2[],s[];{inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;/*s長(zhǎng)度不夠*/

j=0;while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}

j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}s1=〃student〃

s2=〃teacher〃s=〃studentteacher〃鏈串的基本操作——求子串算法intStrSub(char*t,char*s,inti,intlen)/*用t返回串s中第個(gè)i字符開(kāi)始的長(zhǎng)度為len的子串1≤i≤串長(zhǎng)*/{intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf(＂參數(shù)不對(duì)＂);return0;}for(j=0;j<len;j++)

t[j]=s[i+j-1];t[j]=’\0’;return1;}鏈串的基本操作——串比較算法串的比較：通過(guò)組成串的字符之間的比較來(lái)進(jìn)行的。給定兩個(gè)串：X="x1x2…xn"和Y="y1y2…ym"，則：1.當(dāng)n=m且x1=y1，…，xn=ym時(shí)，稱X=Y；2.當(dāng)下列條件之一成立時(shí)，稱X＜Y：⑴n＜m且xi=yi（1≤i≤n）；⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。例：S1="ab12cd"，S2="ab12"，S3="ab13"鏈串的基本操作——串比較算法intStrComp(char*s1,char*s2){inti=0;while(s1[i]==s2[i]&&s1[i]!=’\0’)i++;return(s1[i]-s2[i]);}4.3串的模式匹配（串的定位）模式匹配：給定主串S=“s1s2…sn”和模式T=“t1t2…tm”，在主串S中尋找子串T的過(guò)程稱為模式匹配。如果匹配成功，返回T在S中的位置；如果匹配失敗，返回0。算法的一次執(zhí)行時(shí)間不容忽視：?jiǎn)栴}規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配；算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。模式匹配問(wèn)題有什么特點(diǎn)？4.3串的模式匹配（串的定位）在下面的討論中，為了和C語(yǔ)言中的字符數(shù)組保持一致，采用第2種順序存儲(chǔ)方法，即從數(shù)組下標(biāo)0開(kāi)始存放字符，并且在串尾存儲(chǔ)終結(jié)符'\0'。01234567……MaxLen-1abcdefg\0空閑模式匹配——BF算法（樸素的模式匹配算法）基本思想：從主串（目標(biāo)串）S的第一個(gè)字符開(kāi)始和模式串T的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串S的第二個(gè)字符開(kāi)始和模式串T的第一個(gè)字符進(jìn)行比較，重復(fù)上述過(guò)程，直到T中的字符全部比較完畢，則說(shuō)明本趟匹配成功；或S中字符全部比較完，則說(shuō)明匹配失敗。模式匹配——BF算法（樸素的模式匹配算法）

si……主串S模式T

tjji…回溯i回溯j本趟匹配開(kāi)始位置模式匹配——BF算法（樸素的模式匹配算法）si……主串S模式Tji…

tj例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）ababcabcacbabi=2，j=2失??；i回溯到1，j回溯到0ijijij第1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）jii=2，j=2失敗；i回溯到1，j回溯到0ababcabcacbababcac

第1趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）i=1，j=0失敗i回溯到2，j回溯到0ijababcabcacbababcac

第2趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）iji=1，j=0失敗i回溯到2，j回溯到0ababcabcacbababcac

第2趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）ababcabcacbabi=6，j=4失敗i回溯到3，j回溯到0abcacijijijijij第3趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）iji=6，j=4失敗i回溯到3，j回溯到0ababcabcacbababcac第3趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）i=3，j=0失敗i回溯到4，j回溯到0ijababcabcacbababcac第4趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）iji=3，j=0失敗i回溯到4，j回溯到0ababcabcacbababcac第4趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）i=4，j=0失敗i回溯到5，j回溯到0abcacijababcabcacbab第5趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）iji=4，j=0失敗i回溯到5，j回溯到0abcacababcabcacbab第5趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（樸素的模式匹配算法）abcaci=10，j=5，T中全部字符都比較完畢，匹配成功ijijijijijababcabcacbab第6趟在串S和串T中設(shè)比較的起始下標(biāo)i和j；循環(huán)直到S或T的所有字符均比較完畢2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個(gè)字符；2.2否則，將i和j回溯，準(zhǔn)備下一趟比較；如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標(biāo)；否則，匹配失敗，返回0；模式匹配——BF算法（樸素的模式匹配算法）intIndex_BF(SStrings,SStringt){inti,j;i=0;/*指向串s的第1個(gè)字符*/j=0;/*指向串t的第1個(gè)字符*/while((i<s.curlen-t.curlen))&&(j<t.curlen)){if(s.str[i]==t.str[j]){++i