數(shù)據(jù)結(jié)構(gòu)第4章串

計(jì)算機(jī)學(xué)院第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

可表示為：（a1,a2,……,an）線性結(jié)構(gòu)計(jì)算機(jī)學(xué)院串比較，strcmp(chars1,chars2)串復(fù)制，strcpy(charto,charfrom)串連接，strcat(charto,charfrom)求串長(zhǎng)，strlen(chars)

……調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù)#include<string.h>補(bǔ)充：C語(yǔ)言中常用的串運(yùn)算計(jì)算機(jī)學(xué)院第4章串4.1串類型的定義4.2串的表示和實(shí)現(xiàn)4.3串的模式匹配算法

4.3.1求子串位置的定位函數(shù)

教學(xué)內(nèi)容計(jì)算機(jī)學(xué)院1.理解串的基本操作的定義，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的其它各種操作的方法；2.了解在串的順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的各種操作的方法；3.掌握串的模式匹配的算法4.了解串操作的應(yīng)用方法和特點(diǎn)

教學(xué)目標(biāo)計(jì)算機(jī)學(xué)院4.1串類型的定義串(String)----零個(gè)或多個(gè)字符組成的有限序列串名串值串長(zhǎng)n空串n=0計(jì)算機(jī)學(xué)院a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串計(jì)算機(jī)學(xué)院數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:基本操作:(1)

StrAssign(&T,chars)//串賦值(2)StrCompare(S,T)//串比較(3)StrLength(S)//求串長(zhǎng)(4)Concat(&T,S1,S2)//串聯(lián)ADTString{串的抽象數(shù)據(jù)類型計(jì)算機(jī)學(xué)院

(5)SubString(&Sub,S,pos,len)//求子串

(6)StrCopy(&T,S)//串拷貝

(7)StrEmpty(S)//串判空

(8)ClearString(&S)//清空串

(9)Index(S,T,pos)//子串的位置

(11)Replace(&S,T,V)//串替換

(12)StrInsert(&S,pos,T)//子串插入

(12)StrDelete(&S,pos,len)//子串刪除

(13)DestroyString(&S)//串銷毀}ADTString計(jì)算機(jī)學(xué)院4.2串的表示和實(shí)現(xiàn)定長(zhǎng)順序表示堆分配存儲(chǔ)表示串的塊鏈存儲(chǔ)表示計(jì)算機(jī)學(xué)院定長(zhǎng)順序表示#defineMAXSTRLEN255//用戶可在255以內(nèi)定義最大串長(zhǎng)typedefunsignedcharSString[MAXSTRLEN+1];//0號(hào)單元存放串長(zhǎng)計(jì)算機(jī)學(xué)院串連接的實(shí)現(xiàn)（a)S1[0]+S2[0]MAXSTRLEN計(jì)算機(jī)學(xué)院串連接的實(shí)現(xiàn)（b)S1[0]<MAXSTRLEN而

S1[0]+S2[0]>MAXSTRLEN計(jì)算機(jī)學(xué)院串連接的實(shí)現(xiàn)（c)S1[0]=MAXSTRLEN

計(jì)算機(jī)學(xué)院串連接（算法4.2）--了解計(jì)算機(jī)學(xué)院求子串計(jì)算機(jī)學(xué)院求子串（算法4.3）--了解計(jì)算機(jī)學(xué)院typedefstruct{char*ch;//若串非空,則按串長(zhǎng)分配存儲(chǔ)區(qū),//否則ch為NULLintlength;//串長(zhǎng)度}HString;

堆分配存儲(chǔ)表示相關(guān)算法（75－77頁(yè)）--了解計(jì)算機(jī)學(xué)院串的塊鏈存儲(chǔ)表示計(jì)算機(jī)學(xué)院#defineCHUNKSIZE80//可由用戶定義的塊大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的頭指針和尾指針

intcurlen;//串的當(dāng)前長(zhǎng)度}LString;

串的塊鏈存儲(chǔ)表示計(jì)算機(jī)學(xué)院可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)優(yōu)點(diǎn)：操作方便缺點(diǎn)：存儲(chǔ)密度較低實(shí)際分配的存儲(chǔ)位串值所占的存儲(chǔ)位存儲(chǔ)密度=串的塊鏈存儲(chǔ)表示計(jì)算機(jī)學(xué)院4.3串的模式匹配算法

算法目的：BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點(diǎn)：速度快）算法種類：確定主串中所含子串第一次出現(xiàn)的位置（定位）即如何實(shí)現(xiàn)教材P71Index(S,T,pos)函數(shù)計(jì)算機(jī)學(xué)院

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯BF算法設(shè)計(jì)思想計(jì)算機(jī)學(xué)院將主串的第pos個(gè)字符和模式的第一個(gè)字符比較，若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一個(gè)字符比較。直到主串的一個(gè)連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值0BF算法設(shè)計(jì)思想Index(S,T,pos)計(jì)算機(jī)學(xué)院例：S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，pos=1，

求：串T在串S中第pos個(gè)字符之后的位置圖4.3，可利用演示系統(tǒng)看BF算法執(zhí)行過(guò)程BF算法示例計(jì)算機(jī)學(xué)院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;}BF算法描述（算法4.5）計(jì)算機(jī)學(xué)院若n為主串長(zhǎng)度，m為子串長(zhǎng)度，最壞情況是BF算法時(shí)間復(fù)雜度主串前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位各比較了m次最后m位也各比較了1次總次數(shù)為：(n-m)*m+m＝(n-m+1)*m若m<<n，則算法復(fù)雜度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=1計(jì)算機(jī)學(xué)院KMP（KnuthMorrisPratt）算法/~knuth/《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第1卷基本算法》

98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第2卷半數(shù)值算法》98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第3卷排序與查找》98元KMP算法（特點(diǎn)：速度快）①KMP算法設(shè)計(jì)思想②KMP算法的推導(dǎo)過(guò)程③KMP算法的實(shí)現(xiàn)

（關(guān)鍵技術(shù):計(jì)算next[j]）④KMP算法的時(shí)間復(fù)雜度能否利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動(dòng)速度？能！而且主串S的指針i不必回溯！可提速到O(n+m)！例：①KMP算法設(shè)計(jì)思想：(參見(jiàn)教材P80-84）S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)bca

c’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)

bcac’Index_kmp的返回值應(yīng)為i=6需要討論兩個(gè)問(wèn)題：①如何“記憶”部分匹配結(jié)果？②如何由“記憶”結(jié)果計(jì)算出主串S第i個(gè)字符應(yīng)該與模式T中哪個(gè)字符再比較？即確定模式T中的新比較起點(diǎn)k.iiikk

a

b

aa

b

c②KMP算法的推導(dǎo)過(guò)程：（見(jiàn)教材P81）抓住部分匹配結(jié)果的兩個(gè)特征：兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’注意：j為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn)k，僅剩一個(gè)未知數(shù)k，理論上已可解，且k僅與模式串T有關(guān)！則S前i-1～i-(k-1)位＝T的j-1～j-(k-1)位即(4-3）式含義S=‘a(chǎn)babca

b

cacbab’T=‘a(chǎn)

b

cac’ik則T的k-1～1位＝S前i-1～i-(k-1)位

即(4-2）式含義ikjS=‘a(chǎn)babca

bcacbab’T=‘a(chǎn)bca

c’剛才肯定是在S的i處和T的第j字符處失配設(shè)目前應(yīng)與T的第k字符開(kāi)始比較②KMP算法的推導(dǎo)過(guò)程(續(xù)）：根據(jù)模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’和已知的當(dāng)前失配位置j，可以歸納出計(jì)算新起點(diǎn)k的表達(dá)式。令k=next[j]，則next[j]＝0當(dāng)j＝1時(shí)max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況討論：①next[j]有何意義？一旦失配，應(yīng)從模式串T中第next[j]個(gè)字符開(kāi)始與S的失配點(diǎn)i重新匹配!②next[j]怎么求？后面會(huì)舉例（參見(jiàn)教材P81）第一步，先把模式T所有可能的失配點(diǎn)j所對(duì)應(yīng)的next[j]計(jì)算出來(lái)；第二步：執(zhí)行定位函數(shù)index_kmp（與BF算法模塊非常相似）③KMP算法的實(shí)現(xiàn)—即Index()操作的實(shí)現(xiàn)（見(jiàn)教材P82）

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}//不失配則繼續(xù)比較后續(xù)字符

else{j=next[j];}//S的i指針不回溯，從T的k位置開(kāi)始匹配

}if(j>T[0])returni-T[0];//子串結(jié)束，說(shuō)明匹配成功

elsereturn0;}//Index_KMP怎樣計(jì)算模式T所有可能的失配點(diǎn)j所對(duì)應(yīng)的next[j]？例：模式串T：abaabcac

可能失配位

j：12345678新匹配位next[j]:next[j]＝0當(dāng)j＝1時(shí)max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況01122312討論：j=1時(shí),next[j]≡

0；因?yàn)閷儆凇癹=1”;j=2時(shí),next[j]≡

1；因?yàn)閷儆凇捌渌闆r”；剛才已歸納：j=3時(shí),k={2}，只需查看‘T1’=‘T2’；j=4時(shí),k={2，3}，要查看‘T1’=‘T3’和‘T1T2’=‘T2T3’j=5時(shí),k={2，3，4}，要查看‘T1’=‘T4’、‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值。討論兩個(gè)有關(guān)next[j]的問(wèn)題：①怎樣簡(jiǎn)捷計(jì)算next[j]？可用遞推法編程實(shí)現(xiàn)?。▍⒁?jiàn)P83簡(jiǎn)捷算法）計(jì)算next[j]的時(shí)間為O(m)voidget_next(SStringT,int&next[]){//next函數(shù)值存入數(shù)組nexti=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_nextvoidget_nextval(SStringT,int&nextval[]){//next函數(shù)修正值存入數(shù)組nextvali=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;If(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}elsej=nextval[j];}}//get_nextval②next[j]是否完美無(wú)缺？答：未必，例如當(dāng)S=‘a(chǎn)baaaab’,T=‘a(chǎn)aaab’時(shí)仍有多余動(dòng)作（參見(jiàn)P84改進(jìn)算法,

稱為nextval[j]）i=1;j=0next[1]=0i<T[0]j==0||T[i]==T[j]++i;++j;next[j]=j;j=next[j];ENDYYNN附：求解next[j]算法流程圖:例如：求abaabcac模式串的next函數(shù)next[1]=0next[2]=1pnex