0

次のコードは、二分探索木を二重連結リストに変換するコードです。GDB では問題なく動作しますが、実行するとクラッシュします。二分探索ツリーへの入力が 2 つしかない場合、2 つ以上の入力がある場合は正常に動作し、クラッシュします。コードの問題の可能性。双方向リンクリストは循環リストではありません。したがって、最初のノードの前のノードは NULL であり、最後のノードの次のノードは NULL です。

#include<stdio.h>
struct node{
int data;
struct node* large;
struct node* small;
};

typedef struct node* Node;

void add_to_tree(Node *root, int num){
Node current = *root;
Node temp_store;
Node new_node = malloc(sizeof(Node));
new_node->data = num;
new_node->large = NULL;
new_node->small = NULL;

if(current == NULL){
    current = new_node;
    *root = current;
}
else
{
    while(current != NULL){
        temp_store = current;
        if(num > current->data)
            current = current->large;
        else
            current = current->small;
    }

    if(num <= temp_store->data)
        temp_store->small = new_node;
    else
        temp_store->large = new_node;
}
}
void display_list(Node head){
Node current = head;
if(head == NULL){
    printf("\nThe list is empty");
}
else{
    printf("\nThe list is:\n");
    while(current !=NULL){
        printf("%d\t", current->data);
        current = current->large;
    }
}
}

void join(Node a, Node b){
a->large = b;
b->small = a;
}

Node append(Node a, Node b){
Node aLast;
Node current;

if(a == NULL) return (b);
if(b == NULL) return (a);

current = a;
while(current->large != NULL)
    current = current->large;
aLast = current;

join(aLast, b);

return (a);
}

Node bst_to_dll(Node root){
Node aList;
Node bList;
if(root == NULL)
    return NULL;

aList = bst_to_dll(root->small);
bList = bst_to_dll(root->large);

root->small = NULL;
root->large = NULL;

aList = append(aList, root);
aList = append(aList, bList);

return aList;
}

int main(){
Node bin_tree = NULL;
Node d_list;


add_to_tree(&bin_tree, 1);
add_to_tree(&bin_tree, 2);
add_to_tree(&bin_tree, 3);

d_list = bst_to_dll(bin_tree);

display_list(d_list);

return 0;

}
4

1 に答える 1

1

プログラムは、コンパイル時に警告を生成します。

gcc -g t.c
t.c: In function ‘add_to_tree’:
t.c:13: warning: incompatible implicit declaration of built-in function ‘malloc’

また、Valgrindで32個のエラーが生成され、最初のエラーは次のとおりです。

==29346== Invalid write of size 8
==29346==    at 0x4005E9: add_to_tree (/tmp/t.c:15)
==29346==    by 0x400820: main (/tmp/t.c:97)
==29346==  Address 0x51b6078 is 0 bytes after a block of size 8 alloc'd
==29346==    at 0x4C2A4D6: malloc (coregrind/m_replacemalloc/vg_replace_malloc.c:263)
==29346==    by 0x4005D7: add_to_tree (/tmp/t.c:13)
==29346==    by 0x400820: main (/tmp/t.c:97)

バグを理解するには、これで十分です。

于 2012-09-10T00:27:55.207 に答える