算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）（第2版） 第4章課后習(xí)題答案

PAGEPAGE1習(xí)題答案一、選擇題1-6B、A、B、D、C、B二、填空題1．字符2.O(m+n)3．-100112014．-10-10-1310三、判斷題對(duì)對(duì)錯(cuò)錯(cuò)四、應(yīng)用題1、空串：當(dāng)串的長度n=0時(shí)，串中沒有任何字符，稱為空串，如S=“”；空格串：由空格字符組成的串，稱為空格串，如S=“”子串：串中任意個(gè)連續(xù)的字符組成的子序列被稱為該串的子串?？沾侨我獯淖哟?；任意串S都是S自身的子串。主串：包含子串的串又被稱為該子串的主串。2、KMP的特點(diǎn)是主串無需回溯，主串指針一直往后移動(dòng)，只有子串指針回溯，大大減少算法的比較次數(shù)和回溯次數(shù)。3、五、算法設(shè)計(jì)題1、[題目分析]設(shè)字符串存于字符數(shù)組X中，若轉(zhuǎn)換后的數(shù)是負(fù)數(shù)，字符串的第一個(gè)字符必為'-'轉(zhuǎn)換過程如下：將取出的數(shù)字字符減去字符零（'0'）的ASCII值，變成數(shù)；先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果；如此一個(gè)字符一個(gè)字符的轉(zhuǎn)換，直到字符串結(jié)束，得到結(jié)果。longatoi(char*X){longnum=0; //結(jié)果整數(shù)初始化inti=1; //i為數(shù)組下標(biāo)if(X==NULL){cout<<"PointerisNULL\n";return0;}if(X[0]!='-')num=X[0]-'0'; //如是正數(shù)，x[0]是數(shù)字字符while(X[i]!='\0') //當(dāng)字符串未到尾，進(jìn)行數(shù)的轉(zhuǎn)換num=10*num+(X[i++]-'0'); //先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果if(X[0]=='-')return(-num); //負(fù)數(shù)elsereturn(num); //返回正數(shù)}2、（1）//求重復(fù)子串的長度intrptSubLen(char*p,char*q){ intlen=0;while(*p&&*q){if(*p==*q){ ++len;p++,q++;}elsebreak;}returnlen;}（2）//求最長重復(fù)子串voidlongestRepeatSub(char*arr,intsize,int&maxLen,int&maxIndex){inti,j,len;maxLen=0; //記錄最長重復(fù)子串的長度maxIndex=-1; //記錄最長重復(fù)子串的下標(biāo)for(i=0;i<size;++i){for(j=i+1;j<size;++j){len=rptSubLen(&arr[i],&arr[j]);if(len>maxLen){maxLen=len;maxIndex=i;}}}if(maxLen==0)return;i=maxIndex;cout<<"Thelongestrepeatsubstring：";while(maxLen--)cout<<arr[i++];cout<<endl;}3、//利用4.2.1節(jié)已經(jīng)給定的順序存儲(chǔ)結(jié)構(gòu)的串的類型定義StringString&String::replace(intpos,intnum,constString&t){Stringtemp(*this); inti=0,j=0;if(pos<1||num<0){ //參數(shù)錯(cuò)誤return*this;}curLen+=t.curLen-j; delete[]str; str=newchar[curLen+1]; assert(str!='\0'); while(i<pos-1) //拷貝原串前pos-1個(gè)元素str[i]=temp.str[i++];while(j<t.curLen) //拷貝t串str[i++]=t.str[j++];j=pos+num-1;while(temp.str[j]!='\0') //拷貝原串從第pos+num個(gè)到串尾的元素str[i++]=temp.str[j++];str[i]='\0';return*this;}4、voidInvertStore(charA[]){∥字符串逆序存儲(chǔ)的遞歸算法charch;staticinti=0; ∥使用靜態(tài)變量scanf("%c"，&ch);if(ch!='.') ∥'.'表示字符串輸入結(jié)束{InvertStore(A);A[i++]=ch; ∥字符串逆序存儲(chǔ)}A[i]='\0'; ∥字符串結(jié)尾標(biāo)記}∥InvertStore5、intCountInt（）｛charch;inti=0，a[]； ∥整數(shù)存儲(chǔ)到數(shù)組a，i記整數(shù)個(gè)數(shù)scanf(“％c”，&ch）； ∥從左到右讀入字符串while（ch!=‘#’） ∥‘#’是字符串結(jié)束標(biāo)記if(ch>=’0’&&ch<=’9’) ∥是數(shù)字字符｛num=０； ∥數(shù)初始化while（ch>=’0’&&ch<=’9’） ∥拼數(shù)｛num=num＊10+‘ch’-‘０’；scanf(“％c”，&ch）；｝a[i++]=num；if（ch!=‘#’） ∥若拼數(shù)中輸入了‘#’，則不再輸入scanf（“%c”，&ch）；｝elsescanf（“%c”，&ch）；∥輸入非數(shù)字且非＃時(shí)，繼續(xù)輸入字符printf（“共有%d個(gè)整數(shù)，它們是：”,i）；for（j=０；j<i；j++）｛printf（“%6d”，a[j]）；if（（j+1）％10==0）printf（“\n”）；}∥每10個(gè)數(shù)輸出在一行上｝∥CountInt6、#include<iostream>#include<cstring>#include<string>usingnamespacestd;intmain(){stringarr;inti,j,k=0;while(getline(cin,arr)){ if(arr=="STOP")break;k++;for(i=0,j=arr.length()-1;