【正文】 比較順序串S、T的大小，如果ST則返回正數(shù),如果S=T則返回0,否則返回負(fù)數(shù)。}（7）串的替換操作int Replace_SS(SString amp。 /*將剩余部分復(fù)制到S1中*/ while(S[i++]=T[j++])。 (str1,sizeof(str1))。 n=StrCompare_SS(s1,s2)。 couts1+s2的長度=l3endl。 ()。用堆分配存儲(chǔ)表示串的方法是：在程序執(zhí)行過程中，根據(jù)串變量值的大小，在堆空間中動(dòng)態(tài)分配一個(gè)連續(xù)的地址空間來存儲(chǔ)串變量中的字符，這樣既可以避免產(chǎn)生串操作中的“截?cái)唷爆F(xiàn)象又能合理使用內(nèi)存空間資源。 while(str[len])len++。int Length_HS(HString S){return()。 return((int)([i][i]))。T,HString S1,HString S2)該操作計(jì)算串SS2的連接串T。 while([i++]=[k++])。 for(i=0。S,int pos,HString H){ int i,j,k。 //取S中pos前段內(nèi)容 k=i。}（8）串替換操作的算法int Replace_HS(HString amp。 //重新分配儲(chǔ)存空間 for(i=0。 S=S1。 StrAssign_HS(S1,ss1)。 else coutS1==S2\n。 cout(6)串插入操作：\n請(qǐng)輸入插入位置:。 cout(7)串替換操作；\n輸入替換子串的位置和長度(pos len):\n。 }}3．堆分配存儲(chǔ)表示的特點(diǎn)從以上串基本操作的算法可以看出，堆分配存儲(chǔ)結(jié)構(gòu)的串既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理方便，同時(shí)在操作中對(duì)串的長度又沒有任何限制，更顯靈活，因此該存儲(chǔ)結(jié)構(gòu)在有關(guān)字符串處理的應(yīng)用程序中常被采用。 //塊內(nèi)的字符數(shù)組 Chunk* next。如果塊選取的充分大時(shí)（可在一個(gè)塊中存儲(chǔ)串的所有字符）即為定長存儲(chǔ)；如果每個(gè)塊只放一個(gè)字符時(shí)即為鏈表存儲(chǔ)。如果在串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個(gè)位置開始首次出現(xiàn)的位置 int i=pos1,j=0。 //若匹配成功，則返回T首次出現(xiàn)的開始位置 else return(0)。此算法可使時(shí)間復(fù)雜度在O(m+n)的數(shù)量級(jí)上完成串的模式匹配操作。 //計(jì)算模式串T的長度n while(in1) { if(k==1||T[i]==T[k]) next[++i]=++k。p[i][j]。(4) 此時(shí)i的值+1,j=7，分別指向S的下一個(gè)‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]，轉(zhuǎn)入（2）繼續(xù)。 int *next=new int[m]。 //回溯模式指針j } if(j=m) return(im+1)。 cout輸入位置pos:\n。 num){ int i=0,j=0。 j=0。 int *next=new int[m]。i++。 coutinput string T:\n。如果操作成功函數(shù)返回值1，否則返回值0。}【】應(yīng)用BF模式匹配函數(shù)IndexBF_SS(S,T,pos)實(shí)現(xiàn)算法：int Replace_H(HString amp。}演示程序代碼串替換函數(shù)Replace_S()、Replace_H()的函數(shù)調(diào)用演示程序void main (){ SString S1,T1,V1。(V1,MAXLEN)。}(程序運(yùn)行結(jié)果略)【】編程計(jì)算定長存儲(chǔ)串S中所含不同字符的總數(shù)以及該串中每個(gè)字符的個(gè)數(shù)。int n。jk。i++) { couta[i].ch39。StrAssign(t,Concat(s,”S”))。4．設(shè)S1=“abcdefg”，S2=“pqrst”，函數(shù)Con(x,y)返回x和y的連接串，Subs(S,i,j)返回S中從i個(gè)字符開始的j個(gè)字符組成的子串，Len(S)返回S的長度，則Con(Subs(S1,2,Len(S2)),Subs(S1,Len(S2),2))的結(jié)果是（ ）。n)，該操作計(jì)算T中出現(xiàn)的第一個(gè)最長重復(fù)子串的位置m及其長度n。 上機(jī)實(shí)驗(yàn)本章上機(jī)實(shí)驗(yàn)的主要目的在于使學(xué)生熟悉掌握串類型數(shù)據(jù)的實(shí)現(xiàn)方法和文本模式匹配方法，熟悉文字處理軟件的基本設(shè)計(jì)方法，以及對(duì)于較為復(fù)雜問題的分解求精方法?！緦?shí)現(xiàn)提示】（1）串的數(shù)據(jù)類型HString應(yīng)定義為：struct HString{ char *ch?！读?xí)題參考答案》一、簡答題1．空串和空格串有和不同？2．兩個(gè)字符串相等的充要條件是什么？3．串的3種存儲(chǔ)表示方法是什么？4．分別寫出下面各個(gè)模式串的next數(shù)組：（1）aaabcaab (2)abcabca (3)babbabab (4)abcaabbabcabaac（1）{1 0 1 2 0 0 1 2}，（2）{1 0 0 0 1 2 3}，（3）{1 0 0 1 1 2 3 2}，（4）{1 0 0 0 1 1 2 0 1 2 3 4 2 1 1}5．設(shè)s=”I AM A STUDENT”，t=”GOOD”，q=”WORKER”，下面各個(gè)操作的結(jié)果是什么？(1) StrLength(s)；(2) StrLength(t)；(3) SubString(s,8,7)；(4) SubString(t,2,1)；(5) Index(s,”A”)；(6) Replace(s,”STUDENT”,q)；(7) Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。}二、填空題1．串是一種特殊的線性表，其特殊性主要體現(xiàn)在（1）串中的元素只能是字符，而線性表中的數(shù)據(jù)元素可以是如何類型的數(shù)據(jù)；（2）串的操作對(duì)象是串和子串，而線性表的操作對(duì)象是數(shù)據(jù)元素。 if(!=)return(0)。 coutinput string T:。S,SString T) { for(int i=0。}void main(){ int n。 n=SubsNum(S,T)。i++)if(next[i]m)m=next[i]。str[i]=T[i]。 GetNext(str,next)。 //計(jì)算下一個(gè)next數(shù)組 max=Max(next,k)。 MaxNext(S,m,n)。?39。} //若不相等，則重新開始新一輪比較 } if(j==) return(i+1)。}}7．假定串以定長順序存儲(chǔ)，設(shè)計(jì)一個(gè)求最長公共子串的算法MaxSubs(S,T,amp。 m=1,n=0。 HString S,T。 MaxSubs(S,T,m,n)。 coutinput string T:。i) { pos=1。void MaxSubs(HString S,HString T,int amp。void Replace(HString amp。 //若字符相等或有一個(gè)字符為39。 if()return(0)。 SString S。k=len1。 //str中追加追加一個(gè)非零字符39。n){ int len=Length_SS(T),i,k,max。n)，該操作計(jì)算T中出現(xiàn)的第一個(gè)最長重復(fù)子串的位置m及其長度n。 coutinput string T:。int SubsNum(SString S,SString T){ int num=0,pos=1,len=Length_SS(T)。 if(Equal(S,T))coutS=T\n。}void main(){ char s1[255],s2[255]。5．在串模式匹配的BF算法中，如果主串S=“ababcabcacbab”，模式串T=“abcac”，匹配過程中的元素比較次數(shù)為（16）次，如果用KMP算法，其比較次數(shù)為（12）次。StrAssign(u,”XYXYXYXYXYXY”)。 //100為串?dāng)?shù)目的最大值 int CurNum。系統(tǒng)具有以下基本功能：（1）串賦值；（2）判斷兩個(gè)串是否相等；（3）串聯(lián)接；（4）求串的長度；（5）求子串；（6）子串定位；（7）串替換；（8）顯示串內(nèi)容；（9）串刪除；（10）退出。7．假定串以定長順序存儲(chǔ)，設(shè)計(jì)一個(gè)求最長公共子串的算法MaxSubs(S,T,amp。2．設(shè)串以定長順序存儲(chǔ)，設(shè)計(jì)一個(gè)串復(fù)制操作的算法CopyStr(S,T)，將T的內(nèi)容復(fù)制到S。Printf(“%s%s%s%s%s%s”,”t=”,t,”,v=”,v,”,u=”,Replace(u,v,w))。 } coutendl。 a[k++].n=1。 char ch。以及該類型的數(shù)組a[]，其中ch表示字符串S中的不同字符，n表示字符出現(xiàn)的次數(shù)。 if(Replace_S(S1,T1,V1)) cout定長替換結(jié)果為:\nS1endl。(S1,MAXLEN)。S,HString T, HString V){ int n,pos=1,lt=,lv=。 int lt=Length_SS(T),lv=Length_SS(V)。 coutIndex_BF:\nn=n1,num=num1endl。}void main(){ SString S,T。 while(inamp。 num)的功能是通過KMP算法返回串T在S中首次出現(xiàn)的位置，參數(shù)num表示匹配過程中字符元素的比較次數(shù)。amp。}【】編寫程序，分別計(jì)算模式匹配過程中，BF算法和KMP算法的字符比較次數(shù)。 cout輸入主串S:\n。amp。那么，可以算出用BF算法時(shí)的比較次數(shù)為29次。下面給出KMP模式匹配算法的比較過程：首先求得模式T的next數(shù)組為next[]={1,0,1,2,3,4,5,6}，主串與模式串的字符下標(biāo)初值為i=0,j=0。 for(i=0。令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。由于每趟比較都是在最后一個(gè)字符出現(xiàn)不相等，此時(shí)需要將初始位置指針i回溯到i+1的位置上，并從模式的第一個(gè)字符開始重新比較。T[j]) { if(S[i+j]==T[j])j++。顯然這里隱含要求模式串T不能為空串?？偟膩碚f，用鏈表作為串的存儲(chǔ)方式是不太實(shí)用的。 //串的長度}。由于串長不一定是結(jié)點(diǎn)大小的整數(shù)倍，所以在鏈表的最后一個(gè)結(jié)點(diǎn)不一定能被串中的字符占滿，此時(shí)可補(bǔ)上若干個(gè)非串值字符‘’（或其它非串值字符）。 (ss1,sizeof(ss1))。 (ss1,sizeof(ss1))。 cout(5)取子串操作：\n輸入取子串的位置和長度(pos len):\n。 cout(3)串比較操作：\n比較大小的結(jié)果為：。 int n,pos,len。j。 HString S1。 //將H插入 while([i++]=[k++])。 =new char[+1]。