【正文】 為復(fù)雜的操作。利用串的基本操作函數(shù)構(gòu)造一個(gè)串處理系統(tǒng)，該系統(tǒng)循環(huán)往復(fù)地處理用戶輸入的每一條命令，直至出現(xiàn)終止程序的命令為止。系統(tǒng)具有以下基本功能：（1）串賦值；（2）判斷兩個(gè)串是否相等；（3）串聯(lián)接；（4）求串的長(zhǎng)度；（5）求子串；（6）子串定位；（7）串替換；（8）顯示串內(nèi)容；（9）串刪除；（10）退出。在該系統(tǒng)的執(zhí)行過(guò)程中，如果在命令行中輸入的是一個(gè)串常量，則應(yīng)首先建立它。基本操作函數(shù)的結(jié)果（即函數(shù)值）如果是一個(gè)串，則應(yīng)在尚未分配的區(qū)域內(nèi)重新分配空間存放?！緶y(cè)試數(shù)據(jù)】由設(shè)計(jì)者自行指定?！緦?shí)現(xiàn)提示】（1）串的數(shù)據(jù)類型HString應(yīng)定義為：struct HString{ char *ch。 //串變量中字符數(shù)組的首地址 int length。 //串的長(zhǎng)度}。（2）演示系統(tǒng)的主結(jié)構(gòu)是一個(gè)串頭表StrHeadList，可定義為：struct StrHeadList{ HString StrHead[100]。 //100為串?dāng)?shù)目的最大值 int CurNum。 //當(dāng)前系統(tǒng)中串的總數(shù)}。系統(tǒng)在執(zhí)行過(guò)程中，將各個(gè)串的頭指針依次存儲(chǔ)與串頭數(shù)組StrHead中（假定串的數(shù)目不超過(guò)100）。CurNum為系統(tǒng)中現(xiàn)有的串?dāng)?shù)目，CurNum+1是可為下一個(gè)新串頭指針?lè)峙涞奈恢??！读?xí)題參考答案》一、簡(jiǎn)答題1．空串和空格串有和不同？2．兩個(gè)字符串相等的充要條件是什么？3．串的3種存儲(chǔ)表示方法是什么？4．分別寫(xiě)出下面各個(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)))。6．執(zhí)行以下函數(shù)的顯示結(jié)果是什么？void demonstrate(){StrAssign(s,”THIS IS A BOOK”)。Replace(s,SubString(s,3,7),”ESE ARE”)。StrAssign(t,Concat(s,”S”))。StrAssign(u,”XYXYXYXYXYXY”)。StrAssign(v,SubString(u,6,3)。StrAssign(w,”W”)。printf(“%s%s%s%s%s%s”,”t=”,t,”,v=”,v,”,u=”,Replace(u,v,w))。}二、填空題1．串是一種特殊的線性表，其特殊性主要體現(xiàn)在（1）串中的元素只能是字符，而線性表中的數(shù)據(jù)元素可以是如何類型的數(shù)據(jù)；（2）串的操作對(duì)象是串和子串，而線性表的操作對(duì)象是數(shù)據(jù)元素。2．設(shè)有兩個(gè)串P和Q，那么求Q在P中首次出現(xiàn)的位置的運(yùn)算被稱為（串的模式匹配）。3．設(shè)串S=”I AM A TEACHER”，那么S的長(zhǎng)度為（14）。4．設(shè)S1=“abcdefg”，S2=“pqrst”，函數(shù)Con(x,y)返回x和y的連接串，Subs(S,i,j)返回S中從i個(gè)字符開(kāi)始的j個(gè)字符組成的子串，Len(S)返回S的長(zhǎng)度，則Con(Subs(S1,2,Len(S2)),Subs(S1,Len(S2),2))的結(jié)果是（”bcdefef”）。5．在串模式匹配的BF算法中，如果主串S=“ababcabcacbab”，模式串T=“abcac”，匹配過(guò)程中的元素比較次數(shù)為（16）次，如果用KMP算法，其比較次數(shù)為（12）次。6．模式p1=”abaabcac”的next函數(shù)值序列是（{1 0 0 1 1 2 0 1}）；模式p2=”abcaabbabcab”的next函數(shù)值序列是（{1 0 0 0 1 1 2 0 1 2 3 4}）。三、解答題1．設(shè)串以堆分配方式存儲(chǔ)，設(shè)計(jì)一個(gè)判等操作的算法Equal(S,T)，如果S與T相等則函數(shù)返回1，否則返回0值。int Equal(HString S,HString T){ int i=0。 if(!=)return(0)。 while(i) { if([i]!=[i])return(0)。 i++。 } return(1)。}void main(){ char s1[255],s2[255]。 HString S,T。 coutinput string S:。 (s1,255)。 coutinput string T:。 (s2,255)。 StrAssign_HS(S,s1)。 StrAssign_HS(T,s2)。 if(Equal(S,T))coutS=T\n。 else coutS!=T\n。}2．設(shè)串以定長(zhǎng)順序存儲(chǔ)，設(shè)計(jì)一個(gè)串復(fù)制操作的算法CopyStr(S,T)，將T的內(nèi)容復(fù)制到S。void CopyStr(SString amp。S,SString T) { for(int i=0。S[i]=T[i]。i++)。}3．編寫(xiě)一個(gè)算法SubsNum(S,T)，返回串T在S中重復(fù)出現(xiàn)的次數(shù)（子串不能重疊）。int SubsNum(SString S,SString T){ int num=0,pos=1,len=Length_SS(T)。 while(pos=IndexBF_SS(S,T,pos)) { num++。 pos+=len。 } return(num)。}void main(){ int n。 SString S,T。 coutinput string S:。(S,255)。 coutinput string T:。(T,255)。 coutS=Sendl。 coutT=Tendl。 n=SubsNum(S,T)。 coutT在S中重復(fù)出現(xiàn)n次.\n。}4．編寫(xiě)一個(gè)算法MaxNext(T,amp。m,amp。n)，該操作計(jì)算T中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串的位置m及其長(zhǎng)度n。int Max(int *next,int n)//計(jì)算數(shù)組next[n+1]的最大元素 { int m=next[0],i。 for(i=1。i=n。i++)if(next[i]m)m=next[i]。 return(m)。}void MaxNext(SString T,int amp。m,int amp。n){ int len=Length_SS(T),i,k,max。 //len為串長(zhǎng) int *next=new int[len+1]。 //動(dòng)態(tài)分配next數(shù)組，長(zhǎng)度=len+1 char *p,*str=new char[len+2]。 //動(dòng)態(tài)分配串str for(i=0。str[i]=T[i]。i++)。 //復(fù)制T到str中 str[i++]=39。39。 //str中追加追加一個(gè)非零字符39。39。 str[i]=39。\039。 GetNext(str,next)。 //計(jì)算str的next數(shù)組 m=1。n=Max(next,len)。 p=str+1。k=len1。 for(i=2。ilen。i++,k) //i,p為起始位置，k為剩余串的長(zhǎng)度 { GetNext(p++,next)。 //計(jì)算下一個(gè)next數(shù)組 max=Max(next,k)。 if(maxn){ m=i。n=max。 } }}void main(){ int n,m。 SString S。 coutinput string S:。 (S,sizeof(S))。 coutS=Sendl。 MaxNext(S,m,n)。 cout位置為m,重復(fù)串的最大長(zhǎng)度為n.\n。}input string S:21345345645676789034553456S=21345345645676789034553456位置為5,重復(fù)串的最大長(zhǎng)度為5.Press any key to continueinput string S:asefsdr12345sdydthf12345S=asefsdr12345sdydthf12345位置為8,重復(fù)串的最大長(zhǎng)度為5.5．假定串以堆分配方式存儲(chǔ)，編寫(xiě)一個(gè)實(shí)現(xiàn)串通配符匹配的函數(shù)Pattern_Index(S,T)，其中通配符只有’?’，它可以和任一個(gè)字符匹配成功。int Pattern_Index(HString S,HString T)//求T在S中首次出現(xiàn)的位置，字符’?’為通配符{ int i=0,j=0。 if()return(0)。 while(i+jamp。amp。j) { if([i+j]==[j]||[i+j]==39。?39。||[j]==39。?39。) j++。 //若字符相等或有一個(gè)字符為39。?39。，則繼續(xù)比較后續(xù)字符 else {i++。 j=0。} //若不相等，則重新開(kāi)始新一輪比較 } if(j==) return(i+1)。 //若匹配成功，則返回T首次出現(xiàn)的開(kāi)始位置 else return(0)。 //若匹配不成功，則返回0}6．設(shè)串以堆分配方式存儲(chǔ)，設(shè)計(jì)一個(gè)串置換操作的算法Replace(S,T,X)。該操作將S中所有不重復(fù)的子串T替換為串X。void Replace(HString amp。S,HString T,HString X){ int n,pos=1,lt=,lx=。 while(n=IndexBF_SS(,pos)) { Replace_HS(S,n,lt,X)。 pos=n+lx。}}7．假定串以定長(zhǎng)順序存儲(chǔ)，設(shè)計(jì)一個(gè)求最長(zhǎng)公共子串的算法MaxSubs(S,T,amp。m,amp。n)。該操作返回S、T的最長(zhǎng)公共子串在S中首次出現(xiàn)的開(kāi)始位置m和長(zhǎng)度n。void MaxSubs(HString S,HString T,int amp。m,int amp。n){ int i,k=,pos。 HString sub。 m=1,n=0。 if(k)k=。 for(i=k。i0。i) { pos=1。 while(SubString_HS(sub,T,pos++,i)) if(m=IndexBF_SS(,)) { n=i。 return。 } }}void main(){ char s1[255],s2[255]。 HString S,T。 int m,n。 coutinput string S:。 (s1,255)。 coutinput string T:。 (s2,255)。 StrAssign_HS(S,s1)。 StrAssign_HS(T,s2)。 MaxSubs(S,T,m,n)。 coutm=m,n=nendl。}