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

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

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

  五算法設計

  [題目分析]判斷字符串t是否是字符串s的子串稱為串的模式匹配其基本思想是對串s和t各設一個指針i和ji的值域是mnj的值域是n初始值i和j均為模式匹配從s和t開始若s=t則i和j指針增加若在某個位置si!=tj則主串指針i回溯到i=ij+j仍從開始進行下一輪的比較直到匹配成功(j>n返回子串在主串的位置(ij)否則當i>mn則為匹配失敗

  int index(char s[]t[]int mn)//字符串s和t用一維數組存儲其長度分別為m和n本算法求字符串t在字符串s中的第一次出現如是輸出子串在s中的位置否則輸出
  {int i=j=;
  while (i<=mn && j<=n)
  if (s[i]==t[j]){i++;j++;}//對應字符相等指針後移
  else {i=ij+;j=;}//對應字符不相等I回溯j仍為
  if(i<=mn && j==n) {printf(t在s串中位置是%din+);return(in+);}//匹配成功
  else  return(); //匹配失敗
  }//算法index結束
  main ()//主函數
  {char s[]t[]; int mni;
  scanf(%d%d&m&n);//輸入兩字符串的長度
  scanf(%ss);//輸入主串
  scanf(%st);//輸入子串
  i=index(stmn);
  }//程序結束

  [程序討論]因用C語言實現一維數組的下標從開始m是主串最後一個字符的下標n是t串的最後一個字符的下標若匹配成功最佳情況是s串的第到第n個字符與t匹配時間復雜度為o(n);匹配成功的最差情況是每次均在t的最後一個字符才失敗直到s串的第mn個字符成功其時間復雜度為o((mn)*n)即o(m*n)失敗的情況是s串的第mn個字符比t串某字符比較失敗時間復雜度為o(m*n)之所以串s的指針i最大到mn是因為在mn之後所剩子串長度已經小於子串長度n故不必再去比較算法中未討論輸入錯誤(如s串長小於t串長)

  另外根據子串的定義返回值in+是子串在主串中的位置子串在主串中的下標是in

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


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