二叉搜索樹的內存錯誤

-1

我執行C中的基本BST它好像我的插入函數工作，雖然我得到使用MEMCHECK時，如錯誤：二叉搜索樹的內存錯誤

==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A0D: bst_insert (bst.c:65) 
==7839== by 0x4007A5: main (bst-test.c:22) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A2B: bst_insert (bst.c:61) 
==7839== by 0x4007B2: main (bst-test.c:23) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A0D: bst_insert (bst.c:65) 
==7839== by 0x400A0D: bst_insert (bst.c:65) 
==7839== by 0x4007BF: main (bst-test.c:24) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A2B: bst_insert (bst.c:61) 
==7839== by 0x400A0D: bst_insert (bst.c:65) 
==7839== by 0x4007CC: main (bst-test.c:25) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A0D: bst_insert (bst.c:65) 
==7839== by 0x400A2B: bst_insert (bst.c:61) 
==7839== by 0x4007D9: main (bst-test.c:26) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009EF: bst_insert (bst.c:45) 
==7839== by 0x400A2B: bst_insert (bst.c:61) 
==7839== by 0x400A2B: bst_insert (bst.c:61) 
==7839== by 0x4007E6: main (bst-test.c:27) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009AF: bst_inorder (bst.c:30) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009D0: bst_inorder (bst.c:30) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009AF: bst_inorder (bst.c:30) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009D0: bst_inorder (bst.c:30) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009AF: bst_inorder (bst.c:30) 
==7839== by 0x4009C3: bst_inorder (bst.c:35) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x4009D0: bst_inorder (bst.c:30) 
==7839== by 0x400807: main (bst-test.c:29) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400A7F: bst_preorder (bst.c:77) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400AA0: bst_preorder (bst.c:77) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400A7F: bst_preorder (bst.c:77) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400AA0: bst_preorder (bst.c:77) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400A7F: bst_preorder (bst.c:77) 
==7839== by 0x400A98: bst_preorder (bst.c:84) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400AA0: bst_preorder (bst.c:77) 
==7839== by 0x400825: main (bst-test.c:31) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400AD4: bst_search (bst.c:91) 
==7839== by 0x400B38: dosearch (bst-test.c:10) 
==7839== by 0x400850: main (bst-test.c:34) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400AD4: bst_search (bst.c:91) 
==7839== by 0x400B38: dosearch (bst-test.c:10) 
==7839== by 0x40085D: main (bst-test.c:35) 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400dfe is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400d9f is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400da3 is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400de5 is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400da1 is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400da5 is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Invalid free()/delete/delete[]/realloc() 
==7839== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==7839== by 0x400980: bst_free (bst.c:21) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== Address 0x400da7 is not stack'd, malloc'd or (recently) free'd 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400989: bst_free (bst.c:22) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== Conditional jump or move depends on uninitialised value(s) 
==7839== at 0x400977: bst_free (bst.c:17) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x400992: bst_free (bst.c:23) 
==7839== by 0x40087F: main (bst-test.c:38) 
==7839== 
==7839== 
==7839== HEAP SUMMARY: 
==7839==  in use at exit: 224 bytes in 14 blocks 
==7839== total heap usage: 14 allocs, 7 frees, 224 bytes allocated 
==7839== 
==7839== LEAK SUMMARY: 
==7839== definitely lost: 80 bytes in 8 blocks 
==7839== indirectly lost: 144 bytes in 6 blocks 
==7839==  possibly lost: 0 bytes in 0 blocks 
==7839== still reachable: 0 bytes in 0 blocks 
==7839==   suppressed: 0 bytes in 0 blocks 
==7839== Rerun with --leak-check=full to see details of leaked memory 
==7839== 
==7839== For counts of detected and suppressed errors, rerun with: -v 
==7839== Use --track-origins=yes to see where uninitialised values come from 
==7839== ERROR SUMMARY: 39 errors from 35 contexts (suppressed: 0 from 0)

這裏是我的實現：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include "mylib.h" 
#include "bst.h" 

struct bstnode { 

    char *key; 
    bst left; 
    bst right; 

}; 

bst bst_free(bst b) { 

    if (b == NULL) { 

    return b; 
    } 
    free(b->key); 
    bst_free(b->left); 
    bst_free(b->right); 

    return b; 
} 

void bst_inorder(bst b, void f(char *str)) { 

    if (NULL == b) { 

    return; 
    } 

    bst_inorder(b->left, f); 

    f(b->key); 

    bst_inorder(b->right, f); 

} 

bst bst_insert(bst b, char *str) { 

    if (b == NULL) { 

    bst result = emalloc(sizeof *result); 
    result->key = str; 

    return result; 
    } 

    if (strcmp(b->key, str) == 0) { 

    return b; 
    } 

    if (strcmp(b->key, str) < 0) { 

    b->right = bst_insert(b->right, str); 
    return b; 
    } 

    b->left = bst_insert(b->left, str); 
    return b; 

} 

bst bst_new() { 

    return NULL; 
} 

void bst_preorder(bst b, void f(char *str)) { 

    if (NULL == b) { 

    return; 
    } 

    f(b->key); 

    bst_preorder(b->left, f); 
    bst_preorder(b->right, f); 

} 

int bst_search(bst b, char *str) { 

    if (NULL == b) { 

    return 0; 
    } 

    if (strcmp(b->key, str) == 0) { 

    return 1; 
    } 

    if (strcmp(b->key, str) < 0) { 

    return bst_search(b->right, str); 
    } 

    return bst_search(b->left, str); 

}

我只是測試它的另一個文件和我的輸出爲預期，但我也不太清楚爲什麼我得到這些消息。下面是我用它來檢查我的BST文件：

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

void print_key(char *key) { 
    printf("%s\n", key); 
} 

void dosearch(bst b, char *key) { 
    if (bst_search(b, key) == 0) { 
    printf("%s -- not found\n", key); 
    } else { 
    printf("%s -- found\n", key); 
    } 
} 

int main(void) { 

    bst b = bst_new(); 
    printf("inserting d,b,f,a,c,e,g\n"); 
    b = bst_insert(b, "d"); 
    b = bst_insert(b, "b"); 
    b = bst_insert(b, "f"); 
    b = bst_insert(b, "a"); 
    b = bst_insert(b, "c"); 
    b = bst_insert(b, "e"); 
    b = bst_insert(b, "g"); 
    printf("inorder traversal\n"); 
    bst_inorder(b, print_key); 
    printf("preorder traversal\n"); 
    bst_preorder(b, print_key); 
    printf("searching\n"); 
    dosearch(b, "f"); 
    dosearch(b, "o"); 
    dosearch(b, "x"); 
    dosearch(b, "e"); 
    dosearch(b, "d"); 
    bst_free(b); 
    return EXIT_SUCCESS; 

}

來源

2014-09-24 Paldan

'bst.c'中的哪行是行45和65？你能把它們標出來嗎？ – 2014-09-24 08:18:50

請顯示'bst'類型的定義。 – Lundin 2014-09-24 08:19:51

45是bst_insert下的第一行代碼，65是bst_insert中的最後一行代碼 – Paldan 2014-09-24 08:21:23

雖然我不知道這個emalloc功能使用，正常malloc不初始化分配的內存，這意味着left和right指針將不會被初始化。使用這些未初始化的指針會導致undefined behavior。

解決方案？分配後，只需將這些指針設置爲NULL即可。

來源

2014-09-24 08:21:32

另外'b-> key'指針看起來很腥，一般你會想要一個字符串的硬拷貝，而不僅僅是一個指向調用者字符串文字的指針。特別是不是一個非const的字符串文字指針... – Lundin 2014-09-24 08:25:22

我看到我完全忘了初始化左側和右側。這解決了一個問題。我認爲我的最後一個問題是用我的免費方法。我的錯誤之一是：地址0x400e0e不堆棧，malloc'd或（最近）free'd – Paldan 2014-09-24 08:28:06

@Paldan那是因爲你沒有爲'key'分配內存，你只是存儲一個指向字符串的指針。由於你不爲'key'分配內存，你不應該試圖釋放它。 – 2014-09-24 08:45:05

我猜你定義的 'BST' 像如下：

typedef struct bstnode *bst;

我認爲在bst_insert問題（）。
您確實只爲bst_node的指針變量分配內存。

bst result = emalloc(sizeof *result);

您必須爲bst_node本身和bst_node的鍵分配內存。
以下代碼部分用於解決問題。

bst bst_insert(bst b, char *str) { 
    if (b == NULL) { 
    { 
     bst result = emalloc(sizeof(struct bstnode)); 
     result->left = null; 
     result->right = null; 
     result->key = emalloc(strlen(str) + 1); 
     strcpy(result->key, str); 

     return result; 
    } 
    ..... 
}

來源

2014-09-24 08:37:10

二叉搜索樹的內存錯誤

回答

相關問題