萬盛學電腦網

 萬盛學電腦網 >> 網絡編程 >> 編程語言綜合 >> C++ kmp算法模板代碼解讀

C++ kmp算法模板代碼解讀

  C++編程語言雖然功能強大,應用方式靈活,但是在實際編程中同樣會出現各種各樣的錯誤。在這裡我們將會為大家詳細介紹一下有關C++指針漂移的解決方法,希望本文介紹的內容可以幫助大家解決問題。

  最近我們在工作中碰到一個奇怪的問題,最後確定是多繼承引起的C++指針漂移,跟C++對象模型有關。示意如下:

  class A {...}; class B{...}; class AB : public B, public A {...} ... AB *pab = new AB(); A* pa = (A*)pab; B* pb = (B*)pab; 這時候你發現pa和pb的值是不一樣的!它們中有一個跟pab是相等的,而另外一個產生了偏移。如果把AB的聲明中A和B的順序調換一下,則產生偏移的指針也會變為另外一個。

  為了確定這是編譯器做了轉換的緣故,利用void指針愚弄編譯器:

  void *pv = (void*)pab; pa = (A*)pv; 這時候pa的值倒是跟pab相等了,然而指向了錯誤的地方。從pab到pa的轉換,依賴於路徑的選擇,讓人不是很放心。還不知道把指針放入容器中再取出來,會不會出錯。當然,上面使用了強制類型轉換,在良好的程序中應該避免。如果只有隱式轉換,可以得到正確的結果:

  std::vector v; //implicit type conversion v.insert(v.begin(), pab); void *pv = v[0]; pa = (A*)pv; 以下程序使用Cygwin/g++b編譯通過:

  #include #include class A { public: int a; }; class B { public: int b; }; class AB : public B, public A { public: int ab; }; int main(int argc, char **argv) { AB *pab = new AB(); pab->ab = 1; pab->b = 2; pab->a = 3; A* pa = (A*)pab; B* pb = (B*)pab; printf( "AB: %pn" " A: %pn" " B: %pn", pab, pa, pb); std::vector v; //implicit type conversion v.insert(v.begin(), pab); void *pv = v[0]; pa = (A*)pv; printf("pv is %pnpa is %pnpab %s pvn", pv, pa, (pab == pv) ? "==" : "!="); printf("A.a is %dn", pa->a); //forced type conversion pv = (void*)pab; pa = (A*)pv; printf("Now A.a is %dn", pa->a); } 運行結果:

  AB: 0x6b01f0 A: 0x6b01f4 B: 0x6b01f0 pv is 0x6b01f4 pa  C++編程語言中的模板應用是一個比較復雜的應用技術,我們今天就先從C++ kmp算法模板的基本應用開始學習,從而加深我們對這方面知識的認識程度,方便將來的應用,提高編程效率。

  在使用的時候加上這兩行代碼就行了

  #include < vector> using namespace std;

  C++ kmp算法模板參數說明

  const T *source 待匹配的字符串

  TL sourceLen 待匹配字符串的長度

  const T *pattern 模式串

  TL 模式串長度

  C++ kmp算法模板代碼示例:

  template < class T,class TL> inline int kmpmatch(const T *source,TL sourceLen,const T *pattern,TL patternLen)

  { vector< int> next;

  for ( int i = 0; i < patternLen ; i ++ ) next.push_back(0); next[0] = -1; for( int i = 1 ; i < patternLen ; i ++ )

  { int j = next[i - 1];

  while ( (pattern[i] != pattern[i + 1])&& (j >= 0))

  { j = next[j]; }

  if ( pattern[i] == pattern[j + 1])

  { next[i] = j + 1; }

  else { next[i] = -1; } }

  int i = 0; int j = 0;

  while (( i < sourceLen ) && ( j < patternLen ))

  { if ( source[i] == pattern[j] )

  { i ++; j ++; } else if ( j == 0 )

  { i ++; } else { j = next[j - 1 ] + 1; } }

  if ( j >= patternLen )

  { if ( !next.empty() )

  next.clear();

  return i - patternLen ;

  }

  else

  { if ( !next.empty() ) next.clear();

  return -1; } }

  is 0x6b01f4 pab != pv A.a is 3 Now A.a is 2

copyright © 萬盛學電腦網 all rights reserved