5

私は最近、挿入、検索、削除、および表示操作を行うバイナリ検索ツリーを C で実装しようとするかなり単純なコードを書きました。残念ながら、コードは機能していないようです。

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int data;
    struct TreeNode *leftChildNode;
    struct TreeNode *rightChildNode;
};

typedef struct TreeNode node;
node *rootNode = NULL;

void insertNode(int i, node *n) {
    if(n == NULL) {
        n = (node*)malloc(sizeof(node));
        n->leftChildNode = NULL;
        n->rightChildNode = NULL;
        n->data = i;
    }
    else 
    if(n->data == i)
        printf("\nThis value already exists in the tree!");
    else
    if(i > n->data)
        insertNode(i, n->rightChildNode);
    else
        insertNode(i, n->leftChildNode);
    }

void searchNode(int i, node *n) {
    if(n == NULL)
        printf("\nValue does not exist in tree!");
    else
    if(n->data == i)
        printf("\nValue found!");
    else
    if(i > n->data)
        searchNode(i, n->rightChildNode);
    else
        searchNode(i, n->leftChildNode);
    }

void deleteNode(int i, node *n) {
    if(n == NULL)
        printf("\nValue does not exist in tree!");
    else
    if(n->data == i) {
        if(n->leftChildNode == NULL)
            n = n->rightChildNode;
        else
        if(n->rightChildNode == NULL)
            n = n->leftChildNode;
        else {
            node *temp = n->rightChildNode;
            while(temp->leftChildNode != NULL)
                temp = temp->leftChildNode;
            n = temp;
        }
    }
    else
    if(i > n->data)
        deleteNode(i, n->rightChildNode);
    else
        deleteNode(i, n->leftChildNode);
    }

void displayPreOrder(node *n) {
    if(n != NULL) {
        printf("%d ", n->data);
        displayPreOrder(n->leftChildNode);
        displayPreOrder(n->rightChildNode);
    }
}

void displayPostOrder(node *n) {
    if(n != NULL) {
        displayPostOrder(n->leftChildNode);
        displayPostOrder(n->rightChildNode);
        printf("%d ", n->data);
    }
}

void displayInOrder(node *n) {
    if(n != NULL) {
        displayInOrder(n->leftChildNode);
        printf("%d ", n->data);
        displayInOrder(n->rightChildNode);
    }
}

int main(void) {
    int ch, num, num1;
    do {
        printf("\nSelect a choice from the menu below.");
        printf("\n1. Insert a node.");
        printf("\n2. Search for a node.");
        printf("\n3. Delete a node.");
        printf("\n4. Display the Binary Search Tree.");
        printf("\nChoice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1: printf("\nEnter an element: ");
                    scanf("%d", &num);
                    //printf("YESYES");
                    insertNode(num, rootNode);
                    break;

            case 2: printf("\nEnter the element to be searched for: ");
                    scanf("%d", &num);
                    searchNode(num, rootNode);
                    break;

            case 3: printf("\nEnter the element to be deleted: ");
                    scanf("%d", &num);
                    deleteNode(num, rootNode);
                    break;

            case 4: printf("\nSelect an order for the elements to be display in.");
                    printf("\n1. Pre-order.");
                    printf("\n2. Post-order.");
                    printf("\n3. In-order.");
                    printf("\nChoice: ");
                    scanf("%d", &num1);
                    switch(num1) {
                        case 1: printf("\nPre-order Display: ");
                                displayPreOrder(rootNode);
                                break;

                        case 2: printf("\nPost-order Display: ");
                                displayPostOrder(rootNode);
                                break;

                        case 3: printf("\nIn-order Display: ");
                                displayInOrder(rootNode);
                                break;

                        default: exit(0);
                    }
                    break;

            default: exit(0);
            }
        //printf("%d", rootNode->data);
        printf("\nIf you want to return to the menu, press 1.");
        printf("\nChoice: ");
        scanf("%d", &num);
    } while(num == 1);

    return 0;
}

実際、ブロック inが終了するprintf("%d", rootNode->data);直前のコメント行に注目してください。この行のコメントを外し、プログラムをコンパイルして実行すると、プログラムはセグメンテーション違反をスローします。このエラーが発生する理由と、コード全体が実行されない理由を誰か教えてもらえますか? 前もって感謝します。do-whilemain()

4

4 に答える 4

5

C が引数を処理する方法について誤解しています。C では、ポインターを含め、すべての引数が値で渡されます。関数内でポインターを再割り当てすると、そのポインターのコピーが再割り当てされます。

例えば：

void f ( int *p );

int *p;

f(p);

&p関数内でポインタのアドレス( )が異なります。どちらも同じ場所を指しています (値は同じです) が、アドレスはそれぞれ異なります。の戻り値にポインターを割り当てると、そのポインターmallocの関数ローカル コピーが割り当てられるだけです。

これを修正する 1 つの方法は、別のレベルの間接化を導入し、ポインタのアドレスを渡すことです: のvoid insertNode(int i, node **n)ように呼び出すことができますinsertNode(0, &n)。別のものに変更したい場合は、一度逆参照してから割り当てます*p = malloc(sizeof(node))。

もう 1 つの解決策は、関数がポインターを返して呼び出しコードに割り当てることですreturn malloc(sizeof(node))。malloc（注：実際には初期化コードの後に​​それを返します...また、Cの戻り値をキャストしないでください）。

于 2013-05-09T01:46:14.077 に答える
1

上部で、宣言します

node *rootNode = NULL;

実行しない場合insertNode(成功 - Matt の回答を参照)、ノードを印刷しようとするとノードは NULL のままになるため、segfault が発生するのはそのためです。

于 2013-05-09T01:41:02.920 に答える
1

printf ステートメントのコメントを外すとコードが segfault になる理由は、rootNode が NULL ポインターであるためです。関数呼び出しでこの NULL ポインターを逆参照すると、segfault が発生します。

rootNode が NULL ポインターである理由は、コードによって決して変更されないためです。呼び出すinsertNode() と、ローカル変数nが格納されている値rootNode(この場合は NULL) に設定されます。n関数内のへの変更は変更されinsertNode()ませんrootNode。

コードを修正するには、insertNodeおよびdeleteNode関数を変更して、ルート ノード ポインターへのポインターを受け入れるようにします。たとえば、insertCode()関数は次のようになります。

void insertNode(int i, node **n) {
    if(*n == NULL) {
        (*n) = (node*)malloc(sizeof(node));
        (*n)->leftChildNode = NULL;
        (*n)->rightChildNode = NULL;
        (*n)->data = i;
    }
    else
    {
        if((*n)->data == i)
        {
            printf("\nThis value already exists in the tree!");
        }
        else
        {
            if(i > (*n)->data)
                insertNode(i, &(*n)->rightChildNode);
            else
                insertNode(i, &(*n)->leftChildNode);
        }
    }
}

insertNode()rootNode への参照を使用して呼び出すようにコードを変更する必要もあります。insertNode(num, &rootNode);

また、さまざまな scanf 呼び出しの戻り値を確認することをお勧めします。0 を返す場合scanf("%d",x)、値は int に変換されず、x の内容は未定義です。コードがこのケースを適切に処理することが理想的です。

于 2013-05-09T02:24:26.500 に答える