數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--最小生成樹

1、<p><b>　　成 績(jī) 評(píng) 定 表</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p><b>　　摘 要</b></p><p>　　“計(jì)算機(jī)算法設(shè)計(jì)與分析” 著重介紹了計(jì)算機(jī)算法設(shè)計(jì)領(lǐng)域的基本原則和根本原理。深入分析了一些計(jì)算機(jī)模型上的算法，介紹了一些和設(shè)計(jì)有

2、效算法有關(guān)的數(shù)據(jù)結(jié)構(gòu)和編程技術(shù)，為讀者提供了有關(guān)遞歸方法、分治方法和動(dòng)態(tài)規(guī)劃方面的詳細(xì)實(shí)例和實(shí)際應(yīng)用，并致力于更有效算法的設(shè)計(jì)和開發(fā)。同時(shí)，對(duì)NP完全等問題能否有效求解進(jìn)行了分析，并探索了應(yīng)用啟發(fā)式算法解決問題的途徑。</p><p>　　本文第一問，隨著信息技術(shù)的發(fā)展和嵌入式設(shè)備的廣泛使用．電路布線問題越來越受到人們的重視．要使電子電路獲得最佳性能．不僅元器件的布置占有著重要的地位．而且導(dǎo)線的布設(shè)也是非常重要的

3、．特別是在涉及到線路成本的布線方案中．一個(gè)好的布線算法就顯得尤為重要 本文首先對(duì)一類電路板低成本布線問題進(jìn)行了分析．進(jìn)而給出了解決這一問題的分支限界解法．并對(duì)所提出算法的時(shí)間復(fù)雜度進(jìn)行了分析和討論。</p><p>　　本文第二問，掌握動(dòng)態(tài)規(guī)劃法的原理，并能夠按其原理編程實(shí)現(xiàn)求兩個(gè)序列數(shù)據(jù)的最長(zhǎng)公共子系列，以加深對(duì)其的理解。</p><p>　　關(guān)鍵字：分支限界；布線問題；動(dòng)態(tài)規(guī)劃<

4、/p><p><b>　　目 錄</b></p><p>　　1 分支限界解決布線問題1</p><p><b>　　1.1問題重述1</b></p><p><b>　　1.2問題分析1</b></p><p>　　1.3算法分析與設(shè)計(jì)1</

5、p><p>　　1.4算法的實(shí)現(xiàn)與結(jié)果2</p><p>　　2 動(dòng)態(tài)規(guī)劃解決最長(zhǎng)公共子序列問題9</p><p><b>　　2.1問題重述9</b></p><p><b>　　2.2問題分析9</b></p><p>　　2.3算法分析與設(shè)計(jì)9</p>

6、<p>　　2.4算法實(shí)現(xiàn)與結(jié)果10</p><p><b>　　參考文獻(xiàn)14</b></p><p>　　1 分支限界解決布線問題</p><p><b>　　1.1問題重述</b></p><p>　　`布線問題：如圖1所示，印刷電路板將布線區(qū)域劃分成n*m個(gè)方格。精確的電路布

7、線問題要求確定連接方格a的中點(diǎn)到b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線，如圖1所示。為了避免線路相交，已經(jīng)布線的方格做了封鎖標(biāo)記（如圖1中陰影部分），其他線路不允許穿過被封鎖的方格。</p><p><b>　　1.2問題分析</b></p><p>　　題目的要求是找到最短的布線方案，從圖1的情況看，可以用貪婪算法解決問題，也就是從a開始朝著b的

8、方向垂直布線即可。實(shí)際上，再看一下圖2，就知道貪婪算法策略是行不通的。因?yàn)橐巡季€的放個(gè)沒有規(guī)律的所以直觀上說只能用搜索方法去找問題的解。</p><p>　　根據(jù)布線方法的要求，除邊界或已布線處，每個(gè)E-結(jié)點(diǎn)分支擴(kuò)充的方向有4個(gè)：上、下、左、右，也就是說，一個(gè)E-結(jié)點(diǎn)擴(kuò)充后最多產(chǎn)生4個(gè)活結(jié)點(diǎn)。以圖2的情況為例，圖的搜索過程如圖3所示。</p><p>　　搜索以a為第一個(gè)E-結(jié)點(diǎn)，以后不斷

9、擴(kuò)充新的活結(jié)點(diǎn)，直到b結(jié)束（當(dāng)然反之也可以）。反過來從b到a，按序號(hào)8-7-6-5-4-3-2-1就可以找到最短的布線方案。從圖3中也可以發(fā)現(xiàn)最短的布線方案是不唯一的。且由此可以看出，此問題適合用分支限界搜索。</p><p>　　1.3 算法分析與設(shè)計(jì)</p><p><b>　　算法分析：</b></p><p>　　分支限界搜索法是一種在

10、問題解空間上進(jìn)行搜索嘗試的算法。所謂“分支”是采用廣度優(yōu)先的策略，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有的相鄰結(jié)點(diǎn)。和回溯法一樣，在生成的結(jié)點(diǎn)中，拋棄那些不滿足約束條件（或者說不可能到處最優(yōu)可行解）的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，繼續(xù)搜索。選擇下一個(gè)E-結(jié)點(diǎn)的方式不同，會(huì)出現(xiàn)幾種不同的分值搜索方式。</p><p><b>　　FIFO搜索</b>&l

11、t;/p><p>　　先進(jìn)先出（FIFO）搜索算法要依賴“隊(duì)”做基本的數(shù)據(jù)結(jié)構(gòu)。一開始，根節(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根節(jié)點(diǎn)入隊(duì)。從活結(jié)點(diǎn)隊(duì)中取出根節(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入或節(jié)點(diǎn)隊(duì)列中。再?gòu)幕罱Y(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)（對(duì)中最先進(jìn)來的結(jié)點(diǎn)）為當(dāng)前結(jié)點(diǎn)，……，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。</p><p><

12、;b>　　LIFO搜索</b></p><p>　　后進(jìn)先出（LIFO）搜索算法要依賴“?！弊龌镜臄?shù)據(jù)結(jié)構(gòu)。一開始，根結(jié)點(diǎn)入棧，從棧中彈出一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子入棧，再?gòu)臈Ｖ袕棾鲆粋€(gè)結(jié)點(diǎn)（棧中最后進(jìn)來的結(jié)點(diǎn)）為當(dāng)前擴(kuò)展結(jié)點(diǎn)，……，直到找到一個(gè)解或棧為空為止。</p><p><b

13、>　　優(yōu)先隊(duì)列式搜索</b></p><p>　　為了加速搜索的進(jìn)程，應(yīng)采用有效的方式選擇E-結(jié)點(diǎn)進(jìn)行擴(kuò)展。優(yōu)先隊(duì)列搜索，對(duì)每一個(gè)活結(jié)點(diǎn)計(jì)算一個(gè)優(yōu)先級(jí)（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級(jí)，從當(dāng)前結(jié)點(diǎn)表中優(yōu)先選擇一個(gè)優(yōu)先級(jí)最高（最有利）的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。</p><p><b>　　算法設(shè)計(jì)：&

14、lt;/b></p><p>　　開辟m*n的二維數(shù)組模擬布線區(qū)域，初始值均為0，表示沒有被使用。已使用的位置，通過鍵盤輸入其下標(biāo)，將對(duì)應(yīng)值置為-1.輸入方格a、b的下標(biāo)，存儲(chǔ)在變量中。</p><p>　?、僖婚_始，唯一的活結(jié)點(diǎn)是a。</p><p>　　②從活結(jié)點(diǎn)表中取出后為當(dāng)前擴(kuò)展結(jié)點(diǎn)。</p><p>　?、蹖?duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，按上

15、、下、左、右的順序，找出可布線的位置，加入活結(jié)點(diǎn)隊(duì)列中，</p><p>　?、茉?gòu)幕罱Y(jié)點(diǎn)隊(duì)列中取出后為當(dāng)前擴(kuò)展結(jié)點(diǎn)。</p><p>　?、菀来祟愅?，直到搜索到達(dá)b結(jié)點(diǎn)，然后按序號(hào)8-7-6-5-4-3-2-1輸出最短布線方案，算法結(jié)束?；蚧罱Y(jié)點(diǎn)隊(duì)列已為空，表示無解，算法結(jié)束。</p><p>　　1.4算法的實(shí)現(xiàn)與結(jié)果</p><p>　

16、　通過算法的分析與設(shè)計(jì)，計(jì)算如圖所示4所示的布線問題</p><p><b>　　代碼：</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　typedef struct Position</p&g

17、t;<p><b>　　{</b></p><p><b>　　int row;</b></p><p><b>　　int col;</b></p><p>　　}Position;</p><p>　　typedef struct team</p>

18、<p><b>　　{</b></p><p><b>　　int x;</b></p><p><b>　　int y;</b></p><p>　　struct team *next;</p><p>　　}team,*TEAM;</p><

19、;p>　　Position start,end,path[100];</p><p>　　TEAM team_l=NULL;</p><p>　　int a[100][100];</p><p>　　int m,n,path_len;</p><p>　　void output()</p><p><b&g

20、t;　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n|-------------------布線區(qū)域圖-------------------|\n");</p><p>　　for(i=0;i<m+2;i++)</p><p&

21、gt;<b>　　{</b></p><p>　　for(j=0;j<n+2;j++)</p><p><b>　　{</b></p><p>　　printf("%5d",a[i][j]);</p><p><b>　　}</b></p>

22、<p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("|------------------------------------------------|\n");</p><p><b>　　return;</b

23、></p><p><b>　　}</b></p><p>　　void input_data()</p><p><b>　　{</b></p><p><b>　　char yes;</b></p><p><b>　　int x,y

24、;</b></p><p>　　printf("創(chuàng)建布線區(qū)域...\n\n");</p><p>　　printf("請(qǐng)輸入?yún)^(qū)域大小(行列的個(gè)數(shù)): ");</p><p>　　scanf("%d,%d",&m,&n);</p><p>　　printf(

25、"請(qǐng)輸入開始點(diǎn)坐標(biāo)(x,y): ");</p><p>　　scanf("%d,%d",&start.row,&start.col);</p><p>　　printf("請(qǐng)輸入結(jié)束點(diǎn)坐標(biāo)(x,y): ");</p><p>　　scanf("%d,%d",&en

26、d.row,&end.col);</p><p>　　printf("區(qū)域內(nèi)是否有被占用點(diǎn)? (y/n) ");</p><p>　　fflush(stdin);</p><p>　　scanf("%c",&yes);</p><p>　　fflush(stdin);</p>

27、<p>　　while(yes=='y')</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入占用點(diǎn)的坐標(biāo)(x,y): ");</p><p>　　scanf("%d,%d",&x,&y);</p><p&g

28、t;　　fflush(stdin);</p><p>　　if(x<0 || x>m+1 || y<0 || y>n+1 || (x==start.row && y==start.col) || (x==end.row && y==end.col))</p><p><b>　　{</b></p>

29、<p>　　printf("輸入錯(cuò)誤,請(qǐng)重新輸入!!!\n");</p><p><b>　　continue;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{

30、</b></p><p>　　a[x][y]=-1;</p><p><b>　　}</b></p><p>　　printf("是否還有被占用點(diǎn)? (y/n) ");</p><p>　　scanf("%c",&yes);</p><p&g

31、t;　　fflush(stdin);</p><p><b>　　}</b></p><p>　　for(x=0;x<m+2;x++)</p><p><b>　　{</b></p><p>　　a[0][x]=-1;</p><p>　　a[m+1][x]=-1;&l

32、t;/p><p><b>　　}</b></p><p>　　for(x=0;x<n+2;x++)</p><p><b>　　{</b></p><p>　　a[x][0]=-1;</p><p>　　a[x][n+1]=-1;</p><p>&

33、lt;b>　　}</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　void inq(Position p)</p><p><b>　　{</b></p><p>

34、<b>　　TEAM t,q;</b></p><p><b>　　q=team_l;</b></p><p>　　t=(TEAM)malloc(sizeof(TEAM));</p><p>　　t->x=p.row;</p><p>　　t->y=p.col;</p>&

35、lt;p>　　t->next=NULL;</p><p>　　if(team_l==NULL)</p><p><b>　　{</b></p><p><b>　　team_l=t;</b></p><p><b>　　return ;</b></p>

36、<p><b>　　}</b></p><p>　　while(q->next!=NULL)</p><p><b>　　{</b></p><p>　　q=q->next;</p><p><b>　　}</b></p><p>

37、;　　q->next=t;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　Position outq()</p><p><b>　　{</b></p><p>　　Position

38、 out;</p><p>　　out.row=team_l->x;</p><p>　　out.col=team_l->y;</p><p>　　team_l=team_l->next;</p><p>　　return out;</p><p><b>　　}</b><

39、/p><p>　　void find_path()</p><p><b>　　{</b></p><p>　　Position offset[4];</p><p>　　Position here={start.row,start.col};</p><p>　　Position nbr={0,0}

40、;</p><p>　　int num_of_nbrs=4;</p><p><b>　　int i,j;</b></p><p>　　offset[0].row=0;offset[0].col=1; //右</p><p>　　offset[1].row=1;offset[1].col=0; //下</p>

41、<p>　　offset[2].row=0;offset[2].col=-1;//左</p><p>　　offset[3].row=-1;offset[3].col=0;//上</p><p>　　printf("\n開始搜索路徑...\n");</p><p>　　if((start.row == end.row)&&a

42、mp;(start.col == end.col)){</p><p>　　path_len = 0;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　while(1)</b></p><

43、;p><b>　　{</b></p><p>　　for(i=0;i<num_of_nbrs;i++)</p><p><b>　　{</b></p><p>　　nbr.row=here.row+offset[i].row;</p><p>　　nbr.col=here.col+off

44、set[i].col;</p><p>　　if(a[nbr.row][nbr.col]==0)</p><p><b>　　{</b></p><p>　　a[nbr.row][nbr.col]=a[here.row][here.col] + 1;</p><p>　　if((nbr.row == end.row) &

45、amp;& (nbr.col == end.col))</p><p><b>　　break;</b></p><p>　　inq(nbr); //nbr入隊(duì)</p><p><b>　　}</b></p><p><b>　　}</b></p><

46、;p>　　//是否到達(dá)目標(biāo)位置finish</p><p>　　if((nbr.row == end.row) && (nbr.col == end.col))</p><p><b>　　break;</b></p><p>　　//或節(jié)點(diǎn)隊(duì)列是否為空</p><p>　　if(team_l==N

47、ULL)</p><p><b>　　{ </b></p><p>　　printf("\n沒有結(jié)果!!!\n");</p><p><b>　　return ;</b></p><p><b>　　}</b></p><p>　　h

48、ere=outq();</p><p><b>　　}</b></p><p>　　path_len=a[end.row][end.col];</p><p><b>　　here=end;</b></p><p>　　for(j=path_len-1;j>=0;j--)</p>

49、<p><b>　　{</b></p><p>　　path[j] = here;</p><p>　　for(i = 0;i < num_of_nbrs;i++)</p><p><b>　　{</b></p><p>　　nbr.row = here.row + offset[

50、i].row;</p><p>　　nbr.col = here.col + offset[i].col;</p><p>　　if(a[nbr.row][nbr.col] == j) //+ 2)</p><p><b>　　break;</b></p><p><b>　　}</b></p

51、><p><b>　　here=nbr;</b></p><p><b>　　}</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　void out_path()&l

52、t;/p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　printf("\n路徑為:\n");</p><p>　　printf("(%d,%d) ",start.row,start.col);</p

53、><p>　　for(i=0;i<path_len;i++)</p><p><b>　　{</b></p><p>　　printf("(%d,%d) ",path[i].row,path[i].col);</p><p><b>　　}</b></p>&l

54、t;p>　　printf("\n");</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p&g

55、t;　　input_data();</p><p><b>　　output();</b></p><p>　　find_path();</p><p>　　out_path();</p><p><b>　　output();</b></p><p><b>　　

56、}</b></p><p><b>　　運(yùn)行結(jié)果與分析：</b></p><p>　　根據(jù)運(yùn)行的結(jié)果我們看到，首先要給布線區(qū)域加一道“圍墻”，從開始點(diǎn)進(jìn)行標(biāo)記。直達(dá)到達(dá)結(jié)束點(diǎn)。并且可以看到a到b的路徑不是唯一的，及最優(yōu)解不是唯一的。</p><p>　　2 動(dòng)態(tài)規(guī)劃解決最長(zhǎng)公共子序列問題</p><p>&l

57、t;b>　　2.1 問題重述</b></p><p>　　若給定序列={, ,…,}，則另一序列={,,…,}，是的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{, ,…, }使得對(duì)于所有j=1,2,…,k有：=。例如，序列={B，C，D，B}是序列={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X

58、和Y的公共子序列。請(qǐng)使用C語言編程，設(shè)計(jì)一個(gè)有效的算法解決下述問題：給定2個(gè)序列X={, ,…,}，和Y={ , ,…,}，找出X和Y的最長(zhǎng)公共子序列。</p><p><b>　　2.2問題分析</b></p><p>　　設(shè)序列X={, ,…,}和Y={ , ,…,}的最長(zhǎng)公共子序列為={,,…,}，則</p><p>　　(1)若，則，且

59、是和的最長(zhǎng)公共子序列。</p><p>　　(2)若且，則Z是和Y的最長(zhǎng)公共子序列。</p><p>　　(3)若且，則Z是X和的最長(zhǎng)公共子序列。</p><p>　　由此可見，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。</p><p>　　2.3算法分析與設(shè)計(jì)</p><p><b>

60、　　算法分析：</b></p><p>　　動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題

61、，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中，這就是動(dòng)態(tài)規(guī)劃法的基本思路。</p><p><b>　　算法設(shè)計(jì)：</b></p><p>

62、;　　由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，={, ,…,} ={ , ,…, }。當(dāng)i=0或j=0時(shí)，空序列是和的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。程序的設(shè)計(jì)思路是：調(diào)用函數(shù)void Initialize（），輸入兩個(gè)字符串，對(duì)兩個(gè)串的存儲(chǔ)數(shù)組b，c進(jìn)行動(dòng)態(tài)分配。調(diào)用函數(shù)void LCSLength（int m,int n,string x,st

63、ring y,int**c,int**b），將長(zhǎng)度較小的字符串作為第一參數(shù)，將長(zhǎng)度較大的字符串作為第二個(gè)參數(shù)。調(diào)用函數(shù)void LCS（inti，int j,string x,int**b）構(gòu)造最長(zhǎng)公共子序列調(diào)用函數(shù)。調(diào)用函數(shù)ReadCommand進(jìn)行系統(tǒng)操作屏幕指示，然后利用函數(shù)void Interpret（char&cmd）對(duì)函數(shù)進(jìn)行總體操作，最后得出最長(zhǎng)公共子序列。</p><p>　　2.4算法實(shí)

64、現(xiàn)與結(jié)果</p><p><b>　　代碼如下：</b></p><p>　　#include<iostream></p><p>　　#include<string></p><p>　　using namespace std;</p><p>　　string x,y;

65、//x,y用來存放字符序列</p><p>　　int **c,**b,m,n;</p><p>　　/*m，n分別存儲(chǔ)字符串x,y的長(zhǎng)度,數(shù)組c[i][j]存儲(chǔ)Xi和Yj得最長(zhǎng)公共子序列的長(zhǎng)度，</p><p>　　b[i][j]記錄c[i][j]的值是有哪一個(gè)子問題的解得到的*/</p><p>　　void LCSLength(int

66、m,int n,string x,string y,int **c,int**b);</p><p>　　void LCS(int i,int j,string x,int **b);</p><p>　　void Initialize();//對(duì)數(shù)組b,c動(dòng)態(tài)分配空間以及對(duì)其進(jìn)行初始化</p><p>　　void ReadCommand(char &cm

67、d);</p><p>　　void Interpret(char &cmd);</p><p>　　void Realese();//釋放指針</p><p>　　void Display();</p><p>　　int main()</p><p><b>　　{</b></p

68、><p>　　char cmd;</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　ReadCommand(cmd);</p><p>　　Interpret(cmd);</p><p>　　}whil

69、e(cmd!='q'&&cmd!='Q');</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void ReadCommand(char &cmd)</p><p><b

70、>　　{</b></p><p>　　system("cls"); //清屏</p><p>　　cout<<"\n--------------------------------------------------------------------------\n";</p><p>　　

71、cout<<"\n\t\t\t\t操 作 提 示";</p><p>　　cout<<"\n--------------------------------------------------------------------------\n";</p><p>　　cout<<"\tquit--

72、q/Q \t\t continue---c/C\n";</p><p><b>　　do{</b></p><p>　　cout<<"\n\n\t請(qǐng)選擇操作：";</p><p><b>　　cin>>cmd;</b></p><p>　　cou

73、t<<"\n--------------------------------------------------------------------------\n";</p><p>　　}while(cmd!='c'&&cmd!='C'&&cmd!='q'&&cmd!='Q&

74、#39;);</p><p><b>　　}</b></p><p>　　void Initialize()</p><p><b>　　{</b></p><p>　　cout<<"分別輸入兩個(gè)字符串（每個(gè)字符串以回車結(jié)束）\n";</p><

75、p><b>　　cin>>x;</b></p><p><b>　　cin>>y;</b></p><p>　　m=x.length();</p><p>　　n=y.length();</p><p>　　c=new int*[m+1];</p><

76、;p>　　b=new int*[m+1];</p><p>　　for(int i=0;i<=m;i++)</p><p><b>　　{</b></p><p>　　c[i]=new int[n+1];</p><p>　　b[i]=new int[n+1];</p><p><

77、;b>　　}</b></p><p><b>　　}</b></p><p>　　void Realese()//釋放指針board</p><p><b>　　{</b></p><p>　　for(int i=0;i<=m;i++)</p><p>

78、;<b>　　{</b></p><p>　　delete c[i];</p><p>　　delete b[i];</p><p><b>　　}</b></p><p>　　delete[] c;</p><p>　　delete[] b;</p><

79、p><b>　　}</b></p><p>　　void Interpret(char &cmd)</p><p><b>　　{</b></p><p>　　switch(cmd)</p><p><b>　　{</b></p><p>

80、<b>　　case 'c':</b></p><p>　　case 'C': </p><p>　　Initialize();</p><p>　　LCSLength(m,n,x,y,c,b);</p><p>　　Display();</p><p>　　Rea

81、lese();</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void LCSLength(int m,int n,string x,string y,int **c,int

82、**b)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<=m;i++)c[i][0]=0;</p><p>　　for(i=1;i<=n;i++)c[0][i]=0;</p><p

83、>　　for(i=1;i<=m;i++)</p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{</b></p><p>　　if(x[i-1]==y[j-1])</p><p><b>　　{</b></p><p>　　c

84、[i][j]=c[i-1][j-1]+1;</p><p>　　b[i][j]=1;</p><p><b>　　}</b></p><p>　　else if(c[i-1][j]>=c[i][j-1])</p><p><b>　　{</b></p><p>　　c[

85、i][j]=c[i-1][j];</p><p>　　b[i][j]=2;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　c[i][j]=c[i][j-1

86、];</p><p>　　b[i][j]=3;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//構(gòu)造最長(zhǎng)公共子序列</p><p>　

87、　void LCS(int i,int j,string x,int **b)</p><p><b>　　{</b></p><p>　　if(i==0||j==0)return;</p><p>　　if(b[i][j]==1)</p><p><b>　　{</b></p>&l

88、t;p>　　LCS(i-1,j-1,x,b);</p><p>　　cout<<x[i-1];</p><p><b>　　}</b></p><p>　　else if(b[i][j]==2)LCS(i-1,j,x,b);</p><p>　　else LCS(i,j-1,x,b);</p>

89、;<p><b>　　}</b></p><p>　　void Display()</p><p><b>　　{</b></p><p>　　LCS(m,n,x,b);</p><p>　　cout<<"\n請(qǐng)按回車鍵繼續(xù)！\n";</p>

90、<p>　　cin.get();</p><p>　　cin.get();</p><p><b>　　}</b></p><p><b>　　結(jié)果分析：</b></p><p>　　通過代碼和運(yùn)行結(jié)果，我們能夠看到，首先對(duì)二個(gè)序列進(jìn)行動(dòng)態(tài)分配，將長(zhǎng)度較小的字符串作為第一參數(shù)，將長(zhǎng)度較