c - C 標準二分木

Question

私は、C プログラミングに関してはほとんど初心者です。

数日間、次の形式の式からバイナリツリーを作成しようとしました。

A(B,C(D,$))

各文字がノードです。

'('私のツリーのレベルを下げます（右へ）。

','私の木の左側の枝に行きます

'$'NULL ノードを挿入します。

')'レベルアップを意味します。

これは、2〜3日のコーディングの後に私が思いついたものです:

#define SUCCESS 0

typedef struct BinaryTree
{
char info;
BinaryTree *left,*right,*father;
}BinaryTree;



int create(BinaryTree*nodeBT, const char *expression)
{   
    nodeBT *aux;
    nodeBT *root;
    nodeBT *parent;
    nodeBT=(BinaryTree*) malloc (sizeof(BinaryTree));         
        nodeBT->info=*expression;
    nodeBT->right=nodeBT->left=NULL;
    nodeBT->father = NULL;

    ++expression;   
    parent=nodeBT;                                                 
    root=nodeBT;

    while (*expression)
        {if (isalpha (*expression))
            {aux=(BinaryTree*) malloc (sizeof(BinaryTree));
             aux->info=*expression;
             aux->dr=nodeBT->st=NULL;
             aux->father= parent;
             nodeBT=aux;}

        if (*expression== '(')
            {parent=nodeBT;
            nodeBT=nodeBT->dr;}

        if (*expression== ',')
            {nodeBT=nodeBT->father;
            nodeBT=nodeBT->dr;}

        if (*expression== ')')
            {nodeBT=nodeBT->father;
            parent= nodeBT->nodeBT;}

        if (*expression== '$')
            ++expression;

        ++expression;
    }

nodeBT=root;
return SUCCESS;
}

最後に、新しく作成されたツリーにアクセスしようとすると、「メモリが読み取れない 0xCCCCCC」が表示され続けます。そして、どこが間違っているのか、わずかなヒントもありません。

何か案が？

score 8 · Accepted Answer

いくつかの問題:

type の定義は示していませんが、、、およびをその型へのポインタとしてnodeBT宣言しています。auxrootparent
次に、 aを指すように宣言されていても、auxa を指すように代入します。BinaryTreenodeBT
に割り当てますがaux->dr、これはの一部ではないため、意図した場所にBinaryTree入力したとは限りません。に割り当てますが、それはどちらの一部でもありません。nodeBTBinaryTreenodeBT->stBinaryTree
を代入して、解析されたツリーを返そうとしますnodeBT=root。問題は、C が「値による呼び出し」言語であることです。これは、create関数がに代入するときnodeBT、ローカル変数の値のみを変更していることを意味します。の呼び出し元にcreateは、その変更が表示されません。したがって、呼び出し元はルートノードを受け取りません。これがおそらく、「メモリを読み取れません」というエラーが発生する理由です。呼び出し元は、ルートノードを含むメモリではなく、ランダムメモリにアクセスしています。

「再帰降下」と呼ばれる標準的な手法を使用してパーサーを作成すると、コードは実際にははるかに理解しやすくなります。方法は次のとおりです。

式の文字列から 1 つのノードを解析する関数を書きましょう。単純に、次のような署名が必要です。

BinaryTree *nodeFromExpression(char const *expression) {

ノードを解析するには、まずノードのを取得する必要がありますinfo:

    char info = expression[0];

次に、ノードに子が必要かどうかを確認する必要があります。

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[1] == '(') {

子が必要な場合は、それらを解析する必要があります。ここで、「再帰的」を「再帰的降下」に入れnodeFromExpressionます。各子を解析するために再度呼び出すだけです。左の子を解析するには、の最初の 2 文字をスキップする必要があります。これは、現在のノードのexpression情報とであるためです。(

        leftChild = nodeFromExpression(expression + 2);

しかし、適切な子を解析するためにどれだけスキップするのでしょうか? 左の子の解析中に使用したすべての文字をスキップする必要があります…</p>

        rightChild = nodeFromExpression(expression + ???

それが何文字だったのかわかりません！nodeFromExpression解析したノードだけでなく、消費した文字数の指標も返さなければならないことがわかりました。したがって、それを許可するには、の署名を変更する必要がありnodeFromExpressionます。解析中にエラーが発生した場合はどうなるでしょうか。nodeFromExpression解析したノード、消費した文字数、発生したエラー (エラーがあった場合) を返すために使用できる構造を定義しましょう。

typedef struct {
    BinaryTree *node;
    char const *error;
    int offset;
} ParseResult;

errorifが null でない場合はnodenull でありoffset、エラーが見つかった文字列内のオフセットであると言えます。それ以外の場合offsetは、解析に消費された最後の文字を過ぎたところnodeです。

したがって、最初からやり直して、nodeFromExpressionreturn aを作成しますParseResult。式文字列全体を入力として受け取り、解析を開始する文字列内のオフセットを受け取ります。

ParseResult nodeFromExpression(char const *expression, int offset) {

エラーを報告する方法ができたので、エラーチェックを行いましょう。

    if (!expression[offset]) {
        return (ParseResult){
            .error = "end of string where info expected",
            .offset = offset
        };
    }
    char info = expression[offset++];

これについては最初は触れませんでしたが、$ここで NULL のトークンを処理する必要があります。

    if (info == '$') {
        return (ParseResult){  
            .node = NULL,
            .offset = offset   
        };
    }

これで、子の解析に戻ることができます。

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[offset] == '(') {

したがって、左の子を解析するには、自分自身を再帰的に再度呼び出すだけです。再帰呼び出しでエラーが発生した場合、同じ結果が返されます。

        ParseResult leftResult = nodeFromExpression(expression, offset);
        if (leftResult->error)
            return leftResult;

OK、左の子を正常に解析しました。ここで、子の間のコンマを確認して消費する必要があります。

        offset = leftResult.offset;
        if (expression[offset] != ',') {
            return (ParseResult){
                .error = "comma expected",
                .offset = offset
            };
        }
        ++offset;

nodeFromExpressionこれで、正しい子を解析するために再帰的に呼び出すことができます。

        ParseResult rightResult = nodeFromExpression(expression, offset);

メモリをリークさせたくない場合、エラーのケースはもう少し複雑になります。エラーを返す前に、左の子を解放する必要があります。

        if (rightResult.error) {
            free(leftResult.node);
            return rightResult;
        }

freeを渡しても何もしないことに注意してNULLください。そのため、明示的に確認する必要はありません。

)次に、子の後にチェックして消費する必要があります。

        offset = rightResult.offset;
        if (expression[offset] != ')') {
            free(leftResult.node);
            free(rightResult.node);
            return (ParseResult){
                .error = "right parenthesis expected",
                .offset = offset
            };
        }
        ++offset;

and変数がまだスコープ内にある間に、ローカル変数leftChildと変数を設定する必要があります。rightChildleftResultrightResult

        leftChild = leftResult.node;
        rightChild = rightResult.node;
    }

必要に応じて両方の子を解析したので、返す必要があるノードを作成する準備が整いました。

    BinaryTree *node = (BinaryTree *)calloc(1, sizeof *node);
    node->info = info;
    node->left = leftChild;
    node->right = rightChild;

father最後にもう 1 つ、子のポインターを設定する必要があります。

    if (leftChild) {
        leftChild->father = node;
    }
    if (rightChild) {
        rightChild->father = node;
    }

最後に、成功したを返すことができますParseResult:

    return (ParseResult){
        .node = node,
        .offset = offset
    };
}

簡単にコピーアンドペーストできるように、すべてのコードをこの要点に入れました。

アップデート

コンパイラが構文を気に入らない場合は(ParseResult){ ... }、より優れたコンパイラを探す必要があります。この構文は 1999 年から標準になっています (§6.5.2.5 複合リテラル)。より優れたコンパイラを探している間は、次のように回避できます。

まず、2 つの静的関数を追加します。

static ParseResult ParseResultMakeWithNode(BinaryTree *node, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.node = node;
    result.offset = offset;
    return result;
}

static ParseResult ParseResultMakeWithError(char const *error, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.error = error;
    result.offset = offset;
    return result;
}

次に、問題のある構文をこれらの関数の呼び出しに置き換えます。例:

    if (!expression[offset]) {
        return ParseResultMakeWithError("end of string where info expected",
            offset);
    }

    if (info == '$') {
        return ParseResultMakeWithNode(NULL, offset);
    }

c - C 標準二分木

1 に答える 1

アップデート

Related

Reference