數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書-最長(zhǎng)公共子序列

課程設(shè)計(jì)說(shuō)明書課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)題目：最長(zhǎng)公共子序列院系：計(jì)算機(jī)科學(xué)與信息工程課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目最長(zhǎng)公共子序列學(xué)生姓名所在院系計(jì)算機(jī)科學(xué)與信息工程系專業(yè)、年級(jí)、班軟件工程2班設(shè)計(jì)要求：實(shí)現(xiàn)對(duì)兩個(gè)序列的快速比較并查找出最長(zhǎng)公共子序列。用動(dòng)態(tài)規(guī)劃的方法進(jìn)行實(shí)現(xiàn)。學(xué)生應(yīng)完成的工作：(1)根據(jù)課程設(shè)計(jì)要求，分析思路并構(gòu)建模型，劃分子模塊、完善其功能；(2)根據(jù)各模塊的功能設(shè)計(jì)并編寫程序段、連接各程序段使之形成一個(gè)有機(jī)的整體；(3)調(diào)試、運(yùn)行程序進(jìn)而得到正確的結(jié)果；(4)根據(jù)實(shí)驗(yàn)設(shè)計(jì)運(yùn)行過(guò)程，寫出實(shí)驗(yàn)論文并總結(jié)實(shí)驗(yàn)教訓(xùn)。參考文獻(xiàn)閱讀：(1)C語(yǔ)言程序設(shè)計(jì)（潭浩強(qiáng)第二版，清華大學(xué)出版社）；(2)數(shù)據(jù)結(jié)構(gòu)（吳偉民等C語(yǔ)言版，清華大學(xué)出版社）；(3)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（高曉兵等，清華大學(xué)出版社）；(4)算法分析與設(shè)計(jì)（鄭宗漢、鄭曉明，清華大學(xué)出版社）。工作計(jì)劃：(1)第一周的第一天：小組布置設(shè)計(jì)題目；說(shuō)明進(jìn)度安排。(2)第一周的第二天：小組審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料準(zhǔn)備。(3)第一周的第三天、第四天、第五天：程序編寫、上機(jī)調(diào)試任務(wù)下達(dá)日期：年月日任務(wù)完成日期：年月日指導(dǎo)教師（簽名）：學(xué)生（簽名）：最長(zhǎng)公共子序列摘要：現(xiàn)在幾個(gè)最常用的解決最長(zhǎng)公共子序列(C)問(wèn)題的算法的時(shí)間復(fù)雜度分別是O（pn）,O(n(mp))。這里m、n兩個(gè)待比較字符串的長(zhǎng)度，p是最長(zhǎng)公共子串的長(zhǎng)度。給出一種時(shí)間復(fù)雜度為O(n(mp)),空間復(fù)雜度為O(m+n)的算法.與以前的算法相比,不管在p<<m的情況下,還是在p接近m時(shí),這種算法都有更快的速度。下面我將使用動(dòng)態(tài)規(guī)劃的方法后進(jìn)行求證。關(guān)鍵詞：最長(zhǎng)公共子序列LCS目錄1設(shè)計(jì)背景………………51.1最長(zhǎng)公共子序列的需求…………51.2最長(zhǎng)公共子序列的應(yīng)用…………52．設(shè)計(jì)方案 ……………52.1問(wèn)題描述………52.2系統(tǒng)的模塊化…………………53.方案實(shí)施……………53.1問(wèn)題分析………64．結(jié)果與結(jié)論…………64.1求解過(guò)程………64.2關(guān)鍵程序代碼段詳細(xì)描述……74.3運(yùn)行結(jié)果………94.4課程設(shè)計(jì)總結(jié)…………………105.收獲與致謝…………106.參考文獻(xiàn)……………107.附件…………………101.設(shè)計(jì)背景1.1最長(zhǎng)公共子序列的需求LCS問(wèn)題的算法有著廣泛的應(yīng)用。最初對(duì)LCS問(wèn)題的研究是將它作為一種差分壓縮算法來(lái)研究的。例如，在版本管理系統(tǒng)中，一個(gè)文件經(jīng)過(guò)不斷地修改產(chǎn)生不同的版本，新產(chǎn)生的版本相對(duì)老版本變化并不大。為了節(jié)省存儲(chǔ)空間，我們可以將老文件版本與修改后新版本進(jìn)行比較，找出它們的相同部分和不同部分。這樣就不必將原始文件和修改文件都獨(dú)立存儲(chǔ)，而只需存儲(chǔ)老文件版本以及新老版本的不同部分即可。這種增量式存儲(chǔ)方法在文件版本較多的情況下能夠大大提高存儲(chǔ)效率。兩個(gè)文件版本的比較就類似于LCS問(wèn)題。LCS算法的時(shí)間復(fù)雜度與其它差分壓縮算法比較相對(duì)較高，它也不是壓縮比例最高的差分壓縮算法，所以現(xiàn)在它已經(jīng)基本退出了這方面的應(yīng)用。但在版本管理系統(tǒng)中，對(duì)同一文件的不同版本進(jìn)行比較與合并時(shí)，LCS算法還是有重要作用的。1.2最長(zhǎng)公共子序列的應(yīng)用在版本管理系統(tǒng)中，可以快速進(jìn)行修改存儲(chǔ)。LCS算法還可用在基因工程領(lǐng)域。如確定一種致病基因的基本方法就是將該疾病患者的DNA鏈與健康者的DNA鏈相比較，找出其中的相同部分與不同部分，再進(jìn)行分析。這種基因鏈的比較也可以用LCS算法來(lái)解決。2.設(shè)計(jì)方案2.1問(wèn)題描述最長(zhǎng)公共子序列(LongestCommonSubsequence，LCS)是將兩個(gè)給定字符串分別刪去零個(gè)或多個(gè)字符后得到的長(zhǎng)度最長(zhǎng)的相同字符序列。例如，字符串a(chǎn)bcabcabb與bcacacbb的最長(zhǎng)公共子序列為bcacabb。LCS問(wèn)題就是要求兩個(gè)給定字符串的最長(zhǎng)公共子序列。字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列<i0，i1，…，ik-1>，使得對(duì)所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。2.2系統(tǒng)的模塊化1.程序用到的抽象數(shù)據(jù)類型的定義；2.定義項(xiàng)；3.系統(tǒng)子程序及功能；4.實(shí)現(xiàn)人機(jī)交互。3.方案實(shí)施3.1問(wèn)題分析考慮最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：（1）

如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列；（2）

如果am-1!=bn-1，則若zk-1!=am-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；（3）

如果am-1!=bn-1，則若zk-1!=bn-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問(wèn)題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。4.結(jié)果與結(jié)論4.1求解過(guò)程(1)引進(jìn)一個(gè)二維數(shù)組c[][]，用c[i][j]記錄X[i]與Y[j]的LCS的長(zhǎng)度，b[i][j]記錄c[i][j]是通過(guò)哪一個(gè)子問(wèn)題的值求得的，以決定搜索的方向。

我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計(jì)算出來(lái)。此時(shí)我們根據(jù)X[i]=Y[j]還是X[i]!=Y[j]，就可以計(jì)算出c[i][j]。(2)問(wèn)題的遞歸式寫成：回溯輸出最長(zhǎng)公共子序列過(guò)程：(3)算法分析：由于每次調(diào)用至少向上或向左（或向上向左同時(shí)）移動(dòng)一步，故最多調(diào)用(m+n)次就會(huì)遇到i=0或j=0的情況，此時(shí)開始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)相同，故算法時(shí)間復(fù)雜度為O(m+n)。4.2關(guān)鍵程序代碼段詳細(xì)描述#include<iostream>#include<stdio.h>#include<string.h>#defineMAXLEN100usingnamespacestd;voidLCSLength(char*x,char*y,intm,intn,intc[][MAXLEN],intb[][MAXLEN]){inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=1;}else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}}voidPrintLCS(intb[][MAXLEN],char*x,inti,intj){if(i==0||j==0)return;if(b[i][j]==0){PrintLCS(b,x,i-1,j-1);printf("%c",x[i-1]);}elseif(b[i][j]==1)PrintLCS(b,x,i-1,j);elsePrintLCS(b,x,i,j-1);}intmain(intargc,char**argv){//charx[MAXLEN]={"ABCBDAB"};//chary[MAXLEN]={"BDCABA"};charx[MAXLEN];chary[MAXLEN];cout<<"請(qǐng)輸入第一個(gè)字符串："<<endl;cin>>x;cout<<"請(qǐng)輸入第二個(gè)字符串："<<endl;cin>>y;cout<<"最長(zhǎng)公共子序列為："<<endl;intb[MAXLEN][MAXLEN];intc[MAXLEN][MAXLEN];intm,n;m=strlen(x);n=strlen(y);LCSLength(x,y,m,n,c,b);PrintLCS(b,x,m,n);return0;}4.3程序運(yùn)行結(jié)果運(yùn)行結(jié)果圖：4.4課程設(shè)計(jì)總結(jié)通過(guò)本次設(shè)計(jì)，明白了最長(zhǎng)公共子序列的運(yùn)算過(guò)程。在做最長(zhǎng)公共子序列這個(gè)問(wèn)題時(shí)，嘗試了很多方法進(jìn)行求解，并進(jìn)行了多次的比較，最后得到在已知的算法中，利用動(dòng)態(tài)規(guī)劃進(jìn)行求解時(shí)比較快捷，并在時(shí)間復(fù)雜度和空間復(fù)雜度上有所減小。的在當(dāng)今信息時(shí)代，如何有效的利用計(jì)算機(jī)為人類服務(wù)已越來(lái)越引起人們的重視，遞歸算法正是一種應(yīng)用廣泛且非常有效的解決各種問(wèn)題的算法。5.收獲與致謝總的來(lái)說(shuō),在整個(gè)設(shè)計(jì)的過(guò)程中,對(duì)知識(shí)有了相當(dāng)程度的了解掌握,學(xué)會(huì)了在一個(gè)問(wèn)題上進(jìn)行多種分析，并在不理解的基礎(chǔ)上去翻閱資料解決它，提高了學(xué)習(xí)能力。加深了對(duì)算法的理解。在學(xué)習(xí)的過(guò)程中要靈活的把所學(xué)的知識(shí)運(yùn)用到實(shí)踐當(dāng)中，并且還要鞏固練習(xí)和運(yùn)用，這樣才可以牢牢的記住。試驗(yàn)也對(duì)數(shù)據(jù)結(jié)構(gòu)的知識(shí)進(jìn)行了復(fù)習(xí)，尤其是遞歸及它的實(shí)現(xiàn)等知識(shí)點(diǎn)，在對(duì)程序不斷的修改和逐步改進(jìn)提升的過(guò)程中，積累了不少經(jīng)驗(yàn)，為在以后的學(xué)習(xí)和實(shí)踐應(yīng)用奠定了一定的基礎(chǔ)。這次課程設(shè)計(jì)受益非淺，學(xué)到了不少知識(shí)，同時(shí)也認(rèn)識(shí)到自身的不足，需要加強(qiáng)自身訓(xùn)練，學(xué)以致用，學(xué)會(huì)自我總結(jié)，吸取教訓(xùn)，積累經(jīng)驗(yàn)，在學(xué)習(xí)和實(shí)踐中來(lái)不斷的提升自己。6.參考文獻(xiàn)[1]C語(yǔ)言程序設(shè)計(jì)（潭浩強(qiáng)第二版，清華大學(xué)出版社）；[2]數(shù)據(jù)結(jié)構(gòu)（吳偉民等c語(yǔ)言版，清華大學(xué)出版社）；[3]數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（高曉兵等，清華大學(xué)出版社）；[4]算法分析與設(shè)計(jì)（鄭宗漢、鄭曉明，清華大學(xué)出版社）。7.附件附源程序清單電子檔一份指導(dǎo)教師評(píng)語(yǔ)：1、課程設(shè)計(jì)報(bào)告：a、內(nèi)容：不完整□完整□詳細(xì)□b、方案設(shè)計(jì)：較差□合理□非常合理□c、實(shí)現(xiàn)：未實(shí)現(xiàn)□部分實(shí)現(xiàn)□全部實(shí)現(xiàn)□d、文檔格式：不規(guī)范□基本規(guī)范□規(guī)范□2、出勤：全勤□缺勤