0

你好亲爱的电脑爱好者。我又遇到了一个问题。

我应该编写一个最大堆。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);
}

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
4

1 回答 1

1

仔细看看这些行heap_create：

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

sizeof运算符是对变量命名heap还是对命名类型进行操作heap？仅通过查看并不清楚，但根据 valgrind 输出，它看起来像是在引用变量。它报告分配了 8 个字节，这可能是指针（即heap变量）的大小而不是类型。

因此，拥有一个与类型同名的变量并不是一个好主意。因此，将变量的名称更改为heap类似heap_top或只是h为了避免歧义。然后你应该分配适当的内存量。

于 2017-01-27T21:24:41.713 回答