21

我已经实现了一种压缩算法（使用霍夫曼编码），它使用节点的优先级队列（我定义的结构）。现在，当我在 linux 或 Visual Studio 中运行代码时，一切正常。当我在 Visual Studio 中检查内存泄漏时，没有给出。

现在的问题是，当我使用 valgrind 分析我的程序时，它以信号 11 (sigsegv) 终止。遇到的第一个错误是方法 delete min 中的“大小为 4 的无效读取”。之后的其他错误是：已释放大小为 453 的块内的地址为 0 字节，大小为 4 的无效写入，无效的释放、删除或重新分配。

谁能给我建议，我可能会犯什么样的错误？我已经在互联网上搜索了几个小时，但找不到我做错了什么（特别是因为它在不使用 valgrind 时才有效）。或提示如何调试并找出导致读取错误的原因。

非常感谢！

这是代码，以防有人想要查看它，但我想仅仅深入研究这个特定的代码并不容易。

我猜它与代码的优先级队列有关：

我做霍夫曼部分的部分 - >每次删除2个最小节点并将两者的总和添加回一个节点。

while(queue->size > 1){
    node* n1 = delete_min(queue);
    node* n2 = delete_min(queue); // all the errors are encountered in this call
    node* temp = (node*) calloc(sizeof(node),1);
    temp->amount = n1->amount + n2->amount;
    insert_node(queue,temp);
    n1->parent = temp;
    n2->parent = temp;
    temp->left = n1;
    temp->right = n2;
}

这是优先级队列的 delete_min 和 insert_node 方法：

void insert_node(priority_queue* p_queue, node* x){
    int i = p_queue->size;
    if(i == 0){
        p_queue->queue = (node**) malloc(sizeof(node*));
    }
    else{
        p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
    }
    p_queue->queue[p_queue->size] = x;

    while(i>=0 && p_queue->queue[i]->amount < p_queue->queue[(i-1)/2]->amount){
        node* temp = p_queue->queue[i];
        p_queue->queue[i] = p_queue->queue[(i-1)/2];
        p_queue->queue[(i-1)/2] = temp;
        i = (i-1)/2;
    }
    p_queue->size++;
}

node* delete_min(priority_queue* p_queue){
    node** queue = p_queue->queue;
    node* min = queue[0];

    if(p_queue->size>1){
        int r = 0;
        int current = 1; //left child of root

        queue[0] = queue[p_queue->size-1];
        queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->size));
        while(current < p_queue->size){
            //in case of 2 children, check if current needs to be right or left child
            if(current < p_queue->size-1 && queue[current] > queue[current+1]){
                current++;
            } 
            if(queue[current] < queue[r]){
                node* temp = queue[r];
                queue[r] = queue[current];
                queue[current] = temp;

                r = current;
                current = 2 * current;
            }
            else{
                break;
            }
            current++;
        }
    }
    else{
        free(queue);
        p_queue->size--;
    }
    return min;
}

编辑：添加了 valgrind 输出：

Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049901: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441db64 is 444 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid write of size 4
==1893==    at 0x8049906: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid free() / delete / delete[] / realloc()
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1893== 
==1893== 
==1893== Process terminating with default action of signal 11 (SIGSEGV)
==1893==  Access not within mapped region at address 0x0
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

第 331 行是 delete_min 中的行： node* min = queue[0];

编辑：

现在问题已经解决了。在接受的答案中，解释了原因。只需在 delete_min 中正确分配重新分配的值即可解决所有问题。

//realloc queue and assign new value to local queue var
p_queue->queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->grootte));
queue = p_queue->queue;
4

2 回答 2

28

我会向你解释第一个错误。

==1893== Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

在第 331 行，您可能正在读取一个（无符号）int，它位于您尚未为自己的程序分配的内存的一部分中。

==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==

这部分提供了有关您尝试读取的内存部分的更多信息。它说您已经使用了内存，但 reallox 释放了它。这意味着您正在从旧指针读取已重新分配的内存部分。

您应该确保使用指针 realloc 返回，而不是旧指针。

在 valgrind 之外运行时不会崩溃的原因是大多数时候，相同部分的内存将由 realloc 分配。所以指针保持不变，因此您的代码将起作用。然而，有时，realloc 会决定移动这部分内存，然后你的代码就会崩溃。Valgrind 正试图为此警告你。

当您使用返回的指针时，其余的错误可能会得到解决。

于 2012-11-25T10:41:40.283 回答
3

根据您的 Valgrind 错误，您可能正在访问然后释放已删除的节点。您应该考虑使用相应的行号发布 Valgrind 错误（在 gcc 中使用 -g 编译），以便我们更轻松地为您提供帮助。

编辑：最明显的错误，段错误，是你应该开始调试的地方。此行失败：

while((2*i)+2 < p_queue->grootte-1 && (queue[i]->amount > queue[(2*i)+1]->amount || queue[i]->amount > queue[(2*i)+2]->amount)){

大概是因为queue是NULL。为什么它是空的？可能是因为 realloc 没有分配任何东西。为什么它没有分配任何东西？要么是因为内存不足（不太可能），要么是因为你试图分配大小为 0 的东西。（有关 realloc 的详细信息，请参见http://www.cplusplus.com/reference/cstdlib/realloc/）。你怎么能要求尺寸 0？如果p_queue->size-1是 0。

于 2012-11-24T23:30:50.310 回答