程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> 算法-求助大神:c語言求最長公共子序列問題

算法-求助大神:c語言求最長公共子序列問題

編輯:編程解疑
求助大神:c語言求最長公共子序列問題

我寫的這個能正確求出最長序列元素個數但是輸出的最長序列卻是亂碼,求大神指教。代碼如下:
#include
#include
#include
#define MAX 101

int Long(char a[],char b[],char result[] )
{

int m,n;

m=strlen(a);
n=strlen(b);
int str[MAX][MAX];
int i,j,sum;

for(i=0;i<=m;i++)
{
    str[i][0]=0;
}
for(i=0;i<=n;i++)
{
    str[0][i]=0;
}
for(i=1;i<=m;i++)
{
    for(j=1;j<=n;j++)
    {
        if(a[i-1]==b[j-1])
        {
            str[i][j]=str[i-1][j-1]+1; 
        }
        else if(str[i-1][j]<str[i][j-1])
        {
            str[i][j]=str[i][j-1];
        }
        else
        {
            str[i][j]=str[i-1][j];
        }

    }
}

sum=str[m][n];
return sum;
   result[sum]='\0';
while(sum>=1)
{
    if(a[m-1]==b[n-1])
    {

      result[--sum]=a[m-1]; 
        m--;
        n--;

    }
    else if(str[m-1][n]<str[m][n-1])
    {

        n--;
    }
    else
    {
        m--;
    }
}

}

int main(void)
{
char a[MAX],b[MAX];
char result[MAX];
int i;
printf("請輸入數組a:\n");
gets(a);
printf("請輸入數組b:\n");
gets(b);

Long(a,b,result);
printf("%d\n",Long(a,b,result));
printf("%s",result);

system("PAUSE");
return 0;

}

最佳回答:


 #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 101

char * t;
int * i;

int cmp(const void * p, const void * q)
{
    return strcmp(&t[*(int *)p], &t[*(int *)q]);
}

void Long(char* a, char* b, char ** c)
{  
    t = new char[strlen(a) + strlen(b) + 2];
    strcpy(t, a);
    t[strlen(a)] = '#';
    strcpy(t + strlen(a) + 1, b);
    i = new int[strlen(a) + strlen(b) + 1];
    for (int j = 0; j < strlen(a) + strlen(b) + 1; j++) i[j] = j;
    qsort(i, strlen(a) + strlen(b) + 1, sizeof(int), cmp);
    int ma = 0;
    *c = (t + i[0]);
    for (j = 1; j < strlen(a) + strlen(b) + 1; j++)
    {
        int h = 0;
        char * l = &t[i[j - 1]];
        char * m = &t[i[j]];
        if ((i[j - 1] > strlen(a) && i[j] < strlen(a)) || (i[j] > strlen(a) && i[j - 1] < strlen(a)))
        {
            while (*l == *m && (*l) !='#' && (*m) !='#')
            {
                h++;
                l++;
                m++;
            }
            if (h > ma)
            {
                ma = h;
                *c = (t + i[j]);
            }
        }
    }
    (*c)[ma] = '\0';
}

int main(void)
{
    char a[MAX], b[MAX];
    printf("請輸入數組a:\n");
    gets(a);
    printf("請輸入數組b:\n");
    gets(b);
    char * c;
    Long(a,b,&c);
    printf("%s\n", c);
    return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved