你好亲爱的电脑爱好者。我又遇到了一个问题。
我应该编写一个最大堆。heap.h和main.c是预设的，应该是正确的。
我现在将实现 5 个函数：
Insert_heap
Heapify
Heap_create
Free_heap
Extract_max_heap
目前为止，一切都好。程序编译时没有错误。然而，Valgrind发现了内存错误：
"Invalid read / write of size 8" "use of uninitialized value"
我找不到内存错误。在下面我写的5个函数。我为结构道歉。
法典：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "heap.h"
#define MAX_HEAP_SIZE 400
#define MAX_LINE_SIZE 100
int left(int i) {
i = 2 * i;
return i;
}
int right(int i) {
i = 2 * i + 1;
return i;
}
int parent(int i) {
i = i / 2;
return i;
}
heap* heap_create(size_t capacity) {
heap* heap;
heap = malloc(sizeof(heap));
if(heap == NULL) {
printf("Kein Speicher vorhandenn");
return NULL;
}
heap->size = 0;
heap->capacity = capacity;
heap->elements = malloc(capacity * sizeof(int));
if(heap->elements == NULL) {
printf("Kein Speicher vorhandenn");
return NULL;
}
return heap;
}
void heapify(heap* h, size_t i) {
size_t links = left(i);
size_t rechts = right(i);
size_t largest;
if(links <= h->size) {
if(h->elements[(links)-1]>h->elements[i-1]) {
largest = links;
}
else if(h->elements[(links)-1]<h->elements[i-1])
largest = i;
}
if(rechts <= h->size && h->elements[rechts-1]>h->elements[i]) {
largest = rechts;
}
if(largest != i) {
size_t swap = h->elements[i];
h->elements[i] = h->elements[largest];
h->elements[largest] = swap;
heapify(h, largest);
}
}
int heap_extract_max(heap* h) {
if (h->size < 1) {
printf("Kein Element vorhanden!n");
return -1;
}
int max = h->elements[0];
for(int i = 1; i < ((h->size)-1); i++) {
h->elements[i-1] = h->elements[i];
}
h->size = ((h->size)-1);
heapify(h, 1);
return max;
}
int heap_insert(heap* h, int key) {
if (h->size < (h->capacity)) {
h->size = ((h->size)+1);
int i = h->size;
if(i == 1) {
h->elements[i-1] = key;
}
if(1 < i && i <= ((h->capacity))){
if(h->elements[(parent(i))-1] >= key) {
h->elements[i-1] = key;
}
else if(h->elements[(parent(i)-1)] < key) {
h->elements[i-1] = h->elements[(parent(i)-1)];
i = parent(i);
h->elements[i-1] = key;
heapify(h,h->elements[i-1]);
}
}
}
else if(h->size >= h->capacity) {
return -1;
}
return 0;
}
void heap_free(heap* h) {
free(h->elements);
free(h);
}
瓦尔格林德：
==5080== Memcheck, a memory error detector
==5080== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==5080== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==5080== Command: ./a1
==5080==
==5080== Invalid write of size 8
==5080== at 0x4008AD: heap_create (introprog_maxheap.c:56)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid write of size 8
==5080== at 0x4008BD: heap_create (introprog_maxheap.c:57)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080== Address 0x5203050 is 8 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
#######################
Boarding-Administration
Verfügbare Eingaben:
<Zahl> Verfügbare Sitzreihe eintragen.
n Nächste zu belegende Sitzreihe erhalten.
q Programm beenden.
> 12
==5080== Invalid read of size 8
==5080== at 0x400B45: heap_insert (introprog_maxheap.c:132)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid read of size 8
==5080== at 0x400B4D: heap_insert (introprog_maxheap.c:132)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203050 is 8 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid read of size 8
==5080== at 0x400B5E: heap_insert (introprog_maxheap.c:133)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid write of size 8
==5080== at 0x400B6A: heap_insert (introprog_maxheap.c:133)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid read of size 8
==5080== at 0x400B72: heap_insert (introprog_maxheap.c:134)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
> 33
==5080== Invalid read of size 8
==5080== at 0x400BB0: heap_insert (introprog_maxheap.c:139)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203050 is 8 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid read of size 8
==5080== at 0x400934: heapify (introprog_maxheap.c:80)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Invalid read of size 8
==5080== at 0x4009BC: heapify (introprog_maxheap.c:89)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Conditional jump or move depends on uninitialised value(s)
==5080== at 0x400A06: heapify (introprog_maxheap.c:93)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Use of uninitialised value of size 8
==5080== at 0x400A46: heapify (introprog_maxheap.c:95)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Use of uninitialised value of size 8
==5080== at 0x400A60: heapify (introprog_maxheap.c:96)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Invalid read of size 8
==5080== at 0x400934: heapify (introprog_maxheap.c:80)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Conditional jump or move depends on uninitialised value(s)
==5080== at 0x40093C: heapify (introprog_maxheap.c:80)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Invalid read of size 8
==5080== at 0x4009BC: heapify (introprog_maxheap.c:89)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x5203048 is 0 bytes after a block of size 8 alloc'd
==5080== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5080== by 0x40088C: heap_create (introprog_maxheap.c:51)
==5080== by 0x400F11: main (main_maxheap.c:73)
==5080==
==5080== Conditional jump or move depends on uninitialised value(s)
==5080== at 0x4009C4: heapify (introprog_maxheap.c:89)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Conditional jump or move depends on uninitialised value(s)
==5080== at 0x400A06: heapify (introprog_maxheap.c:93)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Use of uninitialised value of size 8
==5080== at 0x400A1A: heapify (introprog_maxheap.c:94)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Use of uninitialised value of size 8
==5080== at 0x400A46: heapify (introprog_maxheap.c:95)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080==
==5080== Invalid read of size 4
==5080== at 0x400A46: heapify (introprog_maxheap.c:95)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== Address 0x4001202d90 is not stack'd, malloc'd or (recently) free'd
==5080==
==5080==
==5080== Process terminating with default action of signal 11 (SIGSEGV)
==5080== Access not within mapped region at address 0x4001202D90
==5080== at 0x400A46: heapify (introprog_maxheap.c:95)
==5080== by 0x400A74: heapify (introprog_maxheap.c:97)
==5080== by 0x400CBD: heap_insert (introprog_maxheap.c:147)
==5080== by 0x400FA1: main (main_maxheap.c:92)
==5080== If you believe this happened as a result of a stack
==5080== overflow in your program's main thread (unlikely but
==5080== possible), you can try to increase the size of the
==5080== main thread stack using the --main-stacksize= flag.
==5080== The main thread stack size used in this run was 8388608.
==5080==
==5080== HEAP SUMMARY:
==5080== in use at exit: 1,608 bytes in 2 blocks
==5080== total heap usage: 4 allocs, 2 frees, 3,656 bytes allocated
==5080==
==5080== LEAK SUMMARY:
==5080== definitely lost: 0 bytes in 0 blocks
==5080== indirectly lost: 0 bytes in 0 blocks
==5080== possibly lost: 0 bytes in 0 blocks
==5080== still reachable: 1,608 bytes in 2 blocks
==5080== suppressed: 0 bytes in 0 blocks
==5080== Rerun with --leak-check=full to see details of leaked memory
==5080==
==5080== For counts of detected and suppressed errors, rerun with: -v
==5080== Use --track-origins=yes to see where uninitialised values come from
==5080== ERROR SUMMARY: 26 errors from 21 contexts (suppressed: 0 from 0)
Segmentation fault
仔细看看heap_create中的这些行：
heap* heap;
heap = malloc(sizeof(heap));
sizeof运算符是对名为 heap 的变量进行操作，还是对名为 heap 的类型进行操作？ 仅通过查看并不清楚，但根据 valgrind 输出，它看起来像是在引用变量。 它报告分配了 8 个字节，这可能是指针的大小（即heap变量）而不是类型。
因此，使用与类型同名的变量不是一个好主意。 因此，将变量heap的名称更改为类似 heap_top 或只是h以避免歧义。 然后，您应该分配适当的内存量。