纠错?不知道哪儿的错!

Question

#include <stdio.h>
#include <string.h>
#define N 100
int lcslength(char a[], char b[], int c[N][N]);
char *lcs(char str[], char a[], char b[]);
int c[N][N];
char str[N];
int lcslength(char a[], char b[], int c[N][N])
{
   int i, j, sa , sb;
   sa = strlen(a);
   sb = strlen(b);
   for (i = 0; i < sa; i++)
   c[i][0] = 0;
   for (j = 0; j < sb; j++)
   c[0][j] = 0;
   for(i = 1; i <= sa; i++ )
      for( j = 1; j <= sb; j++)
      {
          if(a[i-1] == b[j-1])
          {
             c[i][j] = c[i-1][j-1] + 1;
          }
          if(c[i-1][j] > c[i][j-1])
          {
             c[i][j] = c[i-1][j];
          }
          else
          {
             c[i][j] = c[i][j-1];
          }
      }
      return c[sa][sb];
}char *lcs(char str[], char a[], char b[])
{
   int i, j;
   int k;
   i = strlen(a);
   j = strlen(b);
   k = lcslength(a,b,c);
   str[k] = '\0';
   k = k -1;
   while(k >= 0)
   {
      if(c[i][j] == c[i-1][j]) i--;
      if(c[i][j] == c[i][j-1]) j--;
      else
      {
         str[k] = a[i-1];
 k--;
         i--;
         j--;
      }
   }
   return str;
}
int main()
{
   char a[N], b[N];
   printf("input the first array:\n");
   gets(a);
   printf("input the second array:\n");
   gets(b);
   printf("the lcs:\n");
   puts(lcs(str, a, b));
   return 0;
}
是return c[sa][sb]没有返回值吗?
能不能有人具体指出来

Answer 1

应该返回的是个地址，你给的返回类型怎么是int ？

Answer 2

不知道楼主要实现什么功能，在VC上调试了一下，证实了我的一些猜想。感觉这里有问题
         if(a[i-1] == b[j-1])
          {
             c[i][j] = c[i-1][j-1] + 1; // 假设这里c[i][j] 变为1
          }
 // 因为这里都初始化为0，所以不会出现c[i-1][j] > c[i][j-1])  的情况
          if(c[i-1][j] > c[i][j-1]) 
          {
             c[i][j] = c[i-1][j];
          }
          else
          {
             c[i][j] = c[i][j-1]; // 所以这里c[i][j]又被重新赋值为0
          }
   结果是即使经过多重循环 ，c[i][j]都是为0
   也就是说
 k = lcslength(a,b,c); // 这里k一直是0
   str[k] = '\0';   所以puts(lcs(str, a, b));
没有结果输出就不足为奇了。

Answer 3

这是个最长公共子序列问题.给定两个序列
X = { x1 , x2 , ... , xm }
Y = { y1 , y2 , ... , yn }
求X和Y的一个最长公共子序列举例
X = { a , b , c , b , d , a , b }
Y = { b , d , c , a , b , a }
最长公共子序列为
LSC = { b , c , b , a

Answer 4

我再看了一下，确认问题确实是在int lcslength(char a[], char b[], int c[N][N])
中的
         if(a[i-1] == b[j-1])
          {
             c[i][j] = c[i-1][j-1] + 1; // 假设这里c[i][j] 变为1
          }
 // 因为这里都初始化为0，所以不会出现c[i-1][j] > c[i][j-1])  的情况
          if(c[i-1][j] > c[i][j-1]) 
          {
             c[i][j] = c[i-1][j];
          }
          else
          {
             c[i][j] = c[i][j-1]; // 所以这里c[i][j]又被重新赋值为0
          }

Answer 5

不对啊!
你执行玩{a,b,c,b,d,a,b}中的第一个b后,再执行c时,就有if(c[i-1][j] > c[i][j-1]) 
          {
             c[i][j] = c[i-1][j];
          }
这种情况了

Answer 6

字符串a :   a , b , c , b , d , a , b字符串b:    b , d , c , a , b , a 照你的说法， 执行c时，也就是说i==3时，我在i==3时设了一个条件断点，证实c[i-1][j] 和 c[i][j-1]的值都是0.兄弟，不用画表这么麻烦吧，在vc上调试一下，一切都很清楚。

Answer 7

这个题目是不是我把三个数组的边界搞错了.
我这里有个正确的代码,当时是照着这个编的.
//求给定的两个字符串的最大公共子串   
  #include<iostream>   
  #include<string>   
  using   namespace   std;   
  const   int   n=100;   
  int   c[n][n];   
  char   str[n];   
  int   lcs_len(string   a,string   b,int   c[][n])   
  {   
  int   sa=a.length();   
  int   sb=b.length();   
          int   i,j;   
  for(i=0;i<=sa;++i)c[i][0]=0;   
  for(j=0;j<=sb;++j)c[0][j]=0;   
  for(i=1;i<=sa;++i)   
  {   
  for(j=1;j<=sb;++j)   
  {   
  if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;   
  else   if(c[i][j-1]>c[i-1][j])c[i][j]=c[i][j-1];   
  else   c[i][j]=c[i-1][j];   
  }   
  }   
  return   c[sa][sb];   
  }   
  char* bulid_lcs(char  str[],string  a, string   b)   
  {   
  int  k,i=a.length(),j=b.length();   
  k=lcs_len(a,b,c);   
  str[k]='\0';   
  while(k>0)   
  {   
  if(c[i][j]==c[i-1][j])i--;   
  else   if(c[i][j]==c[i][j-1])j--;   
  else   
  {   
  str[--k]=a[i-1];   
  i--;j--;   
  }   
  }   
  return   str;   
  }   
  int   main()   
  {   
  string   a,b;   
  cout<<"enter   two   strings\n";   
  cout<<"enter   first   string:";   
  cin>>a;   
  cout<<"enter   second   string:";   
  cin>>b;   
  cout<<bulid_lcs(str,a,b);   
  system("PAUSE");   
  return   0;   
  }   
这是正确代码!
动态规划的方法

Answer 8

if(a[i-1] == b[j-1])
          {
             c[i][j] = c[i-1][j-1] + 1;
          }
          if(c[i-1][j] > c[i][j-1])
          {
             c[i][j] = c[i-1][j];
          }
          else
          {
             c[i][j] = c[i][j-1];
          }     和 if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;   
  else   if(c[i][j-1]>c[i-1][j])c[i][j]=c[i][j-1];   
  else   c[i][j]=c[i-1][j];     兄弟，你认为这两段代码一样吗？

Answer 9

问题解决了 ,有时后几天围着一个debug搞.
不知道是不是浪费时间,总想学高手们一下子就知道
原因,但是却不能够.是不是这是程序员必须经历的一个坎.

Answer 10

不是return c[sa][sb]没有返回值，而是是0，所以什么都没有。