【正文】 _SS(T), n=Length_SS(S)。從以上分析的比較過程可知，總的比較次數(shù)為：7+2(527)+1=98次（）再如：主串為S=“abcdabcdabcdabcde”，模式串為T=“abcde”,則next={1,0,0,0,0}。(3) 比較S[i]和T[j]，均為‘a(chǎn)’相同，i++,j++。 }}運行結(jié)果為：1 0 0 1 2 0 1 2 0 1 0 0 11 0 0 1 1 2 0 11 0 1 2 0 0 1 21 0 0 0 1 2 31 0 0 1 1 2 3 21 0 0 0 1 1 2 0 1 2 3 4 2 1 13．KMP模式匹配算法的比較過程假設(shè)主串為S=“aaaaaa……aaaaab”（其中共有52個‘a(chǎn)’和1個‘b’），模式串為T=“aaaaaaab”（其中共有7個‘a(chǎn)’和1個‘b’）。 //計算模式串p[i]的next數(shù)組 for(j=0。 int next[50],i,j。 while(T[n])n++。next數(shù)組定義為：其中next[j]=k表明，存在整數(shù)k滿足條件0kj，并且在模式T中存在下列關(guān)系：“T[0]T[1]…T[k1]”=“T[jk]T[jk+1]…T[j1]”，而對任意的整數(shù)k1(0kk1j)都有：“T[0]T[1]…T[k11]”≠“T[jk1]T[jk1+1]…T[j1]”例如：（1）模式T=“aaaaaaab”的next數(shù)組為next={1,0,1,2,3,4,5,6}（2）模式T=“abaabcac”的next數(shù)組為next={1,0,0,1,1,2,0,1}（3）模式T=“ababcabcacbab”的next數(shù)組為next={1,0,0,1,2,0,1,2,0,1,0,0,1}2．next數(shù)組的算法實現(xiàn)由定義可知，next[0]=1,next[1]=0，假設(shè)現(xiàn)已求得next[0],next[1], …,next[j],那么可以采用以下遞推的方法求出next[j+1]。,，稱之為克努特莫里斯普拉特操作，簡稱KMP算法，他是一種改進的模式匹配算法。例如：S=“aaaaaa……aaaaab”共有52個‘a(chǎn)’和1個‘b’,T=“aaaaaaab”共有7個‘a(chǎn)’和1個‘b’。} //若不相等，則重新開始新一輪比較 } if(!T[j]) return(i+1)。amp。以此類推，直至模式T中的每個字符依次和主串S中的一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)返回T的第一個字符在S中的位置，否則匹配不成功，函數(shù)返回0值。如果匹配成功，函數(shù)返回T在S中第pos個字符以后的串值中第一次出現(xiàn)的開始位置；否則函數(shù)返回0值。其中，串S稱為主串，串T稱為模式。4．塊鏈式存儲表示的特點在一般情況下，對以塊鏈式存儲表示的串進行操作時比較麻煩，比如在串中插入一個子串時可能需要分割結(jié)點，連接兩個串時，如果第一個串的最后一個結(jié)點沒有填滿，還需要添加其它字符。3．塊鏈式存儲的存儲密度在串的塊鏈式存儲結(jié)構(gòu)中，結(jié)點大小的選擇很重要，它直接影響到串處理操作的效率。 //串的頭指針和尾指針 int curlen。2．塊鏈式存儲結(jié)構(gòu)的表示在C++運行環(huán)境中，可將塊鏈式存儲結(jié)構(gòu)表示如下：define CHUNKSIZE 80 //定義每個結(jié)點的大小struct Chunk{ char ch[CHUNKSIZE]。對于串“abcdefghijk”，如果采用每個結(jié)點存放一個字符的鏈表結(jié)構(gòu)存儲，(a)所示；如果采用每個結(jié)點存放三個字符的鏈表結(jié)構(gòu)存儲，(b)所示。 else cout位置不對!\n。 cout輸入替換串T:\n。 else cout位置不對!\n。 cout輸入要插入的子串V:\n。 else cout位置不對!\n。 coutlength=Length_HS(S)endl。 else if(n0)coutS1S2\n。coutlen2=Length_HS(S2)endl。 (ss2,sizeof(ss2))。 SString ss1,ss2。 //取S中剩余的部分 delete[]。 //取S中前面的部分 for(j=0。 =new char[+1]。S,int n,int m,HString T){ int i,j,k=n+m1。 return 1。j++)[i++]=[j]。i++)[i]=[i]。 //位置不合理返回0值 =+。int StrInsert_HS(HString amp。 //將子串復制到Sub中 [i]=0。 //動態(tài)分配子串的存儲空間 =len。int SubString_HS(HString amp。 //將S1復制到T i。 =+。 }}（5）串的連接操作void Concat_HS(HString amp。void ClearString_HS(HString amp。i++) if([i]!=[i])break。 for(i=0。 // }}（2）求串長的操作int Length_HS(HString S)該操作返回串S的長度，如果S為空串則返回0。 //對空串進行初始化 else { =new char[len+1]。T,char str[]){ int len=0,i。 //串的長度}。因此，事先為串變量設(shè)置固定大小空間的數(shù)組不盡合理。 if(Replace_SS(s3,pos,len,T)) cout替換結(jié)果為:\ns3=s3endl。 cout輸入替換串:\n。 if(SubString_SS(sub,s3,pos,len)) coutsub=subendl。 l3=Length_SS(s3)。 else if(n==0)couts1=s2\n。 cout(2)求串長操作：\ns1的長度=l1，s2的長度=l2endl。 StrAssign_SS(s1,str1)。 while(1) { cout(1)串初始化操作：\n輸入兩個字符串:\n。 /*將剩余部分復制到S中*/ return(1)。/*判斷位置是否合理*/ StrCopy_SS(S1,S)。S,int n,int m,SString T){ SString S1。 return (int)(S[i]T[i])。amp。 while(T[i]=s[i])i++。}（5）串復制操作void StrCopy_SS(SString amp。 if((i==MAXLEN)amp。 while(iMAXLENamp。T,char *s)該操作用字符數(shù)組s，初始化定長順序串T。 } Sub[i]=39。Sub,SString S,int pos,int len){ int i=0。S2[k]) return(0)。k++。 i。int Concat_SS(SString amp。 while(S[i])i++。在串的定長順序存儲表示中，按照預定義的大小，為每個定長的串變量分配一個固定長度的存儲區(qū)，所以可以用定長字符數(shù)組來表示。S,pos,len) 刪除串S中第pos個字符開始的len個字符的操作。S,T,V) 將串S中所有不重疊子串T替換為串V的操作。（6）求子串SubString(amp。（3）串比較StrCompare(S,T) 若S=T返回0，ST返回正數(shù)，ST返回負數(shù)。串的基本操作主要有：（1）初始化串StrAssign(amp。4．空格串由一個或多個空格字符組成的串稱為空格串，空格串的長度為串中所含空格字符的個數(shù)。串G中第一個字符‘e’的位置是6，第二個字符‘e’的位置是11。顯然，串為其自身的子串，并規(guī)定空串為任何串的子串。其中，S是串的名字，字符序列a0a1a2…an1是串的值，ai(0≤i≤n1)可以是字母、數(shù)字或其他字符元素；由于在C語言系統(tǒng)中數(shù)組元素的下標是從0開始的，所以串中所含元素的序號等于該元素的下標值加1；串中所含字符的個數(shù)n稱為該串的長度，長度為0的字符串稱為空串（null string）。第4章 串存儲與基本操作的實現(xiàn)第四章 串存儲與基本操作的實現(xiàn)本章學習要點◆熟悉串的相關(guān)概念以及串與線性表的關(guān)系◆重點掌握串的定長存儲、堆分配存儲的表示方法與基本操作的實現(xiàn)◆了解串的各種存儲結(jié)構(gòu)，能根據(jù)需要合理選用串的存儲結(jié)構(gòu)解決實際問題“串”(string)，是字符串的簡稱，它是一種特殊的線性表，其特殊性在于組成線性表的數(shù)據(jù)元素是單個字符。1．串的定義串(string) 是由n個字符組成的有限序列，記為：S=”a0a1a2…an1” (n≥0)。串中的字符在串序列中的序號稱為該字符在該串中的位置；子串的第一個字符在主串中的位置稱為子串在主串中的位置。由于空格符也是一個字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是串G的子串。例如：“abc”=“abc”，“abc”“abcd”，“abxy”“abcdefg”，“132”“123456”，“ABab”“abAB”，“3+2”“2+3”。在線性表的基本操作中，大多以單個元素作為操作對象，比如對線性表的查找、訪問、插入、刪除和排序等；而在串的基本操作中，通常以串整體或串的一部分（子串）作為操作對象，比如子串的查找、截取子串、刪除一個子串、插入子串和子串替換等操作。T,S) 由串S復制生成串T的操作。T,S1,S2) 將串S1和S2連接起來生成串T的操作。（8）串替換Replace(amp。（10）刪除子串StrDelete(amp。本章主要介紹串的3種存儲表示方法：（1）串的定長順序存儲表示法（2）串的堆分配存儲表示法（3）串的塊鏈式存儲表示法串的定長順序存儲表示是用一組地址連續(xù)的存儲單元來存儲串中的字符序列。int Length_SS(SString S) { int i=0。T,SString S1,SString S2)該操作將串SS2連接生成串T，如果在連接過程中產(chǎn)生了截斷（即S1的長度加上S2的長度大于MAXLEN）則返回0，否則返回1。 while(T[i++]=S1[j++])。(T[i]=S2[k])){ i++。amp。Sub,SString S,int pos,int len)該操作截取串S中從第pos個字符開始的連續(xù)的len個字符生成子串Sub，如果位置pos和長度len合理則返回1，否則返回0.int SubString_SS(SString amp。 i++。 }（4）初始化串操作int StrAssign_SS(SString amp。T,char *s){ int i=0。 T[i]=0。 /*判斷是否產(chǎn)生截斷*/ else return 1。T,SString S){ int i=0。 while(S[i]amp。(S[i]==T[i]))i++。int Replace_SS(SString amp。 /*i為開始替換位置，j指向第一個替換字符，k為剩余字符的開始位置*/ if(n1||m0||n+mLength_SS(S)+1||Length_SS(S)+lenmMAXLEN) return(0)。 while(S[i++]=S1[k++