【正文】 n。 ()。 else cout位置不正確\n。 couts1+s2的長度=l3endl。 else couts1s2\n。 n=StrCompare_SS(s1,s2)。 StrAssign_SS(s2,str2)。 (str1,sizeof(str1))。}（8）主函數(shù)演示程序main()void main_SS(){ SString s1,s2,s3,sub,T。 /*將剩余部分復(fù)制到S1中*/ while(S[i++]=T[j++])。 int len=Length_SS(T)。}（7）串的替換操作int Replace_SS(SString amp。T[i]amp。}（6）串比較操作int StrCompare_SS(SString S,SString T)該操作比較順序串S、T的大小，如果ST則返回正數(shù),如果S=T則返回0,否則返回負(fù)數(shù)。T,SString S)該操作將定長順序串S，復(fù)制到定長順序串T。amp。amp。如果不產(chǎn)生截斷（長度合理）返回1，否則返回0。\039。 if(pos1||len0||pos+lenLength_SS(S)+1) return 0。 /*判斷是否產(chǎn)生截斷*/ else return(1)。 } T[i]=0。 while(iMAXLENamp。T,SString S1,SString S2){ int i,j,k。 return(i)。1．定長順序存儲結(jié)構(gòu)在C++運(yùn)行環(huán)境中，定長順序結(jié)構(gòu)定義為：includeincludedefine MAXLEN 255 //定義串的最大長度為255typedef char SString[MAXLEN+1]。既然串是線性表的特例，所以線性表的兩種存儲結(jié)構(gòu)對于串也是適用的。（9）串插入StrInsert(amp。Sub,S,pos,len) 以串S中pos位置開始的len個字符生成子串Sub的操作。（4）求串長度StrLength(S) 返回串S的長度。T,chars) 由字符串常量chars生成字符串T的操作。在串操作中不要將空格串和空串混淆。3．串的比較如果兩個串的長度相等且對應(yīng)位置上的字符相同，則稱這兩個串相等。顯然，在不考慮空子串的情況下，一個長度為n的字符串具有n(n+1)/2個子串。從串的定義可以看出，串實(shí)際上是數(shù)據(jù)元素為字符的特殊的線性表。字符串在計算機(jī)處理實(shí)際問題中使用非常廣泛，比如人名、地名、商品名、設(shè)備名等均為字符串。同樣在文字編輯、自然語言理解和翻譯、源程序的編輯和修改等方面，都離不開對字符串的處理。例如：（1）A=“X123” (長度為4的串)（2）B=“12345654321” (長度為11的串)（3）C=“Bei Jing” (長度為8的串)（4）D=“” (長度為0的空串)（5）E=“This is a string” (長度為16的串)（6）F=“ is a ” (長度為6的串)2．子串、主串和位置串中任意連續(xù)的字符組成的子序列稱為該串的子串；相應(yīng)地，包含子串的串稱為主串。例如：在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。兩個串A、B的比較過程是：從前往后逐個比較對應(yīng)位置上的字符的ASCII碼值，直到不相等或有一個字符串結(jié)束為止，此時的情況有以下幾種：（1）兩個串同時結(jié)束，表示A等于B；（2）A中字符的ASCII碼值大于B中相應(yīng)位置上字符的ASCII碼值或B串結(jié)束，表示A大于B；（3）B中字符的ASCII碼值大于A中相應(yīng)位置上字符的ASCII碼值或A串結(jié)束，表示A小于B。盡管串的定義和線性表極為相似，但是串的基本操作和線性表有很大差別。（2）串復(fù)制StrCopy(amp。（5）串連接Concat(amp。（7）串查找Index(S,T,pos) 返回子串T在S中pos個字符以后出現(xiàn)的位置。S,pos,T) 在串S中第pos個字符前插入串T的操作。在應(yīng)用中具體選用何種存儲結(jié)構(gòu)與串的操作有關(guān)，比如對串進(jìn)行插入和刪除操作運(yùn)算時選用鏈存儲結(jié)構(gòu)較好，對串進(jìn)行查找和求子串運(yùn)算時選用順序存儲結(jié)構(gòu)較好。 //定義定長順序存儲類型SString2．基本操作的C++程序?qū)崿F(xiàn)（1）求串長度操作int Length_SS(SString S)操作返回串S中所含字符的個數(shù)，即串的長度；如果S為空串則返回0。}（2）串連接操作int Concat_SS(SString amp。 i=j=k=0。amp。 if((i==MAXLEN)amp。}（3）求子串操作int SubString_SS(SString amp。 /*判斷位置和長度是否合理*/ while(ilen) {Sub[i]=S[i+pos1]。 return 1。int StrAssign_SS(SString amp。(T[i]=s[i]))i++。s[i]) return 0。void StrCopy_SS(SString amp。int StrCompare_SS(SString S,SString T){ int i=0。amp。S,int n,int m,SString T)該操作將串S中從第n個字符開始的連續(xù)的m個字符替換成串T中的字符，如果n和m的選取合理則返回1，否則返回0。 int i=n1,j=0,k=n+m1。 /*替換S中指定部分的字符*/ i。 char str1[100],str2[100]。/*表示從鍵盤輸入一個可以含有空格字符的長度小于100的字符串到str1中，語句 “cinstr1”不能輸入空格字符（空格符表示輸入結(jié)束）且對串的長度不做檢查。 l1=Length_SS(s1)。 cout(3)串比較操作：\n比較結(jié)果為: 。 Concat_SS(s3,s1,s2)。cout(5)求子串操作：\n輸入開始位置和串長(pos len):\n。 cout(6)串替換操作：\n輸入替換的位置和字符數(shù)(pos len):。 (str1,sizeof(str1))。 }}（程序運(yùn)行過程略）3．定長順序存儲的特點(diǎn)對于定長順序存儲的串在基本操作方面主要有以下特點(diǎn)：（1）對于求串長度和串的復(fù)制操作而言，其時間復(fù)雜度依賴于字符串的長度；（2）在串刪除和串插入操作時必須移動大量的字符；（3）如果在串輸入、串連接、串插入和串替換操作中串值的長度超過MAXLEN，則按約定采取“截尾”法處理，這將導(dǎo)致操作結(jié)果的不合理。1．串的堆分配存儲結(jié)構(gòu)在C++運(yùn)行環(huán)境中，堆分配存儲結(jié)構(gòu)定義為struct HString{ char *ch。T,char str[])該操作由字符串常量str生成一個HString型串T。 //計算串的長度 =len。[i]=str[i]。 }（3）串的比較操作int StrComp_HS(HString S,HString T)該操作比較串S、T的大小。amp。 }（4）串的清空操作void ClearString_HS(HString amp。 =NULL。void Concat_HS(HString amp。 =new char[+1]。 //將S2連接到T的末尾}（6）求子串的算法int SubString_HS(HString amp。 if(pos1||len1||pos+len+1) return(0)。ilen。}（7）串插入操作的算法int StrInsert_HS(HString amp。 HString S1。 //重新分配空間 for(i=0。 for(j=0。 //取S中剩余的內(nèi)容 delete[]。S,int n,int m,HString T)該操作將串S中第n個字符開始的m個字符替換為串T，如果位置n和字符數(shù)m合理返回1否則返回0。 if(n1||m0||n+m+1)return(0)。in1。j++)[i++]=[j]。 return(1)。 while(1) { cout(1)串初始化操作：\n輸入兩個字符串:\n。 StrAssign_HS(S2,ss2)。 n=StrComp_HS(S1,S2)。 Concat_HS(S,S1,S2)。 cinposlen。 cinpos。 StrAssign_HS(V,ss1)。 cinposlen。 StrAssign_HS(T,ss1)。1．塊鏈?zhǔn)酱鎯Φ母拍詈途€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，可以采用鏈表方式存儲串。為了便于進(jìn)行串的操作，當(dāng)以鏈表存儲串值時，除了頭指針head外還可以附設(shè)一個指向尾結(jié)點(diǎn)的指針tail，并給出當(dāng)前串的長度。 //指向下一個結(jié)點(diǎn)的指針}。 //塊鏈?zhǔn)浇Y(jié)構(gòu)的類型定義在一般情況下，對串的操作只需要從前向后掃描即可，故對串值不必建立雙向鏈表。為了便于研究串值的存儲效率我們給出如下存儲密度的計算公式：假定next指針變量占用4個字節(jié)，每個字符占用1個字節(jié)，每個塊中存放m個字符，那么串值的存儲密度可以表示為ρ=m/(m+4)。因此，串的塊鏈?zhǔn)酱鎯Y(jié)構(gòu)不如定長順序存儲和堆分配存儲結(jié)構(gòu)靈活，它占用存儲空間大且操作復(fù)雜。模式匹配是各種串處理系統(tǒng)中最重要的操作之一。在串的模式匹配算法中，最簡單、最直觀的算法是BF（BruteForce,布魯特福斯）算法，在該算法中，分別利用指針i和指針j指示主串S和模式T中當(dāng)前正待比較的字符下標(biāo)。if(i0||pos+Length_SS(T)Length_SS(S)+1) return(0)。 //若字符相等，則繼續(xù)比較后續(xù)字符 else {i++。 //若匹配不成功，則返回0}算法分析：在一般情況下，BF算法的時間復(fù)雜度為O(m+n)，其中m,n分別為串S和T的長度。初始位置指針i一共要回溯527=45次，總的比較次數(shù)為：8(45+1)=368次。1．模式的next數(shù)組模式匹配的KMP算法是，每當(dāng)一趟匹配比較過程中出現(xiàn)字符不相同的情況時，不需要回溯指針i,而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式T向右“滑動”盡可能遠(yuǎn)的一段距離后，再繼續(xù)進(jìn)行比較。計算next數(shù)組的算法void GetNext(char* T,int* next)用C++語言實(shí)現(xiàn)如下void GetNext(char* T,int* next){ int i=0,k=1,n=0。 else k=next[k]。i6。j++)coutnext[j] 。(1) 連續(xù)比較8次時，i=7,j=7，此時分別指向S的第8個‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]。(5) 重復(fù)(2)、(3)、(4)的步驟527=45次后，i、j均指向最后的字符‘b’,即S[i]=T[j]。而用KMP算法的比較過程為：(1) 比較5次后滑動模式T:j=next[4]=0,即向右滑動4個字符，此時j=0,i=4；(2) 再次連續(xù)比較5次后將模式T向右滑動4個字符，此時j=0,i=9；以此類推，共需要比較的次數(shù)為54=20次（）。 //定義模式T的next數(shù)組 if(i0||pos+mn+1) return