【正文】 s2)。 if(n0)couts1s2\n。 else couts1s2\n。 cout(4)串連接操作：\ns1+s2=s3endl。 couts1+s2的長度=l3endl。 cinposlen。 else cout位置不正確\n。 cinposlen。 ()。 StrAssign_SS(T,str1)。 else cout替換不成功!\n。由于串操作基本上是以串整體的形式參與，在應(yīng)用程序中串變量的長度相差較大，并且在操作中串值長度的變化也比較大。用堆分配存儲表示串的方法是：在程序執(zhí)行過程中，根據(jù)串變量值的大小，在堆空間中動態(tài)分配一個連續(xù)的地址空間來存儲串變量中的字符，這樣既可以避免產(chǎn)生串操作中的“截?cái)唷爆F(xiàn)象又能合理使用內(nèi)存空間資源。 //串變量中字符數(shù)組的首地址 int length。2．在堆分配存儲結(jié)構(gòu)中串基本操作的C++程序?qū)崿F(xiàn)（1）串的賦值操作void StrAssign_HS(HString amp。void StrAssign_HS(HString amp。 while(str[len])len++。 if(!len)=NULL。 //在堆內(nèi)存中分配相應(yīng)大小的存儲空間 for(i=0。i++)。int Length_HS(HString S){return()。int StrComp_HS(HString S,HString T){ int i。iamp。i。 return((int)([i][i]))。S)該操作清空串S所占的堆空間。S){ if() { delete[]。 =0。T,HString S1,HString S2)該操作計(jì)算串SS2的連接串T。T,HString S1,HString S2){ int i,j,k。 i=j=k=0。 //分配鏈接串的儲存空間 while([i++]=[j++])。 while([i++]=[k++])。Sub,HString S,int pos,int len)該操作求串S中pos個字符開始的len個字符組成的子串Sub，如果位置合理返回1否則返回0。Sub,HString S,int pos,int len){ int i。 //如果位置不合理時返回0值 =new char[len+1]。 for(i=0。i++) [i]=[pos+i1]。 return(1)。S,int pos,HString H)該操作在串S的第pos個字符前面插入字符串H，如果位置合理返回1，否則返回0。S,int pos,HString H){ int i,j,k。 if(pos1||pos+1) return 0。 =new char[+1]。ipos1。 //取S中pos前段內(nèi)容 k=i。j 。 //將H插入 while([i++]=[k++])。 S=S1。}（8）串替換操作的算法int Replace_HS(HString amp。int Replace_HS(HString amp。 HString S1。 //長度或位置不合理 =+。 //重新分配儲存空間 for(i=0。i++)[i]=[i]。j。 //取T中的內(nèi)容 while([i++]=[k++])。 S=S1。}（9）主函數(shù)演示程序main()void main_HS(){ HString S1,S2,S,sub,V,T。 int n,pos,len。 (ss1,sizeof(ss1))。 StrAssign_HS(S1,ss1)。cout(2)求串長操作：\nlen1=Length_HS(S1)endl。 cout(3)串比較操作：\n比較大小的結(jié)果為：。 if(n0) coutS1S2\n。 else coutS1==S2\n。 cout(4)串連接操作：\n:s1+s2=endl。 cout(5)取子串操作：\n輸入取子串的位置和長度(pos len):\n。 if(SubString_HS(sub,S,pos,len)) coutsub=endl。 cout(6)串插入操作：\n請輸入插入位置:。()。 (ss1,sizeof(ss1))。 if(StrInsert_HS(S,pos,V)) cout插入結(jié)果為 s=endl。 cout(7)串替換操作；\n輸入替換子串的位置和長度(pos len):\n。()。 (ss1,sizeof(ss1))。 if(Replace_HS(S,pos,len,T)) cout結(jié)果為 s=endl。 }}3．堆分配存儲表示的特點(diǎn)從以上串基本操作的算法可以看出，堆分配存儲結(jié)構(gòu)的串既有順序存儲結(jié)構(gòu)的特點(diǎn)，處理方便，同時在操作中對串的長度又沒有任何限制，更顯靈活，因此該存儲結(jié)構(gòu)在有關(guān)字符串處理的應(yīng)用程序中常被采用。由于串中的每個數(shù)據(jù)元素是一個字符，在用鏈表存儲串值時，存在一個“結(jié)點(diǎn)大小”的問題，即每個結(jié)點(diǎn)最多可以存放多少個串中字符。由于串長不一定是結(jié)點(diǎn)大小的整數(shù)倍，所以在鏈表的最后一個結(jié)點(diǎn)不一定能被串中的字符占滿，此時可補(bǔ)上若干個非串值字符‘’（或其它非串值字符）。稱如此定義的串的存儲結(jié)構(gòu)為串的塊鏈?zhǔn)酱鎯Y(jié)構(gòu)。 //塊內(nèi)的字符數(shù)組 Chunk* next。 //塊結(jié)構(gòu)的類型定義struct LString{ Chunk *head,*tail。 //串的長度}。設(shè)尾指針的目的是為了便于進(jìn)行串的連接操作，在串連接時需要處理第一個串尾結(jié)點(diǎn)中的無效字符。如果塊選取的充分大時（可在一個塊中存儲串的所有字符）即為定長存儲；如果每個塊只放一個字符時即為鏈表存儲。顯然，存儲密度?。ū热缑總€塊存放1個字符時ρ=20%），運(yùn)算處理方便，但是存儲占用量大；存儲密度大（比如每個塊存放80個字符時ρ=20/21=95%），雖然存儲占用量小，但是串值的運(yùn)算處理（比如串的插入、刪除、連接和替換等操作）不太方便?？偟膩碚f，用鏈表作為串的存儲方式是不太實(shí)用的。設(shè)S和T是兩個給定的串，在串S中尋找串值等于T的子串的過程稱為模式匹配。如果在串S中找到等于串T的子串，則稱匹配成功；否則匹配失敗。模式匹配的操作記為Index(S,T,pos)，該函數(shù)的功能是，從串S的第pos個字符開始的字符序列中查找值等于T的子字符串。顯然這里隱含要求模式串T不能為空串。算法的基本思想是：從主串S的第pos個字符起和模式T的第一個字符比較，若相等，則繼續(xù)逐個比較后面的字符；否則從主串S的下一個字符起再重新和模式T的第一個字符開始逐個比較。BF算法表示的串查找函數(shù)int IndexBF_SS(SString S,SString T,int pos)的C++語言表示為：int IndexBF_SS(SString S,SString T,int pos=1){//求子串T在S中從pos個位置開始首次出現(xiàn)的位置 int i=pos1,j=0。 while(S[i+j]amp。T[j]) { if(S[i+j]==T[j])j++。 j=0。 //若匹配成功，則返回T首次出現(xiàn)的開始位置 else return(0)。但是在有些情況下，該算法的效率很低。由于每趟比較都是在最后一個字符出現(xiàn)不相等，此時需要將初始位置指針i回溯到i+1的位置上，并從模式的第一個字符開始重新比較。所以，在最壞的情況下BF算法的時間復(fù)雜度為O(mn)。此算法可使時間復(fù)雜度在O(m+n)的數(shù)量級上完成串的模式匹配操作。為此需要引入一個有關(guān)模式串T的整型數(shù)組next，其中第j個元素next[j1]表示當(dāng)模式串T中的第j個字符與主串S中相應(yīng)字符匹配失敗時，在模式T中需要重新和主串S中該字符進(jìn)行比較的字符的下標(biāo)值。令k=next[j]，（1）如果k=1或T[j]=T[k],則轉(zhuǎn)入步驟(3)（2）取k=next[k],再重復(fù)操作(1)、(2)（3）next[j+1]=k+1。 next[0]=1。 //計(jì)算模式串T的長度n while(in1) { if(k==1||T[i]==T[k]) next[++i]=++k。 }}void main(){ char p[6][50]={ababcabcacbab,abaabcac,aaabcaab,abcabca,babbabab,abcaabbabcabaac}。 for(i=0。i++) { GetNext(p[i],next)。p[i][j]。 //顯示輸出p[i]的next數(shù)組 coutendl。下面給出KMP模式匹配算法的比較過程：首先求得模式T的next數(shù)組為next[]={1,0,1,2,3,4,5,6}，主串與模式串的字符下標(biāo)初值為i=0,j=0。 (2) 取j為next[j]=next[7]的值6，即j=6指向T中第7個‘a(chǎn)’(表示模式T向后滑動76=1個字符)。(4) 此時i的值+1,j=7，分別指向S的下一個‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]，轉(zhuǎn)入（2）繼續(xù)。(6) i++,j++操作后j=m(m為T的長度8)，循環(huán)結(jié)束，返回im+1。那么，可以算出用BF算法時的比較次數(shù)為29次。4．KMP模式匹配算法的實(shí)現(xiàn)KMP模式匹配算法int Index_KMP(SString S,SString T,int pos)的C++語言實(shí)現(xiàn)int Index_KMP(SString S,SString T,int pos=1){ int i=pos1,j=0。 int *next=new int[m]。 //位置不合理返回0值 GetNext(T,next)。amp。i++。 //回溯模式指針j } if(j=m) return(im+1)。}void main(){ SString S,T。 cout輸入主串S:\n。 cout輸入子串T:\n。 cout輸入位置pos:\n。 if(n=Index_KMP(S,T,pos)) cout首次匹配地址為:nendl。}【】編寫程序，分別計(jì)算模式匹配過程中，BF算法和KMP算法的字符比較次數(shù)。 num)的功能是通過BF算法返回串T在S中首次出現(xiàn)的位置，參數(shù)num表示匹配過程中元素的比較次數(shù)。 num){ int i=0,j=0。 if(Length_SS(T)Length_SS(S)) return(0)。amp。 if(S[i+j]==T[j])j++。 j=0。 //若匹配成功，則返回T首次出現(xiàn)的開始位置 else return(0)。 num)的功能是通過KMP算法返回串T在S中首次出現(xiàn)的位置，參數(shù)num表示匹配過程中字符元素的比較次數(shù)。 num){ int i=0,j=0。 int *next=new int[m]。 //匹配不成功返回0值 GetNext(T,next)。 while(inamp。jm) { if(j!=1)num++。i++。 //回溯模式指針j } if(j=m) return(im+1)。}void main(){ SString S,T。 while(1) { coutinput s