熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第四章 答案[15]

2013-11-15 14:57:44  來源: 數據結構 

  [題目分析]教材中介紹的串置換有兩種形式第一種形式是replace(sijt)含義是將s串中從第i個字符開始的j個字符用t串替換第二種形式是replace(stv)含義是將s串中所有非重疊的t串用v代替我們先討論第一種形式的替換因為已經給定順序存儲結構我們可將s串從第(i+j)到串尾(即scurlen)移動tcurlenj絕對值個位置(以便將t串插入)若j>tcurlen則向左移;若j<tcurlen則向右移動;若j=tcurlen則不必移動最後將t串復制到s串的合適位置上當然應考慮置換後的溢出問題

  int replace(strtp stint ij)//s和t是用一維數組存儲的串本算法將s串從第i個字符開始的連續j個字符用t串置換操作成功返回否則返回表示失敗
  {if(i< || j< || tcurlen+scurlenj>maxlen)
  {printf(參數錯誤\n);exit();}//檢查參數及置換後的長度的合法性
  if(j<tcurlen)//若s串被替換的子串長度小於t串長度則s串部分右移
  for(k=scurlen;k>=i+j;k) sch[k+tcurlenj]=sch[k];
  else if (j>tcurlen)//s串中被替換子串的長度小於t串的長度
  for(k=i+j;k<=scurlen;k++) sch[k(jtcurlen)]=sch[k];
  for(k=;k<tcurlen;k++) sch[i+k]=tch[k]; //將t串復制到s串的適當位置
  if(j>tcurlen) scurlen=scurlen(jtcurlen);else scurlen=scurlen+(tcurlenj);
  }//算法結束

  [算法討論]若允許使用另一數組在檢查合法性後可將s的第i個(不包括i)之前的子串復制到另一子串如s再將t串接到s串後面然後將s的第i+j直到尾的部分加到s之後最後將s串復制到s主要語句有

  for(k=;k<i;k++) sch[k]=sch[k]; //將s第i個字符前的子串復制到s這時k=i
  for(k=;k<tcurlen;k++) sch[i+k]=tch[k]//將t串接到s的尾部
  l=scurlen+tcurlenj;
  for(k=scurlen;k>i+j;k);//將子串第i+j個字符以後的子串復制到s
  sch[l]=sch[k]
  for(k=;k<scurlen+tcurlenj;k++) sch[k]=sch[k];//將結果串放入s

  下面討論replace(stv)的算法該操作的意義是用串v替換所有在串s中出現的和非空串t相等的不重疊的子串本算法不指定存儲結構只使用串的基本運算

  void replace(string stv)//本算法是串的置換操作將串s中所有非空串t相等且不重復的子串用v代替
  {i=index(st);//判斷s是否有和t相等的子串
  if(i!=)//串s中包含和t相等的子串
  {creat(temp);//creat操作是將串常量(此處為空串)賦值給temp
  m=length(t);n=length(s);//求串t和s的長度
  while(i!=)
  {assign(tempconcat(tempsubstr(si)v));//用串v替換t形成部分結果
  assign(ssubstr(si+mnim+));//將串s中串後的部分形成新的s串
  n=n(i)m;//求串s的長度
  i=index(st);//在新s串中再找串t的位置
  }
  assign(scontact(temps));  //將串temp和剩余的串s連接後再賦值給s
  }//if結束
  }//算法結束

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22614.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.