0

我正在研究一个最长的公共子序列程序，由于某种原因，即使我将其中的所有内容都初始化为 NULL，我的数组仍然被垃圾填满。

    #include "main.h"

    int main()
    {
        //Provided char arrays containing sequences
        char X[] = { ' ', 's', 'k', 'u', 'l', 'l', 'a', 'n', 'd', 'c', 'r', 'o', 's', 's', 'b', 'o', 'n', 'e', 's' };
        char Y[] = { ' ', 'l', 'u', 'l', 'l', 'a', 'b', 'i', 'e', 's', 'f', 'o', 'r', 'b', 'a', 'b', 'i', 'e', 's' };

    //Char array that will contain the directions
    //for the longest subsequence
    char b[ARRAY_ROW][ARRAY_COL];

    int c[ARRAY_ROW][ARRAY_COL];

    //Envoking LCS function
    LongestCommonSubsequence(X, Y, b, c);

    int row = ARRAY_ROW;
    int col = ARRAY_COL;

    //Envoking traverse function
    Traverse(b, X, row, col);

    cout << "END PHASE" << endl;

    return 0;
}

void LongestCommonSubsequence(char x[], char y[], char b[ARRAY_ROW][ARRAY_COL], int c[ARRAY_ROW][ARRAY_COL])
{
    //hardcoded length look back here
    int m = ARRAY_ROW - 1;
    int n = ARRAY_COL - 1;

    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            c[i][j] = 0;
            b[i][j] = 0;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; 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] = '-';
            }
        }
    }

    return;
}

void Traverse(char b[][ARRAY_COL], char x[], int i, int j)
{

    if (i == 0 || j == 0)
        return;
    if (b[i][j] == '\\')
    {
        Traverse(b, x, i - 1, j - 1);
        cout << x[i];
    }
    else if (b[i][j] == '|')
    {
        Traverse(b, x, i - 1, j);
    }
    else
    {
        Traverse(b, x, i, j - 1);
    }
    return;
}

在我的 LongestCommonSubsequence 函数中，我做的第一件事是使用硬编码大小将二维数组初始化为 NULL。但是，在我初始化数组之后，它仍然充满了垃圾。所以当我点击我的 Traverse 函数时，没有一个 if 语句被命中，因为它从不等于那些字符。

4

1 回答 1

0

我找到了解决方案！当我调用 Traverse 函数时

int row = ARRAY_ROW;
int col = ARRAY_COL;

//Envoking traverse function
Traverse(b, X, row, col);

对于最后两个论点，我传入了 19 和 19。然后在我的 Traverse 函数中

void Traverse(char b[][ARRAY_COL], char x[], int i, int j)
{
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == '\\')
    {
        Traverse(b, x, i - 1, j - 1);
        cout << x[i];
    }
    else if (b[i][j] == '|')
    {
        Traverse(b, x, i - 1, j);
    }
    else
    {
        Traverse(b, x, i, j - 1);
    }
    return;
}

我们试图从读取不存在的 b[19][19] 开始，因为我们的数组只有 b[0-18][0-18]。

然后我们通过添加来修复它

int row = ARRAY_ROW - 1;
int col = ARRAY_COL - 1;

//Envoking traverse function
Traverse(b, X, row, col);

现在我们能够找到最长的公共子序列。

于 2015-11-11T01:08:08.807 回答