Max Heap Segmentierung Fehler

Question

Hallo lieber Computerliebhaber. Ich habe wieder ein Problem.

Ich soll einen Max-Heap programmieren. Die heap.h und main.c sind voreingestellt und sollten korrekt sein.

Ich werde jetzt 5 Funktionen implementieren:

Insert_heap 
Heapify 
Heap_create 
Free_heap 
Extract_max_heap 

So weit so gut. Das Programm kompiliert ohne Fehler. Valgrind findet jedoch Speicherfehler:

"Invalid read/write of size 8" "use of uninitialized value" 

Ich kann die Speicherfehler nicht finden. In der Folge folgen die 5 von mir geschriebenen Funktionen. Ich entschuldige mich für die Struktur.

Code:

#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 vorhanden\n"); 
     return NULL; 
    } 
    heap->size = 0; 
    heap->capacity = capacity; 
    heap->elements = malloc(capacity * sizeof(int)); 
    if(heap->elements == NULL) { 
     printf("Kein Speicher vorhanden\n"); 
     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); 
} 

valgrind:

==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 

Answer 1

Werfen Sie einen genaueren Blick auf diese Linien in heap_create:

heap* heap; 
heap = malloc(sizeof(heap)); 

Ist der sizeof Operator auf den variablen Betrieb benannt heap oder der Typ mit der Bezeichnung heap? Es ist nicht klar, nur durch die Suche, aber basierend auf der Valgrind-Ausgabe sieht es so aus, als ob es sich auf die Variable bezieht. Es meldet, dass 8 Bytes zugewiesen wurden, was wahrscheinlich die Größe eines Zeigers ist (d. H. Die heap Variable) und nicht der Typ.

Aus diesem Grund ist es keine gute Idee, eine Variable mit dem gleichen Namen wie ein Typ zu haben. Ändern Sie daher den Namen der Variablen heap in etwas wie heap_top oder nur h, um Mehrdeutigkeiten zu vermeiden. Dann sollten Sie die richtige Menge an Speicher zuweisen.