程序在realloc直接运行时崩溃，但在调试模式下运行正常
程序在realloc直接运行时崩溃，但在调试模式下运行正常
提问于 2018-12-11 22:58:37
我正在尝试实现二进制堆，并在插入或删除新节点时动态分配和释放内存。因此，每当调用insert/delete节点时，我都会使用realloc来增加/减少内存。程序在调试模式下运行良好，但当我直接运行它时，它会崩溃(可能是在realloc)
我的推理是因为如果我删除delete函数中的realloc (这意味着我永远不会释放已经分配的内存)，程序在直接运行时运行得很好。代码中的问题可能是什么？
附言:我在Windows 10上使用Eclipse CDT和Cygwin
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
typedef struct heap
{
uint32_t size;
int32_t* heaparray;
}heap;
void insert_max(heap** h1, int32_t value)
{
uint32_t hole;
heap* h = *h1;
if(h->size == 0)
{
h->size = 2;
h->heaparray = (int32_t *)(malloc(sizeof(int32_t) * h->size));
h->heaparray[0] = 0;
h->heaparray[1] = value;
return;
}
hole = h->size++;
h->heaparray[0] = value;
h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));
//sift up
for(; value > h->heaparray[hole/2]; hole /= 2)
{
h->heaparray[hole] = h->heaparray[hole/2];
}
h->heaparray[hole] = value;
}
void printheap(heap* h)
{
uint32_t index;
printf("\nHeap: ");
for(index = 1; index < h->size; index++)
{
printf("%3d\t", h->heaparray[index]);
}
}
void siftDown_max(heap** h1, uint32_t index)
{
uint32_t rightIndex, leftIndex, maxIndex, temp;
heap* h = *h1;
leftIndex = (2 * index);
rightIndex = (2 * index) + 1;
if(rightIndex >= h->size)
{
if(leftIndex >= h->size)
return;
else
{
maxIndex = leftIndex;
}
}
else
{
if(h->heaparray[rightIndex] >= h->heaparray[leftIndex])
{
maxIndex = rightIndex;
}
else
{
maxIndex = leftIndex;
}
}
if(h->heaparray[index] < h->heaparray[maxIndex])
{
temp = h->heaparray[index];
h->heaparray[index] = h->heaparray[maxIndex];
h->heaparray[maxIndex] = temp;
siftDown_max(h1, maxIndex);
}
}
void siftDown_min(heap** h1, uint32_t index)
{
uint32_t rightIndex, leftIndex, minIndex, temp;
heap* h = *h1;
leftIndex = 2 * index;
rightIndex = (2 * index) + 1;
if(rightIndex >= h->size)
{
if(leftIndex >= h->size)
{
return;
}
else
{
minIndex = leftIndex;
}
}
else
{
if(h->heaparray[leftIndex] <= h->heaparray[rightIndex])
{
minIndex = leftIndex;
}
else
{
minIndex = rightIndex;
}
}
if(h->heaparray[index] > h->heaparray[minIndex])
{
temp = h->heaparray[minIndex];
h->heaparray[minIndex] = h->heaparray[index];
h->heaparray[index] = temp;
siftDown_min(h1, minIndex);
}
}
void Delete(heap** h1, bool maxflag)
{
uint32_t hole = 0;
heap* h = *h1;
if(h->size == 1)
{
h = NULL;
return;
}
else
{
hole = --h->size;
h->heaparray[1] = h->heaparray[hole];
h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));
if(maxflag)
{
siftDown_max(h1, 1);
}
else
{
siftDown_min(h1, 1);
}
}
}
void insert_min(heap** h1, int32_t value)
{
uint32_t hole_index = 0;
heap* local_heap = *h1;
if (local_heap->size == 0)
{
local_heap->size = 2;
local_heap->heaparray = (int32_t*)malloc(sizeof(int32_t) * local_heap->size);
local_heap->heaparray[0] = 0;
local_heap->heaparray[1] = value;
return;
}
hole_index = local_heap->size++;
local_heap->heaparray[0] = value;
for(; value < local_heap->heaparray[hole_index/2]; hole_index /= 2)
{
local_heap->heaparray[hole_index] = local_heap->heaparray[hole_index / 2];
}
local_heap->heaparray[hole_index] = value;
}
int main(void)
{
int hy = 0;
heap *newheap = (heap *)(malloc(sizeof(heap)));
newheap->size = 0;
insert_max(&newheap, 5);
insert_max(&newheap, 3);
insert_max(&newheap, 8);
insert_max(&newheap, 2);
insert_max(&newheap, 10);
insert_max(&newheap, 13);
insert_max(&newheap, 7);
insert_max(&newheap, 26);
insert_max(&newheap, 11);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
Delete(&newheap, true);
printheap(newheap);
insert_max(&newheap, 134);
printheap(newheap);
heap *minheap = (heap *)(malloc(sizeof(heap)));
minheap->size = 0;
insert_min(&minheap, 5);
printheap(minheap);
insert_min(&minheap, 3);
printheap(minheap);
insert_min(&minheap, 8);
printheap(minheap);
insert_min(&minheap, 2);
printheap(minheap);
insert_min(&minheap, 10);
printheap(minheap);
insert_min(&minheap, 13);
printheap(minheap);
insert_min(&minheap, 7);
printheap(minheap);
insert_min(&minheap, 26);
printheap(minheap);
insert_min(&minheap, 11);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
Delete(&minheap, false);
printheap(minheap);
insert_min(&minheap, 138);
printheap(minheap);
hy = 3;
return EXIT_SUCCESS;
}回答 1
Stack Overflow用户
发布于 2018-12-11 23:40:56
您在使用realloc时有一个潜在的错误
h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));如果realloc由于任何原因失败，它将返回NULL。当这种情况发生时，你的程序将严重崩溃。realloc只是一个丑陋的函数，你应该非常小心地使用它。
我没有解决你问题的办法。但是，我确实有一些关于构建堆的一般性建议，以及一般情况下可调整大小的集合数据结构。
通过在每次插入和删除时重新分配，您已经创建了一个具有O(n)插入和O(n)删除的堆。您也可以使用无序数组，因为每次重新分配和复制内存的开销掩盖了堆结构的好处。
如果你想使用一个动态数组，你应该从一些最小的大小开始，比如说16个项目，并跟踪你的数组中的空闲空间。当你重新分配的时候，增加超过1。也许你最好的选择是将数组的大小加倍。这样，你就可以摊销重新分配的成本。您的插入和删除变成O(log )而不是O(n)。
关键是您的heap结构需要一个count字段来跟踪堆中当前的项数：
typedef struct heap
{
uint32_t size; /* size of the heap array */
uint32_t count; /* number of items currently in the heap */
int32_t* heaparray;
}heap;所以当你插入的时候，你要检查count == size。如果是，则重新分配以使大小加倍。在插入和删除时，请始终在计算中使用count (而不是当前代码中的size )。
删除项目时，仅当size > count*2时才重新分配。这样，就可以最大限度地减少对realloc的调用。如果想要最小化堆占用的空间量，您可能还需要一个可以调用的trimToCount函数。
另外，重新考虑您对基于1的堆的选择。C数组是从0开始的，所以堆的根在索引0处是有意义的。调整父计算和子计算以便它们与基于0的堆一起工作是很简单的。有关此处推理的更多信息，请参阅https://stackoverflow.com/a/49806133/56778和http://blog.mischel.com/2016/09/19/but-thats-the-way-weve-always-done-it/。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53726812
复制相关文章
相似问题