程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 最長公共子序列的C++實現---附二維指針的使用方法

最長公共子序列的C++實現---附二維指針的使用方法

編輯:C++入門知識

想了挺久到底第一篇在這兒的博客寫什麼好,剛好這兩天又一次看到動態規劃的LCS算法覺得還是有點意思的,就拿來寫了寫,第一篇博客就發它吧。

#include<iostream><iomanip>
 
 LCS_Length( *X,  *Y,  *count[], *tag[], length_X, 
     ( i = ; i < length_X+; i++] =  ( i = ; i < length_Y+; i++][i] =  ( i = ; i <= length_X; i++ ( j = ; j <= length_Y; j++ (X[i-] == Y[j - = count[i-][j-]+= 
             (count[i-][j] > count[i][j-= count[i-= = count[i][j-= 
 Print_LCS( *tag[], *X, Length_X,  (Length_X ==  || Length_Y ==  i = Length_X, j = (tag[i][j] == <<X[i-]<<setw(-,j- (tag[i][j] == --
     *X =  *Y =  *count[ ( i = ; i < ; i++=  [];       
 *tag[ ( i = ; i < ; i++=  [<<<<count[][]<<<< 

 

  主要函數有兩個,一個函數是做出保存最長公共子序列的元素個數的矩陣,這裡給出的示例中,兩個字符串都各6個字符,所以給出的是7行7列矩陣(第一行第一列全為零)。

另外一個函數即為打印函數,從矩陣右下角一位開始遍歷到[0][0]位,凡是遇到tag[i][j]標志為0則將該位的字符打印出來。算法比較簡單易懂,具體可以參考《算法導論》。

 

下面補充說一個問題:二維指針到底怎麼用。比如前面的二維數組初始化,如果我希望能夠通過字符串的長度來給我的二維數組定義大小,而不是用常數來指定,使得我們可以通過strlen()函數來定義長度,那麼就要用到二維指針。

注意:int *Arr[strlen(str)];這種聲明方式是不正確的,編譯器會提示錯誤,數組的聲明必須使用常量。下面給出正確的示例:

        

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved