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

1、精選課件1第第4章章 串串 4.1 串的基本概念串的基本概念4.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu) 本章小結(jié)本章小結(jié)4.3 串的模式匹配串的模式匹配 精選課件2 串串（或字符串），是由零個(gè)或多個(gè)（或字符串），是由零個(gè)或多個(gè)字符字符組成的組成的有窮序列有窮序列。含零個(gè)字符的串稱為空串，用含零個(gè)字符的串稱為空串，用表示。表示。 串中所含字符的個(gè)數(shù)稱為該串中所含字符的個(gè)數(shù)稱為該串的長(zhǎng)度串的長(zhǎng)度（或串長(zhǎng)）。（或串長(zhǎng)）。 通常將一個(gè)串表示成通常將一個(gè)串表示成“a1a2an”的形式。其中最外邊的雙的形式。其中最外邊的雙引號(hào)本身不是串的內(nèi)容，它們是串的標(biāo)志，以便將串與標(biāo)識(shí)引號(hào)本身不是串的內(nèi)容，它們是串的標(biāo)志，以便

2、將串與標(biāo)識(shí)符（如變量名等）加以區(qū)別。每個(gè)符（如變量名等）加以區(qū)別。每個(gè)ai（1in）代表一個(gè)字符。）代表一個(gè)字符。4.1 串的基本概念串的基本概念精選課件3 當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等并且各個(gè)對(duì)應(yīng)位置上的字符都當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等并且各個(gè)對(duì)應(yīng)位置上的字符都相同時(shí)，這兩個(gè)串才是相同時(shí)，這兩個(gè)串才是相等相等的。的。 一個(gè)串中任意個(gè)連續(xù)字符組成的一個(gè)串中任意個(gè)連續(xù)字符組成的子序列子序列（含空串）稱為該（含空串）稱為該串的子串。例如，串的子串。例如，“a”、“ab”、“abc”和和“abcd”等都是等都是“abcde”的子串（的子串（真子串真子串是指不包含自身的所有子串）。是指不包含自身的所有子串）

3、。精選課件4思考題：思考題：串和線性表串和線性表有什么異同？有什么異同？精選課件5例例4.1 問題問題: “abcde”有多少個(gè)有多少個(gè)真子串真子串?解解:空串?dāng)?shù)空串?dāng)?shù):1含含1個(gè)字符的子串?dāng)?shù)個(gè)字符的子串?dāng)?shù):5含含2個(gè)字符的子串?dāng)?shù)個(gè)字符的子串?dāng)?shù):4含含3個(gè)字符的子串?dāng)?shù)個(gè)字符的子串?dāng)?shù):3含含4個(gè)字符的子串?dāng)?shù)個(gè)字符的子串?dāng)?shù):2共有共有1+2+3+4+5=15個(gè)子串。個(gè)子串。推廣：推廣：含有含有n個(gè)相互相同字符的串有個(gè)相互相同字符的串有n(n+1)/2個(gè)真子串。個(gè)真子串。精選課件6 串的基本運(yùn)算如下串的基本運(yùn)算如下: StrAssign(&s,cstr)：將字符串常量將字符串常量cstr賦給

4、串賦給串s，即生，即生成其值等于成其值等于cstr的串的串s。StrCopy(&s,t)：串復(fù)制。將串串復(fù)制。將串t賦給串賦給串s。StrEqual(s,t)：判串相等。若兩個(gè)串：判串相等。若兩個(gè)串s與與t相等則返回真；相等則返回真；否則返回假。否則返回假。StrLength(s)：求串長(zhǎng)。返回串求串長(zhǎng)。返回串s中字符個(gè)數(shù)。中字符個(gè)數(shù)。Concat(s,t)：串連接串連接:返回由兩個(gè)串返回由兩個(gè)串s和和t連接在一起形連接在一起形成的新串。成的新串。SubStr(s,i,j)：求子串。返回串求子串。返回串s中從第中從第i（1in）個(gè)字）個(gè)字符開始的、由連續(xù)符開始的、由連續(xù)j個(gè)字符組成的子

5、串。個(gè)字符組成的子串。精選課件7InsStr(s1,i,s2)：插入。將串插入。將串s2插入到串插入到串s1的第的第i（1in+1）個(gè)字符中，即將個(gè)字符中，即將s2的第一個(gè)字符作為的第一個(gè)字符作為s1的第的第i個(gè)字符，并返個(gè)字符，并返回產(chǎn)生的新串?；禺a(chǎn)生的新串。DelStr(s,i,j)：刪除。從串刪除。從串s中刪去從第中刪去從第i（1in）個(gè)字符開）個(gè)字符開始的長(zhǎng)度為始的長(zhǎng)度為j的子串，并返回產(chǎn)生的新串。的子串，并返回產(chǎn)生的新串。RepStr(s,i,j,t)：替換。在串替換。在串s中，將第中，將第i（1in）個(gè)字符開）個(gè)字符開始的始的j個(gè)字符構(gòu)成的子串用串個(gè)字符構(gòu)成的子串用串t替換，并返回

6、產(chǎn)生的新串。替換，并返回產(chǎn)生的新串。DispStr(s)：串輸出。輸出串串輸出。輸出串s的所有元素值。的所有元素值。精選課件84.2.1 串的順序存儲(chǔ)及其基本操作實(shí)現(xiàn)串的順序存儲(chǔ)及其基本操作實(shí)現(xiàn) 4.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu) 在順序串中，串中的字符被依次存放在一組連續(xù)的存在順序串中，串中的字符被依次存放在一組連續(xù)的存儲(chǔ)單元里。一般來說，一個(gè)字節(jié)（儲(chǔ)單元里。一般來說，一個(gè)字節(jié)（8位）可以表示一個(gè)字符位）可以表示一個(gè)字符（即該字符的（即該字符的ASCII碼）。碼）。因此，一個(gè)內(nèi)存單元可以存儲(chǔ)多個(gè)字符。例如，一個(gè)因此，一個(gè)內(nèi)存單元可以存儲(chǔ)多個(gè)字符。例如，一個(gè)32位的內(nèi)存單元可以存儲(chǔ)位的內(nèi)存單元可

7、以存儲(chǔ)4個(gè)字符（即個(gè)字符（即4個(gè)字符的個(gè)字符的ASCII碼）。碼）。 精選課件9串的順序存儲(chǔ)有兩種方法：一種是每個(gè)單元只存一個(gè)字符，串的順序存儲(chǔ)有兩種方法：一種是每個(gè)單元只存一個(gè)字符，這稱為這稱為非緊縮格式非緊縮格式（其存儲(chǔ)密度?。涣硪环N是每個(gè)單元存放（其存儲(chǔ)密度?。?；另一種是每個(gè)單元存放多個(gè)字符，這稱為多個(gè)字符，這稱為緊縮格式緊縮格式（其存儲(chǔ)密度大）。（其存儲(chǔ)密度大）。 A B C D E F G H I J K L M N 1001 1002 1003 1004 1005 1006 1007 1008 1009 100a 100b 100c 100d 100e A B C D E F G

8、 H I J K L M N 1000 1001 1002 1003 非緊縮格式示例非緊縮格式示例 緊縮格式示例緊縮格式示例 精選課件10對(duì)于非緊縮格式的順序串，其類型定義如下：對(duì)于非緊縮格式的順序串，其類型定義如下： #define MaxSize 100typedef struct char dataMaxSize; int length; SqString; 其中其中data域用來存儲(chǔ)字符串，域用來存儲(chǔ)字符串，length域用來存儲(chǔ)字符域用來存儲(chǔ)字符串的當(dāng)前長(zhǎng)度，串的當(dāng)前長(zhǎng)度，MaxSize常量表示允許所存儲(chǔ)字符串的最常量表示允許所存儲(chǔ)字符串的最大長(zhǎng)度。在大長(zhǎng)度。在C語言中每個(gè)字符串以語

9、言中每個(gè)字符串以0標(biāo)志結(jié)束。標(biāo)志結(jié)束。精選課件11 順序串中實(shí)現(xiàn)串的基本運(yùn)算如下。順序串中實(shí)現(xiàn)串的基本運(yùn)算如下。 （1）StrAssign(s,cstr)將一個(gè)字符串常量賦給串將一個(gè)字符串常量賦給串s，即生成一個(gè)其值等于，即生成一個(gè)其值等于cstr的串的串s。void StrAssign(SqString &s,char cstr)/s為引用型參數(shù)為引用型參數(shù) int i; for (i=0;cstri!=0;i+)s.datai=cstri; s.length=i;建立順序串的算法。建立順序串的算法。精選課件12（2）StrCopy(s,t)將串將串t復(fù)制給串復(fù)制給串s。void S

10、trCopy(SqString &s,SqString t)/s為引用型參數(shù)為引用型參數(shù) int i; for (i=0;it.length;i+)s.datai=t.datai; s.length=t.length;精選課件13（3）StrEqual(s,t) 判串相等：若兩個(gè)串判串相等：若兩個(gè)串s與與t相等返回真（相等返回真（1）；否則返回假（）；否則返回假（0）。）。bool StrEqual(SqString s,SqString t) bool same=true; int i; if (s.length!=t.length)/長(zhǎng)度不相等時(shí)返回長(zhǎng)度不相等時(shí)返回0same=fa

11、lse; else for (i=0;is.length;i+) if (s.datai!=t.datai) same=false;break; return same;精選課件14（4）StrLength(s)求串長(zhǎng)：返回串求串長(zhǎng)：返回串s中字符個(gè)數(shù)。中字符個(gè)數(shù)。int StrLength(SqString s) return s.length;精選課件15（5）Concat(s,t)串連接：返回由兩個(gè)串串連接：返回由兩個(gè)串s和和t連接在一起形成的新串。連接在一起形成的新串。SqString Concat(SqString s,SqString t) SqString str; int i;

12、 str.length=s.length+t.length; for (i=0;is.length;i+) /s.data0.s.length-1strstr.datai=s.datai; for (i=0;it.length;i+) /t.data0.t.length-1strstr.datas.length+i=t.datai; return str;精選課件16（6）SubStr(s,i,j) 求子串：返回串求子串：返回串s中從第中從第i（1iStrLength(s)）個(gè)字符開始的、）個(gè)字符開始的、由連續(xù)由連續(xù)j個(gè)字符組成的子串。參數(shù)不正確時(shí)返回一個(gè)空串。個(gè)字符組成的子串。參數(shù)不正確時(shí)返

13、回一個(gè)空串。SqString SubStr(SqString s,int i,int j) SqString str; int k; str.length=0; if (is.length | js.length)return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串 for (k=i-1;ki+j-1;k+) /s.datai.i+jstrstr.datak-i+1=s.datak; str.length=j; return str; 精選課件17（7）InsStr(s1,i,s2) 將串將串s2插入到串插入到串s1的第的第i（1iStrLength(s)+1）個(gè)字符中，即）個(gè)字

14、符中，即將將s2的第一個(gè)字符作為的第一個(gè)字符作為s1的第的第i個(gè)字符，并返回產(chǎn)生的新串。參數(shù)個(gè)字符，并返回產(chǎn)生的新串。參數(shù)不正確時(shí)返回一個(gè)空串。不正確時(shí)返回一個(gè)空串。SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if (is1.length+1) /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串return str; for (j=0;ji-1;j+) /將將s1.data0.i-2strstr.dataj=s1.dataj; for (j=0;js2.length;j+) /s2.

15、data0.s2.length-1strstr.datai+j-1=s2.dataj; for (j=i-1;js1.length;j+) /s1.datai-1.s1.length-1strstr.datas2.length+j=s1.dataj; str.length=s1.length+s2.length; return str;精選課件18（8）DelStr(s,i,j) 從串從串s中刪去第中刪去第i（1iStrLength(s)）個(gè)字符開始的長(zhǎng)度為）個(gè)字符開始的長(zhǎng)度為j的的子串，并返回產(chǎn)生的新串。參數(shù)不正確時(shí)返回一個(gè)空串。子串，并返回產(chǎn)生的新串。參數(shù)不正確時(shí)返回一個(gè)空串。SqStri

16、ng DelStr(SqString s,int i,int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串 for (k=0;ki-1;k+) /s.data0.i-2strstr.datak=s.datak; for (k=i+j-1;ks.length;k+) /s.datai+j-1.s.length-1strstr.datak-j=s.datak; str.length=s.length-j; return str;精選課件19

17、（9）RepStr(s,i,j,t) 在串在串s中，將第中，將第i（1iStrLength(s)）個(gè)字符開始的）個(gè)字符開始的j個(gè)字符構(gòu)個(gè)字符構(gòu)成的子串用串成的子串用串t替換，并返回產(chǎn)生的新串。參數(shù)不正確時(shí)返回一替換，并返回產(chǎn)生的新串。參數(shù)不正確時(shí)返回一個(gè)空串。個(gè)空串。SqString RepStr(SqString s,int i,int j,SqString t) int k; SqString str; str.length=0; if (is.length | i+j-1s.length) return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串 for (k=0;ki-1;k

18、+)/s.data0.i-2strstr.datak=s.datak; for (k=0;kt.length;k+) /t.data0.t.length-1strstr.datai+k-1=t.datak; for (k=i+j-1;k0) for (i=0;is.length;i+) printf(%c,s.datai);printf(n); 精選課件21例例4.2 設(shè)計(jì)順序串上實(shí)現(xiàn)串比較運(yùn)算設(shè)計(jì)順序串上實(shí)現(xiàn)串比較運(yùn)算Strcmp(s,t)的算法。的算法。 解：解：本例的算法思路如下本例的算法思路如下: （1）比較）比較s和和t兩個(gè)串共同長(zhǎng)度范圍內(nèi)的對(duì)應(yīng)字符兩個(gè)串共同長(zhǎng)度范圍內(nèi)的對(duì)應(yīng)字符:

19、若若s的字符的字符t的字符，返回的字符，返回1； 若若s的字符的字符t的字符，返回的字符，返回-1； 若若s的字符的字符=t的字符的字符,按上述規(guī)則繼續(xù)比較。按上述規(guī)則繼續(xù)比較。 （2）當(dāng)（）當(dāng)（1）中對(duì)應(yīng)字符均相同時(shí)，比較）中對(duì)應(yīng)字符均相同時(shí)，比較s和和t的長(zhǎng)度的長(zhǎng)度: 兩者相等時(shí)，返回兩者相等時(shí)，返回0； s的長(zhǎng)度的長(zhǎng)度t的長(zhǎng)度，返回的長(zhǎng)度，返回1； s的長(zhǎng)度的長(zhǎng)度t的長(zhǎng)度，返回的長(zhǎng)度，返回-1。精選課件22int Strcmp(SqString s,SqString t) int i,comlen; if (s.lengtht.length)comlen=s.length;/求求s和和t

20、的共同長(zhǎng)度的共同長(zhǎng)度 else comlen=t.length; for (i=0;it.datai)return 1;else if (s.datait.length)/streturn 1; else return -1;/sdata=cstri;r-next=p;r=p; r-next=NULL;精選課件27（2）StrCopy(s,t) 將串將串t復(fù)制給串復(fù)制給串s。以下采用尾插法建立復(fù)制后的鏈串。以下采用尾插法建立復(fù)制后的鏈串s。void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; s=(LiStri

21、ng *)malloc(sizeof(LiString); r=s;/r始終指向尾節(jié)點(diǎn)始終指向尾節(jié)點(diǎn) while (p!=NULL)/將將t的所有節(jié)點(diǎn)復(fù)制到的所有節(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;精選課件28（3）StrEqual(s,t)判串相等：若兩個(gè)串判串相等：若兩個(gè)串s與與t相等則返回真；否則返回假。相等則返回真；否則返回假。bool StrEqual(LiString *s,LiString *t) LiString *p=s-ne

22、xt,*q=t-next; while (p!=NULL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL)return true; elsereturn false;精選課件29（4）StrLength(s)求串長(zhǎng)：返回串求串長(zhǎng)：返回串s中字符個(gè)數(shù)。中字符個(gè)數(shù)。int StrLength(LiString *s) int i=0; LiString *p=s-next; while (p!=NULL) i+;p=p-next; return i;精選課件30（5）Concat(s,t)

23、串連接：返回由兩個(gè)串串連接：返回由兩個(gè)串s和和t連接在一起形成的新串。以下采連接在一起形成的新串。以下采用尾插法建立鏈串用尾插法建立鏈串str并返回其地址。并返回其地址。LiString *Concat(LiString *s,LiString *t) LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str; while (p!=NULL)/將將s的所有節(jié)點(diǎn)復(fù)制到的所有節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-n

24、ext=q;r=q;p=p-next; p=t-next;精選課件31 while (p!=NULL)/將將t的所有節(jié)點(diǎn)復(fù)制到的所有節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;精選課件32（6）SubStr(s,i,j) 求子串：返回串求子串：返回串s中從第中從第i（1iStrLength(s)）個(gè)字符開始）個(gè)字符開始的、由連續(xù)的、由連續(xù)j個(gè)字符組成的子串，參數(shù)不正確時(shí)返回一個(gè)空串。個(gè)字符組成的子串，參數(shù)不正確時(shí)返回一個(gè)空串

25、。以下采用尾插法建立鏈串以下采用尾插法建立鏈串str并返回其地址。并返回其地址。LiString *SubStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點(diǎn)指向新建鏈表的尾節(jié)點(diǎn) if (iStrLength(s) | jStrLength(s)return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串 for (k=0;knext;精選課件33 for (k

26、=1;kdata=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;精選課件34（7）InsStr(s1,i,s2) 將串將串s2插入到串插入到串s1的第的第i（1iStrLength(s)+1）個(gè)字符位置，）個(gè)字符位置，即將即將s2的第的第1個(gè)字符作為個(gè)字符作為s1的第的第i個(gè)字符，個(gè)字符，s2的第的第2個(gè)字符作為個(gè)字符作為s1的的第第i+1個(gè)字符，等等，并返回產(chǎn)生的新串個(gè)字符，等等，并返回產(chǎn)生的新串, 參數(shù)不正確時(shí)返回一個(gè)參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串空串。以下采用尾插法建立鏈串str并返回其地址。并返回其地址。L

27、iString *InsStr(LiString *s,int i,LiString *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點(diǎn)指向新建鏈表的尾節(jié)點(diǎn) if (iStrLength(s)+1)return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串精選課件35 for (k=1;kdata=p-data; r-next=q;r=q; p=p-next; while (p1!=N

28、ULL)/將將t的所有節(jié)點(diǎn)復(fù)制到的所有節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString); q-data=p1-data; r-next=q;r=q; p1=p1-next; while (p!=NULL)/將將*p及其后的節(jié)點(diǎn)復(fù)制到及其后的節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str;精選課件36（8）DelStr(s,i,j) 從串從串s中刪去從第中刪去從第i（1iStrLe

29、ngth(s)）個(gè)字符開始的長(zhǎng)度）個(gè)字符開始的長(zhǎng)度為為j的子串，并返回產(chǎn)生的新串的子串，并返回產(chǎn)生的新串, 參數(shù)不正確時(shí)返回一個(gè)空串。參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串以下采用尾插法建立鏈串str并返回其地址。并返回其地址。LiString *DelStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點(diǎn)指向新建鏈表的尾節(jié)點(diǎn) if (iStrLength(s

30、) | jStrLength(s)return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串精選課件37 for (k=0;kdata=p-data;r-next=q;r=q;p=p-next; for (k=0;knext; while (p!=NULL)/將將*p及其后的節(jié)點(diǎn)復(fù)制到及其后的節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;精選課件38（9）RepStr(s,i,j,t) 在串在串s中，將第中，將第i（1

31、iStrLength(s)）個(gè)字符開始的）個(gè)字符開始的j個(gè)字符個(gè)字符構(gòu)成的子串用串構(gòu)成的子串用串t替換，并返回產(chǎn)生的新串，參數(shù)不正確時(shí)返替換，并返回產(chǎn)生的新串，參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串回一個(gè)空串。以下采用尾插法建立鏈串str并返回其地址。并返回其地址。LiString *RepStr(LiString *s,int i,int j,LiString *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=s

32、tr;/r指向新建鏈表的尾節(jié)點(diǎn)指向新建鏈表的尾節(jié)點(diǎn) if (iStrLength(s) | jStrLength(s) return str; /參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串精選課件39 for (k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next; for (k=0;knext; while (p1!=NULL)/將將t的所有節(jié)點(diǎn)復(fù)制到的所有節(jié)點(diǎn)復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-next=q;r=q;p1=p1-nex

33、t; while (p!=NULL)/將將*p及其后的節(jié)點(diǎn)復(fù)制到及其后的節(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; r-next=NULL; return str;精選課件40（10）DispStr(s)輸出串輸出串s的所有元素值。的所有元素值。void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data);p=p-next; printf(n);精選課

34、件41 例例4.3 在鏈串中在鏈串中,設(shè)計(jì)一個(gè)算法把最先出現(xiàn)的子串設(shè)計(jì)一個(gè)算法把最先出現(xiàn)的子串a(chǎn)b改改為為xyz。 解：解：在串在串s中找到最先出現(xiàn)的子串中找到最先出現(xiàn)的子串“ab”，p指向指向data域值域值為為a的結(jié)點(diǎn)，其后為的結(jié)點(diǎn)，其后為data域值為域值為b的結(jié)點(diǎn)。將它們的的結(jié)點(diǎn)。將它們的data域值分別改為域值分別改為x和和z，再創(chuàng)建一個(gè)，再創(chuàng)建一個(gè)data域值為域值為y的結(jié)點(diǎn)，的結(jié)點(diǎn)，將其插入到將其插入到*p之后。本例算法如下之后。本例算法如下:精選課件42void Repl(LiString *&s) LiString *p=s-next,*q; int find=0;

35、while (p-next!=NULL & find=0) /查找查找ab子串子串 if (p-data=a & p-next-data=b)/找到子串找到子串 p-data=x;p-next-data=z;/替換為替換為xyz q=(LiString *)malloc(sizeof(LiString); q-data=y;q-next=p-next;p-next=q; find=1;else p=p-next; 精選課件434.3 串的模式匹配串的模式匹配 設(shè)有主串設(shè)有主串s和子串和子串t，子串，子串t的定位就是要在主串的定位就是要在主串s中找到中找到一個(gè)與子串一個(gè)與子串t相

36、等的子串。通常把主串相等的子串。通常把主串s稱為稱為目標(biāo)串目標(biāo)串，把子串，把子串t稱為稱為模式串模式串，因此定位也稱作，因此定位也稱作模式匹配模式匹配。 模式匹配成功是指在目標(biāo)串模式匹配成功是指在目標(biāo)串s中找到一個(gè)模式串中找到一個(gè)模式串t；不成；不成功則指目標(biāo)串功則指目標(biāo)串s中不存在模式串中不存在模式串t。 精選課件444.4.1 Brute-Force算法算法 Brute-Force簡(jiǎn)稱為簡(jiǎn)稱為BF算法，亦稱簡(jiǎn)單匹配算法，其基本算法，亦稱簡(jiǎn)單匹配算法，其基本思路是思路是: 從目標(biāo)串從目標(biāo)串s=“s0s1sn-1”的第一個(gè)字符開始和模式串的第一個(gè)字符開始和模式串t=“t0t1tm-1”中的第一

37、個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較中的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從目標(biāo)串后續(xù)字符；否則從目標(biāo)串s的第二個(gè)字符開始重新與模式串的第二個(gè)字符開始重新與模式串t的第一個(gè)字符進(jìn)行比較。依次類推的第一個(gè)字符進(jìn)行比較。依次類推,若從模式串若從模式串s的第的第i個(gè)字符個(gè)字符開始，每個(gè)字符依次和目標(biāo)串開始，每個(gè)字符依次和目標(biāo)串t中的對(duì)應(yīng)字符相等，則匹配成中的對(duì)應(yīng)字符相等，則匹配成功功,該算法返回該算法返回i；否則，匹配失敗，函數(shù)返回；否則，匹配失敗，函數(shù)返回-1。 精選課件45int indexpos(SqString str,SqString substr) int i,j,k,i

38、dx=-1; for (i=0;istr.length;i+) for (j=i,k=0;str.dataj=substr.datak; j+,k+); if (k=substr.length) /注意注意j每次從每次從i開始開始,有回溯有回溯 return(i); return(-1);算法算法1 1精選課件46int index(SqString s,SqString t) int i=0,j=0; while (is.length & j=t.length)return(i-t.length);/返回匹配的第一個(gè)字符的下標(biāo)返回匹配的第一個(gè)字符的下標(biāo) elsereturn(-1);

39、/模式匹配不成功模式匹配不成功算法算法2 2精選課件47 例如，設(shè)目標(biāo)串例如，設(shè)目標(biāo)串s=“aaaaab”，模式串，模式串t=“aaab”。s的長(zhǎng)度的長(zhǎng)度為為n（n=6），），t的長(zhǎng)度為的長(zhǎng)度為m（m=4）。用指針）。用指針i指示目標(biāo)串指示目標(biāo)串s的的當(dāng)前比較字符位置，用指針當(dāng)前比較字符位置，用指針j指示模式串指示模式串t的當(dāng)前比較字符位的當(dāng)前比較字符位置。模式匹配過程如下圖所示。置。模式匹配過程如下圖所示。 第 1 趟匹配 s=a a a a a b i=3 t=a a a b j=3 失敗,修改為 第 2 趟匹配 s=a a a a a b i=4 t=a a a b j=3 第 3 趟匹

40、配 s=a a a a a b i=6 t=a a a b j=4 成功，返回 i-t.length=2 i=i-j+1=1 j=0 失敗,修改為 i=i-j+1=2 j=0 精選課件48 這個(gè)算法簡(jiǎn)單，易于理解，但效率不高，主要原因是主串這個(gè)算法簡(jiǎn)單，易于理解，但效率不高，主要原因是主串指針指針i在若干個(gè)字符序列比較相等后，若有一個(gè)字符比較不相在若干個(gè)字符序列比較相等后，若有一個(gè)字符比較不相等，仍需回溯（即等，仍需回溯（即i=i-j+1）。）。 該算法在最好情況下的時(shí)間復(fù)雜度為該算法在最好情況下的時(shí)間復(fù)雜度為O(m)，即主串的前，即主串的前m個(gè)字符正好等于模式串的個(gè)字符正好等于模式串的m個(gè)字

41、符。在最壞情況下的時(shí)間復(fù)雜個(gè)字符。在最壞情況下的時(shí)間復(fù)雜度為度為O(n*m)。 精選課件49 4.3.2 KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同共同提出的，簡(jiǎn)稱提出的，簡(jiǎn)稱KMP算法算法。該算法較。該算法較BF算法有較大改進(jìn)，主算法有較大改進(jìn)，主要是消除了主串指針的回溯，從而使算法效率有了某種程要是消除了主串指針的回溯，從而使算法效率有了某種程度的提高。度的提高。精選課件50目標(biāo)串目標(biāo)串s=aaaaab，模式串，模式串t=aaab。 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 BF算法下一步是從算法下一

42、步是從s1開始開始其實(shí)沒有必要從其實(shí)沒有必要從s1開始，為什么？開始，為什么？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 應(yīng)有一個(gè)數(shù)組應(yīng)有一個(gè)數(shù)組next，使使next3=2精選課件51模式串中究竟是什么信息呢？模式串中究竟是什么信息呢？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 nexti是指下標(biāo)為是指下標(biāo)為i的字符前有多少個(gè)的字符前有多少個(gè)真子串真子串的字符。的字符。精選課件52 所謂所謂真子串真子串是指模式串是指模式串t存在某個(gè)存在某個(gè)k（0kj），使得）

43、，使得t0t1tk = tj-ktj-k+1tj 成立。成立。 例如，例如，t= abab, 即即t0t1t2t3 也就是說，也就是說， “ab”是真子串。是真子串。 真子串就是模式串中隱藏的信息，利用它來提高模式匹配真子串就是模式串中隱藏的信息，利用它來提高模式匹配的效率。的效率。精選課件53模式串模式串t=“abcac”，用，用next數(shù)組存放這些數(shù)組存放這些“部分匹配部分匹配”信息信息 。j01234tjabcacnextj-10001精選課件54 歸納起來，定義歸納起來，定義nextj函數(shù)如下函數(shù)如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng)此

44、集合非空時(shí)當(dāng)此集合非空時(shí) -1 當(dāng)當(dāng)j=0時(shí)時(shí) 0 其他情況其他情況nextj=j0123tjababnextj-1001t=“abab”對(duì)應(yīng)的對(duì)應(yīng)的next數(shù)組如下數(shù)組如下:精選課件55void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.length-1) if (k=-1 | t.dataj=t.datak) j+;k+; nextj=k;else k=nextk; 由模式串由模式串t求出求出next值：值：精選課件56int KMPIndex(SqString s,SqString t) int

45、nextMaxSize,i=0,j=0; GetNext(t,next); while (is.length & j=t.length)return(i-t.length);/返回匹配模式串的首字符下標(biāo)返回匹配模式串的首字符下標(biāo) elsereturn(-1);/返回不匹配標(biāo)志返回不匹配標(biāo)志KMP算法：算法：精選課件57 設(shè)主串設(shè)主串s的長(zhǎng)度為的長(zhǎng)度為n，子串，子串t長(zhǎng)度為長(zhǎng)度為m。 在在KMP算法中求算法中求next數(shù)組的時(shí)間復(fù)雜度為數(shù)組的時(shí)間復(fù)雜度為O(m)，在后，在后面的匹配中因主串面的匹配中因主串s的下標(biāo)不減即不回溯，比較次數(shù)可記為的下標(biāo)不減即不回溯，比較次數(shù)可記為n，所以所以KMP算法總的時(shí)間復(fù)雜度為算法總的時(shí)間復(fù)雜度為O(n+m)。精選課件58 第第 1 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失敗失敗 第第 2 2 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失敗失敗 第第 3 3 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=1,j=next1=0 失敗失敗 第第 4 4 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=0,j=next0=-