第4章習(xí)題答案.doc

第4章 串習(xí)題41.名詞解釋：串、空串、空格串、子串。解：串是有限的字符序列，從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的不同之處在于串的元素是字符。空串是不含任何字符的串，其長(zhǎng)度為0?？崭袷且粋€(gè)字符，其ASCII碼值是32?？崭翊怯煽崭窠M成的串，其長(zhǎng)度等于空格的個(gè)數(shù)。串中任意連續(xù)的若干字符組成的子序列稱為該串的子串。2.已知三個(gè)字符串分別為，。利用串的基本運(yùn)算得到結(jié)果串為，要求寫(xiě)出得到結(jié)果串所用的函數(shù)及執(zhí)行算法。解：串可看作由以下兩部分組成：和，設(shè)這兩部分分別叫串s1和s2，要設(shè)法從、中得到這兩部分，然后使用連接操作連接s1和s2得到。i=index();/s1=substr(,i,length()-i+1);/取出串s1j=index(,);/求串在串中的起始位置，串中后是s2=substr(,j+3,length()-j-2);/形成串s2=concat(s1,s2);3.已知字符串中存放一段英文，寫(xiě)出算法，將其按給定的長(zhǎng)度格式化成兩端對(duì)齊的字符串，其多余的字符存入。解：題目要求將字符串S1拆分成字符串S2和S3，要求字符串S2“按給定長(zhǎng)度n格式化為兩端對(duì)齊的字符串”，即長(zhǎng)度為n且首尾字符不能為空格字符。算法從左到右掃描字符串S1，找到第一個(gè)非空格字符，計(jì)數(shù)到n，第n個(gè)拷入字符串S2的字符不能為空格，然后將余下字符復(fù)制到字符串S3中。void format(char *S1,char *S2,char *S3,int n) char *p=S1,*q=S2; int i=0; while(*p!= 0&*p= )p+;/濾掉S1左端空格 if(*p= 0)printf(字符串S1為空串或空格串n);exit(0); while(*p!= 0&in)*q=*p;q+;p+;i+;/字符串S1向字符串S2中復(fù)制 if(*p= 0)printf(字符串S1沒(méi)有%d個(gè)有效字符n,n);exit(0); if(*(-q)= )/若最后一個(gè)字符為空格，則需要向后找到第一個(gè)非空格字符p-;/p指針也后退while(*p!= 0&*p= )p+;/往后查找一個(gè)非空格字符作為串S2的尾字符if(*p= 0)printf(串S1沒(méi)有%d個(gè)兩端對(duì)齊的字符串n,n);exit(0);*q=*p;/字符串S2最后一個(gè)非空字符*(+q)= 0;/S2字符串結(jié)束標(biāo)記 q=S3;p+;/將S1串其余部分送字符串S3 while(*p!= 0)*q=*p;q+;p+; *q= 0;/置串S3結(jié)束標(biāo)記4.假設(shè)采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)表示串，編寫(xiě)算法，求串的含不同字符的總數(shù)和每個(gè)字符的個(gè)數(shù)。解：typedef struct char ch; int num;mytype;void StrAnalyze(SString S)/統(tǒng)計(jì)串S中字符的種類和個(gè)數(shù) int i,j; char c; mytype T100; /用結(jié)構(gòu)數(shù)組T存儲(chǔ)統(tǒng)計(jì)結(jié)果 for(i=1;i=S0+1;i+)Ti-1.ch=0; for(i=1;i=S0;i+)c=Si;j=0;while(Tj.ch&Tj.ch!=c)j+; /查找當(dāng)前字符c是否已記錄過(guò)if(Tj.ch) Tj.num+;else Tj.ch=c;Tj.num=1; /for for(j=0;Tj.ch;j+)printf(%c: %dn,Tj.ch,Tj.num);/StrAnalyze5.假設(shè)采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)表示串，編寫(xiě)算法，從串中刪除所有和串相同的子串。解：void SubString_Delete(SString &s,SString t,int &num)/從串s中刪除所有與t相同的子串,num為刪除次數(shù) int i,j,k; for(i=1;i=s0-t0+1;i+)for(j=1;jt0)/找到了與t匹配的子串for(k=i;k=s0-t0;k+)sk=sk+t0; /左移刪除s0-=t0;num+; /for/Delete_SubString6.編寫(xiě)算法，實(shí)現(xiàn)堆存儲(chǔ)結(jié)構(gòu)的串的置換操作Replace(&S,T,V)。解：void HString_Replace(HString &S,HString T,HString V,int & num)/堆結(jié)構(gòu)串上的置換操作,返回置換次數(shù) int i,j,k,m; for(i=0;i=S.length-T.length;i+)for(j=i,k=0;kT.length&S.chj=T.chk;j+,k+);if(k=T.length) /找到了與T匹配的子串:分三種情況處理if(T.length=V.length)for(m=1;m=T.length;m+) S.chi+m-1=V.chm-1;/新子串長(zhǎng)度與原子串相同時(shí):直接替換 else if(T.length=i+T.length;m-)S.chm+V.length-T.length=S.chm; for(m=0;mV.length;m+)S.chi+m=V.chm; else /新子串長(zhǎng)度小于原子串時(shí):先將后部左移for(m=i+V.length;mS.length+V.length-T.length;m+)S.chm=S.chm-V.length+T.length;for(m=0;mV.length;m+)S.chi+m=V.chm;S.length+=V.length-T.length;i+=V.length;num+;/if /for/HString_Replace7.編寫(xiě)算法，實(shí)現(xiàn)堆存儲(chǔ)結(jié)構(gòu)的串基本操作Concat(&S,S1,S2)。解：void HString_Concat(HString s1,HString s2,HString &t) /將堆結(jié)構(gòu)表示的串s1和s2連接為新串t int i,j; if(t.ch) free(t.ch); t.ch=new chars1.length+s2.length; for(i=1;i=s1.length;i+) t.chi-1=s1.chi-1; for(j=1;j=s2.length;j+,i+) t.chi-1=s2.chj-1; t.length=s1.length+s2.length;/HString_Concat8.假設(shè)以塊鏈結(jié)構(gòu)表示串，試編寫(xiě)判別給定字符串是否具有對(duì)稱性的算法，并要求算法的時(shí)間復(fù)雜度為。解：int LString_Palindrome(LString L) /判斷以塊鏈結(jié)構(gòu)存儲(chǔ)的串L是否為回文序列,是則返回1,否則返回0 InitStack(S); p=S.head;i=0;k=1; /i指示元素在塊中的下標(biāo),k指示元素在整個(gè)序列中的序號(hào)(從1開(kāi)始) for(k=1;k=S.curlen;k+) if(kchi); /將前半段的字符入串 else if(k(S.curlen+1)/2) Pop(S,c); /將后半段的字符與棧中的元素相匹配 if(p-chi!=c) return 0; /失配 if(+i=CHUNKSIZE) /轉(zhuǎn)到下一個(gè)元素,當(dāng)為塊中最后一個(gè)元素時(shí),轉(zhuǎn)到下一塊 p=p-next; i=0; /for return 1; /成功匹配/LString_Palindrome9.令，試分別求出它們的next函數(shù)值和nextval函數(shù)值。解：j1234567串Sabcabaanextj0111232nextvalj0110132j1234567891011121314151617181920串Tabcaabb