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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將一個(gè)字符串常量賦給串s,即生成一個(gè)其值等于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頁(yè)，當(dāng)前為第9頁(yè)。數(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頁(yè)，當(dāng)前為第10頁(yè)。

(3)StrEqual(s,t)

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

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

返回由兩個(gè)串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頁(yè)，當(dāng)前為第13頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(6)SubStr(s,i,j)

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

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

(8)DelStr(s,i,j)

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

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

在串s中,將第i(1≤i≤StrLength(s))個(gè)字符開(kāi)始的j個(gè)字符構(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ù)不正確時(shí)返回空串*/ returnstr;數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第19頁(yè)。數(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頁(yè)，當(dāng)前為第20頁(yè)。數(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頁(yè)，當(dāng)前為第21頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

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

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

intStrcmp(SqStrings,SqStringt){ inti,comlen; if(s.length<t.length)comlen=s.length;/*求s和t的共同長(zhǎng)度*/ elsecomlen=t.length; for(i=0;i<comlen;i++)/*逐個(gè)字符比較*/ 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頁(yè)，當(dāng)前為第23頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串4.2.2串的鏈?zhǔn)酱鎯?chǔ)及其基本操作實(shí)現(xiàn)也可以采用鏈?zhǔn)椒绞酱鎯?chǔ)串,即用單鏈表形式存儲(chǔ)串。這稱為鏈?zhǔn)酱蜴湸?。鏈串中的結(jié)點(diǎn)類型定義:

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

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

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

將一個(gè)字符串常量t賦給串s,即生成一個(gè)其值等于t的串s。以下采用尾插法建立鏈串。voidStrAssign(LiString*&s,chart[]){ inti; LiString*r,*p; /*r始終指向尾結(jié)點(diǎn)*/ 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頁(yè)，當(dāng)前為第26頁(yè)。數(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é)點(diǎn)*/ while(p!=NULL) /*將t的所有結(jié)點(diǎn)復(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頁(yè)，當(dāng)前為第27頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

(3)StrEqual(s,t)

判斷兩個(gè)串是否相等:若兩個(gè)串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頁(yè)，當(dāng)前為第28頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(4)StrLength(s)求串長(zhǎng):返回串s中字符個(gè)數(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頁(yè)，當(dāng)前為第29頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(5)Concat(s,t)

返回由兩個(gè)串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é)點(diǎn)復(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頁(yè)，當(dāng)前為第30頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

p=t->next; while(p!=NULL)/*將t的所有結(jié)點(diǎn)復(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頁(yè)，當(dāng)前為第31頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(6)SubStr(s,i,j)

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

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í)返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第32頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*找第i-1個(gè)結(jié)點(diǎn),由p指向它*/ p=p->next; for(k=1;k<=j;k++)/*s[i]開(kāi)始的j個(gè)結(jié)點(diǎn)=>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頁(yè)，當(dāng)前為第33頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(7)InsStr(s1,i,s2)

將串s2插入到串s1的第i(1≤i≤StrLength(s)+1)個(gè)字符中,即將s2的第一個(gè)字符作為s1的第i個(gè)字符,并返回產(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í)返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第34頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=1;k<i;k++)/*將s的前i個(gè)結(jié)點(diǎn)復(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é)點(diǎn)復(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é)點(diǎn)復(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頁(yè)，當(dāng)前為第35頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(8)DelStr(s,i,j)

從串s中刪去從第i(1≤i≤StrLength(s))個(gè)字符開(kāi)始的長(zhǎng)度為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í)返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第36頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*將s的前i-1個(gè)結(jié)點(diǎn)復(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個(gè)結(jié)點(diǎn)*/ p=p->next; while(p!=NULL)/*將*p及其后的結(jié)點(diǎn)復(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頁(yè)，當(dāng)前為第37頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串(9)RepStr(s,i,j,t)

在串s中,將第i(1≤i≤StrLength(s))個(gè)字符開(kāi)始的j個(gè)字符構(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í)返回空串*/ }數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第38頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

for(k=0;k<i-1;k++)/*將s的前i-1個(gè)結(jié)點(diǎn)復(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個(gè)結(jié)點(diǎn)*/ p=p->next; while(p1!=NULL)/*將t的所有結(jié)點(diǎn)復(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頁(yè)，當(dāng)前為第39頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

while(p!=NULL)/*將*p及其后的結(jié)點(diǎn)復(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頁(yè)，當(dāng)前為第40頁(yè)。數(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頁(yè)，當(dāng)前為第41頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串

例4.3在鏈串中,設(shè)計(jì)一個(gè)算法把最先出現(xiàn)的子串"ab"改為"xyz"。解:在串s中找到最先出現(xiàn)的子串"ab",p指向data域值為'a'的結(jié)點(diǎn),其后為data域值為'b'的結(jié)點(diǎn)。將它們的data域值分別改為'x'和'z',再創(chuàng)建一個(gè)data域值為'y'的結(jié)點(diǎn),將其插入到*p之后。本例算法如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第42頁(yè)。數(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頁(yè)，當(dāng)前為第43頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串4.3串的模式匹配設(shè)有主串s和子串t,子串t的定位就是要在主串s中找到一個(gè)與子串t相等的子串。通常把主串s稱為目標(biāo)串,把子串t稱為模式串,因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個(gè)模式串t；不成功則指目標(biāo)串s中不存在模式串t。例：s=“abcdefghij”,t=“fghi”Index(s,t)=6數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第44頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串4.3.1Brute-Force算法

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

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

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

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

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

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

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

數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第60頁(yè)。數(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)時(shí),存在:"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)式說(shuō)明模式串中的子串"t0t1…tk-1"已和主串"si-ksi-k+1…si-1"匹配,下一次可直接比較si和tk,若不存在(4.2)式,則結(jié)合(4.1)式說(shuō)明在"t0t1…tj-1"中不存在任何以t0為首字符子串與"si-j+1si-j+2…si-1"中以si-1為末字符的匹配子串,下一次可直接比較si和t0。數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第61頁(yè)。數(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頁(yè)，當(dāng)前為第62頁(yè)。數(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)此集合非空時(shí)

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

0其他情況next[j]=j0123t[j]ababnext[j]-1001t=“abab”對(duì)應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第63頁(yè)。數(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)此集合非空時(shí)

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

0其他情況next[j]=j01234t[j]ababcnext[j]-10012t=“ababc”對(duì)應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第64頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串j012345t[j]aaaabanext[j]-101231t=“aaaaba”對(duì)應(yīng)的next數(shù)組如下:數(shù)據(jù)結(jié)構(gòu)第4章串全文共81頁(yè)，當(dāng)前為第65頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章串next[0]=-1,next[1]=0,當(dāng)next[j]=k時(shí)，求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頁(yè)，當(dāng)前為第66頁(yè)。next[0]=-1,next[1]=0,當(dāng)next[j]=k時(shí)，求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頁(yè)，當(dāng)前為第67頁(yè)。數(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或比較的字符相等時(shí)*/{ j++;k++; next[j]=k;} else