Ошибка сегментации максимальной кучи

Question

Здравствуйте, дорогой любитель компьютера. У меня снова есть проблема.

Я должен запрограммировать Max-Heap. 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" 

Я не могу найти ошибки памяти. В следующих пяти функциях, написанных мною. Извиняюсь за структуру.

Код:

#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

Всмотритесь в эти строки в heap_create:

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

ли sizeof оператор, действующий на переменную с именем heap, или тип с именем heap? Это не ясно, просто глядя, но, основываясь на выходе valgrind, похоже, что это относится к переменной. Он сообщает, что было выделено 8 байт, что, вероятно, является величиной указателя (то есть переменной heap), а не типом.

Из-за этого не рекомендуется иметь переменную с тем же именем, что и тип. Поэтому измените имя переменной heap на что-то вроде heap_top или просто h, чтобы избежать двусмысленности. Затем вы должны выделить необходимый объем памяти.