數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--最小生成樹-資料下載頁
2025-06-02 22:52本頁面
【正文】 t**b)。 void LCS(int i,int j,string x,int **b)。 void Initialize()。//對數(shù)組 b,c 動 態(tài)分配空間以及對其進行初始化 void ReadCommand(char amp。cmd)。 void Interpret(char amp。cmd)。 void Realese()。//釋放指針 void Display()。 int main() { char cmd。 do { ReadCommand(cmd)。 Interpret(cmd)。 }while(cmd!=39。q39。amp。amp。cmd!=39。Q39。)。 return 0。 } void ReadCommand(char amp。cmd) { system(cls)。 //清屏 cout\n\n。 cout\n\t\t\t\t操 作 提 示 。 cout\n\n。 cout\tquitq/Q \t\t continuec/C\n。 do{ cout\n\n\t 請選擇操作 ： 。 cincmd。 cout\n\n。 }while(cmd!=39。c39。amp。amp。cmd!=39。C39。amp。amp。cmd!=39。q39。amp。amp。cmd!=39。Q39。)。 } void Initialize() { cout分別輸入兩個字符串 （ 每個字符串以回車結(jié)束 ） \n。 cinx。 ciny。 m=()。 12 n=()。 c=new int*[m+1]。 b=new int*[m+1]。 for(int i=0。i=m。i++) { c[i]=new int[n+1]。 b[i]=new int[n+1]。 } } void Realese()//釋放指針 board { for(int i=0。i=m。i++) { delete c[i]。 delete b[i]。 } delete[] c。 delete[] b。 } void Interpret(char amp。cmd) { switch(cmd) { case 39。c39。: case 39。C39。: Initialize()。 LCSLength(m,n,x,y,c,b)。 Display()。 Realese()。 break。 } } void LCSLength(int m,int n,string x,string y,int **c,int**b) { int i,j。 for(i=0。i=m。i++)c[i][0]=0。 for(i=1。i=n。i++)c[0][i]=0。 for(i=1。i=m。i++) for(j=1。j=n。j++) { if(x[i1]==y[j1]) 13 { c[i][j]=c[i1][j1]+1。 b[i][j]=1。 } else if(c[i1][j]=c[i][j1]) { c[i][j]=c[i1][j]。 b[i][j]=2。 } else { c[i][j]=c[i][j1]。 b[i][j]=3。 } } } //構(gòu)造最長公共子序列 void LCS(int i,int j,string x,int **b) { if(i==0||j==0)return。 if(b[i][j]==1) { LCS(i1,j1,x,b)。 coutx[i1]。 } else if(b[i][j]==2)LCS(i1,j,x,b)。 else LCS(i,j1,x,b)。 } void Display() { LCS(m,n,x,b)。 cout\n請按回車鍵繼續(xù)！ \n。 ()。 ()。 } 結(jié)果分析： 14 通過代碼和運行結(jié)果，我們能夠看到， 首先對二個序列進行動態(tài)分配， 將長度較小的字符串作為第一參數(shù)，將長度較大的字符串作為第二個參數(shù)。 然后調(diào)用函數(shù)進行分析， 最長公共子序列可能不是唯一的，但是本文的 結(jié)果只能輸出一個，所以本文的 算法還需要改進。 15 參考文獻 【 1】 《算法設(shè)計與分析》 王曉東編著 電子工業(yè)出版社。
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1