計算機數(shù)據(jù)結(jié)構(gòu)

算法設(shè)計題(每題10分，共30分)【嚴(yán)題集4.12③】編寫一個實現(xiàn)串的置換操作Replace(&S,T,V)的算法。解：intReplace(Stringtype&S,StringtypeT,StringtypeV);/將串S中所有子串T替換為V,并返回置換次數(shù){for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++)雄意i的取值范圍if(!StrCompare(SubString(S,i,Strlen(T)),T))/找到了與T匹配的子串{〃分別把T的前面和后面部分保存為head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail));//把head,V,tail連接為新串i+=Strlen(V);//當(dāng)前指針跳到插入串以后n++;n++;}//ifreturnn;}//Replace分析:i+=Strlen(V);這一句是必需的，也是容易忽略的.如省掉這一句，則在某些情況下，會引起不希望的后果,雖然在大多數(shù)情況下沒有影響.請思考:設(shè)S='place',T='ace',V='face',則省掉i+=Strlen(V);運行時會出現(xiàn)什么結(jié)果？【全國專升本資格考試】寫出將字符串反序的遞歸或遞推算法，例如字符串為“abcsxw”，反序為“wxscba”(注：這也是嚴(yán)題集4.10③編寫對串求逆的遞推算法)請注意遞歸和遞推的區(qū)別！遞推是由“小”到“大”遞進(jìn)；遞歸是由“大”到“小”嵌套。算法思路：①假定用單鏈表結(jié)構(gòu)存儲字符串；if沒有到尾部字符就不停調(diào)用自身函數(shù)，直至到達(dá)末尾，再從尾部返回并打印字符；遞歸算法的一般形式：(殷人凱題集P102遞歸算法的一般形式：(殷人凱題集P102)voidp(參數(shù)表){if(遞歸結(jié)束條件)可直接求解步驟； 基本項elsep(較小的參數(shù))； 歸納項}Invert(stringlistnode*p){if(!p)return(0);elseInvert(p->next);printf("％c”>data)}如果當(dāng)前串長為0,則return(-1)否則開始遞歸：if串沒有到末尾，則P=P->next;再調(diào)用invert(s);elseprintf(p->data);return嚴(yán)題集4.10③答案：voidString_Reverse(Stringtypes,Stringtype&r)//求s的逆串rStrAssign(r,'');/初始化r為空串for(i=Strlen(s);i;i--){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c));/把s的字符從后往前添加到r中 /這是遞推算法。}}//String_Reverse3.【嚴(yán)題集5.18⑤】試設(shè)計一個算法，將數(shù)組An中的元素A[0]至A[n-1]循環(huán)右移k位，并要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)解：分析:要把A的元素循環(huán)右移k位，則A[0]移至A[k],A[k]移至A[2k]......直到最終回到A[0],然而這并沒有全部解決問題，因為有可能有的元素在此過程中始終沒有被訪問過，而是被跳了過去.分析可知，當(dāng)n和k的最大公約數(shù)為p時，只要分別以A[0],A[1],...A[p-1]為起點執(zhí)行上述算法，就可以保證每一個元素都被且僅被右移一次，從而滿足題目要求,也就是說,A的所有元素分別處在p個"循環(huán)鏈"上面,舉例如下：n=15,k=6，則p=3.第一條鏈:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]./已“順便”移動了A[6]、A[12]…第二條鏈:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三條鏈:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學(xué)證明，但作者相信上述規(guī)律應(yīng)該是正確的.程序如下：voidRSh(intA[n],intk)//把數(shù)組A的元素循環(huán)右移k位，只用一個輔助存儲空間{for(i=1;i<=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公約數(shù)pfor(i=0;i<p;i++){j=i;l=(i+k)%n;temp=A[i];while(l!=i){A[j]=temp;temp=A[l];A[l]=A[j];j=l;l=(j+k)%n;}//循環(huán)右移一步A[i]=temp;}//for}//RSh附加題：利用C的庫函數(shù)strlen,strcpy(或strncpy)寫一個算法voidStrDelete(char*S,intt,intm)，刪除串S中從位置i開始的連續(xù)的m個字符。若iNstrlen(S)，則沒有字符被刪除；若i+mNstrlen(S)，則將S中從位置i開始直至末尾的字符均被刪去。提示：strlen是求串長(length)函數(shù)：i