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 関数では、最初に 2D 配列をハードコードされたサイズで NULL に初期化します。ただし、配列を初期化した後も、まだゴミでいっぱいです。そのため、Traverse 関数をヒットしても、if ステートメントはヒットしません。これらの文字と等しくならないからです。

4

1 に答える 1

0

解決策を見つけました！トラバース関数を呼び出していたとき

int row = ARRAY_ROW;
int col = ARRAY_COL;

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

最後の 2 つの引数については、19 と 19 で合格していました。次に、トラバース機能で

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[0-18][0-18] しか移動しないため、存在しない b[19][19] を読み取ることから始めようとしました。

次に、追加して修正しました

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

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

これで、最長の共通部分列を見つけることができます。

于 2015-11-11T01:08:08.807 に答える