串的定義及其基本運算課件

4.1串的定義及其基本運算4.2串的定長順序存儲及基本運算4.3串的堆存儲結構第四章串作業(yè)6：P235（1，2）4.1串的定義及其基本運算第四章串作業(yè)6：P235（4.1.1串的定義定義：串(string)是由零個或多個任意字符組成的字符序列，又稱為字符串(characterstring)，一般記為:4.1串的定義及其基本運算s=〝a1a2a3…an〞說明:1)其中s是串名，用雙引號括起來的字符序列是串的值。2)ai(1<=i<=n)可以是字母、數(shù)字或其他字符；n為串中字符的個數(shù)，稱為串的長度,i是序號。3)一個長度為零的串稱為空串，表示為s=“”或。4)空格也是合法字符，空格串是字符,為空格的串。4.1.1串的定義4.1串的定義及其基本運算s=〝a1幾個術語空串：長度為0的字符串；空格串：由空格字符組成的字符串，長度>1.子串:字符串中任意個連續(xù)的字符構成的序列;母串:包含該子串的字符串;兩串相等:兩個字符串的長度相等且各對應位置上的字符都相同.字符的位置：從1開始子串的位置：該子串第一個字符的位置幾個術語空串：長度為0的字符串；4.1.2串的基本運算1.求串的長度StrLength(s)；2.串賦值StrAssign(s1,s2);3.兩個串的連接StrConcat(s1,s2,s)或StrConcat(s1,s2)4.求某串的子串SubStr(s,i,len)；5.串比較StrCmp(s1,s2)；6.子串定位StrIndex(s,t);7.插入子串StrInsert(s,i,t)；8.刪除子串StrDelete(s,i,len)；9.置換StrRep(s,t,r)。4.1.2串的基本運算1.求串的長度StrLength(4.2.1存儲結構的實現(xiàn)#defineMAXSIZE256typedefstruct{chardata[MAXSIZE];

intcurlen;}SeqString;4.2串的定長順序存儲及基本運算第一種：第二種：#defineMAXSIZE256chars[MAXSIZE];abefi0256s.curlencdgh13478s.dataMAXSIZE-1abefi0256cdgh13478\09MAXSIZE-14.2.1存儲結構的實現(xiàn)#defineMAXSIZE25第三種：#defineMAXSIZE256chars[MAXSIZE+1];abefi0256cdgh1347899MAXSIZE第三種：#defineMAXSIZE256abefi024.2.2運算實現(xiàn)（采用第二種表示串長的方式）1.求串的長度StrLength(s)；intStrLength(chars[]){intlen=0;while(s[len]!=‘\0’)len++;returnlen;}2.串賦值StrAssign(s1,s2);voidStrAssign(s1,s2)chars1[],s2[];{intj=0;while(s2[j]!=‘\0’){s1[j]=s2[j];j++;}s1[j]=‘\0’;}4.2.2運算實現(xiàn)（采用第二種表示串長的方式）1.求串的長3.兩個串的連接StrConcat1(s1,s2,s)4.求某串的子串SubStr(s,i,len)；5.串比較StrCmp(s1,s2)；3.兩個串的連接StrConcat1(s1,s2,s)4.4.2.3模式匹配設s和t是給定的兩個串，在主串s中查找子串t的過程稱為~。其中t也稱為模式。為運算方便，字符串采用定長存儲，且用第三種方式表示串長：#defineMAXSIZE256chars[MAXSIZE+1];abefi0256cdgh1347899MAXSIZE4.2.3模式匹配設s和t是給定的兩個串，在主串s中查找子串1.簡單的模式匹配算法（BF算法）（1）算法思想：例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”s：acabaabaabcacaabct：abaabcaci=1j=1s：acabaabaabcacaabct：abaabcaci=2j=2if（s[i]==t[j]）{i++；j++；}if（s[i]！=t[j]）{i回溯到本趟開始的下一個；j回溯到1；}1.簡單的模式匹配算法（BF算法）（1）算法思想：例s：acabaabaabcacaabct：abaabcaci=2j=1s：acabaabaabcacaabct：abaabcaci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5i=8j=6s：acabaabaabcacaabct：abaabcaci=4j=1s：acabaabs：acabaabaabcacaabct：abaabcaci=5j=1i=6j=2s：acabaabaabcacaabct：abaabcaci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j=8i=14j=9（2）算法實現(xiàn)循環(huán)條件？什么時候回溯？回溯時i、j如何計算？如何判斷匹配是否成功？匹配成功時，返回的起始位置如何計算？見P59的算法4-4s：acabaab2.改進后的模式匹配算法（KMP算法）s：acabaabaabcacaabct：abaabcaci=8j=6s：acabaabaabcacaabct：abaabcaci=8k=3（1）KMP算法思想：i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑動到某個位置k。2.改進后的模式匹配算法（KMP算法）s：（2）k位置的確定——next函數(shù)用next函數(shù)來確定k的值，即k=next（j）；j12345678模式串abaabcacnext（j）

[例4-1]求模式串“abaabcac”的next函數(shù)值next(j)=max{k|1<=k<j且”t1t2…tk-1”=”tj-k+1tj-k+2…tj-1”1其他情況0j=101122312（2）k位置的確定——next函數(shù)用next函數(shù)來確定k的值練習：求下列模式串的next函數(shù)值AAABAABAACAABABAABRACADABRAASSTACASTRA練習：求下列模式串的next函數(shù)值例：主串S:“aabcbabcaabcaababc”模式串t:“abcaababc”j123456789模式串abcaababcnext[j]

011122323s：aabcbabcaabcaababct：abcaababci=1j=1i=2j=2s：aabcbabcaabcaababct：abcaababci=2j=1i=3j=2i=4j=3i=5j=4例：主串S:“aabcbabcaabcaababc”jj123456789模式串abcaababcnext[j]

011122323s：aabcbabcaabcaababct：abcaababci=5j=1s：aabcbabcaabcaababct：abcaababci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7s：aabcbabcaabcaababct：abcaababci=12j=3i=13j=4i=14j=5i=15j=6i=16j=7i=17j=8i=18j=9i=19j=10j123456789模式串a（3）KMP算法實現(xiàn)循環(huán)條件？什么時候回溯？回溯時i、j如何計算？如何判斷匹配是否成功？匹配成功時，返回的起始位置如何計算？見P61的算法4-5（3）KMP算法實現(xiàn)循環(huán)條件？見P61的算法4-5（4）如何求next函數(shù)next[1]=0;設next[i-1]=k，如何求next[i]？（令j=i）j123456789模式串abcabcdbcnext[j]0i=2j=1k=next[j]=01next(j)=max{k|1<=k<j且”t1t2…tk-1”=”tj-k+1tj-k+2…tj-1”1其他情況0j=1第一種情況：k==0next[i]=k+1；

（4）如何求next函數(shù)next[1]=0;j123第二種情況:t[k]==t[j]j123456789模式串abcabcdbcnext[j]011123i=6j=5next[i]=k+1；

k=2第二種情況:t[k]==t[j]j1234第三種情況：t[k]≠t[j]

j123456789模式串abaababbanext[j]0112234i=8j=73（1）回溯k=next[k]直至t[j]==t[k]j123456789模式串abcabcdbcnext[j]0111234i=8j=71（2）回溯k=next[k]直至k==0k=4k=2k=4k=1k=0next[i]=k+1；next[i]=k+1；第三種情況：t[k]≠t[j]j123j123456789模式串abcaababcnext[j]

0i=2：j=1，k=next[1]=0next[i]=k+1=1i=3：j=2，k=next[2]=1，t[k]≠t[j]，k回溯111k=next[1]=0next[i]=k+1=1i=4：j=3，k=next[3]=1，t[k]≠t[j]，k回溯k=next[1]=0next[4]=k+1=1求next[i]：i=1next[i]=0i=5：j=4，k=next[4]=1，t[k]=t[j]next[i]=k+1=22j123456789模式串ai=6：j=5，k=next[5]=2，t[k]≠t[j]，k回溯23k=next[2]=1，t[k]=t[j]next[i]=k+1=2i=7：j=6，k=next[6]=2，t[k]=t[j]next[i]=k+1=3j123456789模式串abcaababcnext[j]

01112i=8：j=7，k=next[7]=3，t[k]≠t[j]，k回溯k=next[3]=1，t[k]=t[j]next[i]=k+1=22i=9：j=8，k=next[8]=2，t[k]=t[j]next[i]=k+1=33i=6：j=5，k=next[5]=2，t[k]≠t算法實現(xiàn)：voidGetNext(chart[],intnext[]){inti=2,j,k;next[1]=0;j=i-1；k=next[j]；while(i<=t[0]){if(k==0||t[k]==t[j]){next[i]=k+1;i++;j=i-1；k=next[j];}elsek=next[k];/*k回溯*/}理解P63算法4-6算法實現(xiàn)：理解P63算法4-6作業(yè)：根據(jù)NEXT算法求下列模式串的next函數(shù)值（寫出過程）AAABABRACADABRAASSTACASTRA練習：根據(jù)NEXT算法求下列模式串的next函數(shù)值（寫出過程）AABAACAABABA作業(yè)：根據(jù)NEXT算法求下列模式串的next函數(shù)值（寫出4.3串的堆存儲結構4.3.1串名的存儲映像1.帶串長度的索引表typedefstruct{charname[MAXNAME];intlength;char*stradr;}LNode;2.帶末尾指針的索引表typedefstruct{charname[MAXNAME];char*stradr，*enadr;}ENode;3.帶特征位的索引表typedefstruct{charname[MAXNAME];inttag;union{char*stradr，charvalue[4];}uval;}TNode;4.3串的堆存儲結構4.3.1串名的存儲映像typed4.3.2堆存儲結構基本思想：在內存中開辟能存儲足夠多的串、地址連續(xù)的存儲空間作為應用程序只所有串的可利用存儲空間，稱為堆空間。（未分配區(qū)域）（已分配區(qū)域）charstore[SMAX+1];intfree;typedefstruct{intlength;intstradr;}Hstring;4.3.2堆存儲結構基本思想：charstore[SM4.1串的定義及其基本運算4.2串的定長順序存儲及基本運算4.3串的堆存儲結構第四章串作業(yè)6：P235（1，2）4.1串的定義及其基本運算第四章串作業(yè)6：P235（4.1.1串的定義定義：串(string)是由零個或多個任意字符組成的字符序列，又稱為字符串(characterstring)，一般記為:4.1串的定義及其基本運算s=〝a1a2a3…an〞說明:1)其中s是串名，用雙引號括起來的字符序列是串的值。2)ai(1<=i<=n)可以是字母、數(shù)字或其他字符；n為串中字符的個數(shù)，稱為串的長度,i是序號。3)一個長度為零的串稱為空串，表示為s=“”或。4)空格也是合法字符，空格串是字符,為空格的串。4.1.1串的定義4.1串的定義及其基本運算s=〝a1幾個術語空串：長度為0的字符串；空格串：由空格字符組成的字符串，長度>1.子串:字符串中任意個連續(xù)的字符構成的序列;母串:包含該子串的字符串;兩串相等:兩個字符串的長度相等且各對應位置上的字符都相同.字符的位置：從1開始子串的位置：該子串第一個字符的位置幾個術語空串：長度為0的字符串；4.1.2串的基本運算1.求串的長度StrLength(s)；2.串賦值StrAssign(s1,s2);3.兩個串的連接StrConcat(s1,s2,s)或StrConcat(s1,s2)4.求某串的子串SubStr(s,i,len)；5.串比較StrCmp(s1,s2)；6.子串定位StrIndex(s,t);7.插入子串StrInsert(s,i,t)；8.刪除子串StrDelete(s,i,len)；9.置換StrRep(s,t,r)。4.1.2串的基本運算1.求串的長度StrLength(4.2.1存儲結構的實現(xiàn)#defineMAXSIZE256typedefstruct{chardata[MAXSIZE];

intcurlen;}SeqString;4.2串的定長順序存儲及基本運算第一種：第二種：#defineMAXSIZE256chars[MAXSIZE];abefi0256s.curlencdgh13478s.dataMAXSIZE-1abefi0256cdgh13478\09MAXSIZE-14.2.1存儲結構的實現(xiàn)#defineMAXSIZE25第三種：#defineMAXSIZE256chars[MAXSIZE+1];abefi0256cdgh1347899MAXSIZE第三種：#defineMAXSIZE256abefi024.2.2運算實現(xiàn)（采用第二種表示串長的方式）1.求串的長度StrLength(s)；intStrLength(chars[]){intlen=0;while(s[len]!=‘\0’)len++;returnlen;}2.串賦值StrAssign(s1,s2);voidStrAssign(s1,s2)chars1[],s2[];{intj=0;while(s2[j]!=‘\0’){s1[j]=s2[j];j++;}s1[j]=‘\0’;}4.2.2運算實現(xiàn)（采用第二種表示串長的方式）1.求串的長3.兩個串的連接StrConcat1(s1,s2,s)4.求某串的子串SubStr(s,i,len)；5.串比較StrCmp(s1,s2)；3.兩個串的連接StrConcat1(s1,s2,s)4.4.2.3模式匹配設s和t是給定的兩個串，在主串s中查找子串t的過程稱為~。其中t也稱為模式。為運算方便，字符串采用定長存儲，且用第三種方式表示串長：#defineMAXSIZE256chars[MAXSIZE+1];abefi0256cdgh1347899MAXSIZE4.2.3模式匹配設s和t是給定的兩個串，在主串s中查找子串1.簡單的模式匹配算法（BF算法）（1）算法思想：例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”s：acabaabaabcacaabct：abaabcaci=1j=1s：acabaabaabcacaabct：abaabcaci=2j=2if（s[i]==t[j]）{i++；j++；}if（s[i]！=t[j]）{i回溯到本趟開始的下一個；j回溯到1；}1.簡單的模式匹配算法（BF算法）（1）算法思想：例s：acabaabaabcacaabct：abaabcaci=2j=1s：acabaabaabcacaabct：abaabcaci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5i=8j=6s：acabaabaabcacaabct：abaabcaci=4j=1s：acabaabs：acabaabaabcacaabct：abaabcaci=5j=1i=6j=2s：acabaabaabcacaabct：abaabcaci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j=8i=14j=9（2）算法實現(xiàn)循環(huán)條件？什么時候回溯？回溯時i、j如何計算？如何判斷匹配是否成功？匹配成功時，返回的起始位置如何計算？見P59的算法4-4s：acabaab2.改進后的模式匹配算法（KMP算法）s：acabaabaabcacaabct：abaabcaci=8j=6s：acabaabaabcacaabct：abaabcaci=8k=3（1）KMP算法思想：i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑動到某個位置k。2.改進后的模式匹配算法（KMP算法）s：（2）k位置的確定——next函數(shù)用next函數(shù)來確定k的值，即k=next（j）；j12345678模式串abaabcacnext（j）

[例4-1]求模式串“abaabcac”的next函數(shù)值next(j)=max{k|1<=k<j且”t1t2…tk-1”=”tj-k+1tj-k+2…tj-1”1其他情況0j=101122312（2）k位置的確定——next函數(shù)用next函數(shù)來確定k的值練習：求下列模式串的next函數(shù)值AAABAABAACAABABAABRACADABRAASSTACASTRA練習：求下列模式串的next函數(shù)值例：主串S:“aabcbabcaabcaababc”模式串t:“abcaababc”j123456789模式串abcaababcnext[j]

011122323s：aabcbabcaabcaababct：abcaababci=1j=1i=2j=2s：aabcbabcaabcaababct：abcaababci=2j=1i=3j=2i=4j=3i=5j=4例：主串S:“aabcbabcaabcaababc”jj123456789模式串abcaababcnext[j]

011122323s：aabcbabcaabcaababct：abcaababci=5j=1s：aabcbabcaabcaababct：abcaababci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7s：aabcbabcaabcaababct：abcaababci=12j=3i=13j=4i=14j=5i=15j=6i=16j=7i=17j=8i=18j=9i=19j=10j123456789模式串a（3）KMP算法實現(xiàn)循環(huán)條件？什么時候回溯？回溯時i、j如何計算？如何判斷匹配是否成功？匹配成功時，返回的起始位置如何計算？見P61的算法4-5（3）KMP算法實現(xiàn)循環(huán)條件？見P61的算法4-5（4）如何求next函數(shù)next[1]=0;設next[i-1]=k，如何求next[i]？（令j=i）j123456789模式串abcabcdbcnext[j]0i=2j=1k=next[j]=01next(j)=max{k|1<=k<j且”t1t2…tk-1”=”tj-k+1tj-k+2…tj-1”1其他情況0j=1第一種情況：k==0next[i]=k+1；

（4）如何求next函數(shù)next[1]=0;j123第二種情況:t[k]==t[j]j123456789模式串abcabcdbcnext[j]011123i=6j=5next[i]=k+1；

k=2第二種情況:t[k]==t[j]j1234第三種情況：t[k]≠t[j]

j123456789模式串abaababbanext[j]0112234i=8j=73（1）回溯k=next[k]直至t[j]==t[k]j123456789模式串abcabcdbcnext[j]0111234i=8j=71（2）回溯k=next[k]直至k==0k=4k=2k=4k=1k=0next[i]=k+1；next[i]=k+1；第三種情況：t[k]≠t[j]j123j123456789模式串abcaababcnext[j]

0i=2：j=1，k=next[1]=0next[i]=k+1=1i=3：j=2，k=next[2]=1，t[k]≠t[j]，k回溯111k=next[1]=0next[i]=k+1=1i=4：j=3，k=next[3]=1，t[k]≠t[j]，k回溯k=next[1]=0next[4]=k+1=1求next[i]：i=1next[i]=