第4章習(xí)題答案.doc_第1頁
第4章習(xí)題答案.doc_第2頁
第4章習(xí)題答案.doc_第3頁
第4章習(xí)題答案.doc_第4頁
第4章習(xí)題答案.doc_第5頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

第4章 串習(xí)題41.名詞解釋:串、空串、空格串、子串。解:串是有限的字符序列,從數(shù)據(jù)結(jié)構(gòu)角度講,串屬于線性結(jié)構(gòu)。與線性表的不同之處在于串的元素是字符??沾遣缓魏巫址拇?,其長度為0。空格是一個字符,其ASCII碼值是32??崭翊怯煽崭窠M成的串,其長度等于空格的個數(shù)。串中任意連續(xù)的若干字符組成的子序列稱為該串的子串。2.已知三個字符串分別為,。利用串的基本運(yùn)算得到結(jié)果串為,要求寫出得到結(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.已知字符串中存放一段英文,寫出算法,將其按給定的長度格式化成兩端對齊的字符串,其多余的字符存入。解:題目要求將字符串S1拆分成字符串S2和S3,要求字符串S2“按給定長度n格式化為兩端對齊的字符串”,即長度為n且首尾字符不能為空格字符。算法從左到右掃描字符串S1,找到第一個非空格字符,計數(shù)到n,第n個拷入字符串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沒有%d個有效字符n,n);exit(0); if(*(-q)= )/若最后一個字符為空格,則需要向后找到第一個非空格字符p-;/p指針也后退while(*p!= 0&*p= )p+;/往后查找一個非空格字符作為串S2的尾字符if(*p= 0)printf(串S1沒有%d個兩端對齊的字符串n,n);exit(0);*q=*p;/字符串S2最后一個非空字符*(+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è)采用定長順序存儲結(jié)構(gòu)表示串,編寫算法,求串的含不同字符的總數(shù)和每個字符的個數(shù)。解:typedef struct char ch; int num;mytype;void StrAnalyze(SString S)/統(tǒng)計串S中字符的種類和個數(shù) int i,j; char c; mytype T100; /用結(jié)構(gòu)數(shù)組T存儲統(tǒng)計結(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是否已記錄過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è)采用定長順序存儲結(jié)構(gòu)表示串,編寫算法,從串中刪除所有和串相同的子串。解: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àn)堆存儲結(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;/新子串長度與原子串相同時:直接替換 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 /新子串長度小于原子串時:先將后部左移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àn)堆存儲結(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)表示串,試編寫判別給定字符串是否具有對稱性的算法,并要求算法的時間復(fù)雜度為。解:int LString_Palindrome(LString L) /判斷以塊鏈結(jié)構(gòu)存儲的串L是否為回文序列,是則返回1,否則返回0 InitStack(S); p=S.head;i=0;k=1; /i指示元素在塊中的下標(biāo),k指示元素在整個序列中的序號(從1開始) 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)到下一個元素,當(dāng)為塊中最后一個元素時,轉(zhuǎn)到下一塊 p=p-next; i=0; /for return 1; /成功匹配/LString_Palindrome9.令,試分別求出它們的next函數(shù)值和nextval函數(shù)值。解:j1234567串Sabcabaanextj0111232nextvalj0110132j1234567891011121314151617181920串Tabcaabb

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論