资源描述：
《最长公共子序列课程设计文档及源码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最长公共子序列◊课程设计项目:说明：若给定序歹！JX二{Xi,X2,・・・,Xm}，则另一序列Z={zi,z2,...,zk},是X的子序列是指存在一个严格递增下标序列使得对于所有戸1,2,…,k有：zj=xijo例如,序列Z={B,C,D,B}是序列X二{A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7)o给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。设计要求：请使用C语言编程,设计一个有效的算法解决下述问题：给定2个序列X={xi,x2,...,xm}和Y={yi
2、,y2,...,yn}，找出X和Y的最长公共子序列。设计提示：{z={z设序列X={xi,X2,...,Xm}和Y={yi,y2,...,yn}的最长公共子序列为,Z2,・・.,Zk}，则若若若17—/lz123z(z(z(Xm=yn,则Zk=Xni=yn,且Zk_
3、是Xm-l和yn-l的最长公共子序列。XmHyn且ZkHXm，则Z是Xm.
4、和Y的最长公共子序列。XmHyn且ZkHy”则Z是X和yn-i的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。由最长公共子序列问题的最优子结构性质
5、建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中,Xi={xi,x2,...,xi}；Yj={y],y2,...,yj}o当i=0或j=0时，空序列是xi和比的最长公共子序列。故此时C[i][j]=Oo其他情况下，由最优子结构性质可建立递归关系如下：0/=0,7=0c[i][j]=c[i—1][/—1]+1i,j>0;兀=兀max{(?[/][j-1],c[i-1][j]}z,j>0;x,.丰y.◊课程设计目的：用c语言编程列出解决的方法，复习c语言的用法，提高动手实践能力◊课程设计内容♦需求分析：1.本演
6、示程序中，输入的x序列和y序列是任意的，当然是在不超过MAXSIZE的前提下进行的；1.演示程序以用户和计算机的对话方式执行，即在计算机的终端上显示“提示信息”Z后，由用户在键盘上输入相应数据(即X序列和Y序列)2.测试数据(1)x序列：ADJdjfk48*&*d(j*&hj6GHh%$y序列：AhdhGHGF67HGHGA%&HGF%$输出：Adh6GH%$(1)x序列：SDJFKJdkjfjA&*UJGHJ&A$y序列：SHJhjhdA&657HGFT$输岀：SJdA&GHA$(2)其余省略♦概要设计1.voidlcs_length(c
7、har*x,char*y,intc[][MAXSIZE])c[i,j]记录序列Xi和Yj的最长公共子序列的长度根据下面条件，构造类似图lcsjength的表0i=0J=0c[i][j]=^c[/-l][j-l]+lmax{c[/][j-1],c[i-1][j]}j0123456012345670QQ0QQQQT0T0T011Q1—1?12—20T1T12—2T2T201T1t2?23—30T12T2t3T30T13T340LT2tT34?4BAABCBDAB图LcsjengthCA2.intles(intc[][MAX
8、SIZE],char*x,char*y,intlen_x,intlen_y,char*lcs^arr)♦详细设计1.元素类型：C[i][j]记录Xi和Yj序列的最长公共子序列长度Lcs_arr数组存储最长公共子序列的元素2.每个模块的分析(1)主程序模块：intmain(void){inti,c;charx[MAXSIZE],y[MAXSIZE];wh订cd){printf(〃'y‘tocontinue,andyoucaninputlistofxandy;'rftostop:“)；c=getchar();if(c二二’n'){printf(
9、z，Areyousuretoquit,'y‘toquit,tocontinue:“)；getchar();c=getchar();if(cH'y'){exit(1);}elseif(c=='n'){getchar();printf(Z，Pleaseinputthearrayofx(like:ABCDEF):“)；if(fgets(x,sizeof(x),stdin)=NULL)exit(1);printf(z，Pleaseinputthearrayofy(like:ABCDEF):“)；if(fgets(y,sizeof(y),stdin)
10、=NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y
