最长公共子序列的C实现及文档

#include<stdio.h> #include<string.h> #define N 100 char b[N][N]; //用来快速构造x和y的一个LCS int c[N][N]; //表c[0..m,0..n]为一个按行计算表项的表,c[m，n]包含x和y的一个LCS的长度 void Init_Array(char *x) { printf("输入长度不超过%d的序列:\n",N); scanf("%s",x); } void LCS_LENGTH(char *x,char *y,int m,int n) { for(int i=0;i<=m;i++)//x和y中元素是从x[0]、y[0]开始 c[i][0]=0; for(int j=0;j<=n;j++) c[0][j]=0; for(i=0;i<=m;i++) for(j=0;j<=n;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]='*'; //*表示斜向上的箭头 } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]='|'; //|表示向上的箭头 } else { c[i][j]=c[i][j-1]; b[i][j]='-'; //-表示向左的箭头 } } } void PRINT_LCS(char x[],int i,int j) { if(i==-1||j==-1) //x和y中元素是从x[0]、y[0]开始 return; if(b[i][j]=='*') { PRINT_LCS(x,i-1,j-1); printf("%c",x[i]); } else if(b[i][j]=='|') PRINT_LCS(x,i-1,j); else PRINT_LCS(x,i,j-1); } void main( ) { char x[N],y[N]; int m,n,i,j; Init_Array(x); printf("***************************************\n"); Init_Array(y); printf("***************************************\n"); m=strlen(x); n=strlen(y); LCS_LENGTH(x,y,m,n); printf("表c为:\n"); for(i=0;i<=m;i++) { for(j=0;j<=n;j++) printf("%5d",c[i][j]); printf("\n"); } printf("***************************************\n"); printf("表b为:\n"); for(i=1;i<=m;i++) { for(j=1;j<=n;j++) printf("%5c",b[i][j]); printf("\n"); } printf("***************************************\n"); printf("x和y的LCS为:\n"); PRINT_LCS(x,m,n); printf("\n\n"); }