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

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

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

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

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

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

教學目標計算機學院4.1串類型的定義串(String)----零個或多個字符組成的有限序列串名串值串長n空串n=0計算機學院a=‘BEI’,b=‘JING’

c=‘BEIJING’

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

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

(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計算機學院4.2串的表示和實現(xiàn)定長順序表示堆分配存儲表示串的塊鏈存儲表示計算機學院定長順序表示#defineMAXSTRLEN255//用戶可在255以內(nèi)定義最大串長typedefunsignedcharSString[MAXSTRLEN+1];//0號單元存放串長計算機學院串連接的實現(xiàn)（a)S1[0]+S2[0]MAXSTRLEN計算機學院串連接的實現(xiàn)（b)S1[0]<MAXSTRLEN而

S1[0]+S2[0]>MAXSTRLEN計算機學院串連接的實現(xiàn)（c)S1[0]=MAXSTRLEN

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

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

intcurlen;//串的當前長度}LString;

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

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

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

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

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

（關(guān)鍵技術(shù):計算next[j]）④KMP算法的時間復雜度能否利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動速度？能！而且主串S的指針i不必回溯！可提速到O(n+m)！例：①KMP算法設(shè)計思想：(參見教材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的返回值應為i=6需要討論兩個問題：①如何“記憶”部分匹配結(jié)果？②如何由“記憶”結(jié)果計算出主串S第i個字符應該與模式T中哪個字符再比較？即確定模式T中的新比較起點k.iiikk

a

b

aa

b

c②KMP算法的推導過程：（見教材P81）抓住部分匹配結(jié)果的兩個特征：兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’注意：j為當前已知的失配位置，我們的目標是計算新起點k，僅剩一個未知數(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è)目前應與T的第k字符開始比較②KMP算法的推導過程(續(xù)）：根據(jù)模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’和已知的當前失配位置j，可以歸納出計算新起點k的表達式。令k=next[j]，則next[j]＝0當j＝1時max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況討論：①next[j]有何意義？一旦失配，應從模式串T中第next[j]個字符開始與S的失配點i重新匹配!②next[j]怎么求？后面會舉例（參見教材P81）第一步，先把模式T所有可能的失配點j所對應的next[j]計算出來；第二步：執(zhí)行定位函數(shù)index_kmp（與BF算法模塊非常相似）③KMP算法的實現(xiàn)—即Index()操作的實現(xià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位置開始匹配

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

elsereturn0;}//Index_KMP怎樣計算模式T所有可能的失配點j所對應的next[j]？例：模式串T：abaabcac

可能失配位

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

0；因為屬于“j=1”;j=2時,next[j]≡

1；因為屬于“其他情況”；剛才已歸納：j=3時,k={2}，只需查看‘T1’=‘T2’；j=4時,k={2，3}，要查看‘T1’=‘T3’和‘T1T2’=‘T2T3’j=5時,k={2，3，4}，要查看‘T1’=‘T4’、‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值。討論兩個有關(guān)next[j]的問題：①怎樣簡捷計算next[j]？可用遞推法編程實現(xiàn)?。▍⒁奝83簡捷算法）計算next[j]的時間為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]是否完美無缺？答：未必，例如當S=‘a(chǎn)baaaab’,T=‘a(chǎn)aaab’時仍有多余動作（參見P84改進算法,

稱為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