Làm thế nào để giải phóng struct đệ quy (Trie)

Question

CUỐI CÙNG EDIT

chức năng của tôi mà giải phóng bộ nhớ hoạt động đúng, và như milevyo đã gợi ý, vấn đề nằm ở chỗ tạo nút, mà tôi đã cố định. Bây giờ tôi có một vấn đề riêng biệt, nơi chương trình segfaults khi chạy bình thường, nhưng nó không thể được sao chép trong gdb hoặc valgrind. Tuy nhiên, đó là một câu hỏi riêng biệt hoàn toàn.

Tôi đã phát hiện ra rằng sự phân đoạn này xảy ra vì tôi không kiểm tra ký tự EOF đúng cách. As per Cliff B's answer in this question, kiểm tra EOF chỉ xảy ra sau ký tự cuối cùng trong tệp. Kết quả là, trong hàm của tôi tải tệp từ điển, tôi đã gán ký tự cuối cùng của tệp cho một số i (trong trường hợp này là -1 theo lệnh gọi printf) và cố tạo và truy cập nút con nếu chỉ số -1. Điều này gây ra một lỗi phân đoạn, và cũng gây ra vấn đề với chức năng dỡ hàng của tôi, mà sẽ không dỡ bỏ nút cuối cùng tôi tạo ra.

Tại sao lỗi phân đoạn không xuất hiện khi tôi chạy chương trình trong gdb hoặc valgrind, tôi không biết.

EDIT 3

khi bước qua chức năng tải của tôi nơi tạo nút xảy ra, tôi nhận thấy một hành vi bất ngờ. Tôi tin rằng vấn đề nằm ở đâu đó trong các dòng mã này, được nhúng trong vòng lặp for. Việc truyền tới (node*) chỉ để an toàn, mặc dù nó không ảnh hưởng đến việc chạy mã theo kiến ​​thức của tôi.

// if node doesnt exist, calloc one, go to node 
if (current_node->children[i] == NULL) 
{ 
    current_node->children[i] = (node*) calloc(1, sizeof(node)); 
    nodes++; 
} 
current_node = current_node->children[i]; 

Trong khi đẩy mạnh thông qua chức năng tải, tôi thấy rằng current_node->children[i] của tôi dường như calloc 'ed đúng cách (tất cả trẻ em thiết lập để NULL), nhưng thời điểm này tôi bước vào current_node->children[i] và kiểm tra con của nó (xem hình dưới đây) , Tôi thấy rằng các địa chỉ bị bóp nghẹt. Cụ thể, con số'trong nút con được đặt thành 0x0 vì một số lý do. Trong khi 0x0 được cho là bằng NULL (đúng với tôi nếu tôi sai), hàm free_all của tôi dường như muốn đi vào con trỏ 0x0, điều này tất nhiên dẫn đến một segfault. Có ai có thể làm sáng tỏ điều này có thể xảy ra không?

Values of children[i]

EDIT 2: Tôi đang sử dụng calloc để tạo ra các nút của tôi

root = calloc(1, sizeof(node));

Đối với các nút con của tôi, họ được tạo ra trong một vòng lặp for nơi tôi lặp qua nhân vật của tệp từ điển tôi đang đọc.

if (current_node->children[i] == NULL) 
{ 
    current_node->children[i] = calloc(1, sizeof(node)); 
    nodes++; 
} 

c trong trường hợp này đại diện cho nhân vật của từ được đọc trong tôi nhận được i sử dụng như sau:.

if (c == '\'') 
    i = 26; 
else if (isalpha(c)) 
    i = c - 97; 

EDIT: Tôi nghĩ rằng một cái gì đó trong việc tạo nút của tôi là bị lỗi, như milevyo gợi ý.Điều này là do nếu tôi in ra các địa chỉ, nó đi từ 0x603250 đến 0x603340 đến 0x603430 đến 0x603520, sau đó cuối cùng là (nil), trước khi nó được phân tách. Tôi đã xác minh rằng nút gốc được truyền chính xác bằng cách in ra giá trị của nó trong gdb. Tôi sẽ cố gắng tìm ra.

ORIGINAL HỎI

Tôi đang chạy vào một segfault khi cố gắng để giải phóng một struct đệ quy, nhưng không thể tìm ra lý do tại sao, và muốn giúp đỡ.

struct của tôi được định nghĩa như sau:

typedef struct node 
{ 
    bool is_word; 
    struct node* children[27]; 
} 
node; 

này có nghĩa là để thực hiện một cấu trúc Trie trong đó để tải một cuốn từ điển vào, vì mục đích của một kiểm tra chính tả. Sau khi kiểm tra chính tả được thực hiện, tôi cần giải phóng bộ nhớ mà tôi đã phân bổ cho bộ ba.

Đây là chức năng hiện tại của tôi mà nên giải phóng Trie khi thông qua các nút gốc, nhưng nó segfaults khi làm như vậy, mặc dù không phải ngay lập tức:

void free_all(node* curs) 
{ 
    int i; 

    // recursive case (go to end of trie) 
    for (i = 0; i < 27; i++) 
    { 
     if (curs->children[i] != NULL) 
     { 
      free_all(curs->children[i]); 
     } 
    } 

    // base case 
    free(curs); 
} 

đâu có thể tôi đã đi sai? Nếu cần thêm thông tin, vui lòng cho tôi biết.

Answer 1

tôi nghĩ rằng, nút gốc bị lỗi (có thể là null). nếu không, hãy tìm nơi khác. trong việc tạo nút chẳng hạn.

void free_all(node* curs) 
{ 
    int i; 
    if(!curs) return; // safe guard including root node. 

    // recursive case (go to end of trie) 
    for (i = 0; i < 27; i++) 
     free_all(curs->children[i]); 


    // base case 
    free(curs); 
} 

Answer 2

Chức năng free_all là ok. Bạn phải kiểm tra bạn đặt thành NULL tất cả trẻ em không được phân bổ. Điều này bao gồm các nút không phải là lá, nhưng không có tất cả các trẻ em 27.

Nếu điều đó ổn, hoặc sửa chữa nó không khắc phục được segfault, bạn phải gỡ lỗi.