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

串 - 串的存儲結構 - 串運算的實現(二)

2013-11-15 15:45:27  來源: 數據結構 

  順序串上的子串定位運算

  ()樸素的串匹配算法的基本思想

  即用一個循環來依次檢查nm+個合法的位移i(≤i≤nm)是否為有效位移

  具體過程【 參見動畫演示 】

  ()順序串上的串匹配算法

  以下以第二種定長的順序串類型作為存儲結構給出串匹配的算法

  #define MaxStrSize //該值依賴於應用由用戶定義

  typedef struct{

  char ch[MaxStrSize]; //可容納個字符並依次存儲在ch[n]中

  int length;

  }SeqString;

  int Naive StrMatch(SeqString TSeqString P)

  {//找模式P在目標T中首次出現的位置成功返回第個有效位移否則返回

  int ijk;

  int m=Plength; //模式串長度

  int n=Tlength; //目標串長度

  for(i=;i<=nm;i++){ //<=i<=nm是合法的位移

  j=;k=i; //下面用while循環判定i是否為有效位移

  while(j

  k++;j++;

  }

  if(j==m) //既T[i..i+m-1]=P[0..m-1]

  return i; //i為有效位移,否則查找下一個位移

  }//endfor

  return -1; //找不到有效位移,匹配失敗

  }//NaiveStrMatch

  (3)算法分析

  ①最壞時間復雜度

  該算法最壞情況下的時間復雜度為O((n-m+1)m)。tW.wINGwIT.Com

  分析:當目標串和模式串分別是"a n-1 b"和"a m-1 b"時,對所有n-m+1個合法的位移,均要比較m個字符才能確定該位移是否為有

  效位移,因此所需比較字符的總次數為(n-m+1)m。

  ②模式匹配算法的改進

  樸素的串匹配算法雖然簡單,但效率低。其原因是在檢查位移i是否為有效位移時,沒有利用檢查位移i-1,i,…,0時的部分匹配

  結果。

  若利用部分匹配結果,模式串右滑動的距離就不會是每次一位,而是每次使其向右滑動得盡可能遠。這樣可使串匹配算法的最壞

  時間控制在O(m+n)數量級上。具體可【參閱有關文獻】。

  5、鏈串上的子串定位運算

  用結點大小為1的單鏈表做串的存儲結構時,實現樸素的串匹配算法很簡單。只是現在的位移shift是結點地址而非整數,且單鏈

  表中沒有存儲長度信息。若匹配成功,則返回有效位移所指的結點地址,否則返回指針。具體算法如下:

  LinkStrNode *LinkStrMatch(LinkString T,LinkString P)

  {//在鏈串上求模式P在目標T首次出現的位置

  LinkStrNode * shift,*t,*p;

  shift=T; //shift表示位移

  t=shift;p=P;

  while(t&&p) {

  if(t->data==p->data){ //繼續比較後續結點中字符

  t=t->next;

  p=p->next;

  }

  else{ //已確定shift為無效位移

  shift=shift->next; //模式右移,繼續判定shift是否為有效位移

  t=shift;

  p=P;

  }

  }//endwhile

  if(p==NULL)

  return shift; //匹配成功

  else

  return NULL; //匹配失敗

  }

  該算法的時間復雜度與順序表上樸素的串匹配算法相同。


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