求最长公共子序列 运行时不能输出子序列的结果 单步执行时b[i][j]=-858993460 求解
#include <stdio.h>#include <time.h>
#include <string.h>
#include <stdlib.h>
#define M 100
#define N 100
int num;
//最长公共子序列的长度
void LCS_length(char x[],char y[])
{
int m,n,i,j;
int c[M][N],b[M][N];
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
b[i][j]=0;
}
m=num;//数组x的长度
n=num;//数组Y的长度
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]=1;//斜
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;//上
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;//左
}
}
}
printf("最长公共子序列的长度为:%d\n",c[m][n]);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
printf("%d ",b[i][j]);
printf("\n");
}
//printf("%d ",b[m][n]);
//return 0;
}
//最长公共子序列
int Print_LCS(int b[M][N],char x[],int i,int j)
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
Print_LCS(b,x,i-1,j-1);
printf("%c ",x[i-1]);
}
else
if(b[i][j]==2)
Print_LCS(b,x,i-1,j);
else
Print_LCS(b,x,i,j-1);
return 0;
}
int main()
{
FILE *fp;
char number;
int i,m,n,b[M][N];
char x[M],y[N];
srand((unsigned) time(NULL)); //用时间做种,每次产生随机数不一样
printf("产生的字母的个数:");
scanf("%d",&num);
fp=fopen("input.txt","w");
if(fp==NULL)
{
printf("open file failed\n");
return -1;
}
for (i=0; i<num; i++)
{
number = rand() % 4 + 'a' ; //产生字母的随机数
x[i] = number;
fprintf(fp,"%c ",x[i]);
}
fprintf(fp,"\n");
for (i=0; i<num; i++)
{
number = rand() % 4 + 'a' ; //产生字母的随机数
y[i] = number;
fprintf(fp,"%c ",y[i]);
}
fprintf(fp,"\n");
fclose(fp);
LCS_length(x,y);
m=num;//数组x的长度
n=num;//数组Y的长度
printf("最长公共子序列为:");
Print_LCS(b,x,m,n);
return 0;
}