首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

求大神指点,关于最大公共子序列程序!

2013-01-07 
求大神指导,关于最大公共子序列程序!!挑错挑了好久,但实在不懂哪里错了,代码如下~说是内存溢出好像。。。#inc

求大神指导,关于最大公共子序列程序!!
挑错挑了好久,但实在不懂哪里错了,代码如下~
说是内存溢出好像。。。

#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
   int i,j;
   for(i=1;i<=m;i++) c[i][0]=0;
   for(i=1;i<=n;i++) c[0][i]=0;
   for(i=1;i<=m;i++)
     for(j=1;j<=n;j++)
     {
       if(x[i]==y[j])
        {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;}
     }
}

void LCS(int i,int j,char *x,int b[8][7] )
{
   if(i==0||j==0) return;
   if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}
   else if(b[i][j]=2)  LCS(i-1,j,x,b);
   else LCS(i,j-1,x,b);
}
int main()
{
   int c[8][7]={{0}};
   int b[8][7]={{0}};  
   char X[8]={' ','A','B','C','B','D','A','B'};
   char Y[7]={' ','B','D','C','A','B','A'};
   LCSLength(8,7,X,Y,c,b);
   printf("最大公共子序列长度为%d\n",c[7][6]);
   LCS(7,6,X,b);
   return 1;
}

[解决办法]
不看算法 数组访问越界了。。
[解决办法]
LCSLength(8,7,X,Y,c,b);
=>
LCSLength(7,6,X,Y,c,b);

else if(b[i][j]=2)
=>
else if(b[i][j]==2)
[解决办法]
//最长公共子序列字符个数
//c[i][j]保存字符串 {xi},{yj},(长度分别为i,j)的最长公共子序列的字符个数
//i=0或者是j=0 时,c[i][j]必定为零, i,j>=0 且 xi=yj, c[i][j]=c[i-1][j-1]+1
//若 i,j>0 但xi!=yj, c[i][j]=max{ c[i-1][j] , c[i][j-1] }
#include <stdio.h>
#include <string.h>
int c[1001][1001];
void lcs(int a, int b, char x[], char y[], int c[][1001]) {
    int i,j;
    for(i=1;i<a;i++)
        c[i][0]=0; //if b==0, set c[i][j]=0;
    for(i=1;i<b;i++)
        c[0][i]=0; // if a==0; set c[i][j]=0;
    for(i=1;i<=a;i++) // if a!=0,b!=0 loop
        for(j=1;j<=b;j++) {
            if(x[i-1]==y[j-1])
                c[i][j]=c[i-1][j-1]+1;
            else if (c[i-1][j]>=c[i][j-1])
                c[i][j]=c[i-1][j];
            else
                c[i][j]=c[i][j-1];
        }
}


int main() {
    char x[1001],y[1001];
    while ( scanf("%s%s",x,y)!=EOF ) {
        int a=strlen(x);
        int b=strlen(y);
        memset(c,0,sizeof(c));
        lcs(a,b,x,y,c);
        printf("%d\n",c[a][b]);
    }
    return 0;
}

热点排行