我已经实现了一个压缩算法(使用霍夫曼编码),它使用节点的优先级队列(我定义的结构)。现在,当我在Linux或Visual Studio中运行代码时,一切正常。当我检查visual studio中的内存泄漏时,没有给出。Valgrind:无效的读取大小4 - > sigsegv,工作正常,没有valgrind和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行:节点* min =队列[0];
编辑:
现在问题就解决了。在接受的答案中,解释原因。只需指定realloced值正确,在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;
'while((2 * i)+2 < p_queue-> size-1' < - - 你提前停了,如果2 * i + 2 == size-1',左边的孩子仍然存在于队列中,但是你 –
delete_min中的代码确实不是很清楚,所以我重写了它(请参阅新代码),使用该程序仍然有效,但是在使用valgrind进行检查时,发现完全相同的错误仍然出现,我仍然不明白为什么它在运行时会工作,但在使用valgrind时失败 – HaS