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

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

4.1串的基本概念4.2串的存儲結(jié)構(gòu)

本章小結(jié)4.3串的模式匹配

數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)第4章串

串(或字符串),是由零個或多個字符組成的有窮序列。含零個字符的串稱為空串,用Ф表示。串中所含字符的個數(shù)稱為該串的長度(或串長)。通常將一個串表示成"a1a2…an"的形式。其中,最外邊的雙引號本身不是串的內(nèi)容,它們是串的標(biāo)志,以便將串與標(biāo)識符(如變量名等)加以區(qū)別。每個ai(1≤i≤n)代表一個字符。4.1串的基本概念數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)第4章串

當(dāng)且僅當(dāng)兩個串的長度相等并且各個對應(yīng)位置上的字符都相同時,這兩個串才是相等的。一個串中任意個連續(xù)字符組成的子序列(含空串)稱為該串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)第4章串

串的基本運(yùn)算如下:(1)StrAssign(&s,chars):將一個字符串常量賦給串s,即生成一個其值等于chars的串s。

(2)StrCopy(&s,t):串復(fù)制:將串t賦給串s。

(3)StrEqual(s,t):判串相等:若兩個串s與t相等則返回真；否則返回假。

(4)StrLength(s):求串長:返回串s中字符個數(shù)。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(5)Concat(s,t):串連接:返回由兩個串s和t連接在一起形成的新串。

(6)SubStr(s,i,j):求子串:返回串s中從第i(1≤i≤StrLength(s))個字符開始的、由連續(xù)j個字符組成的子串。

(7)InsStr(s1,i,s2):將串s2插入到串s1的第i(1≤i≤StrLength(s)+1)個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(8)DelStr(s,i,j):從串s中刪去從第i(1≤i≤StrLength(s))個字符開始的長度為j的子串,并返回產(chǎn)生的新串。

(9)RepStr(s,i,j,t):替換:在串s中,將第i(1≤i≤StrLength(s))個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。

(10)DispStr(s):串輸出:輸出串s的所有元素值。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)第4章串4.2.1串的順序存儲及其基本操作實現(xiàn)串是一種特殊的線性表,在非緊縮格式中,它的每個結(jié)點僅由一個字符組成,因此存儲串的方法也就是存儲線性表的一般方法。存儲串最常用的方式是采用順序存儲,即把串的字符順序地存儲在內(nèi)存一片相鄰的空間,這稱為順序串。4.2串的存儲結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第7頁。數(shù)據(jù)結(jié)構(gòu)第4章串

順序存儲采用一般順序表的存儲結(jié)構(gòu),其類型定義如下:

#defineMaxSize100 typedefstruct { chardata[MaxSize]; intlength; }SqString;

其中,data域用來存儲字符串,length域用來存儲字符串的當(dāng)前長度,MaxSize常量表示允許所存儲字符串的最大長度。在C語言中每個字符串以'\0'標(biāo)志結(jié)束。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)第4章串

順序串中實現(xiàn)串的基本運(yùn)算如下:(1)StrAssign(s,cstr)

將一個字符串常量賦給串s,即生成一個其值等于cstr的串s。

voidStrAssign(SqString&s,charcstr[]){inti;for(i=0;cstr[i]!='\0';i++)s.data[i]=cstr[i];s.length=i;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(2)StrCopy(s,t)

將串t復(fù)制給串s。voidStrCopy(SqString&s,SqStringt)/*引用型參數(shù)*/{inti;for(i=0;i<t.length;i++)s.data[i]=t.data[i];s.length=t.length;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第10頁。

(3)StrEqual(s,t)

判斷兩個串是否相等:若兩個串s與t相等返回真(1)；否則返回假(0)。intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.length!=t.length)same=0;/*長度不相等時返回0*/elsefor(i=0;i<s.length;i++) if(s.data[i]!=t.data[i])/*有對應(yīng)字符不相同時返回0*/{ same=0; break; }returnsame;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第11頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(4)Strlength(s)求串長:返回串s中字符個數(shù)。intStrLength(SqStrings){returns.length;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第12頁。數(shù)據(jù)結(jié)構(gòu)第4章串(5)Concat(s,t)

返回由兩個串s和t連接在一起形成的新串。SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.length=s.length+t.length;for(i=0;i<s.length;i++)/*將s.data[0]～s.data[s.length-1]復(fù)制到str*/ str.data[i]=s.data[i];for(i=0;i<t.length;i++)/*將t.data[0]～t.data[t.length-1]復(fù)制到str*/str.data[s.length+i]=t.data[i];returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第13頁。數(shù)據(jù)結(jié)構(gòu)第4章串(6)SubStr(s,i,j)

返回串s中從第i(1≤i≤StrLength(s))個字符開始的、由連續(xù)j個字符組成的子串。SqStringSubStr(SqStrings,inti,intj){ SqStringstr;intk;str.length=0; if(i<=0||i>s.length||j<0||i+j-1>s.length)returnstr;/*參數(shù)不正確時返回空串*/ for(k=i-1;k<i+j-1;k++)/*s.data[i]～s.data[i+j]=>str*/str.data[k-i+1]=s.data[k]; str.length=j; returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第14頁。數(shù)據(jù)結(jié)構(gòu)第4章串(7)InsStr(s1,i,s2)

將串s2插入到串s1的第i個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。SqStringInsStr(SqStrings1,inti,SqStrings2){ intj; SqStringstr;str.length=0; if(i<=0||i>s1.length+1)/*參數(shù)不正確時返回空串*/ returnstr;數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第15頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(j=0;j<i-1;j++)/*s1.data[0]～s1.data[i-2]=>str*/ str.data[j]=s1.data[j]; for(j=0;j<s2.length;j++)/*s2.data[0]～s2.data[s2.length-1]=>str*/ str.data[i+j-1]=s2.data[j]; for(j=i-1;j<s1.length;j++)/*s1.data[i-1]～s.data[s1.length-1]=>str*/ str.data[s2.length+j]=s1.data[j]; str.length=s1.length+s2.length; returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第16頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(8)DelStr(s,i,j)

從串s中刪去第i(1≤i≤StrLength(s))個字符開始的長度為j的子串,并返回產(chǎn)生的新串。SqStringDelStr(SqStrings,inti,intj){ intk;SqStringstr; str.length=0; if(i<=0||i>s.length||i+j>s.length+1)/*參數(shù)不正確時返回空串*/returnstr;數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第17頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*s.data[0]～s.data[i-2]=>str*/str.data[k]=s.data[k];for(k=i+j-1;k<s.length;k++)/*s.data[i+j-1]～data[s.length-1]=>str*/str.ch[k-j]=s.ch[k];str.length=s.length-j;returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第18頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(9)RepStr(s,i,j,t)

在串s中,將第i(1≤i≤StrLength(s))個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。SqStringRepStr(SqStrings,inti,intj,SqStringt){ intk;SqStringstr; str.length=0; if(i<=0||i>s.length||i+j-1>s.length)/*參數(shù)不正確時返回空串*/ returnstr;數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第19頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++) /*s.data[0]～s.data[i-2]=>str*/ str.data[k]=s.data[k]; for(k=0;k<t.length;k++)/*t.data[0…t.length-1]=>str*/ str.data[i+k-1]=t.data[k]; for(k=i+j-1;k<s.length;k++)/*s.data[i+j-1]～data[s.length-1]=>str*/str.data[t.length+k-j]=s.data[k]; str.length=s.length-j+t.length; returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第20頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(10)DispStr(s)輸出串s的所有元素值。voidDispStr(SqStrings){inti;if(s.length>0){for(i=0;i<s.length;i++)printf("%c",s.data[i]);printf("\n");}}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第21頁。數(shù)據(jù)結(jié)構(gòu)第4章串

例4.1設(shè)計順序串上實現(xiàn)串比較運(yùn)算Strcmp(s,t)的算法。解:本例的算法思路如下:(1)比較s和t兩個串共同長度范圍內(nèi)的對應(yīng)字符:①若s的字符＜t的字符,返回-1；②若s的字符＞t的字符,返回1；③若s的字符=t的字符,按上述規(guī)則繼續(xù)比較。

(2)當(dāng)(1)中對應(yīng)字符均相同時,比較s1和s2的長度:①兩者相等時,返回0；②s的長度＞t的長度,返回1；③s的長度＜t的長度,返回-1。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第22頁。數(shù)據(jù)結(jié)構(gòu)第4章串

intStrcmp(SqStrings,SqStringt){ inti,comlen; if(s.length<t.length)comlen=s.length;/*求s和t的共同長度*/ elsecomlen=t.length; for(i=0;i<comlen;i++)/*逐個字符比較*/ if(s.data[i]<t.data[i])return-1; elseif(s.data[i]>t.data[i])return1; if(s.length==t.length) /*s==t*/ return0; elseif(s.length<t.length) /*s<t*/ return-1; elsereturn1; /*s>t*/}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第23頁。數(shù)據(jù)結(jié)構(gòu)第4章串4.2.2串的鏈?zhǔn)酱鎯捌浠静僮鲗崿F(xiàn)也可以采用鏈?zhǔn)椒绞酱鎯Υ?即用單鏈表形式存儲串。這稱為鏈?zhǔn)酱蜴湸?。鏈串中的結(jié)點類型定義:

typedefstructsnode{chardata;structsnode*next;}LiString;數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第24頁。數(shù)據(jù)結(jié)構(gòu)第4章串

其中data域用來存儲組成字符串的字符,next域用來指向下一個結(jié)點。每個字符對應(yīng)一個結(jié)點,一個這樣的鏈表存儲一個字符串。下圖所示是一個結(jié)點大小為1的鏈串。鏈串示意圖數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第25頁。

下面討論在鏈串上實現(xiàn)串基本運(yùn)算的算法。(只講1,2)(1)StrAssign(s,t)

將一個字符串常量t賦給串s,即生成一個其值等于t的串s。以下采用尾插法建立鏈串。voidStrAssign(LiString*&s,chart[]){ inti; LiString*r,*p; /*r始終指向尾結(jié)點*/ s=(LiString*)malloc(sizeof(LiString)); s->next=NULL;r=s; for(i=0;t[i]!='\0';i++) {p=(LiString*)malloc(sizeof(LiString)); p->data=t[i];r->next=p;r=p; } r->next=NULL;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第26頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(2)StrCopy(s,t)

將串t復(fù)制給串s。以下采用尾插法建立復(fù)制后的鏈串s。

voidStrCopy(LiString*&s,LiString*t){ LiString*p=t->next,*q,*r; s=(LiString*)malloc(sizeof(LiString)); s->next=NULL;s->next=NULL; r=s; /*r始終指向尾結(jié)點*/ while(p!=NULL) /*將t的所有結(jié)點復(fù)制到s*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;r->next=q;r=q; p=p->next; } r->next=NULL;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第27頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(3)StrEqual(s,t)

判斷兩個串是否相等:若兩個串s與t相等則返回真(1)；否則返回假(0)。

intStrEqual(LiString*s,LiString*t){ LiString*p=s->next,*q=t->next; while(p!=NULL&&q!=NULL&&p->data==q->data) {p=p->next;q=q->next;} if(p==NULL&&q==NULL)return1; elsereturn0;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第28頁。數(shù)據(jù)結(jié)構(gòu)第4章串(4)StrLength(s)求串長:返回串s中字符個數(shù)。

intStrLength(LiString*s){inti=0;LiString*p=s->next;while(p!=NULL){i++; p=p->next;}returni;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第29頁。數(shù)據(jù)結(jié)構(gòu)第4章串(5)Concat(s,t)

返回由兩個串s和t連接在一起形成的新串。

LiString*Concat(LiString*s,LiString*t){ LiString*str,*p=s->next,*q,*r; str=(LiString*)malloc(sizeof(LiString)); str->next=NULL;r=str; while(p!=NULL)/*將s的所有結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第30頁。數(shù)據(jù)結(jié)構(gòu)第4章串

p=t->next; while(p!=NULL)/*將t的所有結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; } returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第31頁。數(shù)據(jù)結(jié)構(gòu)第4章串(6)SubStr(s,i,j)

返回串s中從第i(1≤i≤StrLength(s))個字符開始的、由連續(xù)j個字符組成的子串。

LiString*SubStr(LiString*s,inti,intj){ intk; LiString*str,*p=s->next,*q,*r; str=(LiString*)malloc(sizeof(LiString)); str->next=NULL;r=str; if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) {printf("參數(shù)不正確\n"); returnstr; /*參數(shù)不正確時返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第32頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*找第i-1個結(jié)點,由p指向它*/ p=p->next; for(k=1;k<=j;k++)/*s[i]開始的j個結(jié)點=>str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; } returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第33頁。數(shù)據(jù)結(jié)構(gòu)第4章串(7)InsStr(s1,i,s2)

將串s2插入到串s1的第i(1≤i≤StrLength(s)+1)個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。

LiString*InsStr(LiString*s,inti,LiString*t){ intk; LiString*str,*p=s->next,*p1=t->next,*q,*r; str=(LiString*)malloc(sizeof(LiString)); str->next=NULL;r=str; if(i<=0||i>StrLength(s)+1) {printf("參數(shù)不正確\n"); returnstr; /*參數(shù)不正確時返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第34頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=1;k<i;k++)/*將s的前i個結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next; } while(p1!=NULL)/*將t的所有結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p1->data;q->next=NULL; r->next=q;r=q;p1=p1->next; } while(p!=NULL)/*將*p及其后的結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next; } returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第35頁。數(shù)據(jù)結(jié)構(gòu)第4章串(8)DelStr(s,i,j)

從串s中刪去從第i(1≤i≤StrLength(s))個字符開始的長度為j的子串,并返回產(chǎn)生的新串。

LiString*DelStr(LiString*s,inti,intj){ intk; LiString*str,*p=s->next,*q,*r; str=(LiString*)malloc(sizeof(LiString)); str->next=NULL;r=str; if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) {printf("參數(shù)不正確\n"); returnstr; /*參數(shù)不正確時返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第36頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*將s的前i-1個結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next; } for(k=0;k<j;k++)/*讓p沿next跳j個結(jié)點*/ p=p->next; while(p!=NULL)/*將*p及其后的結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next; } returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第37頁。數(shù)據(jù)結(jié)構(gòu)第4章串(9)RepStr(s,i,j,t)

在串s中,將第i(1≤i≤StrLength(s))個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。

LiString*RepStr(LiString*s,inti,intj,LiString*t){ intk; LiString*str,*p=s->next,*p1=t->next,*q,*r; str=(LiString*)malloc(sizeof(LiString)); str->next=NULL;r=str; if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) {printf("參數(shù)不正確\n"); returnstr;/*參數(shù)不正確時返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第38頁。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*將s的前i-1個結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next; } for(k=0;k<j;k++)/*讓p沿next跳j個結(jié)點*/ p=p->next; while(p1!=NULL)/*將t的所有結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p1->data;q->next=NULL; r->next=q;r=q;p1=p1->next; }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第39頁。數(shù)據(jù)結(jié)構(gòu)第4章串

while(p!=NULL)/*將*p及其后的結(jié)點復(fù)制到str*/ {q=(LiString*)malloc(sizeof(LiString)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; } returnstr;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第40頁。數(shù)據(jù)結(jié)構(gòu)第4章串

(10)DispStr(s)

輸出串s的所有元素值。

voidDispStr(LiString*s){ LiString*p=s->next; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第41頁。數(shù)據(jù)結(jié)構(gòu)第4章串

例4.3在鏈串中,設(shè)計一個算法把最先出現(xiàn)的子串"ab"改為"xyz"。解:在串s中找到最先出現(xiàn)的子串"ab",p指向data域值為'a'的結(jié)點,其后為data域值為'b'的結(jié)點。將它們的data域值分別改為'x'和'z',再創(chuàng)建一個data域值為'y'的結(jié)點,將其插入到*p之后。本例算法如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第42頁。數(shù)據(jù)結(jié)構(gòu)第4章串

voidRepl(LiString*&s){ LiString*p=s->next,*q;intfind=0; while(p->next!=NULL&&find==0) {if(p->data==‘a(chǎn)’&&p->next->data==‘b’)/*找到*/ {p->data='x';p->next->data='z'; /*替換為xyz*/ q=(lstring*)malloc(sizeof(lstring)); q->data='y';q->next=p->next; p->next=q; find=1; } elsep=p->next; }}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第43頁。數(shù)據(jù)結(jié)構(gòu)第4章串4.3串的模式匹配設(shè)有主串s和子串t,子串t的定位就是要在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標(biāo)串,把子串t稱為模式串,因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個模式串t；不成功則指目標(biāo)串s中不存在模式串t。例：s=“abcdefghij”,t=“fghi”Index(s,t)=6數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第44頁。數(shù)據(jù)結(jié)構(gòu)第4章串4.3.1Brute-Force算法

Brute-Force簡稱為BF算法,亦稱簡單匹配算法,其基本思路是:

從目標(biāo)串s="s0s1…sn-1"的第一個字符開始和模式串t="t0t1…tm-1"中的第一個字符比較,若相等,則繼續(xù)逐個比較后續(xù)字符；否則從目標(biāo)串s的第二個字符開始重新與模式串t的第一個字符進(jìn)行比較。依次類推,若從模式串s的第i個字符開始,每個字符依次和目標(biāo)串t中的對應(yīng)字符相等,則匹配成功,該算法返回i；否則,匹配失敗,函數(shù)返回-1。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第45頁。數(shù)據(jù)結(jié)構(gòu)第4章串

例如,設(shè)目標(biāo)串s=“cddcdc”,模式串t=“cdc”。s的長度為n(n=6),t的長度為m(m=3)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。BF模式匹配過程如下所示。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第46頁。數(shù)據(jù)結(jié)構(gòu)第4章串目標(biāo)串s=“cddcdc”,模式串t=“cdc”存儲在順序串時的BF模式匹配過程如下所示。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=0j=0數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第47頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=1j=1數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第48頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=2j=2當(dāng)i=2,j=2時，匹配不成功。此時，ii-j+1,j0即i=1,j=0數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第49頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=1j=0當(dāng)i=2,j=2時，匹配不成功。此時，ii-j+1,j0即i=1,j=0當(dāng)i=1,j=0時，匹配不成功。此時，ii-j+1,j0即i=2,j=0數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第50頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=2j=0當(dāng)i=2,j=0時，匹配不成功。此時，ii-j+1,j0即i=3,j=0數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第51頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=3j=0當(dāng)i=3,j=0時，對應(yīng)字符相等，ii+1,jj+1即i=4,j=1數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第52頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=4j=1當(dāng)i=4,j=1時，對應(yīng)字符相等，ii+1,jj+1即i=5,j=2數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第53頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=5j=2當(dāng)i=5,j=2時，對應(yīng)字符相等，ii+1,jj+1即i=6,j=3數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第54頁。數(shù)據(jù)結(jié)構(gòu)第4章串data[……..]lenS:cddcdc6[0][1][2][3][4]…data[……..]lent:cdc3[0][1][2][3][4]…i=6j=3當(dāng)i=6,j=3時，匹配成功，此時，j==t.len,i-t.len就是匹配的起始位置數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第55頁。數(shù)據(jù)結(jié)構(gòu)第4章串intindex(SqStrings,SqStringt){inti=0,j=0,k;while(i<s.len&&j<t.len){if(s.data[i]==t.data[j]) /*繼續(xù)匹配下一個字符*/ {i++;j++;/*主串和子串依次匹配下一個字符*/} else/*主串、子串指針回溯重新開始下一次匹配*/ {i=i-j+1; /*主串從下一個位置開始匹配*/j=0;/*子串從頭開始匹配*/}}if(j>=t.length)k=i-t.length; /*返回匹配的第一個字符的下標(biāo)*/elsek=-1; /*模式匹配不成功*/returnk;}數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第56頁。數(shù)據(jù)結(jié)構(gòu)第4章串

這個算法簡單,易于理解,但效率不高,主要原因是:主串指針i在若干個字符序列比較相等后,若有一個字符比較不相等,仍需回溯(即i=i-j+1)。該算法在最好情況下的時間復(fù)雜度為O(m),即主串的前m個字符正好等于模式串的m個字符。在最壞情況下的時間復(fù)雜度為O(n*m)。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第57頁。數(shù)據(jù)結(jié)構(gòu)第4章串最壞情況：O(m*n)例：檢查模式串：“00000001”是否在以下主串中：匹配過程中，指針回溯次數(shù)n-m+1,每次需比較m次“0000000000”數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第58頁。數(shù)據(jù)結(jié)構(gòu)第4章串4.3.2KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,簡稱KMP算法。該算法較BF算法有較大改進(jìn),主要是消除了主串指針的回溯,從而使算法效率有了某種程度的提高。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第59頁。數(shù)據(jù)結(jié)構(gòu)第4章串例:主串s=“s0s1.......si...........................sn-1”

模式串t=“t0t1......tj......tm-1”設(shè)s=“abababa”,t=“ababc”,第一次匹配過程如下所示。

此時不必從i=1(i=i-j+1=1),j=0重新開始第二次匹配。因t0≠t1,s1=t1,必有s1≠t0,又因t0=t2,s2=t2,所以必有s2=t0。s3=t1。因此,第二次匹配可直接從i=4,j=2開始。

數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第60頁。數(shù)據(jù)結(jié)構(gòu)第4章串

現(xiàn)在我們討論一般情況。設(shè)s=“s0s1…sn-1”,t=“t0t1…tm-1”,當(dāng)si≠tj(0≤i≤n-m,0≤j＜m)時,存在:"t0t1…tj-1"="si-jsi-j+1…si-1"(4.1)若模式串中存在的真子串滿足:"t0t1…tk-1"="tj-ktj-k+1…tj-1"(0＜k＜j)(4.2)

由(4.1)式說明模式串中的子串"t0t1…tk-1"已和主串"si-ksi-k+1…si-1"匹配,下一次可直接比較si和tk,若不存在(4.2)式,則結(jié)合(4.1)式說明在"t0t1…tj-1"中不存在任何以t0為首字符子串與"si-j+1si-j+2…si-1"中以si-1為末字符的匹配子串,下一次可直接比較si和t0。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第61頁。數(shù)據(jù)結(jié)構(gòu)第4章串s=“s0s1…si-j…...si-j+k-1si-j+k…si-k-1si-k…si-1si……sn-1”||...||||...||||...||||t="t0……tk-1tk…tj-k-1tj-k…tj-1tj…tm-1"ijs=“s0s1…si-j...…si-j+k-1si-j+k…si-k-1si-k…si-1

si……sn-1”||…||t="t0…tk-1tk…"j=ki不變?nèi)魌0……tk-1

==tj-k…tj-1數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第62頁。數(shù)據(jù)結(jié)構(gòu)第4章串

為此,定義next[j]函數(shù)如下:

max{k|0<k<j,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1”}

當(dāng)此集合非空時

-1當(dāng)j=0時

0其他情況next[j]=j0123t[j]ababnext[j]-1001t=“abab”對應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第63頁。數(shù)據(jù)結(jié)構(gòu)第4章串

為此,定義next[j]函數(shù)如下:

max{k|0<k<j,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1”}

當(dāng)此集合非空時

-1當(dāng)j=0時

0其他情況next[j]=j01234t[j]ababcnext[j]-10012t=“ababc”對應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第64頁。數(shù)據(jù)結(jié)構(gòu)第4章串j012345t[j]aaaabanext[j]-101231t=“aaaaba”對應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第65頁。數(shù)據(jù)結(jié)構(gòu)第4章串next[0]=-1,next[1]=0,當(dāng)next[j]=k時，求next[j+1]=?t=“t0……tk-1tk…tj-k-1tj-k…...tj-1tj…..."有t0……tk-1

==tj-k…...tj-1若tk==tj,則有

t0……tk-1tk

==tj-k…...tj-1tjt=“t0……tk-1tk…...........

tj-k…...tj-1tjtj+1…...”則next[j+1]=k+1數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第66頁。next[0]=-1,next[1]=0,當(dāng)next[j]=k時，求next[j+1]=?t=“t0……tk-1tk…tj-k-1tj-k…...tj-1tj…..."有t0……tk-1

==tj-k…...tj-1若tk

≠tj,設(shè)next[j+1]=d已知t0….........…..tk-1==tj-k…................tj-1t=“t0……td-1.....tk-1…...

ti-k.....

tj-d+1…...tj-1tjtj+1…...”則t0......td-1==tj-d+1......tj,有t0......td-2==tj-d+1......tj-1而tj-d+1......tj-1==tk-d+1......tk-1所以，t0......td-2==tk-d+1......tk-1td-1==tj則next[k]=d-1，td-1==tj

即k=next[j],d=next[k]+1,若td-1==tj

，則next[j+1]=d數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁，當(dāng)前為第67頁。數(shù)據(jù)結(jié)構(gòu)第4章串由模式串t求出next值的算法如下:voidGetNext(SqStringt,intnext[]){intj,k;j=0;k=-1;next[0]=-1;while(j<t.length-1){if(k==-1||t.ch[j]==t.ch[k])/*k為-1或比較的字符相等時*/{ j++;k++; next[j]=k;} else