0

私は再帰的に木を横断し、再帰を通して文字列を運ぼうとしています。

アイデアは（ハフマンコーディングの場合）、ルートから始めて、左に行く場合は0を文字列に連結し、右に行く場合は1を連結します。リーフに到達すると、最終的な文字列は0の文字列になります。そして1sはあなたの「エンコーディング」です。

これが私の関数です：

void encode_tree(bin_node *root, char *string)
{
if(root->left==NULL && root->right==NULL)
{
    root->encoding = string;
    printf("%d got an encoding of %s\n", root->data, root->encoding);
    return;
}

root->encoding = string;
encode_tree(root->left, strcat(string, "0"));
encode_tree(root->right, strcat(string, "1"));
}

しかし、このコードは間違っています、それは私に間違ったエンコーディングを与えます。

私がこの木を持っているとしましょう：

            3\65

        6\-1

            3\70

    9\-1

            2\66

        3\-1

            1\67
16\-1

    7\68

7/86のエンコーディングは0、1 / 67は100、2 / 66は101、3/70は110、3/65は111である必要があります。

しかし、これが私の関数から得られるエンコーディングです：

 7/68 got an encoding of 0
 1/67 got an encoding of 0100
 2/66 got an encoding of 01001
 3/70 got an encoding of 0100110
 3/65 got an encoding of 01001101
4

2 に答える 2

2

ここでの問題は、割り当てられた一意の文字列が1つだけであり、各要素に独自の一意のエンコーディングを与えようとしていることです。これは機能しません。これは、最後までに、それらがすべて同じ文字列を参照しているためです。

新しい文字列を使用または割り当てる必要があり、それをに割り当てるたびstrdupにコピーします。stringbin_node::encoding

変化する

root->encoding = string;

SetEncoding（root、string）;へ

どこ

void SetEncoding(bin_node* n, char* e)
{
    char *d = malloc (strlen (e) + 1);   // Space for length plus nul
    if (d == NULL) return NULL;          // No memory
    strcpy (d,s);                        // Copy the characters
    n->encoding = d; 
}
于 2013-02-25T01:41:03.617 に答える
0

strcatには文字列の末尾に文字を追加する効果がありますが、末尾から文字を削除するコードはどこにありますか？以下の例では、「1」の値が「0」の値に置き換わっていることに注意してください。これはあなたのコードには当てはまりません。コードは「0」を追加し、次に「0」の後に「1」を追加します。

// usage: encode_tree(root, string, string);
void encode_tree(bin_node *root, char *string, char *end)
{
    if(root->left==NULL && root->right==NULL)
    {
        *end = '\0';
        printf("%d got an encoding of %s\n", root->data, root->encoding);
        return;
    }

    root->encoding = string;
    *end = '0'; encode_tree(root->left, string, end + 1);
    *end = '1'; encode_tree(root->right, string, end + 1);

}

于 2013-02-25T03:03:40.567 に答える