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

Здравствуйте уважаемый компьютерщик. У меня в очередной раз проблема.

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

Не могу найти ошибки памяти. Далее следуют 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 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);
}

валгринд:

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

c segmentation-fault heap max-heap
person CL89    schedule 27.01.2017    source источник
comment
Не связано, но вместо того, чтобы делать, например. i = 2 * i;, за которым следует return i;, почему бы просто не сделать return 2 * i;?   -  person Some programmer dude    schedule 27.01.2017
comment
Что касается вашей проблемы, начните с создания отладочной версии вашей программы (если вы используете gcc, добавьте флаг -g). Затем снова бегите вместе с Вальгриндом. Теперь Valgrind сможет сообщить вам, где обнаружена проблема. Если вы этого не понимаете, отредактируйте свой вопрос, включив вывод Valgrind, и укажите, где в коде вы показываете ошибки (используя комментарии к этим строкам)   -  person Some programmer dude    schedule 27.01.2017
comment
Пожалуйста, отредактируйте свой вопрос вместо того, чтобы пытаться опубликовать его в виде комментария.   -  person Some programmer dude    schedule 27.01.2017
comment
проблема в функции heapify и heap-insert... но я не знаю, где найти. конечно у меня есть столбцы от valgrind но я не знал где ошибка   -  person CL89    schedule 27.01.2017
comment
heap* heap; heap = malloc(sizeof(heap)); Попробуйте -Wshadow и посмотрите, сможете ли вы обнаружить проблему.   -  person EOF    schedule 27.01.2017
comment
Номера строк в valgrind не совпадают с номерами строк в вашем коде. Это затрудняет примирение двух. Не могли бы вы запустить valgrind для кода, который вы разместили? Я бы запустил его сам, но в настоящее время он не работает на MacOS. Кроме того, можем ли мы увидеть heap.h?   -  person Schwern    schedule 28.01.2017
comment
heap = malloc(sizeof(heap)); --› heap = malloc(sizeof *heap); Также избегайте использования имени типа/структуры, совпадающего с именем объекта.   -  person chux - Reinstate Monica    schedule 28.01.2017
comment
эта строка: heap->elements = malloc(capacity * sizeof(int)); говорит, что поле: elements является указателем на массив значений int, НО эта строка: size_t swap = h->elements[i]; говорит, что поле: elements является указателем на массив значений size_t. В опубликованном коде МНОГО таких несоответствий. При компиляции всегда включайте все предупреждения, а затем исправьте эти предупреждения. (для gcc при минимальном использовании: -Wall -Wextra -pedantic -Wconversion -std=gnu99 )   -  person user3629249    schedule 28.01.2017
comment
из кода ожидается, что 1) структура heap определена в файле heap.h, и этот файл также содержит ВСЕ прототипы функций. Это очень плохая идея, потому что: 1) вызывающая функция НИКОГДА не должна вызывать несколько функций в опубликованном коде 2) раскрывает реализацию данных внешнему миру. Предложите 1) функциям, которые никогда не будут вызываться, добавить и удалить модификатор static из заголовочного файла 2) переместить определение структуры heap в размещенный код,   -  person user3629249    schedule 28.01.2017
comment
два определения: #define MAX_HEAP_SIZE 400 и #define MAX_LINE_SIZE 100 не используются в опубликованном коде, поэтому их следует удалить   -  person user3629249    schedule 28.01.2017

Ответы (1)


arrow_upward
1
arrow_downward

Внимательно посмотрите на эти строки в heap_create:

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

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

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

person dbush    schedule 27.01.2017