最長(zhǎng)公共子序列課程設(shè)計(jì)文檔及源碼

課程設(shè)計(jì)項(xiàng)目：說(shuō)明：若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={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和Y的公共子序列。設(shè)計(jì)要求：請(qǐng)使用C語(yǔ)言編程，設(shè)計(jì)一個(gè)有效的算法解決下述問(wèn)題：給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。設(shè)計(jì)提示：設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長(zhǎng)公共子序列。由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：課程設(shè)計(jì)目的：用c語(yǔ)言編程列出解決的方法，復(fù)習(xí)c語(yǔ)言的用法，提高動(dòng)手實(shí)踐能力課程設(shè)計(jì)內(nèi)容需求分析：本演示程序中，輸入的x序列和y序列是任意的，當(dāng)然是在不超過(guò)MAXSIZE的前提下進(jìn)行的；演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)的終端上顯示“提示信息”之后，由用戶在鍵盤(pán)上輸入相應(yīng)數(shù)據(jù)(即X序列和Y序列)測(cè)試數(shù)據(jù)x序列：ADJdjfk48*&*dfj*&hj6GHh%$y序列：AhdhGHGF67HGHG^%&HGF%$輸出：Adh6GH%$x序列：SDJFKJdkjfj^&*UJGHJ&^$y序列：SHJhjhd^&657HGH^$輸出：SJd^&GH^$(3)其余省略概要設(shè)計(jì)voidlcs_length(char*x,char*y,intc[][MAXSIZE])c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度根據(jù)下面條件，構(gòu)造類(lèi)似圖lcs_length的表圖Lcs_length2．intlcs(intc[][MAXSIZE],char*x,char*y,intlen_x,intlen_y,char*lcs_arr)把最長(zhǎng)公共子序列存儲(chǔ)在lcs_arr中，并返回子序列的長(zhǎng)度詳細(xì)設(shè)計(jì)元素類(lèi)型：C[i][j]記錄Xi和Yj序列的最長(zhǎng)公共子序列長(zhǎng)度Lcs_arr數(shù)組存儲(chǔ)最長(zhǎng)公共子序列的元素每個(gè)模塊的分析主程序模塊：intmain(void){inti,c;charx[MAXSIZE],y[MAXSIZE];while(1){printf("'y'tocontinue,andyoucaninputlistofxandy;'n'tostop:");c=getchar();if(c=='n'){ printf("Areyousuretoquit,'y'toquit,'n'tocontinue:"); getchar(); c=getchar(); if(c=='y'){ exit(1); } elseif(c=='n'){ getchar();printf("Pleaseinputthearrayofx(like:ABCDEF):");if(fgets(x,sizeof(x),stdin)==NULL)exit(1);printf("Pleaseinputthearrayofy(like:ABCDEF):");if(fgets(y,sizeof(y),stdin)==NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y,c);printf("Thelongestchildsequenceofxandyare:");lcs(c,x,y,len_x,len_y);printf("\n");}else{printf("theerrorinput,youshouldinput'y'or'n'\n\n");getchar();}} elseif(c=='y'){getchar();printf("Pleaseinputthearrayofx(like:ABCDEF):");if(fgets(x,sizeof(x),stdin)==NULL)exit(1);printf("Pleaseinputthearrayofy(like:ABCDEF):");if(fgets(y,sizeof(y),stdin)==NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y,c);printf("Thelongestchildsequenceofxandyare:");lcs(c,x,y,len_x,len_y);printf("\n");}else{printf("theerrorinput,youshouldinput'y'or'n'\n\n");getchar();}}return0;}構(gòu)造lcs_length表模塊//createthelcs_lengthtablevoidlcs_length(char*x,char*y,intc[][MAXSIZE]){inti,j;intlen_x=strlen(x);intlen_y=strlen(y);//Allofthefirstcolumnare0for(i=0;i<=len_x;++i)c[i][0]=0;//Allofthefirstroware0for(i=0;i<=len_y;++i)c[0][i]=0;for(i=1;i<=len_x;++i)for(j=1;j<=len_y;++j){//Thesituation:c[i][j]=c[i-1][j-1]+1(i,j>0;Xi=Yj)if(x[i-1]==y[j-1])c[i][j]=c[i-1][j-1]+1;//Thesituation:c[i][j]=max(c[i][j-1],c[i-1][j])(i,j>0;Xi!=Yi)elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];}}找出最長(zhǎng)子序列模塊voidlcs(intc[][MAXSIZE],char*x,char*y,intlen_x,intlen_y){inti,j;if(len_x==0||len_y==0)return;if(x[len_x-1]==y[len_y-1]){lcs(c,x,y,len_x-1,len_y-1);printf("%c",x[len_x-1]);}elseif(c[len_x-1][len_y]>=c[len_x][len_y-1])lcs(c,x,y,len_x-1,len_y);elselcs(c,x,y,len_x,len_y-1);}函數(shù)調(diào)用關(guān)系圖main()main()lcs_length()lcs()完整的程序#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXSIZE100//createthelcs_lengthtablevoidlcs_length(char*x,char*y,intc[][MAXSIZE]){inti,j;intlen_x=strlen(x);intlen_y=strlen(y);//Allofthefirstcolumnare0for(i=0;i<=len_x;++i)c[i][0]=0;//Allofthefirstroware0for(i=0;i<=len_y;++i)c[0][i]=0;for(i=1;i<=len_x;++i)for(j=1;j<=len_y;++j){//Thesituation:c[i][j]=c[i-1][j-1]+1(i,j>0;Xi=Yj)if(x[i-1]==y[j-1])c[i][j]=c[i-1][j-1]+1;//Thesituation:c[i][j]=max(c[i][j-1],c[i-1][j])(i,j>0;Xi!=Yi)elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];}}voidlcs(intc[][MAXSIZE],char*x,char*y,intlen_x,intlen_y){inti,j;if(len_x==0||len_y==0)return;if(x[len_x-1]==y[len_y-1]){lcs(c,x,y,len_x-1,len_y-1);printf("%c",x[len_x-1]);}elseif(c[len_x-1][len_y]>=c[len_x][len_y-1])lcs(c,x,y,len_x-1,len_y);elselcs(c,x,y,len_x,len_y-1);}intmain(void){inti,c;charx[MAXSIZE],y[MAXSIZE];while(1){printf("'y'tocontinue,andyoucaninputlistofxandy;'n'tostop:");c=getchar();if(c=='n'){ printf("Areyousuretoquit,'y'toquit,'n'tocontinue:"); getchar(); c=getchar(); if(c=='y'){ exit(1); } elseif(c=='n'){ getchar();printf("Pleaseinputthearrayofx(like:ABCDEF):");if(fgets(x,sizeof(x),stdin)==NULL)exit(1);printf("Pleaseinputthearrayofy(like:ABCDEF):");if(fgets(y,sizeof(y),stdin)==NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y,c);printf("Thelongestchildsequenceofxandyare:");lcs(c,x,y,len_x,len_y);printf("\n");}else{printf("theerrorinput,youshouldinput'y'or'n'\n\n");getchar();}} elseif(c=='y'){getchar();printf("Pleaseinputthearrayofx(like:ABCDEF):");if(fgets(x,sizeof(x),stdin)==NULL)exit(1);printf("Pleaseinputthearrayofy(like:ABCDEF):");if(fgets(y,sizeof(y),stdin)==NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y,c);printf("Thelongestchildse